Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 2 / ii / Solution

We first need the minimal-member bound for a Razborov-closed family: an $r$-closed family has at most $(r-1{)}^k$ inclusion-minimal members of size $k$. Indeed, its minimal members of size at most $k$ cannot contain $r$ sets whose pairwise intersections lie inside a proper subset of another minimal member, since closure would then contain that proper subset. The resulting set-system bound is proved by induction on $r$: fix one member $D$, partition the remaining members according to their intersections $C\subseteq D$, delete $C$, and apply the $(r-1,k-|C|)$ bound in each class. Summing over $C$ gives

If $⟨A⟩$ is not the set of all graphs, no inclusion-minimal member of $A$ has size zero or one. Every $m$-clique in $⟨A⟩$ contains a minimal $W\in A$, so the number of such cliques is at mostDividing by $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ and usingthe assumed $2(r-1)m\le n$ gives a proportion at mostThus either $⟨A⟩$ is universal or it contains at most half of all $m$-cliques.