Minimum degree stability of H-free graphs
<p>Given an (r + 1)-chromatic graph H, the fundamental edge stability result of Erdős and Simonovits says that all n-vertex H-free graphs have at most (1 − 1/r + o(1))( n 2 ) edges, and any H-free graph with that many edges can be made r-partite by deleting o(n 2 ) edges. Here we con...
| Hlavní autor: | |
|---|---|
| Médium: | Journal article |
| Jazyk: | English |
| Vydáno: |
Springer
2023
|
| _version_ | 1826311079588790272 |
|---|---|
| author | Illingworth, F |
| author_facet | Illingworth, F |
| author_sort | Illingworth, F |
| collection | OXFORD |
| description | <p>Given an (r + 1)-chromatic graph H, the fundamental edge stability result of Erdős and Simonovits says that all n-vertex H-free graphs have at most (1 − 1/r + o(1))( n 2 ) edges, and any H-free graph with that many edges can be made r-partite by deleting o(n 2 ) edges. Here we consider a natural variant of this – the minimum degree stability of H-free graphs. In particular, what is the least c such that any n-vertex H-free graph with minimum degree greater than cn can be made r-partite by deleting o(n 2 ) edges? We determine this least value for all 3- chromatic H and for very many non-3-colourable H (all those in which one is commonly interested) as well as bounding it for the remainder. This extends the Andrásfai-Erdős-Sós theorem and work of Alon and Sudakov</p> |
| first_indexed | 2024-03-07T08:03:04Z |
| format | Journal article |
| id | oxford-uuid:10b41b53-020e-43dc-86df-4480242b3a57 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:03:04Z |
| publishDate | 2023 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:10b41b53-020e-43dc-86df-4480242b3a572023-10-13T06:26:36ZMinimum degree stability of H-free graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:10b41b53-020e-43dc-86df-4480242b3a57EnglishSymplectic ElementsSpringer2023Illingworth, F<p>Given an (r + 1)-chromatic graph H, the fundamental edge stability result of Erdős and Simonovits says that all n-vertex H-free graphs have at most (1 − 1/r + o(1))( n 2 ) edges, and any H-free graph with that many edges can be made r-partite by deleting o(n 2 ) edges. Here we consider a natural variant of this – the minimum degree stability of H-free graphs. In particular, what is the least c such that any n-vertex H-free graph with minimum degree greater than cn can be made r-partite by deleting o(n 2 ) edges? We determine this least value for all 3- chromatic H and for very many non-3-colourable H (all those in which one is commonly interested) as well as bounding it for the remainder. This extends the Andrásfai-Erdős-Sós theorem and work of Alon and Sudakov</p> |
| spellingShingle | Illingworth, F Minimum degree stability of H-free graphs |
| title | Minimum degree stability of H-free graphs |
| title_full | Minimum degree stability of H-free graphs |
| title_fullStr | Minimum degree stability of H-free graphs |
| title_full_unstemmed | Minimum degree stability of H-free graphs |
| title_short | Minimum degree stability of H-free graphs |
| title_sort | minimum degree stability of h free graphs |
| work_keys_str_mv | AT illingworthf minimumdegreestabilityofhfreegraphs |