Exact stability for Turán's theorem

DOI10.19086/AIC.31079zbMATH Open1482.05160arXiv2004.10685OpenAlexW4205315408MaRDI QIDQ5028504FDOQ5028504

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

Publication date: 10 February 2022

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

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.

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

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

zbMATH Keywords

stabilityextremal graph theorystability theoremTurán's theorem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

• A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs
• Stability for large forbidden subgraphs
• Turán's theorem inverted
• 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
• Extension of Turán's theorem to the 2-stability number
• An extension of Turán's theorem, uniqueness and stability
• 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 version of Dirac's theorem and its applications for generalized Turán problems
• Stability results for graphs with a critical edge
• 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)