Shannon Capacity and Related Graph Invariants for Lexicographic Products
Abstract
This paper studies the Shannon capacity of lexicographic products of finite simple graphs, together with the Lovász theta function and the fractional Haemers number. The Shannon capacity is proved to be supermultiplicative under lexicographic products in either order, and these products are compared with the strong product. We explicitly construct three countably infinite families of lexicographic powers based on the Schläfli graph, the McLaughlin graph, and its second subconstituent; in each family, pairing each member with its complement yields strict supermultiplicativity and arbitrarily large multiplicative gaps. Bounds and exact-capacity criteria for lexicographic products are derived, and the resulting upper bounds are shown to be incomparable. The capacities of lexicographic products involving Kneser graphs, their complements, and q-analogues of Kneser graphs are determined. It is also shown that a lexicographic product with a complete outer factor preserves the Shannon capacity of an arbitrary inner factor. The capacities of iterated lexicographic powers are determined, including those of self-complementary graphs that are vertex-transitive or strongly regular. Elementary, self-contained proofs are also given for three known results: the multiplicativity of the Lovász theta function and the fractional Haemers number under lexicographic products, and the equality of the fractional and ordinary Lovász theta functions. Finally, an open problem concerning the Shannon capacities of lexicographic and strong products is posed.
Related
- Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
- Unlocking Exponential and Unbounded Robust Gains in Shannon Capacity of Classical Multiple Access Channels with Causal CSIT via Quantum Entanglement Assistance
- Strengthening Recursive Constructions for Zero-Error Shannon Capacity
- ℓ2-Betti numbers and Σ-invariants of graph products of cyclic groups and their automorphisms
- Secondary Chow Invariants beyond Lawson--Massey Products
BibTeX
@misc{sason2026shannon,
title = {{Shannon Capacity and Related Graph Invariants for Lexicographic Products}},
author = {Igal Sason},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.06573},
eprint = {2608.06573},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.06573},
}
RIS
TY - UNPB
TI - Shannon Capacity and Related Graph Invariants for Lexicographic Products
AU - Igal Sason
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.06573
UR - https://arxiv.org/abs/2608.06573
AB - This paper studies the Shannon capacity of lexicographic products of finite simple graphs, together with the Lovász theta function and the fractional Haemers number. The Shannon capacity is proved to be supermultiplicative under lexicographic products in either order, and these products are compared with the strong product. We explicitly construct three countably infinite families of lexicographic powers based on the Schläfli graph, the McLaughlin graph, and its second subconstituent; in each family, pairing each member with its complement yields strict supermultiplicativity and arbitrarily large multiplicative gaps. Bounds and exact-capacity criteria for lexicographic products are derived, and the resulting upper bounds are shown to be incomparable. The capacities of lexicographic products involving Kneser graphs, their complements, and q-analogues of Kneser graphs are determined. It is also shown that a lexicographic product with a complete outer factor preserves the Shannon capacity of an arbitrary inner factor. The capacities of iterated lexicographic powers are determined, including those of self-complementary graphs that are vertex-transitive or strongly regular. Elementary, self-contained proofs are also given for three known results: the multiplicativity of the Lovász theta function and the fractional Haemers number under lexicographic products, and the equality of the fractional and ordinary Lovász theta functions. Finally, an open problem concerning the Shannon capacities of lexicographic and strong products is posed.
ER -