An improved double-exponential lower bound for $r_4(5,n)$

Abstract

The Ramsey number $r_k(s,n)$ is the smallest integer $N$ such that every $N$-vertex $k$-graph contains either a copy of $K_s^{(k)}$ or an independent set of size $n$. A well-known conjecture of Erdős and Hajnal states that for any fixed $4\le k<s$, $r_k(s,n)\ge {\mathrm{twr}}_{k-1}(\hat{I}\text{c◯}(n)).$ At present, only the last two cases of this conjecture remain open, namely $r_4(5,n)\ge 2^{2^{\hat{I}\text{c◯}(n)}}$ and $r_4(6,n)\ge 2^{2^{\hat{I}\text{c◯}(n)}}$. Recently, Du, Hu, Liu, and Wang achieved a breakthrough by proving $r_4(5,n)\ge 2^{2^{\hat{I}\text{c◯}(n^{1/7})}}$, which is the first double-exponential lower bound for $r_4(5,n)$. In this note, we improve this to $2^{2^{\hat{I}\text{c◯}(n^{1/5})}}$ by modifying their construction and reducing the greedy selection of local maxima from seven layers to five, thereby making further progress towards the Erdős-Hajnal conjecture.

9 pages