Strong graph power ($G^{⊠m}$)

An iterated strong graph product has vertices that are words of length $m$ in the graph's vertex set. Distinct words are nonadjacent exactly when some coordinate contains distinct nonadjacent entries. This differs from the distance-based graph power.

The capacity is the exponential growth rate of the independence numbers of strong graph powers. Products of independent sets make these numbers supermultiplicative, and Fekete lemma gives the limit and its equality to the supremum. Passing to every second power gives $c(G⊠G)=c(G{)}^2$.

A fitting matrix over a field has nonzero diagonal entries and zero entries at distinct nonadjacent vertices. Its tensor powers fit strong graph powers. On an independent set the restricted matrix is diagonal and nonsingular, so its cardinality is at most the matrix rank. This yields the capacity upper bound over every field.

Choose points $a_v\in F^r$ and polynomials $f_v$ in a finite-dimensional polynomial space $M$, with $f_v(a_v)\ne 0$ and $f_v(a_w)=0$ for distinct nonadjacent vertices. Evaluation produces a fitting matrix of rank at most ${\dim }_{F}M$. Equivalently, tensoring the polynomial spaces gives linearly independent polynomials for every independent code in a strong power, proving $c(G)\le {\dim }_{F}M$.

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 $\left(\genfrac{}{}{0ex}{}{2m}{m}\right)n^m$. Taking $2m$th roots gives the displayed bound.

Capacity of a disjoint union can strictly exceed the sum of the capacities. On the five-element subsets of a twenty-point set, join distinct sets when their intersection is odd. Linear polynomials over ${\mathbb{F}}_2$ bound its capacity by twenty; squarefree quadratic polynomials over ${\mathbb{F}}_3$ bound its complement's capacity by $\left(\genfrac{}{}{0ex}{}{20}{2}\right)=190$. The complement-pair lower bound is $2\sqrt{\left(\genfrac{}{}{0ex}{}{20}{5}\right)}>210$, establishing strict nonadditivity.

These five words are independent in the strong square of the cycle graph $C_5$: a nonzero difference is a nonedge in the first or the second coordinate. A three-dimensional orthonormal representation with common vertical squared component $1/\sqrt{5}$ proves the matching upper bound. Consequently $c(C_5)=\vartheta (C_5)=\sqrt{5}$.