Advances in the Shannon capacity of graphs

Nitay Lavi; Igal Sason; Nitay Lavi; Igal Sason

doi:10.3934/math.2026111

AIMS Mathematics

2026, Volume 11, Issue 1: 2747-2796. doi: 10.3934/math.2026111

Previous Article Next Article

Research article Special Issues

Advances in the Shannon capacity of graphs

Nitay Lavi ¹,
Igal Sason ^{1,2
,
,}

1.
The Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Haifa 3200003, Israel
2.
Faculty of Mathematics, Technion–Israel Institute of Technology, Haifa 3200003, Israel

Received: 29 September 2025 Revised: 09 January 2026 Accepted: 23 January 2026 Published: 28 January 2026
MSC : 05C35, 05C50, 05C69, 05C76, 94A15

We derive exact values and new bounds for the Shannon capacity of two families of graphs: the $ q $-Kneser graphs and the tadpole graphs. We also construct a countably infinite family of connected graphs whose Shannon capacity is not attained by the independence number of any finite strong power. Building on recent work of Schrijver, we establish sufficient conditions under which the Shannon capacity of a polynomial in graphs, formed via disjoint unions and strong products, equals the corresponding polynomial of the individual capacities, thereby reducing the evaluation of such capacities to that of their components. Finally, we prove an inequality relating the Shannon capacities of the strong product of graphs and their disjoint union, which yields alternative proofs of several known bounds as well as new tightness conditions. In addition to contributing to the computation of the Shannon capacity of graphs, this paper is intended to serve as an accessible entry point to those wishing to work in this area.
- Shannon capacity of graphs,
- zero-error information theory,
- strong graph product,
- graph polynomials,
- independence number,
- Kneser graphs,
- tadpole graphs
Citation: Nitay Lavi, Igal Sason. Advances in the Shannon capacity of graphs[J]. AIMS Mathematics, 2026, 11(1): 2747-2796. doi: 10.3934/math.2026111

Related Papers:

Abstract

We derive exact values and new bounds for the Shannon capacity of two families of graphs: the $ q $-Kneser graphs and the tadpole graphs. We also construct a countably infinite family of connected graphs whose Shannon capacity is not attained by the independence number of any finite strong power. Building on recent work of Schrijver, we establish sufficient conditions under which the Shannon capacity of a polynomial in graphs, formed via disjoint unions and strong products, equals the corresponding polynomial of the individual capacities, thereby reducing the evaluation of such capacities to that of their components. Finally, we prove an inequality relating the Shannon capacities of the strong product of graphs and their disjoint union, which yields alternative proofs of several known bounds as well as new tightness conditions. In addition to contributing to the computation of the Shannon capacity of graphs, this paper is intended to serve as an accessible entry point to those wishing to work in this area.

References

