Low-complexity encoding conjecture for hypergraph Ramsey colorings
Low-complexity encoding conjecture for hypergraph Ramsey colorings
A pair construction of a -graph coloring is a coloring of obtained from functions and by setting
for . Its complexity is . For -graphs , let be the smallest such that every -edge-coloring of of complexity at most contains a red copy of or a blue copy of . Low-complexity encoding conjecture. There exists an absolute constant such that, for all -graphs and ,
whenever . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.