The conjecture that blowup Ramsey numbers must depend on the base graph

Let GrHG \overset{r}{\longrightarrow} H mean that every rr-edge-coloring of GG contains a monochromatic copy of HH, and let B(GrH;t)\mathrm{B}(G \overset{r}{\longrightarrow} H;t) be the minimum nn such that every rr-coloring of G[n]G[n] contains a monochromatic canonical copy of H[t]H[t]. Dependence-on-GG conjecture. There exists a graph HH and integers r,t2r,t\geq 2 such that there are graphs G1,G2,G_1,G_2,\ldots with GirHG_i \overset{r}{\longrightarrow} H for every ii and

supiB(GirH;t)=.\sup_i \mathrm{B}(G_i \overset{r}{\longrightarrow} H;t)=\infty.

This asserts that, although the exponential constant can be made independent of GG, the blowup Ramsey number itself cannot in general be bounded independently of GG. The source reports counterexamples for certain HH and rr, so this conjecture is refuted.

Sources & referencesView supporting material

Primary source

Jacob Fox, Sammy Luo and Yuval Wigderson, “Extremal and Ramsey results on graph blowups”, arXiv:1912.08328 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.