Erdős–Hajnal off-diagonal hypergraph Ramsey conjecture

At least 8 years old · documented by

For integers 4≤k<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 twr⁡1(x)=x\operatorname{twr}_1(x)=x and twr⁡i+1(x)=2twr⁡i(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

twr⁡k−1(cn)<rk(s,n)<twr⁡k−1(c′n).\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 s≥k+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.

References

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.