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

For a family $A\subseteq [n{]}^{(\le l)}$, let $⟨A⟩$ be the set of graphs on $[n]$ containing the clique on some $W\in A$. Write $A^{\ast }$ for its Razborov closure: whenever $W_1,\dots ,W_r\in A$ andwith all sets of size at most $l$, closure adjoins $W$. A family is $r$-closed when $A=A^{\ast }$.

For closed $A,B$, define the lattice operationsThe corresponding error sets are

The Razborov gate-by-gate approximation lemma says that if a monotone circuit of size at most $M$ computes a graph family $S$, and $\tilde{S}$ is obtained by evaluating the same circuit with $\square ,\bigsqcup$, then there are at most $M$ pairs of intermediate lattice elements such thatThis follows by induction through the circuit: an AND gate can introduce only a ${\delta }_{\cap }$ error, and an OR gate only a ${\delta }_{\cup }$ error.