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

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$.