Induced Subgraph Density. I. A loglog Step Towards Erdős–Hajnal

Matija Bucić, Tung Nguyen, Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In 1977, Erdős and Hajnal made the conjecture that, for every graph H, there exists c > 0 such that every H-free graph G has a clique or stable set of size at least |G|c, and they proved that this is true with |G|c replaced by 2c√log |G|. Until now, there has been no improvement on this result (for general H). We prove a strengthening: that for every graph H, there exists c > 0 such that every H-free graph G with |G| ≥ 2 has a clique or stable set of size at least 2c√log |G| log log |G| . Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of Rödl, Nikiforov, and the theorem of Erdős and Hajnal mentioned above.

Original languageEnglish (US)
Pages (from-to)9991-10004
Number of pages14
JournalInternational Mathematics Research Notices
Volume2024
Issue number12
DOIs
StatePublished - Jun 1 2024

All Science Journal Classification (ASJC) codes

  • General Mathematics

Fingerprint

Dive into the research topics of 'Induced Subgraph Density. I. A loglog Step Towards Erdős–Hajnal'. Together they form a unique fingerprint.

Cite this