An improved double-exponential lower bound for $r_4(5,n)$
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914550955114496 |
|---|---|
| author | Fan, Chunchao Li, Mingze Lin, Qizhong Ning, Bo |
| author_facet | Fan, Chunchao Li, Mingze Lin, Qizhong Ning, Bo |
| contents | 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 \operatorname{twr}_{k-1}(Ω(n)).$ At present, only the last two cases of this conjecture remain open, namely $r_4(5,n)\ge2^{2^{Ω(n)}}$ and $r_4(6,n)\ge2^{2^{Ω(n)}}$. Recently, Du, Hu, Liu, and Wang achieved a breakthrough by proving $r_4(5,n)\ge 2^{2^{Ω(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^{Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_04105 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An improved double-exponential lower bound for $r_4(5,n)$ Fan, Chunchao Li, Mingze Lin, Qizhong Ning, Bo Combinatorics 05D10 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 \operatorname{twr}_{k-1}(Ω(n)).$ At present, only the last two cases of this conjecture remain open, namely $r_4(5,n)\ge2^{2^{Ω(n)}}$ and $r_4(6,n)\ge2^{2^{Ω(n)}}$. Recently, Du, Hu, Liu, and Wang achieved a breakthrough by proving $r_4(5,n)\ge 2^{2^{Ω(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^{Ω(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. |
| title | An improved double-exponential lower bound for $r_4(5,n)$ |
| topic | Combinatorics 05D10 |
| url | https://arxiv.org/abs/2605.04105 |