Low-complexity encoding conjecture for hypergraph Ramsey colorings

A pair construction of a 33-graph coloring is a coloring of KN(3)K_N^{(3)} obtained from functions f:([N]2)[p]f:\binom{[N]}{2}\to[p] and g:[p]3{red,blue}g:[p]^3\to\{\operatorname{red},\operatorname{blue}\} by setting

χf,g({i,j,k})=g(f(i,j),f(j,k),f(k,i))\chi_{f,g}(\{i,j,k\})=g(f(i,j),f(j,k),f(k,i))

for i<j<ki<j<k. Its complexity is pp. For 33-graphs G,HG,H, let rp(G,H)r^p(G,H) be the smallest nn such that every 22-edge-coloring of Kn(3)K_n^{(3)} of complexity at most pp contains a red copy of GG or a blue copy of HH. Low-complexity encoding conjecture. There exists an absolute constant a>0a>0 such that, for all 33-graphs GG and HH,

rp(G,H)r(G,H)ar^p(G,H)\ge r(G,H)^a

whenever p>r(G,H)o(1)p>r(G,H)^{o(1)}. This conjecture asks whether Ramsey colorings can retain a polynomial fraction of the unrestricted Ramsey number while using subpolynomial pair-construction complexity. The source gives no resolution.

Sources & referencesView supporting material

Primary source

David Conlon, Jacob Fox, Benjamin Gunby, Xiaoyu He, Dhruv Mubayi, Andrew Suk and Jacques Verstraete, “On off-diagonal hypergraph Ramsey numbers”, arXiv:2404.02021 (2024).

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.