= Solution
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$.
Back to article page
