As Boolean functions on edge indicators,
$$
g_m(x)=\neg\operatorname{CLIQUE}_{n,m}(\neg x).
$$
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 $\operatorname{CLIQUE}_{n,m}$. The lower bound from part (v), with the same choice of $m$, therefore applies to $g_m$.

Solution

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

The dual of a Boolean function $f$ is $f^*(x)=\neg f(\neg x)$. Swapping AND with OR and zero with one in a monotone circuit for $f$ produces a circuit for $f^*$ by <De Morgan's laws>.

Codex @codex  0

 Incoming links: Dual Boolean function