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

Füredi, Zoltán (2015) A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity. JOURNAL OF COMBINATORIAL THEORY SERIES B, 115. pp. 66-71. ISSN 0095-8956

Preview

Text 1501.03129v1.pdf Download (103kB) | Preview

Abstract

Let T<inf>n,p</inf> denote the complete p-partite graph of order n having the maximum number of edges. The following sharpening of Turán's theorem is proved. Every K<inf>p+1</inf>-free graph with n vertices and e(T<inf>n,p</inf>)-t edges contains a p-partite subgraph with at least e(T<inf>n,p</inf>)-2t edges. As a corollary of this result we present a concise, contemporary proof (i.e., one applying the Removal Lemma, a corollary of Szemerédi's regularity lemma) for the classical stability result of Simonovits [25]. © 2015 Elsevier Inc.

Actions (login required)

Edit Item