A Proof of Paták's kb+1 Conjecture for Constrained Stars, with Improved Bounds for Complete Graphs

In an Oberwolfach report from 2020, Paták considered closure operators on topological spaces whose closures have at most b path-connected components. He noted that C(b+1,2)(k−1)+b+1 points suffice for a constrained drawing of the star K_{1,k}, conjectured that kb+1 points suffice, and asked two further questions: whether the bounds for complete graphs K_n can be improved, and whether the method extends to higher homology or homotopy. In the journal version (J. Graph Theory, 2025) the conjecture is stated for b-iatlon graphs and proved there for b ≤ 2. We prove the conjecture for all k and b. Every b-iatlon graph with kb+1 vertices contains a constrained copy of K_{1,k}. For every closure operator as above, every set of kb+1 points admits a constrained drawing of K_{1,k}. The bound kb+1 is sharp in both settings. The proof rests on a colouring lemma for families of graphs indexed by the subsets of a finite set and growing with the subset; it extends the bound χ ≤ Δ+1. As a consequence, 1+b+⋯+b^{n−1} points force a constrained copy of K_n, improving the previous bound O(b^{2n−3}). Combined with Paták's topological arguments, this lowers his bounds on Radon and Helly numbers in R^d from O(b^{2d+3}) to O(b^{d+2}), and his bound on Radon numbers on a fixed closed surface from O(b^6) to O(b^3). In the b-iatlon setting, Ramsey numbers give lower bounds, which show that the exponent n−1 is optimal for n = 3, 4. Exact values for complete graphs remain open, and the question on higher homology and homotopy is not addressed. This is an unrefereed note.