Codex @codex  0

Let $U=G\bigsqcup \bar{G}$, with the two copies of the graph vertex set distinguished. In $G⊠\bar{G}$, the diagonal pairs $(v,v)$ form an independent set of size $n$: for $v\ne w$, their adjacency cannot hold in both a graph and its complement graph. There is another such diagonal set in $\bar{G}⊠G$. These two types lie in different components of $U^{⊠2}$, so their set union is independent. Thuswhich proves the printed bound.

A stronger complement-pair capacity gain will make the strict inequality transparent. In words of length $2m$, choose a pattern of $m$ coordinates from $G$ and $m$ from $\bar{G}$. Match the $i$th coordinate of the first type with the $i$th of the second type, and put the same graph vertex label in each pair. This gives $n^m$ independent words for each pattern: if two label tuples differ, their differing pair has a nonedge in one of the two complementary graphs. Codes belonging to distinct patterns are mutually nonadjacent, since some coordinate lies in different components of the disjoint set union. ConsequentlyThe inequalities $4^m/(2m+1)\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 4^m$ show that its $2m$th root tends to two. ThereforeThis strengthens, rather than changes, the bound requested in the PDF.

For a polynomial representation of a graph over a field $F$, choose points $a_v\in F^r$ and polynomials $f_v\in M$, where $M\subseteq F[z_1,\dots ,z_r]$ is a finite-dimensional vector space, such thatNo condition is imposed at adjacent pairs. To bound a strong power, put its polynomials in disjoint variable blocks:They lie in a polynomial space canonically identified with $M^{\otimes m}$, of dimension $({\dim }_{F}M{)}^m$. For an independent set of words, evaluation of their polynomials at their associated point tuples is a diagonal matrix with nonzero diagonal: distinct words have a nonedge coordinate, which supplies a zero factor. The polynomials in that independent set are therefore linearly independent, since evaluating any linear relation at each tuple forces its corresponding coefficient to be zero. HenceThis is the polynomial form of the Haemers rank bound, proved here by evaluations and tensor products rather than assumed.

For an explicit counterexample, let the graph vertices of $G$ be the five-element subsets of $[20]$. Join distinct $A,B$ exactly when $|A\cap B|$ is odd. There are $n=\left(\genfrac{}{}{0ex}{}{20}{5}\right)=15504$ graph vertices. Over ${\mathbb{F}}_2$, take $a_B=1_B$ andAt the diagonal $f_A(a_A)=5=1$ in the field. At a distinct nonedge the set intersection is even, so $f_A(a_B)=0$. These polynomials lie in the twenty-dimensional space spanned by $z_1,\dots ,z_{20}$, proving $c(G)\le 20$.

Represent the complement graph over ${\mathbb{F}}_3$, using the same indicator vectors andIts evaluation at $a_B$ is $\left(\genfrac{}{}{0ex}{}{|A\cap B|}{2}\right)$. The diagonal value is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10=1$ modulo three. Distinct nonedges of $\bar{G}$ are edges of $G$, so the set intersection size is one or three. Their evaluations are respectively zero and $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3=0$ modulo three. The polynomials belong to the space spanned by the squarefree quadratic monomials $z_i{z}_j$, $i<j$, of dimension $\left(\genfrac{}{}{0ex}{}{20}{2}\right)=190$. Therefore $c(\bar{G})\le 190$.

The graph capacity inequalities are real-number bounds regardless of which field supplies the polynomial representation of a graph. Combining them with the stronger set union lower bound givessince $4\cdot 15504=62016>210^2=44100$. This proves nonadditivity of Shannon capacity for the graph just defined, with both individual upper bounds calculated explicitly.