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

For integers 2k<s<n2\le k < s < n and 2t(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 3tk3\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

twrt2(nc)<rk(k+1,t;Pn)<twrt2(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.

Sources & referencesView supporting material

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.