ABSTRACT
Most of the extremal problems we consider in this book ask for the maximum possible size of a family that satisfies a prescribed property. If this maximum size is determined, then one can try to describe all families attaining this size, i.e. the extremal families. If (up to isomorphism) there is a unique extremal family, or there is just a limited number of them, then one can hope for a stability result. Such a theorem would state that every family of almost extremal size, must have very similar structure to (one of) the extremal family(ies). The first such result was obtained by Erdős [153] and Simonovits [513] who proved the following stability version of Turan’s famous theorem on graphs with clique number at most p: for every δ > 0 there exists an ε > 0 and n 0 such that if a graph on n ≥ n 0 vertices does not contain a clique of size p + 1 and has at most εn 2 fewer edges than the extremal graphs, then after the removal of at most δn 2 edges of G one can obtain a subgraph of an extremal graph.
