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)) \binom{n}{2}$ edges, and any $H$-free graph with that many edges can be made $r$-partite by deleting $o(n^{2})$ edges...
| 主要作者: | |
|---|---|
| 格式: | Journal article |
| 语言: | English |
| 出版: |
2021
|
| _version_ | 1826261435295989760 |
|---|---|
| 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)) \binom{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-06T19:21:24Z |
| format | Journal article |
| id | oxford-uuid:1a369879-3bc3-4833-bdce-6be72f7154d2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:21:24Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | oxford-uuid:1a369879-3bc3-4833-bdce-6be72f7154d22022-03-26T10:53:31ZMinimum degree stability of H-free graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1a369879-3bc3-4833-bdce-6be72f7154d2EnglishSymplectic Elements2021Illingworth, 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)) \binom{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 |