HEXAGONbeta

A finite-delay code for lexicographic graph products

Primarily AI-generated textHuman understanding: some partsmath.IT — Information Theorymath.CO — Combinatorics

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Oct 15, 2026 / CC BY 4.0

Abstract

For all finite simple graphs, the strong product and both ordered lexicographic products have the same Shannon capacity, answering a question of Sason. An explicit code conversion delays one component by a single block, with rate loss tending to zero. The equality extends to arbitrary mixtures of the two products and survives adjoining an additional strong-product factor.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.

Tools used

Bolzano team
Bolzano

References

  1. C. E. Shannon, The zero error capacity of a noisy channel , IRE Transactions on Information Theory 2 (1956), no. 3, 8--19. https://doi.org/10.1109/TIT.1956.1056798.DOI
  2. L. Lovász, On the Shannon capacity of a graph , IEEE Transactions on Information Theory 25 (1979), no. 1, 1--7. https://doi.org/10.1109/TIT.1979.1055985.DOI
  3. I. Sason, Shannon capacity and related graph invariants for lexicographic products , Entropy 28 (2026), no. 9, article 994. https://doi.org/10.3390/e28090994. All item numbers cited here refer to this journal version. The corresponding open question and candidate-family inequality in arXiv:2608.06573v5 are equations (155) and (170), respectively. https://arxiv.org/abs/2608.06573v5.arXivDOI
  4. J. Körner and A. Orlitsky, Zero-error information theory , IEEE Transactions on Information Theory 44 (1998), no. 6, 2207--2229. https://doi.org/10.1109/18.720537.DOI
  5. W. Haemers, On some problems of Lovász concerning the Shannon capacity of a graph , IEEE Transactions on Information Theory 25 (1979), no. 2, 231--232. https://doi.org/10.1109/TIT.1979.1056027.DOI
  6. N. Alon, The Shannon capacity of a union , Combinatorica 18 (1998), 301--310. https://doi.org/10.1007/PL00009824.DOI
  7. D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product , Journal of Combinatorial Theory, Series B 19 (1975), 87--95. https://doi.org/10.1016/0095-8956(75)90076-3.DOI
  8. N. Alon and E. Lubetzky, The Shannon capacity of a graph and the independence numbers of its powers , IEEE Transactions on Information Theory 52 (2006), no. 5, 2172--2176. https://doi.org/10.1109/TIT.2006.872856; https://arxiv.org/abs/cs/0608021.DOI
  9. J. Zuiddam, The asymptotic spectrum of graphs and the Shannon capacity , Combinatorica 39 (2019), 1173--1184. https://doi.org/10.1007/s00493-019-3992-5; https://arxiv.org/abs/1807.00169v2.DOI
  10. P. Vrana, Probabilistic refinement of the asymptotic spectrum of graphs , Combinatorica 41 (2021), 873--904. https://doi.org/10.1007/s00493-020-4324-5; https://arxiv.org/abs/1903.01857.DOI
Show all 12 referencesShow fewer references
  1. T. Fritz, A unified construction of semiring-homomorphic graph invariants , Journal of Algebraic Combinatorics 54 (2021), 693--718. https://doi.org/10.1007/s10801-020-00983-y; https://arxiv.org/abs/1901.01090v3.DOI
  2. A. Schrijver, On the Shannon capacity of sums and products of graphs , Indagationes Mathematicae 34 (2023), 37--41. https://doi.org/10.1016/j.indag.2022.08.009; https://arxiv.org/abs/2204.06853.DOI

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentOct 15, 2026