Sharpness of h(n,k,Kᵣ) upper bound

Conjecture on sharpness of Theorem 1.1 · arXiv:2102.10220

arXiv Conjecture high confidence— first stated 2021-03-19

Authors: Jacob Fox, Zoe Himwich, Nitya Mani

Status open high confidence

Fox, Himwich, and Mani prove the upper bound h(n, k, K_r) ≤ c_r n²/k^{(r-1)/(r-2)} for all r ≥ 3 and establish the matching lower bound for r = 3, leaving the sharpness for r ≥ 4 as an open conjecture. No follow-up paper proving or disproving the conjecture for general r ≥ 4 was found in the indexed literature. The paper was published in the Journal of Graph Theory (2022/2023).

Reviewer notes. The conjecture is open for r ≥ 4. The r = 3 case (triangle-free) is settled by the authors themselves in the original paper. No indexed follow-up paper addressing the general case was found across four targeted web searches. The internal reference arXiv:2105.03956 (Scott–Seymour–Spirkl, pure pairs) is unrelated and was discarded after abstract verification.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For each integer $r \geq 3$ there is $c_r$ such that for all positive integers $n, k$ with $n$ sufficiently large in terms of $k$, $$h(n, k, K_r) = \Theta_r\!\left(\frac{n^2}{k^{(r-1)/(r-2)}}\right),$$ i.e., the upper bound $h(n, k, K_r) \leq c_r \dfrac{n^2}{k^{(r-1)/(r-2)}}$ is tight up to the constant factor $c_r$.

Context

Theorem 1.1 establishes the upper bound $h(n,k,K_r) \leq c_r n^2/k^{(r-1)/(r-2)}$ for all $r \geq 3$. The authors prove the matching lower bound for $r=3$ and conjecture the bound is sharp for all $r \geq 3$.

Source paper

Making an $H$-Free Graph $k$-Colorable
Jacob Fox, Zoe Himwich, Nitya Mani · 2021-03-19
https://arxiv.org/abs/2102.10220 PDF source