Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
math.CO
Submitted: 2026-10-30
Updated: 2026-10-30
Comments: 46 pages: 18 pages main text including references and 28 pages supplementary appendices; 2 figures, 8 tables
Code: https://github.com/JuliusAZeiss/shannon-or-capacity-data
License: http://creativecommons.org/licenses/by/4.0/
The gist: We disprove the analogue of Hedetniemi's conjecture for Shannon OR-capacity, which asserts that the capacity of a categorical product equals the smaller capacity of its factors.
Abstract
We disprove the analogue of Hedetniemi's conjecture for Shannon OR-capacity, which asserts that the capacity of a categorical product equals the smaller capacity of its factors. For every sufficiently large complete graph, we construct a second graph of larger capacity such that their categorical product has capacity strictly below that of the complete graph. Further constructions show that, for every real threshold above an explicit constant, both factor capacities can exceed that threshold while the product capacity lies below it. We also construct graph pairs, again with one complete factor, whose capacities tend to infinity while their product capacity is subpolynomial in the smaller factor capacity. Whether the product capacity must nevertheless tend to infinity whenever both factor capacities do remains open. The proofs use spectral interpolation, which also yields a single spectral point violating Hedetniemi's identity throughout the complete-factor family. Finally, we identify the categorical product as the distinguishability graph of a random-switching model for zero-error communication. In this model, our constructions show that switching can reduce the zero-error rate to a vanishing fraction of the smaller individual rate.
Sources
- New Methods in Coding Theory: Error-Correcting Codes and the Shannon Capacity
- Counterexamples to the weak Hedetniemi Conjecture
- Probabilistic refinement of the asymptotic spectrum of graphs
- A counterexample to the quantum Hedetniemi conjecture
- A survey on Hedetniemi's conjecture
- The asymptotic spectrum of graphs and the Shannon capacity
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality