Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 30 min ago
PreprintarXiv licencearXiv

The Erdős--Hajnal hypergraph Ramsey problem for r4(6,n)

  • Longma Du
  • Xinyu Hu
  • Ruilong Liu
  • Guanghui Wang
Open at sourcePDFDOICite

Abstract

The Ramsey number rk(s,n) is the smallest integer N such that every N-vertex k-graph contains either a copy of Ks(k) or an independent set of size n. Erdős and Hajnal conjectured that for every fixed s>k≥ 4, one has rk(s,n)≥ twrk−1(Ω(n)). This conjecture was independently verified by Mubayi and Suk, and by Conlon, Fox and Sudakov, for k≥4 and s≥ k+3. In this paper, we prove that r4(6,n)≥ 22cn for some absolute constant c>0, improving upon our previous bound. Consequently, we confirm the Erdős--Hajnal conjecture for rk(k+2,n) for all fixed k≥4.

Related

  1. On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
    Tung Nguyen, Bartosz Walczak
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Rainbow Triangles and the Erdős-Hajnal Problem in Projective Geometries
    Carolyn Chun, James Dylan Douthitt, Wayne Ge +3
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  3. Erdős-Hajnal for excluding paths
    Tung H. Nguyen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. The Erdős-Hajnal Property for the six-vertex Graph with Edge Set {ab,bc,cd,de,af,bf,df}
    Viet-Hoang Tran, Tan M. Nguyen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. The Erdős--Hajnal property for paths
    Shenwei Huang, Yidong Zhou, Yuwen Zhou
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{du2026erdőshajnal,
  title = {{The Erdős--Hajnal hypergraph Ramsey problem for $r_4(6,n)$}},
  author = {Longma Du and Xinyu Hu and Ruilong Liu and Guanghui Wang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26563},
  eprint = {2609.26563},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26563},
}
RIS
TY  - UNPB
TI  - The Erdős--Hajnal hypergraph Ramsey problem for r_4(6,n)
AU  - Longma Du
AU  - Xinyu Hu
AU  - Ruilong Liu
AU  - Guanghui Wang
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.26563
UR  - https://arxiv.org/abs/2609.26563
AB  - 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. Erdős and Hajnal conjectured that for every fixed s>k≥ 4, one has r_k(s,n)≥ twr_k−1(Ω(n)). This conjecture was independently verified by Mubayi and Suk, and by Conlon, Fox and Sudakov, for k≥4 and s≥ k+3. In this paper, we prove that r_4(6,n)≥ 2^2^cn for some absolute constant c>0, improving upon our previous bound. Consequently, we confirm the Erdős--Hajnal conjecture for r_k(k+2,n) for all fixed k≥4.
ER  -