Variants of the Erdos-Szekeres and Erdos-Hajnal Ramsey problems

Abstract

Given integers $\ell ,n$, the $\ell$th power of the path $P_n$ is the ordered graph $P_n^{\ell }$ with vertex set $v_1<v_2<\cdots <v_n$, and all edges of the form $v_i{v}_j$ where $|i-j|\le \ell$. The ramsey number $r(P_n^{\ell },P_n^{\ell })$ is the minimum $N$ such that every 2-coloring of $\left(\genfrac{}{}{0ex}{}{[N]}{2}\right)$ results in a monochromatic copy of $P_n^{\ell }$. It is well-known that $r(P_n^1,P_n^1)=(n-1{)}^2+1$. For $\ell >1$, Balko-Cibulka-Král-Kynčl proved that $r(P_n^{\ell },P_n^{\ell })<c_{\ell }{n}^{128\ell }$ and asked for the growth rate for fixed $\ell$. When $\ell =2$, we improve this upper bound by proving $r(P_n^2,P_n^2)<c{n}^{19.5}$. Using this result, we determine the correct tower growth rate of the $k$-uniform hypergraph ramsey number of a $(k+1)$-clique versus an ordered tight path. Finally, we consider an ordered version of the classical Erd Hos-Hajnal hypergraph ramsey problem, improve the tower height given by the trivial upper bound, and conjecture that this tower height is optimal.

10 pages, accepted European Journal of Combinatorics

References in corpus (1)

• Counting monochromatic copies of K_4: a new lower bound for the Ramsey multiplicity problem