Shannon Capacity

The Shannon capacity , sometimes also denoted , of a graph is defined in terms of its independence number by

(1)

where denotes the graph strong product (Shannon 1956, Alon and Lubetzky 2006). The Shannon capacity is an important information-theoretic parameter because it represents the effective size of an alphabet in a communication model represented by a graph (Alon 1998).

The independence number gives the lower bound

(2)

The Lovász number and Haemers number give upper bounds.

The Shannon capacity is in general very difficult to calculate (Brimkov et al. 2000). In fact, the Shannon capacity of the cycle graph was not determined as until 1979 (Lovász 1979), and the Shannon capacity of is perhaps one of the most notorious open problems in extremal combinatorics (Bohman 2003).

For , Protti (2026) reported an explicit independent set in the 213-fold graph strong product , giving

(3)

The same release gives an explicit independent set in the 522-fold graph strong product and hence

(4)

The constructions were co-developed with OpenAI models and checked using Lean 4, including exact cardinalities and strict comparisons with the preceding lower bounds. The numerical verification uses native evaluation rather than kernel-only arithmetic replay. Independent statement review and specialist review remained pending as of Sep. 10, 2026. The exact values of and remain unknown.

Lovász (1979) showed that the Shannon capacity of the -Kneser graph is , that of a vertex-transitive self-complementary graph (which includes all Paley graphs) is , and that of the Petersen graph is 4.

As a consequence of a superexponential lower bound for multicolor triangle Ramsey numbers, an AI-generated proof given by OpenAI (2026) established that is unbounded among graphs with . Thus no function of the independence number is an upper bound for Shannon capacity.

All graphs whose Shannon capacity is known attain their capacity either at (i.e., at their independence number; e.g., perfect graphs), (e.g., self-complementary vertex-transitive graphs-including the Paley graphs), or else do not attain it at any value of (e.g., the graph union of the cycle graph with a singleton graph) (Alon and Lubetzky 2006).

The alternative OR-capacity convention is , where is the graph complement. Zeiss (2026, Theorem 1) gives counterexamples to the minimum rule for this convention under the graph categorical product. For every integer , a graph satisfies

(5)

Here is the complete graph. The stronger construction makes the product capacity subpolynomial in , while both factor capacities are at least (Zeiss 2026, Theorem 3). The finite certificates were not independently replayed here. Zeiss (2026) reports AI assistance in exploring constructions and developing verification programs.