Stability‐type results for hereditary properties

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{χ( H ): H∉ ∈ P }. Then any graph G * ∈ P on n vertices, which was obtained by removing at most$(1/t+o (1)) \left(_{2}^{n}\right)$edges from the complete graph G = K n , has edit distance o ( n 2 ) 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 K n 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 ,½) 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 ( n 2 ) to a graph T n ( r, s , ½) almost surely. Here T n ( r, s , ½) 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 ½. In addition, several strengthened versions of this result are shown. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 65–83, 2009