[1]	C. E. Shannon, The zero error capacity of a noisy channel, IEEE T. Inform. Theory, 2 (1956), 8–19. https://doi.org/10.1109/TIT.1956.1056798 doi: 10.1109/TIT.1956.1056798
[2]	N. Alon, Graph powers, In: Contemporary Combinatorics (B. Bollobás, Ed.), Bolyai Soc. Math. Stud., Springer, Budapest, Hungary, 10 (2002), 11–28. Available from: https://www.tau.ac.il/nogaa/PDFS/cap2.pdf.
[3]	N. Alon, Lovász, vectors, graphs and codes, In: Building Bridges Ⅱ—Mathematics of László Lovász (I. Bárány, G. O. H. Katona and A. Sali, Eds.), Bolyai Soc. Math. Stud., Springer, Budapest, Hungary, 28 (2019), 1–16. https://doi.org/10.1007/978-3-662-59204-5_1
[4]	M. Jurkiewicz, A survey on known values and bounds on the Shannon capacity, In: Selected Topics in Modern Mathematics - Edition 2014, eds. G. Gancarzewicz, M. Skrzyński, Publishing House AKAPIT, Kraków, Poland, 2014, 115–128. Available from: https://repozytorium.biblos.pk.edu.pl/resources/25729.
[5]	J. Körner, A. Orlitsky, Zero-error information theory, IEEE T. Inform. Theory, 44 (1998), 2207–2229. https://doi.org/10.1109/18.720537 doi: 10.1109/18.720537
[6]	I. Csiszár, J. Körner, Information theory, coding theorems for discrete memoryless systems, 2 Eds., Cambridge University Press, 2011.
[7]	N. Alon, The Shannon capacity of a union, Combinatorica, 18 (1998), 301–310. https://doi.org/10.1007/PL00009824 doi: 10.1007/PL00009824
[8]	N. Alon, E. Lubetzky, The Shannon capacity of a graph and the independence numbers of its powers, IEEE T. Inform. Theory, 52 (2006), 2172–2176. https://doi.org/10.1109/TIT.2006.872856 doi: 10.1109/TIT.2006.872856
[9]	H. Boche, C. Deppe, Computability of the zero-error capacity of noisy channels, Information, 16 (2025), 571. https://doi.org/10.1109/ITW48936.2021.9611383 doi: 10.1109/ITW48936.2021.9611383
[10]	F. Guo, Y. Watanabe, On graphs in which the Shannon capacity is unachievable by finite product, IEEE T. Inform. Theory, 36 (1990), 622–623. https://doi.org/10.1109/18.54907 doi: 10.1109/18.54907
[11]	L. Lovász, On the Shannon capacity of a graph, IEEE T. Inform. Theory, 25 (1979), 1–7. https://doi.org/10.1109/TIT.1979.1055985 doi: 10.1109/TIT.1979.1055985
[12]	L. Lovász, Graphs and geometry, American Mathematical Society, 65 (2019). https://doi.org/10.1090/coll/065
[13]	Y. Bi, A. Tang, On upper bounding Shannon capacity of graph through generalized conic programming, Optim. Lett., 13 (2019), 1313–1323. https://doi.org/10.1007/s11590-019-01436-7 doi: 10.1007/s11590-019-01436-7
[14]	B. Bukh, C. Cox, On a fractional version of Haemers' bound, IEEE T. Inform. Theory, 65 (2019), 3340–3348. https://doi.org/10.1109/TIT.2018.2889108 doi: 10.1109/TIT.2018.2889108
[15]	W. H. Haemers, On some problems of Lovász concerning the Shannon capacity of a graph, IEEE T. Inform. Theory, 25 (1979), 231–232. https://doi.org/10.1109/TIT.1979.1056027 doi: 10.1109/TIT.1979.1056027
[16]	S. Hu, I. Tamo, O. Shayevitz, A bound on the Shannon capacity via a linear programming variation, SIAM J. Discrete Math., 32 (2018), 2229–2241. https://doi.org/10.1137/17M115565X doi: 10.1137/17M115565X
[17]	D. E. Knuth, The sandwich theorem, Electron. J. Combin., 1 (1994), 1–48. https://doi.org/10.37236/1193
[18]	B. Csonka, G. Simonyi, Shannon capacity, Lovász $\vartheta$ number, and the Mycielski construction, IEEE T. Inform. Theory, 70 (2024), 7632–7646. https://doi.org/10.1109/TIT.2024.3394775 doi: 10.1109/TIT.2024.3394775
[19]	G. Simonyi, Shannon capacity and the categorical product, Electron. J. Combin., 28 (2021), 1–23. https://doi.org/10.37236/9113 doi: 10.37236/9113
[20]	D. de Boer, P. Buys, J. Zuiddam, The asymptotic spectrum distance, graph limits, and the Shannon capacity, preprint, 2024. https://doi.org/10.48550/arXiv.2404.16763
[21]	P. Buys, S. Polak, J. Zuiddam, A group-theoretic approach to Shannon capacity of graphs and a limit theorem from lattice packings, preprint, 2025. https://doi.org/10.48550/arXiv.2506.14654
[22]	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 doi: 10.1007/s00493-019-3992-5
[23]	A. Wigderson, J. Zuiddam, Asymptotic spectra: Theory, applications and extensions, preprint, 2025. Available from: https://staff.fnwi.uva.nl/j.zuiddam//papers/convexity.pdf.
[24]	V. Strassen, The asymptotic spectrum of tensors, J. Reine Angew. Math., 384 (1988), 102–152. https://doi.org/10.1515/crll.1988.384.102 doi: 10.1515/crll.1988.384.102
[25]	A. Abiad, C. Dalfó, M. A. Fiol, The Shannon capacity of graph powers, IEEE T. Inform. Theory, 72 (2026), 100–111. https://doi.org/10.1109/TIT.2025.3628011 doi: 10.1109/TIT.2025.3628011
[26]	S. C. Polak, A. Schrijver, New lower bound on the Shannon capacity of $\mathsf{C}_{{7}}$ from circular graphs, Inform. Process. Lett., 143 (2019), 37–40. https://doi.org/10.1016/j.ipl.2018.11.006 doi: 10.1016/j.ipl.2018.11.006
[27]	T. Bohman, A limit theorem for the Shannon capacities of odd cycles. Ⅱ, Proc. Amer. Math. Soc., 133 (2005), 537–543. Available from: https://www.jstor.org/stable/4097960.
[28]	A. Schrijver, On the Shannon capacity of sums and products of graphs, Indag. Math., 34 (2023), 37–41. https://doi.org/10.1016/j.indag.2022.08.009 doi: 10.1016/j.indag.2022.08.009
[29]	C. Godsil, K. Meagher, Erdős-Ko-Rado theorems, Cambridge University Press, 2016. https://doi.org/10.1017/CBO9781316414958
[30]	B. Lv, K. Wang, The eigenvalues of $q$-Kneser graphs, Discrete Math., 312 (2012), 1144–1147. https://doi.org/10.1016/j.disc.2011.11.042 doi: 10.1016/j.disc.2011.11.042
[31]	R. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, 2 Eds., 2011. https://doi.org/10.1201/b10959
[32]	R. S. Hales, Numerical invariants and the strong product of graphs, J. Combin. Theory Ser. B, 15 (1973), 146–155. https://doi.org/10.1016/0095-8956(73)90014-2 doi: 10.1016/0095-8956(73)90014-2
[33]	C. Godsil, G. Royle, Algebraic graph theory, Springer, 2001. https://doi.org/10.1007/978-1-4613-0163-9
[34]	L. Lovász, personal communication, January 2026.
[35]	I. Sason, An example showing that Schrijver's $\vartheta$-function need not upper bound the Shannon capacity of a graph, AIMS Math., 10 (2025), 15294–15301. https://doi.org/10.3934/math.2025685 doi: 10.3934/math.2025685
[36]	I. Sason, Observations on Lovász $\vartheta$-function, graph capacity, eigenvalues, and strong products, Entropy, 25 (2023), 104. https://doi.org/10.3390/e25010104 doi: 10.3390/e25010104
[37]	E. R. Scheinerman, D. H. Ullman, Fractional graph theory: A rational approach to the theory of graphs, Dover Publications, 2013. Available from: https://www.ams.jhu.edu/ers/wp-content/uploads/2015/12/fgt.pdf.
[38]	A. E. Brouwer, A. Schrijver, Uniform hypergraphs, in: A. Schrijer (ed.), Packing and Covering in Combinatorics, Mathematical Centre Tracts 106, Amsterdam, 1979, 39–73.
[39]	I. Sason, Observations on graph invariants with the Lovász $\vartheta$-function, AIMS Math., 9 (2024), 15385–15468. https://doi.org/10.3934/math.2024747 doi: 10.3934/math.2024747
[40]	The Sage Developers, SageMath, the Sage Mathematics Software System, Version 9.3, August 2021. Available from: https://www.sagemath.org/.
[41]	T. Bohman, R. Holzman, V. Natarajan, On the independence numbers of the cubes of odd cycles, Electron. J. Combin., 20 (2013), P10. https://doi.org/10.37236/2598 doi: 10.37236/2598
[42]	N. Charpenay, M. Le Treust, Zero-error coding with a generator set of variable-length words, In: Proceedings of the 2020 IEEE International Symposium on Inform. Theory, Los Angeles, CA, USA, 2020, 78–83. https://doi.org/10.1109/ISIT44484.2020.9174059
[43]	M. Aigner, G. M. Ziegler, Proofs from the book, 6 Eds., Springer, Berlin, Germany, 2018. https://doi.org/10.1007/978-3-662-57265-8
[44]	W. Dörfler, W. Imrich, Über das starke produkt von graphen, Monatsh. Math., 74 (1970), 97–102.
[45]	R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math., 70 (1971), 59–101. Available from: https://scispace.com/pdf/cardinal-multiplication-of-structures-with-a-reflexive-1bw5w0tzrt.pdf.
[46]	J. Feigenbaum, A. A. Schäffer, Finding the prime factors of strong direct product graphs in polynomial time, Discrete Math., 109 (1992), 77–102. https://doi.org/10.1016/0012-365X(92)90280-S doi: 10.1016/0012-365X(92)90280-S
[47]	N. Charpenay, M. Le Treust, A. Roumy, On the additivity of optimal rates for independent zero-error source and channel problems, IEEE T. Inform. Theory, 2025. https://doi.org/10.1109/TIT.2025.3639292
[48]	K. Marton, On the Shannon capacity of probabilistic graphs, J. Comb. Theory B, 57 (1993), 183–195. https://doi.org/10.1006/jctb.1993.1015 doi: 10.1006/jctb.1993.1015
[49]	C. Greene, D. J. Kleitman, Proof techniques in the theory of finite sets, in MAA Studies in Math. Assoc. of Amer., Washington, D.C., 1978. Available from: https://www.semanticscholar.org/paper/Proof-techniques-in-the-theory-of-finite-sets-Greene-Kleitman/d6d94511006c1f9a7e9212cbb05f636060cebd78.
[50]	S. Jukna, Extremal combinatorics with applications in computer science, 2 Eds., Springer, 2011. https://doi.org/10.1007/978-3-642-17364-6
[51]	L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Math., 13 (1975), 383–390. https://doi.org/10.1016/0012-365X(75)90058-8 doi: 10.1016/0012-365X(75)90058-8
[52]	T. J. J. Mussche, Extremal combinatorics in generalized Kneser graphs, Discrete Algebra and Geometry, Technische Universiteit Eindhoven, 2009. https://doi.org/10.6100/IR642440
[53]	A. Acín, R. Duanc, D. E. Roberson, A. B. Sainz, A. Winter, A new property of the Lovász number and duality relations between graph parameters, Discrete Appl. Math., 216 (2017), 489–501. https://doi.org/10.1016/j.dam.2016.04.028 doi: 10.1016/j.dam.2016.04.028
[54]	B. Bollobás, Random graphs, 2 Eds., Cambridge University Press, 2001. https://doi.org/10.1017/CBO9780511814068
[55]	F. Juhász, On the asymptotic behavior of the Lovász theta function for random graphs, Combinatorica, 2 (1982), 153–155. https://doi.org/10.1007/BF02579314 doi: 10.1007/BF02579314

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)