A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity

DOI10.1016/J.JCTB.2015.05.001MaRDI QIDQ490983zbMATH OpenOpenAlexFDO

Authors Zoltán Füredi

Publication date 21 August 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

stabilityextremal graphsTurán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: The following sharpening of Tur'an's theorem is proved. Let $T_{n,p}$ denote the complete $p$--partite graph of order $n$ having the maximum number of edges. If $G$ is an $n$-vertex $K_{p+1}$-free graph with $e(T_{n,p})-t$ edges then there exists an (at most) $p$-chromatic subgraph $H_0$ such that $e(H_0)geqe(G)-t$. Using this result we present a concise, contemporary proof (i.e., one applying Szemer'edi's regularity lemma) for the classical stability result of Simonovits.

Recommendations

• Exact stability for Turán's theorem
• Stability results for graphs with a critical edge
• Making K_r+1-free graphs r-partite
• Strong Turán stability
• Strong Turán stability

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 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 2086426 (Why is no real title available?)
• scientific article; zbMATH DE number 850070 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3258858 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3307332 (Why is no real title available?)
• scientific article; zbMATH DE number 3365308 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A hypergraph extension of Turán's theorem
• A new proof of the graph removal lemma
• Avoiding Patterns in Matrices Via a Small Number of Changes
• Bipartite subgraphs
• Books versus triangles
• Graph removal lemmas
• On the computation of edit distance functions
• On the number of edge disjoint cliques in graphs of given size
• On the structure of linear graphs
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The maximum edit distance from hereditary graph properties

Cited in

(38)

• Strong forms of stability from flag algebra calculations
• Maximum number of triangle-free edge colourings with five and six colours
• Hypergraphs with minimum positive uniform Turán density
• An analytic approach to stability
• The maximum spectral radius of graphs without friendship subgraphs
• Extremal graphs with given stability number and connectivity. II
• Improving the Caro-Wei bound and applications to Turán stability
• Stability from graph symmetrization arguments in generalized Turán problems
• New short proofs to some stability theorems
• Uniform hypergraphs with many edge‐colorings avoiding a fixed rainbow expanded complete graph
• Stability results for two classes of hypergraphs
• Remarks on an edge-coloring problem
• The spectral radius of graphs with no odd wheels
• Stability of extremal hypergraphs with applications to an edge-coloring problem
• A rainbow Erdös-Rothschild problem
• Exact solutions to the Erdős-Rothschild problem
• On graphs with a large number of edge-colorings avoiding a rainbow triangle
• Strong Turán stability
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Graphs with many edge-colorings such that complete graphs are rainbow
• Two Conjectures in Ramsey--Turán Theory
• Spectral extremal graphs for intersecting cliques
• A note on bipartite subgraphs and triangle-independent sets
• Edge-colorings avoiding patterns in a triangle
• Refinement on Spectral Turán’s Theorem
• Short proofs of some extremal results. III
• Strong Turán stability
• The spectral radius of graphs with no intersecting odd cycles
• Stability from graph symmetrisation arguments with applications to inducibility
• Making K_r+1-free graphs r-partite
• Every graph is eventually Turán-good
• Some sharp results on the generalized Turán numbers
• On the maximum number of edges in \(k\)-critical graphs
• On stability of the Erdős-Rademacher problem
• On a colored Turán problem of Diwan and Mubayi
• An extension of the rainbow Erdős-Rothschild problem
• Exact stability for Turán's theorem
• Stability results for graphs with a critical edge

This page was built for publication: A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity

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