TY - JOUR

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

AU - Bucić, Matija

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

N1 - Publisher Copyright:
© The Author(s) 2024. Published by Oxford University Press.

PY - 2024/6/1

Y1 - 2024/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85192959628&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85192959628&partnerID=8YFLogxK

U2 - 10.1093/imrn/rnae065

DO - 10.1093/imrn/rnae065

M3 - Article

AN - SCOPUS:85192959628

SN - 1073-7928

VL - 2024

SP - 9991

EP - 10004

JO - International Mathematics Research Notices

JF - International Mathematics Research Notices

IS - 12

ER -