Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 12 min ago
Peer-reviewedCC BYBulletin of the London Mathematical Society

Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures

  • Matija Bucić1,2
  • Jacob Fox3
  • Huy Tuan Pham4
4 affiliations
  1. 1Department of Mathematics Princeton University Princeton New Jersey USA
  2. 2Faculty of Mathematics University of Vienna Vienna Austria
  3. 3Department of Mathematics Stanford University Stanford California USA
  4. 4Department of Mathematics University of Chicago Chicago Illinois USA
Open at sourcePDFDOICite

Abstract

It is well‐known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős–Hajnal conjecture. In this note, we prove that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott, and Seymour; Nguyen, Scott, and Seymour; and Gishboliner and Shapira. We deduce that the family of string graphs satisfies the polynomial Rödl conjecture. We also derive analogous results for hypergraphs, tournaments, ordered graphs, and colored graphs.

Related

  1. Erdős-Hajnal for excluding paths
    Tung H. Nguyen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. 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
  3. The Erdős--Hajnal property for paths
    Shenwei Huang, Yidong Zhou, Yuwen Zhou
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
    Tung Nguyen, Bartosz Walczak
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The Erdős--Hajnal hypergraph Ramsey problem for r4(6,n)
    Longma Du, Xinyu Hu, Ruilong Liu +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@article{bucic2026equivalence,
  title = {{Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures}},
  author = {Matija Bucić and Jacob Fox and Huy Tuan Pham},
  journal = {Bulletin of the London Mathematical Society},
  year = {2026},
  month = oct,
  doi = {10.1112/blms.70493},
  url = {https://doi.org/10.1112/blms.70493},
  note = {CC BY},
}
RIS
TY  - JOUR
TI  - Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures
AU  - Matija Bucić
AU  - Jacob Fox
AU  - Huy Tuan Pham
PY  - 2026
DA  - 2026/10/01
JO  - Bulletin of the London Mathematical Society
DO  - 10.1112/blms.70493
UR  - https://doi.org/10.1112/blms.70493
AB  - It is well‐known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős–Hajnal conjecture. In this note, we prove that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott, and Seymour; Nguyen, Scott, and Seymour; and Gishboliner and Shapira. We deduce that the family of string graphs satisfies the polynomial Rödl conjecture. We also derive analogous results for hypergraphs, tournaments, ordered graphs, and colored graphs.
SN  - 0024-6093
SN  - 1469-2120
ER  -