{
  "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.",
  "abstract_shown": true,
  "affiliations": [
    "Department of Mathematics Princeton University Princeton New Jersey USA",
    "Faculty of Mathematics University of Vienna Vienna Austria",
    "Department of Mathematics Stanford University Stanford California USA",
    "Department of Mathematics University of Chicago Chicago Illinois USA"
  ],
  "article_type": null,
  "arxiv": null,
  "author_total": 3,
  "authors": [
    {
      "affs": [
        0,
        1
      ],
      "name": "Matija Bucić",
      "orcid": "0000-0002-1055-3309"
    },
    {
      "affs": [
        2
      ],
      "name": "Jacob Fox",
      "orcid": "0000-0002-0664-497X"
    },
    {
      "affs": [
        3
      ],
      "name": "Huy Tuan Pham",
      "orcid": "0000-0003-4659-4345"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/92wwjpnmm80zq.bib",
  "cited_by": 14,
  "doi": "10.1112/blms.70493",
  "fulltext_url": null,
  "id": "92wwjpnmm80zq",
  "issns": [
    "0024-6093",
    "1469-2120"
  ],
  "landing_url": "https://doi.org/10.1112/blms.70493",
  "language": "en",
  "licence": "CC-BY",
  "licence_label": "CC BY",
  "licence_source": "journal",
  "licence_url": "https://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "openalex",
      "2607|Limits and Structures in Graph Theory"
    ]
  ],
  "openalex": "W4392822464",
  "pdf_url": "https://onlinelibrary.wiley.com/doi/pdfdirect/10.1112/blms.70493",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-01",
  "publisher": "Wiley",
  "ris": "https://research.draconitic.com/paper/92wwjpnmm80zq.ris",
  "sources": [
    {
      "first_seen": "2026-11-04T13:21:00Z",
      "native_id": "W4392822464",
      "source": "openalex",
      "url": "https://doi.org/10.1112/blms.70493"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "openalex:2607|Limits and Structures in Graph Theory",
      "subfield": "combinatorics"
    }
  ],
  "title": "Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures",
  "title_text": "Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures",
  "type": "peer-reviewed",
  "updated_at": "2026-11-09T13:21:00Z",
  "url": "https://research.draconitic.com/paper/92wwjpnmm80zq",
  "venue": "Bulletin of the London Mathematical Society",
  "versions": []
}