Exact stability for Turán's theorem

DOI10.19086/AIC.31079MaRDI QIDQ5028504zbMATH OpenOpenAlexFDO

Authors Dániel Korándi, Alexander Roberts, Alex Scott

Publication date 10 February 2022

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2004.10685

zbMATH Keywords

stabilityextremal graph theorystability theoremTurán's theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

Abstract: Tur'an's Theorem says that an extremal $K_{r+1}$-free graph is $r$-partite. The Stability Theorem of ErdH{o}s and Simonovits shows that if a $K_{r+1}$-free graph with $n$ vertices has close to the maximal $t_r(n)$ edges, then it is close to being $r$-partite. In this paper we determine exactly the $K_{r+1}$-free graphs with at least $m$ edges that are farthest from being $r$-partite, for any $mge{t}_r(n)-delt{a}_r{n}^2$. This extends work by ErdH{o}s, GyH{o}ri and Simonovits, and proves a conjecture of Balogh, Clemen, Lavrov, Lidick'y and Pfender.

Recommendations

• Strong Turán stability
• Strong Turán stability
• Making K_r+1-free graphs r-partite
• A stability theorem for maximal \(K_{r+1}\)-free graphs
• Stability for large forbidden subgraphs

Cites work

• scientific article; zbMATH DE number 426334 (Why is no real title available?)
• scientific article; zbMATH DE number 4214034 (Why is no real title available?)
• scientific article; zbMATH DE number 3691361 (Why is no real title available?)
• scientific article; zbMATH DE number 3523543 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• Degrees and matchings
• Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
• How to make a graph bipartite
• Making K_r+1-free graphs r-partite
• Making a K₄-free graph bipartite
• Maximum \(K_{r+1}\)-free graphs which are not \(r\)-partite.
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the non-\((p-1)\)-partite \(K_p\)-free graphs
• Stability results for graphs with a critical edge
• Stability results for random discrete structures
• Strong Turán stability
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The number of graphs without forbidden subgraphs
• The typical structure of sparse \(K_{r+1}\)-free graphs
• Unit distances and diameters in Euclidean spaces

Cited in

(18)

• A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs
• Turán's theorem inverted
• Stability for large forbidden subgraphs
• Strong Turán stability
• A generalization of Turán's theorem
• Strong Turán stability
• Improving the Caro-Wei bound and applications to Turán stability
• Stability and exact Turán numbers for matroids
• An extension of Turán's theorem, uniqueness and stability
• Extension of Turán's theorem to the 2-stability number
• Maximum \(K_{r+1}\)-free graphs which are not \(r\)-partite.
• Stability from graph symmetrization arguments in generalized Turán problems
• Turán’s Theorem Through Algorithmic Lens
• Stability results for graphs with a critical edge
• Stability version of Dirac's theorem and its applications for generalized Turán problems
• Making K_r+1-free graphs r-partite
• On stability of the Erdős-Rademacher problem
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity

This page was built for publication: Exact stability for Turán's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028504)