Making Kr+1-free graphs r-partite
| Autor: | József Balogh, Bernard Lidický, Mikhail Lavrov, Florian Pfender, Felix Christian Clemen |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Statistics and Probability
Applied Mathematics Existential quantification 010102 general mathematics 0102 computer and information sciences 01 natural sciences Graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) 0101 mathematics Stability theorem Mathematics |
| Zdroj: | Combinatorics, Probability and Computing. 30:609-618 |
| ISSN: | 1469-2163 0963-5483 |
| DOI: | 10.1017/s0963548320000590 |
| Popis: | The Erd\H{o}s-Simonovits stability theorem states that for all \epsilon >0 there exists \alpha >0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - \alpha n^2, then one can remove \epsilon n^2 edges from G to obtain an r-partite graph. F\"uredi gave a short proof that one can choose \alpha=\epsilon. We give a bound for the relationship of \alpha and \varepsilon which is asymptotically sharp as \epsilon \to 0. Comment: 12 pages, 1 figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|