New Tower-Type Lower Bounds for Hypergraph Ramsey Numbers

Abstract

The Ramsey number $r_k(s,m)$ is the smallest $N$ such that any red/blue coloring of the $k$-subsets of $[N]$ contains a red $s$-set or a blue $m$-set. For fixed $k$ and $s$, and for sufficiently large $m$, the tower growth rate is determined by the stepping-up lemma, but for $s=m=k+1$ the available stepping-up lemmas do not apply. Fox asked for estimates of $r_k(k+1,k+1)$. Pudlák, Rödl, and Wesley gave the first tower-type bound: $r_k(k+1,k+1)\ge s_3(\lfloor k/4\rfloor )\ge 4{\mathrm{twr}}_{\lfloor k/4\rfloor -4}(2)$, where $s_3(k)$ is the $3$-color shift number and ${\mathrm{twr}}_1(2)=2$, ${\mathrm{twr}}_{i+1}(2)=2^{{\mathrm{twr}}_i(2)}$. In this paper, for $k\ge 6$, we improve the lower bound to $r_k(k+1,k+1)>s_3(\lfloor k/2\rfloor -2)$ by overcoming an obstruction in their construction. In addition, we give an exact characterization of $s_3(k)$ and, for $k\ge 5$, obtain a new explicit lower bound $s_3(k)\ge ({\mathrm{twr}}_{k-2}(2){)}^2$, which improves the result of Pudlák and Rödl. Consequently, for $k\ge 14$, $r_k(k+1,k+1)>({\mathrm{twr}}_{\lfloor k/2\rfloor -4}(2){)}^2$.