Erdős–Hajnal tower-growth conjecture for rk(k+1,t;n)r_k(k+1,t;n)

For integers k3k\geq3 and 2tk2\leq t\leq k, let rk(k+1,t;n)r_k(k+1,t;n) be the Erdős–Hajnal Ramsey parameter. 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 is a constant c=c(k,t)>0c=c(k,t)>0 such that

rk(k+1,t;n)twrt1(cn).r_k(k+1,t;n)\geq \operatorname{twr}_{t-1}(c n).

The source gives the matching tower-level upper bound rk(k+1,t;n)twrt1(nc)r_k(k+1,t;n)\leq\operatorname{twr}_{t-1}(n^c) and conjectures that this is the correct tower growth rate. The cases t=2t=2 and partial bounds for t=3t=3 are known, but the general lower bound remains open.

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.