The ordered Erdős–Hajnal tower-growth conjecture for tight paths

About 10 years old · traced to

For integers 2≤k<s<n2\le k < s < n and 2≤t≤(sk)2\le t\le {s\choose k}, let rk(s,t;Pn)r_k(s,t;P_n) be the minimum NN such that every red/blue coloring of the kk-sets of [N][N] contains a monochromatic blue copy of the tight path PnP_n or a set of ss vertices inducing at least tt red edges. Ordered Erdős–Hajnal tower-growth conjecture. For 3≤t≤k3\le t\le k, there are positive constants c=c(k,t)c=c(k,t) and c′=c′(k,t)c'=c'(k,t) such that

twr⁡t−2(nc)<rk(k+1,t;Pn)<twr⁡t−2(nc′).\operatorname{twr}_{t-2}(n^c)<r_k(k+1,t;P_n)<\operatorname{twr}_{t-2}(n^{c'}).

This conjecture proposes the ordered analogue of the Erdős–Hajnal tower hierarchy for cliques, with tight paths replacing complete hypergraphs; its validity is presented as the paper's main contribution and remains open in the source.

References

Primary source

Dhruv Mubayi, “Variants of the Erdos-Szekeres and Erdos-Hajnal Ramsey problems”, arXiv:1609.07670 (2016).

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.