Induced subgraph density. II. Sparse and dense sets in cographs
A well-known theorem of Rödl says that for every graph H, and every ε > 0, there exists δ > 0 such that if G does not contain an induced copy of H, then there exists X ⊆ V (G) with |X| ≥ δ|G| such that one of G[X], G[X] has edge-density at most ε. But how does δ depend on ε? Fox and Sudakov co...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2024
|
| _version_ | 1817930829229195264 |
|---|---|
| author | Fox, J Nguyen, T Scott, A Seymour, P |
| author_facet | Fox, J Nguyen, T Scott, A Seymour, P |
| author_sort | Fox, J |
| collection | OXFORD |
| description | A well-known theorem of Rödl says that for every graph H, and every ε > 0, there exists δ > 0 such that if G does not contain an induced copy of H, then there exists X ⊆ V (G) with |X| ≥ δ|G| such that one of G[X], G[X] has edge-density at most ε. But how does δ depend on ε? Fox and Sudakov conjectured that the dependence is at most polynomial: that for all H there exists c > 0 such that for all ε with 0 < ε ≤ 1/2, Rödl’s theorem holds with δ = ε c . This conjecture implies the Erdős-Hajnal conjecture, and until now it had not been verified for any non-trivial graphs H. Our first result shows that it is true when H = P<sub>4</sub>. Indeed, in that case we can take δ = ε, and insist that one of G[X], G[X] has maximum degree at most ε2 |G|).
<br>
Second, we will show that every graph H that can be obtained by substitution from copies of P<sub>4</sub> satisfies the Fox-Sudakov conjecture. To prove this, we need to work with a stronger property. Let us say H is viral if there exists c > 0 such that for all ε with 0 < ε ≤ 1/2, if G contains at most ε c |G| |H| copies of H as induced subgraphs, then there exists X ⊆ V (G) with |X| ≥ ε c |G| such that one of G[X], G[X] has edge-density at most ε. We will show that P<sub>4</sub> is viral, using a “polynomial P<sub>4</sub>-removal lemma” of Alon and Fox. We will also show that the class of viral graphs is closed under vertex-substitution.
<br>Finally, we give a different strengthening of Rödl’s theorem: we show that if G does not contain an induced copy of P<sub>4</sub>, then its vertices can be partitioned into at most 480ε −4 subsets X such that one of G[X], G[X] has maximum degree at most ε|X|. |
| first_indexed | 2024-09-25T04:34:07Z |
| format | Journal article |
| id | oxford-uuid:d2273f4e-0b9b-4ba9-9d4f-5a2ecbb56ad2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:12:20Z |
| publishDate | 2024 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:d2273f4e-0b9b-4ba9-9d4f-5a2ecbb56ad22024-10-15T11:54:26ZInduced subgraph density. II. Sparse and dense sets in cographsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d2273f4e-0b9b-4ba9-9d4f-5a2ecbb56ad2EnglishSymplectic ElementsElsevier2024Fox, JNguyen, TScott, ASeymour, PA well-known theorem of Rödl says that for every graph H, and every ε > 0, there exists δ > 0 such that if G does not contain an induced copy of H, then there exists X ⊆ V (G) with |X| ≥ δ|G| such that one of G[X], G[X] has edge-density at most ε. But how does δ depend on ε? Fox and Sudakov conjectured that the dependence is at most polynomial: that for all H there exists c > 0 such that for all ε with 0 < ε ≤ 1/2, Rödl’s theorem holds with δ = ε c . This conjecture implies the Erdős-Hajnal conjecture, and until now it had not been verified for any non-trivial graphs H. Our first result shows that it is true when H = P<sub>4</sub>. Indeed, in that case we can take δ = ε, and insist that one of G[X], G[X] has maximum degree at most ε2 |G|). <br> Second, we will show that every graph H that can be obtained by substitution from copies of P<sub>4</sub> satisfies the Fox-Sudakov conjecture. To prove this, we need to work with a stronger property. Let us say H is viral if there exists c > 0 such that for all ε with 0 < ε ≤ 1/2, if G contains at most ε c |G| |H| copies of H as induced subgraphs, then there exists X ⊆ V (G) with |X| ≥ ε c |G| such that one of G[X], G[X] has edge-density at most ε. We will show that P<sub>4</sub> is viral, using a “polynomial P<sub>4</sub>-removal lemma” of Alon and Fox. We will also show that the class of viral graphs is closed under vertex-substitution. <br>Finally, we give a different strengthening of Rödl’s theorem: we show that if G does not contain an induced copy of P<sub>4</sub>, then its vertices can be partitioned into at most 480ε −4 subsets X such that one of G[X], G[X] has maximum degree at most ε|X|. |
| spellingShingle | Fox, J Nguyen, T Scott, A Seymour, P Induced subgraph density. II. Sparse and dense sets in cographs |
| title | Induced subgraph density. II. Sparse and dense sets in cographs |
| title_full | Induced subgraph density. II. Sparse and dense sets in cographs |
| title_fullStr | Induced subgraph density. II. Sparse and dense sets in cographs |
| title_full_unstemmed | Induced subgraph density. II. Sparse and dense sets in cographs |
| title_short | Induced subgraph density. II. Sparse and dense sets in cographs |
| title_sort | induced subgraph density ii sparse and dense sets in cographs |
| work_keys_str_mv | AT foxj inducedsubgraphdensityiisparseanddensesetsincographs AT nguyent inducedsubgraphdensityiisparseanddensesetsincographs AT scotta inducedsubgraphdensityiisparseanddensesetsincographs AT seymourp inducedsubgraphdensityiisparseanddensesetsincographs |