# Verification report — OWR-1703876-006 (Paták's constrained-star question)

Verification date: 2026-09-30.

**Verdict.** Question (1) of the record is answered: kb+1 points always suffice for a
constrained drawing of the star K_{1,k}, and kb points do not. This holds for every closure
operator on every topological space such that the closure of each (b+1)-point set has at most b
path-connected components, and also in Paták's b-iatlon setting. There it proves Conjecture 1 of
Paták (J. Graph Theory 2025), which was known only for b ≤ 2. For question (2), the bound for
constrained copies of K_n improves from O(b^{2n−3}) to 1+b+⋯+b^{n−1}, and Ramsey numbers give
lower bounds for p(K_n,b); exact values remain open. Question (3) is not addressed. So the
bundled record is **partially solved**. The note is unrefereed.

Two independent verification runs, both AI-assisted, checked this work. The first ran before the
paper was written. The second checked a draft of the paper; this version contains the corrections
it asked for (see the two sections on the verification runs below).

## Statement checked
- **Primary source.** P. Paták, "Helly numbers of disconnected sets", Oberwolfach Report
  30/2020 (Discrete Geometry), Oberwolfach Rep. 17 (2020), no. 2, pp. 1500–1501,
  doi:10.4171/OWR/2020/30.
  - The report defines constrained drawings of K_n in a point set S, for a closure operator whose
    closures have at most b path-connected components.
  - It states that C(b+1,2)(k−1)+b+1 points suffice for the star K_{1,k}.
  - It asks: (1) how many points are needed for K_{1,k} (conjectured answer kb+1); (2) whether
    the bounds for K_n can be improved; (3) whether the approach extends to non-trivial homology
    or homotopy in higher dimensions.
- **Journal version.** P. Paták, "A sharper Ramsey theorem for constrained drawings", J. Graph
  Theory 109(4) (2025) 401–411, doi:10.1002/jgt.23226. We read arXiv:1909.08489v4, the latest
  arXiv version on 2026-09-30. The typeset journal version was not seen, so the paper cites
  numbered results of this work as they are numbered in arXiv v4.
  - It introduces b-iatlon graphs and the function p(G,b).
  - It proves p(K_n,b) ≤ b·Σ_{j≤n−2} C(b+1,2)^j + 1 = O(b^{2n−3}) (Theorem 1).
  - It proves p(K_{1,k},b) ≥ kb+1 (Lemma 1) and p(K_{1,k},2) = 2k+1 (Lemma 2).
  - It states Conjecture 1: bn+1 vertices force a constrained K_{1,n} in every b-iatlon graph.
- **Corpus record.** ulamai/UnsolvedMath, OWR-1703876-006 (current HF status `open`). It bundles
  all three questions. The HF clean statement places the closure operator on R^2. The results
  below hold on every topological space, and the sharpness example works in every R^d,
  including R^2.

## Readings
| Reading | Answered? | Result |
|---|---|---|
| (1) closure setting: least number of points forcing a constrained K_{1,k} (report; HF statement on R^2) | yes | exactly kb+1: Theorem 1.2(b), and Theorem 1.2(c) (slab closure operator on R^d, d ≥ 1) |
| (1) b-iatlon setting: Paták's Conjecture 1, p(K_{1,k},b) = kb+1 | yes (proved) | Theorem 1.2(a); lower bound from Paták's Lemma 1 |
| (1) with only "every (b+1)-set has two points in one path component of its closure" | yes | same bound kb+1 (Theorem 1.2(b)) |
| (2) better bounds for K_n (b-iatlon setting) | improved, not settled | R(n,b+1) ≤ p(K_n,b) ≤ Σ_{j<n} b^j (Theorem 1.3); exponent n−1 optimal for n = 3, 4; p(K_3,2) = 6 (upper bound by computer) |
| (2) closure setting | improved, not settled | Σ_{j<n} b^j points suffice (Theorem 1.3); lower bound only (n−1)b+1 (slabs) |
| (3) homology/homotopy in higher dimensions | not addressed | — |

