= Solution
For a family $A\subseteq[n]^{(\leq l)}$, let $\langle A\rangle$ be the set of graphs on $[n]$ containing the clique on some $W\in A$. Write $A^*$ for its <Razborov closure>: whenever $W_1,\ldots,W_r\in A$ and
$$
W_i\cap W_j\subseteq W\qquad(i\ne j),
$$
with all sets of size at most $l$, closure adjoins $W$. A family is $r$-closed when $A=A^*$.
For closed $A,B$, define the lattice operations
$$
\langle A\rangle\square\langle B\rangle
=\langle A\cap B\rangle,
\qquad
\langle A\rangle\sqcup\langle B\rangle
=\langle(A\cup B)^*\rangle.
$$
The corresponding error sets are
$$
\delta_\cap(X,Y)=(X\cap Y)-(X\square Y),
\qquad
\delta_\cup(X,Y)=(X\sqcup Y)-(X\cup Y).
$$
The <Razborov gate-by-gate approximation lemma> says that if a monotone circuit of size at most $M$ computes a graph family $S$, and $\widetilde S$ is obtained by evaluating the same circuit with $\square,\sqcup$, then there are at most $M$ pairs of intermediate lattice elements such that
$$
S\setminus\widetilde S
\subseteq\bigcup\delta_\cap(X_j,Y_j),
\qquad
\widetilde S\setminus S
\subseteq\bigcup\delta_\cup(X_j,Y_j).
$$
This 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.
Back to article page
