Stability-type results for hereditary properties

Noga Alon, Uri Stav

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

The classical Stability Theorem of Erdös and Simonovits can be stated as follows. For a monotone graph property P, let t≥2 be such that t+1=min{x(H):H∉P }. Then any graph G*ΕP on n vertices, which was obtained by removing at most (1/t+o(1))(n2) edges from the complete graph G=Kn, has edit distance o(n2) to T n(t), the Turán graph on n vertices with t parts. In this paper we extend the above notion of stability to hereditary graph properties. It turns out that to do so the complete graph Kn has to be replaced by a random graph. For a hereditary graph property P , consider modifying the edges of a random graph G=G(n,1/2) to obtain a graph G* that satisfies P in (essentially) the most economical way. We obtain necessary and sufficient conditions on P , which guarantee that G* has a unique structure. In such cases, for a pair of integers (r,s), which depends on P , G* , has distance o(n2) to a graph Tn(r,s,1/2) almost surely. Here Tn(r,s,1/2) denotes a graph, which consists of almost equal-sized r+s parts, r of them induce an independent set, s induce a clique and all the bipartite graphs between parts are quasi-random (with edge density 1/2). In addition, several strengthened versions of this result are shown.

Original languageEnglish (US)
Pages (from-to)65-83
Number of pages19
JournalJournal of Graph Theory
Volume62
Issue number1
DOIs
StatePublished - Sep 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Cut distance
  • Edit distance
  • Extremal graph theory
  • Hereditary properties
  • Stability theorem

Fingerprint Dive into the research topics of 'Stability-type results for hereditary properties'. Together they form a unique fingerprint.

  • Cite this