Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929320054751232 |
|---|---|
| author | Bucić, Matija Fox, Jacob Pham, Huy Tuan |
| author_facet | Bucić, Matija Fox, Jacob Pham, Huy Tuan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_08303 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures Bucić, Matija Fox, Jacob Pham, Huy Tuan Combinatorics 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. |
| title | Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.08303 |