Erdős–Hajnal off-diagonal hypergraph Ramsey conjecture

For integers 4k<s4\leq k<s and nn, let rk(s,n)r_k(s,n) be the least NN such that every red/blue coloring of the edges of the complete kk-uniform hypergraph on NN vertices contains a red copy of the complete kk-uniform hypergraph on ss vertices or a blue copy on nn vertices. Define twr1(x)=x\operatorname{twr}_1(x)=x and twri+1(x)=2twri(x)\operatorname{twr}_{i+1}(x)=2^{\operatorname{twr}_i(x)}. Erdős–Hajnal conjecture. There are constants c,c>0c,c'>0 such that

twrk1(cn)<rk(s,n)<twrk1(cn).\operatorname{twr}_{k-1}(cn)<r_k(s,n)<\operatorname{twr}_{k-1}(c'n).

This conjecture predicts the correct tower growth for the off-diagonal numbers with smaller values of ss than those covered by the known lower bound. It is verified in the source for sk+3s\geq k+3, while the cases r4(5,n)r_4(5,n) and r4(6,n)r_4(6,n) are substantially harder.

Sources & referencesView supporting material

Primary source

Dhruv Mubayi and Andrew Suk, “A survey of hypergraph Ramsey problems”, arXiv:1707.04229 (2018).

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.