Unavoidable G-dependence in blowup Ramsey prefactor

Conjecture on unavoidable G-dependence in Theorem 2 · arXiv:1912.08328

arXiv Informal medium confidence— first stated 2020-04-06

Authors: Jacob Fox, Sammy Luo, Yuval Wigderson

Status solved high confidence

Girão and Hancock (arXiv:2205.12826, European J. Combin. 120 (2024) 103984) proved the conjecture affirmatively: for every 3-chromatically connected graph H (including triangles), the dependence on G in the multiplicative factor a(G,H,r) of the bound B(G→rH;t) ≤ a·b^t is unavoidable. They also showed the complementary result that for forests F the factor a can be chosen independently of G.

Cited literature (1)

proof Two Ramsey problems in blowups of graphs (2024)

António Girão, Robert Hancock · European Journal of Combinatorics · arXiv:2205.12826

Proves the conjecture by establishing that for every 3-chromatically connected graph H (in particular the triangle K_3), the G-dependence in the multiplicative factor a(G,H,r) is necessary; conversely, for forests the factor a can be taken independent of G.

Reviewer notes. Conjecture settled affirmatively by Girão–Hancock arXiv:2205.12826 (European J. Combin. 2024): G-dependence in the prefactor is unavoidable for 3-chromatically connected H and unnecessary for forests.

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

Informal. For some graph $H$, the dependence on $G$ in the multiplicative factor $a = a(G, H, r)$ of the bound $B(G \xrightarrow{r} H; t) \leq a \cdot b^t$ (Theorem 2) is unavoidable.

Context

Theorem 2 shows that the exponential constant $b$ can be taken independent of $G$, but the multiplicative prefactor $a$ still depends on $G$. The authors believe this residual dependence is necessary for some $H$, and refer to the concluding remarks for further details.

Notes. Stated in both the abstract and the introduction as a belief/conjecture without a labelled theorem environment; concluding remarks section was not fully captured in the PDF extraction.

Source paper

Extremal and Ramsey results on graph blowups
Jacob Fox, Sammy Luo, Yuval Wigderson · 2020-04-06
https://arxiv.org/abs/1912.08328 PDF source