Structure and stability of triangle-free set systems

Abstract:

We define the notion of stability for a monotone property of set systems. This phenomenon encompasses some classical results in combinatorics, foremost among them the Erdős-Simonovits stability theorem. A triangle is a family of three sets $A, B, C$ such that $A \cap B$, $B \cap C$, $C \cap A$ are each nonempty, and $A \cap B \cap C= \emptyset$. We prove the following new theorem about the stability of triangle-free set systems. Fix $r\ge 3$. For every $\delta >0$, there exist $\epsilon >0$ and $n_0=n_0(\epsilon , r)$ such that the following holds for all $n>n_0$: if $|X|=n$ and $\mathcal {G}$ is a triangle-free family of $r$-sets of $X$ containing at least $(1-\epsilon ){n-1 \choose r-1}$ members, then there exists an $(n-1)$-set $S \subset X$ which contains fewer than $\delta {n-1 \choose r-1}$ members of $\mathcal {G}$. This is one of the first stability theorems for a nontrivial problem in extremal set theory. Indeed, the corresponding extremal result, that for $n \ge 3r/2>4$ every triangle-free family $\mathcal {G}$ of $r$-sets of $X$ has size at most ${n-1 \choose r-1}$, was a longstanding conjecture of Erdős (open since 1971) that was only recently settled by Mubayi and Verstraëte (2005) for all $n\ge 3r/2$.