Metraipolis › archive › dc_acfc0ca49977

Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation — arXiv:2610.41977

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.41977
License (as archived): CC0-1.0
Archived: 2026-11-03T08:18:42.856Z
SHA-256 of the archived text: 2822a60d6ddbadbb2b4f48dd3890546524ec03e4dad7a9ae2c101e1294df467e
Stable URL of this page: https://metraipolis.com/documento/dc_acfc0ca49977

How to cite

Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation — arXiv:2610.41977 — arXiv (en), https://arxiv.org/abs/2610.41977 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_acfc0ca49977 (Metraipolis archive dc_acfc0ca49977, sha256 2822a60d6ddbadbb2b4f48dd3890546524ec03e4dad7a9ae2c101e1294df467e)

BibTeX

@misc{dcacfc0ca49977,
  title = {Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation — arXiv:2610.41977},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41977},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_acfc0ca49977; sha256 2822a60d6ddbadbb2b4f48dd3890546524ec03e4dad7a9ae2c101e1294df467e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41977. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.41977 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T08:05:23.790Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).