Intersection theorems
Dániel Gerbner, Balázs Patkós · 2018
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.