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

DOI10.1016/J.JCTB.2015.05.001zbMATH Open1319.05074arXiv1501.03129OpenAlexW1543148594MaRDI QIDQ490983FDOQ490983

Zoltán Füredi

Publication date: 21 August 2015

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

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.

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

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

zbMATH Keywords

stabilityextremal graphsTurán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure of linear graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bipartite subgraphs
• A hypergraph extension of Turán's theorem
• Title not available (Why is that?)
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• A new proof of the graph removal lemma
• Graph removal lemmas
• Title not available (Why is that?)
• On the computation of edit distance functions
• Title not available (Why is that?)
• Avoiding Patterns in Matrices Via a Small Number of Changes
• The maximum edit distance from hereditary graph properties
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of edge disjoint cliques in graphs of given size
• Books versus triangles
• Title not available (Why is that?)

Cited In (35)

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

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)