Given integers l,nl,n, the llth power of the path PnPn is the ordered graph Pnl with vertex set v1 1l>1, Balko–Cibulka–Kral–Kyncl proved that r(Pnl,Pnl)<cln128l and asked for the growth rate for fixed ll. When l=2l=2, we improve this upper bound substantially by proving r(Pn2,Pn2)<cn19.5. Using this result, we determine the correct tower growth rate of the kk-uniform hypergraph Ramsey number of a (k+1)(k+1)-clique versus an ordered tight path. Finally, we consider an ordered version of the classical Erdős–Hajnal hypergraph Ramsey problem, improve the tower height given by the trivial upper bound, and conjecture that this tower height is optimal.
['Dhruv Mubayi']
Variants of the Erdős–Szekeres and Erdős–Hajnal Ramsey problems