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 -