New bounds of two hypergraph Ramsey problems

Abstract

We focus on two hypergraph Ramsey problems. First, we consider the Erdős-Hajnal function $r_k(k+1,t;n)$. In 1972, Erdős and Hajnal conjectured that the tower growth rate of $r_k(k+1,t;n)$ is $t-1$ for each $2\le t\le k$. To finish this conjecture, it remains to show that the tower growth rate of $r_4(5,4;n)$ is three. We prove a superexponential lower bound for $r_4(5,4;n)$, which improves the previous best lower bound $r_4(5,4;n)\ge 2^{\hat{I}\text{c◯}(n^2)}$ from Mubayi and Suk (\emph{J. Eur. Math. Soc., 2020}). Second, we prove an upper bound for the hypergraph Erdős-Rogers function $f_{k+1,k+2}^{(k)}(N)$ that is an iterated $(k-3)$-fold logarithm in $N$ for each $k\ge 5$. This improves the previous upper bound that is an iterated $(k-13)$-fold logarithm in $N$ for $k\ge 14$ due to Mubayi and Suk (\emph{J. London Math. Soc., 2018}), in which they conjectured that $f_{k+1,k+2}^{(k)}(N)$ is an iterated $(k-2)$-fold logarithm in $N$ for each $k\ge 3$.

18 pages