Induced subgraph density. I. A loglog step towards Erdos-Hajnal
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914684061351936 |
|---|---|
| author | Bucić, Matija Nguyen, Tung Scott, Alex Seymour, Paul |
| author_facet | Bucić, Matija Nguyen, Tung Scott, Alex Seymour, Paul |
| contents | 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 $2^{c\sqrt{\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|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_10147 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Induced subgraph density. I. A loglog step towards Erdos-Hajnal Bucić, Matija Nguyen, Tung Scott, Alex Seymour, Paul Combinatorics 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 $2^{c\sqrt{\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|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\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. |
| title | Induced subgraph density. I. A loglog step towards Erdos-Hajnal |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2301.10147 |