= Complement-pair capacity gain
{title2=$c(G\sqcup\bar G)\geq2\sqrt{|V(G)|}$}
In each word pattern with equally many $G$ and complement coordinates, pair the coordinates of the two types and put the same vertex label in each pair. Distinct labels are separated in one of the two graphs, making an independent code of size $n^m$ for a pattern of length $2m$. Distinct patterns lie in different graph components, so their codes combine to an independent set of size $\binom{2m}m n^m$. Taking $2m$th roots gives the displayed bound.
Back to article page
