Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
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.
Related
- Hedetniemi's Conjecture for Uncountable Complementary Graphs
- A counterexample to the quantum Hedetniemi conjecture
- Counterexamples to the Monotone Completeness Conjecture
- Counterexamples to the ordinary Fried conjecture near hyperbolic metrics
- Counterexamples to the inhomogeneous Duffin-Schaeffer Conjecture
BibTeX
@misc{zeiss2026hedetniemis,
title = {{Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation}},
author = {Julius A. Zeiss},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41977},
eprint = {2610.41977},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41977},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
AU - Julius A. Zeiss
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41977
UR - https://arxiv.org/abs/2610.41977
AB - 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.
ER -