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

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.

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.

Let an $m$-clique on vertex set $Z$ belong toThen $Z$ contains minimal members $X\in A$ and $Y\in B$, but contains no member of $A\cap B$. If $|X\cup Y|\le l$, upward closure of both closed families would put $X\cup Y$ in $A\cap B$, a contradiction. Hence $|X\cup Y|>l$, so either $|X|>l/2$ or $|Y|>l/2$.

Using the minimal-member bound from part (ii), the number of possible $Z$ is at mostAfter division by $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ and use of $2(r-1)m\le n$, this is at most

Put $C=A\cup B$. ThenGenerate a uniformly random complete $(m-1)$-partite graph by independently assigning one of $m-1$ colours to each vertex and joining vertices of different colours. Such a graph contains the clique on $W$ exactly when the colouring is injective on $W$.

Construct $C^{\ast }$ by adjoining one forced set at a time. There are at most $n^l$ possible sets of size at most $l$. If $W$ is newly forced by $W_1,\dots ,W_r$, then, conditional on $W$ being rainbow, the events that each $W_i$ is not rainbow depend on disjoint petals $W_i\setminus W$. Since $l^2\le m$, each has conditional probability at most $1/2$. Their simultaneous probability is therefore at most $2^{-r}$. A union bound over the at most $n^l$ closure steps givesThis is exactly the claimed proportion of complete $(m-1)$-partite graphs.

Let a monotone circuit of size $M$ compute the $m$-clique function, and let $\tilde{S}=⟨A⟩$ be its lattice approximation from part (i). If $\tilde{S}$ is not universal, part (ii) says that it misses at least half of all positive $m$-cliques. The approximation lemma and part (iii) then implyIf $\tilde{S}$ is universal, every complete $(m-1)$-partite graph is a negative input that must be covered by a union-error set. Part (iv) givesThereforeChoosewith constants satisfying the two hypotheses and $r>2l{\log }_{2}n$. Both lower bounds are thenSince the graph has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ input variables, this is exponential in a positive power of the number of inputs, up to a logarithmic factor.

As Boolean functions on edge indicators,Thus $g_m$ is the dual Boolean function of the clique function. Given a monotone circuit for $g_m$, swap every AND gate with an OR gate and swap the constants zero and one. De Morgan's laws show that the resulting circuit has the same size and computes ${\mathrm{CLIQUE}}_{n,m}$. The lower bound from part (v), with the same choice of $m$, therefore applies to $g_m$.