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

preprint2015arXivOpen access

Abstract

The following sharpening of Turán's theorem is proved. Let Tn,pT_{n,p} denote the complete pp--partite graph of order nn having the maximum number of edges. If GG is an nn-vertex Kp+1K_{p+1}-free graph with e(Tn,p)−te(T_{n,p})-t edges then there exists an (at most) pp-chromatic subgraph H0H_0 such that e(H0)≥e(G)−te(H_0)\geq e(G)-t. Using this result we present a concise, contemporary proof (i.e., one applying Szemerédi's regularity lemma) for the classical stability result of Simonovits.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.