## Results in the paper
- **Theorem 2.2 (colouring lemma).** Let (G_T), T ⊆ V, be a monotone family of graphs, meaning
  that G_T has vertex set T and E(G_T) ⊆ E(G_T') for T ⊆ T'. If no pair (c, L) with |L| = k
  satisfies cx ∈ E(G_{V∖(L∖{x})}) for all x ∈ L, then V is the union of k pairwise disjoint
  independent sets, so |V| ≤ kα.
  - Since subsets of independent sets are independent, this is equivalent to covering V by k
    independent sets. The induction uses the disjoint form.
  - The proof is an induction that passes to the link of a point p, where every set is
    considered together with p.
  - For G_T = G[T] the lemma gives χ ≤ Δ+1.
- **Theorem 1.2.**
  - (a) p(K_{1,k},b) = kb+1, which proves Paták's Conjecture 1.
  - (b) In the closure setting, kb+1 points suffice; an infinite S is first restricted to a
    finite subset of size kb+1.
  - (c) The slab closure operator cl(Y) = ∪_i conv(Y ∩ R_i) on R^d shows that kb points do not
    suffice.
- **Lemma 4.1 / Corollary 4.2.** p(K_1+G,b) ≤ b·p(G,b)+1 (Paták's argument for his
  Proposition 1(6), now with the sharp star bound).
  - Hence p(K_n,b) ≤ Σ_{j<n} b^j and p(K_{m,n},b) ≤ n b^m + Σ_{j<m} b^j.
  - For example, p(K_3,2) ≤ 7 (previously 9), and for K_{3,3} with b = 3 the bound is 94
    (previously 562).
- **Proposition 4.3 / Example 4.4 / Corollary 4.5.** p(G,b) ≥ r(G,K_{b+1}) (Ramsey number), so
  p(K_n,b) ≥ R(n,b+1).
  - The 5-cycle with labels L_{i,i+1} = {{i+2},{i+3}} is an exact certificate for
    p(K_3,2) ≥ 6.
  - p(K_3,2) ≤ 6 is a computation (exhaustive search, and SAT).
  - By Kim and by Mattheus–Verstraete, p(K_3,b) = Ω(b²/log b) and p(K_4,b) = Ω(b³/log⁴ b), so the
    exponent n−1 is optimal for n = 3, 4.
  - For stars, p(K_{1,k},b) = r(K_{1,k},K_{b+1}) = kb+1 (Chvátal).
- **Lemma 4.6.** p(t·G,b) ≤ p(G,b) + (t−1)(|V(G)| + (b−1)|E(G)|). This is Paták's argument for
  his Proposition 1(9); the label count of a copy is at most its number of edges.
- **Proposition 4.7 (new in this version).** p(G,b) ≥ |V(G)| + (b−1)ν(G), where ν(G) is the
  matching number: in a b-iatlon graph whose labels all have b−1 elements, the labels of the
  edges of a maximum matching of a constrained copy are pairwise disjoint and avoid the copy.
  - p(t·K_2,b) = t(b+1) (upper bound from Lemma 4.6), while r(t·K_2,K_{b+1}) = 2t+b−1. The
    difference is (t−1)(b−1), which is positive for t, b ≥ 2; for example p(2·K_2,2) = 6 and
    r(2·K_2,K_3) = 5.
  - For K_2 ∪ K_1 (an edge and an isolated vertex), p(K_2 ∪ K_1, 2) ≥ 4 > 3 = r(K_2 ∪ K_1, K_3).
- **Section 5 (re-derived, not quoted).** In Paták's proofs of his Theorems 2 and 4, the number
  of points enters only through a constrained copy of K_{d+3}, resp. (g+1)·K_{3,3}, in the
  b-iatlon graph H_P of the point set, whose labels all have b−1 elements.
  - R^d: r(cl) ≤ Σ_{j≤d+2} b^j = O(b^{d+2}) and h(F) ≤ Σ_{1≤j≤d+2} b^j, down from O(b^{2d+3}).
    The Helly number is as in Paták's Definition 5: the least h such that every finite
    subfamily with empty intersection contains h (not necessarily distinct) members whose
    intersection is empty.
  - Closed surfaces of genus g: r(cl) ≤ 3b³+b²+b+1+g(9b−3), down from O(b^6). The genus term
    differs from the one indicated in Paták's Section 5, because stars may now use a different
    label on every edge.
  - R^2: r(cl) ≤ 3b³+b²+b+1. Paták states and proves his Proposition 2 only for b = 3, with the
    bound 562. His argument, which applies the Hanani–Tutte theorem to a constrained copy of
    K_{3,3}, works verbatim for every b; the paper says so and does not attribute a general-b
    statement to him.
  - The topological inputs (Paták's Lemmas 5–6, [GPP+17, Cor. 14], Schaefer–Štefankovič,
    Hanani–Tutte) are used as published and were not re-verified.
- **Section 6 (open problems).**
  - Problem 6.1 asks whether p(G,b) = r(G,K_{b+1}) for every **connected** graph G, and in
    particular whether p(K_n,b) = R(n,b+1). The draft asked this for every graph, which is false
    by Proposition 4.7.
  - For connected G on n vertices, b disjoint copies of K_{n−1} give r(G,K_{b+1}) ≥ (n−1)b+1,
    which is at least the bound n+(b−1)ν(G) of Proposition 4.7.
  - Equality holds for all stars, for b = 1, and for (K_3,2). SAT computations of the second
    verification run give p(G,2) = r(G,K_3) for P_4, C_4, the paw and K_4 − e (value 7) and
    for K_3 (value 6). These are computations and are used in no proof.
  - Problem 6.2 asks for the closure-setting threshold for K_n, where only (n−1)b+1 and
    Σ_{j<n} b^j are known.

## Computations (scripts and outputs in reproducibility/)
- **Lead** (`lead/`, written for this release; shares no code with the finder's scripts).
  - `check_theorem.py` (standard library, about 30 s):
    - Theorem 2.2 by brute force on all 46,656 monotone graph systems with 4 points, and on
      20,000 / 3,000 / 300 random systems with 5 / 6 / 7 points;
    - the C_5 certificate;
    - exhaustive backtracking: no choice function on 6 points avoids a constrained K_3 (815,671
      nodes); on 5 points brute force and backtracking agree on 2,124 such choice functions;
    - the proof run as an algorithm on random b-iatlon graphs with kb+1 vertices;
    - the arithmetic of the bounds.
  - `sat_checks.py` (PySAT/CaDiCaL):
    - no counterexample to Theorem 2.2 among all monotone graph systems with n ≤ 8 (all k);
    - Paták's definitions give thresholds kb / kb+1 for (k,b) ∈ {(1,3),(2,2),(3,2),(2,3),(4,2),
      (2,4),(3,3)};
    - p(K_3,2) = 6.
- **Finder** (`claimant/`).
  - The proof as an algorithm with a separate checker: all systems on 4 points, 12,000 random
    systems, and random b-iatlon graphs up to (k,b) = (2,6), (6,2), (3,4), (4,3).
  - Adversarial SAT-generated inputs.
  - SAT threshold checks in the closure and b-iatlon settings.
  - A counterexample-guided check of the colouring statement for monotone partition systems with
    n = 7, 8 and k ≤ 4, and with n = 9 and k ≤ 5 (the recorded outputs). The second verification
    run ran the remaining cases with n ≤ 8, and all of them hold.
  - Small examples showing that a naive induction, which deletes a point instead of passing to
    its link, fails (Remark 2.3).
- **First independent verification run** (AI-assisted; see `verifier/README.md`).
  - It ran before the paper was written. It checked the statement against the Oberwolfach report
    and arXiv v4, and the proofs of Theorem 2.2, of the b-iatlon reduction (Theorem 3.3), of the
    closure reduction (in the direct form given after the proof of Theorem 1.2(b)), of the slab
    example (Proposition 3.7), and of Lemma 4.1 with the bound for K_n in Corollary 4.2.
  - It re-ran the finder's scripts and reproduced their recorded outputs. It did not run the lead
    programs, which were written later.
  - With its own code it checked: brute force for Theorem 2.2 (n = 4 exhaustive, n = 5, 6
    random); a SAT search for counterexamples to Theorem 2.2 (UNSAT for n ≤ 8, and for n = 9 with
    k = 2, 3, 4); a SAT encoding of Paták's definitions (thresholds kb / kb+1 in six cases); and
    p(K_3,2) = 6.
  - It did not check Proposition 4.3, Corollary 4.5, Lemma 4.6 or Section 5.
  - Its scratch scripts were not kept.
- **Second independent verification run** (AI-assisted; programs and outputs in
  `independent_run_2/`, see its README).
  - It checked a draft of the paper: the statements against the Oberwolfach report and arXiv v4,
    the proofs of Sections 2–4 step by step, and, in arXiv v4, where the number of points enters
    Paták's proofs used in Section 5 (the topological arguments were not re-verified).
  - With its own code, written before it read the lead and finder programs, it checked:
    - Theorem 2.2 by brute force on all 46,656 systems with 4 points (every k) and on 20,000 /
      4,000 / 1,000 random systems with 5 / 6 / 7 points;
    - Theorem 2.2 by SAT: UNSAT for every n ≤ 9 and every k < n; the corollary |V| ≤ kα for
      seven cases up to (k,a) = (3,3) and (5,2);
    - Paták's definitions by SAT: p(K_{1,k},b) = kb+1 for thirteen pairs (k,b) up to (3,3),
      (5,2) and (2,5), with the models at N = kb decoded and re-checked; kb+1 vertices suffice
      for (6,2);
    - p(K_3,2) = 6 by an exhaustive C enumeration (2,124 of 3^10 choices on 5 points avoid a
      constrained K_3, none of 3^20 on 6 points) and by SAT;
    - the C_5 certificate, Paták's Lemma 1 graphs, the proof of Theorem 3.3 and the construction
      of Lemma 4.1 as algorithms, and the arithmetic of Sections 4 and 5;
    - the Problem 6.1 tests of Section 6.
  - It re-ran the lead programs (`check_theorem.py`, `sat_checks.py 8`) and several finder
    scripts from the extracted draft package and reproduced all recorded outputs apart from
    timings.
  - Some of its runs that no claim depends on were stopped before they finished; see
    `independent_run_2/README.md`.

## First independent verification run (before the paper was written)
Verdicts of the first independent verification run (2026-09-30):

| Item | Verdict |
|---|---|
| Statement fidelity | CONFIRMED (report re-downloaded; the question is answered as intended, not on a literal or misprint reading) |
| Proofs | CONFIRMED (colouring lemma line by line; closure and b-iatlon reductions; slab example; join inequality) |
| Computations | CONFIRMED (finder's outputs reproduced; four independent checks) |
| Answer as posed | question (1): CONFIRMED (sufficiency and sharpness); record as a whole: partially solved |
| Novelty | CONFIRMED as far as can be checked (no priority claim) |
| Presentation | REQUIRED FIXES (below) |

The required fixes were applied as follows.
1. **Scope.** The title, abstract, introduction and "Scope and priority" paragraph say that (1)
   is solved, (2) is improved with exact values open, and (3) is not addressed. The suggested HF
   status is `partially_solved`, not `solved`.
2. **Literature.** Semantic Scholar lists four records citing Paták's paper: the survey
   arXiv:2602.07552; Avvakumov–Bin–Goaoc arXiv:2601.02920v2, which partially answers Conjecture 2
   only; and two records of Pálvölgyi, "Radon numbers grow linearly" (arXiv:1912.02239; DCG 68
   (2022) 165–171). All three works were read and cited, and none treats Conjecture 1. The
   zbMATH query for documents citing the journal version returns no results. The second
   verification run showed that the same query form does return citing documents for an older
   paper, so zbMATH records no citing document; since zbMATH's citation data are incomplete,
   this is weak evidence.
3. **Radon/Helly.** The consequences are re-derived in Section 5 instead of being quoted. R^d
   gives O(b^{d+2}). For surfaces the genus term is g(9b−3), from up to 9 labels per copy of
   K_{3,3}. Paták's exact constant is not quoted.
4. **Minor points.**
   - Infinite S is restricted to a finite (kb+1)-subset.
   - Paták's Lemma 1 is credited for the lower bound.
   - The paper remarks that Theorem 2.2 generalises χ ≤ Δ+1 (Remark 2.3).
   - The lower bound (n−1)b+1 for K_n is shown not to be tight by an exact certificate
     (p(K_3,2) ≥ 6). The upper bound p(K_3,2) ≤ 6 is labelled as a computation.
5. **Expert check.** The first run also asked for an independent expert check before any public
   relabelling or deposit. No human expert has checked this note, and such a check is still
   advised. The second independent verification run, which was AI-assisted, checked a draft of
   the paper (next section); it is not a peer review.

In the same revision we added the Ramsey lower bound p(G,b) ≥ r(G,K_{b+1}) and its consequences
(Proposition 4.3, Corollary 4.5), Lemma 4.6 and Section 5 in their present form, and
Problems 6.1–6.2. The first verification run did not check these additions.

## Second independent verification run (on a draft of the paper)
Verdicts of the second independent verification run (2026-09-30):

| Item | Verdict |
|---|---|
| Statement fidelity | CONFIRMED (report and arXiv v4 fetched again; definitions, conjecture and questions transcribed correctly) |
| Proofs | CORRECT, with minor gaps and one false open problem (fixes 1, 4 and 5 below) |
| Computations | CONFIRMED (own code; full re-run of the release package) |
| Novelty and credit | CONFIRMED as far as can be checked; no earlier proof found; credits accurate |
| Presentation | MINOR REVISION (fixes 1–6 below) |
| Fatal problems | none |

The required fixes were applied as follows.
1. **Problem 6.1.** The draft asked whether p(G,b) = r(G,K_{b+1}) for every graph G. This is
   false for some disconnected graphs: p(K_2 ∪ K_1, 2) ≥ 4 > 3 = r(K_2 ∪ K_1, K_3), and
   p(t·K_2,b) = t(b+1) > 2t+b−1 = r(t·K_2,K_{b+1}) for t, b ≥ 2, because
   p(G,b) ≥ |V(G)| + (b−1)ν(G). The paper now proves this lower bound and the values for t·K_2
   (Proposition 4.7), states Problem 6.1 for connected graphs, and quotes the computations for
   P_4, C_4, the paw, K_4 − e and K_3 at b = 2 as computations.
2. **Description of the first verification run.** The Verification paragraph (item 4) and this
   report now say that the first run ran before the paper was written, what it checked, that it
   re-ran the finder's scripts and not the lead programs, which own checks it made, and that it
   did not check Proposition 4.3, Corollary 4.5, Lemma 4.6 or Section 5. The phrases saying that
   it re-derived every proof and re-ran the scripts were removed. The second run is described as
   item 5 of the Verification paragraph.
3. **Helly number.** Section 5 now uses Paták's Definition 5 (h not necessarily distinct members
   with empty intersection in every finite subfamily with empty intersection).
4. **Proof of Theorem 2.2.** The theorem is stated for k pairwise disjoint independent sets, and
   the paper notes that covers can be refined to partitions because subsets of independent sets
   are independent; the induction uses the disjoint form.
5. **Theorem 5.3, R^2.** The paper says that Paták's Proposition 2 is stated and proved only for
   b = 3 (bound 562) and that his argument, with the Hanani–Tutte theorem for K_{3,3}, works
   verbatim for every b.
6. **Numbering.** The introduction says that numbered results of the journal paper are cited as
   in arXiv:1909.08489v4, since the typeset journal version was not seen.

Optional suggestions taken up: the zbMATH sentence is rephrased as weak evidence; Verification
item 3 states the recorded range of the counterexample-guided search and no longer says that the
induction "must" pass to the link; the page range 919–941 was added to Mattheus–Verstraete
(checked on the journal's website). The bibliography labels were kept.

## Relation to the literature, novelty and scope
- **Searches (30 September 2026; all anonymous, logged).**
  - arXiv API: author Paták; "constrained drawing(s)", "iatlon", "constrained copy"; Radon and
    Helly numbers with path-connected components; recent Radon/Helly papers.
  - Crossref (all DOIs of the bibliography verified); OpenAlex (no citing works of
    doi:10.1002/jgt.23226); zbMATH Open (no citing document recorded; weak evidence, see above);
    Semantic Scholar (four citing records, see above).
  - Two web searches found only Paták's paper.
  - The second verification run made searches of the same kinds independently (arXiv API,
    Crossref, OpenAlex, zbMATH Open, Semantic Scholar, one web search) and found no earlier
    proof.
- **Findings.** Only arXiv:1909.08489v4 / JGT 2025 treats the star question. Its v1 (2019) has no
  star conjecture. The February 2026 survey by Paták and Patáková still quotes O(b^{2d+3}) for
  Helly numbers (its Theorem 30) and does not list the star question among its open problems.
  No proof of Conjecture 1 for b ≥ 3 was found. The argument is short and an expert may know it.
  This negative search is not a proof of priority.
- **Scope.**
  - Question (1): answered completely in both settings.
  - Question (2): improved upper bound Σ_{j<n} b^j and lower bound R(n,b+1) for p(K_n,b); exact
    values open, including whether p(G,b) = r(G,K_{b+1}) for every connected G (Problem 6.1;
    for some disconnected G it fails, Proposition 4.7). In the closure setting the known lower
    bound is only (n−1)b+1 (Problem 6.2).
  - Question (3): not addressed.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/