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...
| 1. autor: | |
|---|---|
| Format: | Journal article |
| Język: | English |
| Wydane: |
2021
|
| Streszczenie: | <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> |
|---|