This letter addresses an open question concerning a variant of the Lovász $ \vartheta $ function, which was introduced by Schrijver and independently by McEliece et al. (1978). The question of whether this variant provides an upper bound on the Shannon capacity of a graph was explicitly stated by Bi and Tang (2019). This letter presents an explicit example of a graph on 32 vertices, which shows that, in contrast to the Lovász $ \vartheta $ function, this variant does not necessarily upper bound the Shannon capacity of a graph. The example, previously outlined by the author in a recent paper (2024), is presented here in full detail, making it easy to follow and verify. By resolving this question, the note clarifies a subtle but significant distinction between these two closely related graph invariants.
Citation: Igal Sason. An example showing that Schrijver's $ \vartheta $-function need not upper bound the Shannon capacity of a graph[J]. AIMS Mathematics, 2025, 10(7): 15294-15301. doi: 10.3934/math.2025685
This letter addresses an open question concerning a variant of the Lovász $ \vartheta $ function, which was introduced by Schrijver and independently by McEliece et al. (1978). The question of whether this variant provides an upper bound on the Shannon capacity of a graph was explicitly stated by Bi and Tang (2019). This letter presents an explicit example of a graph on 32 vertices, which shows that, in contrast to the Lovász $ \vartheta $ function, this variant does not necessarily upper bound the Shannon capacity of a graph. The example, previously outlined by the author in a recent paper (2024), is presented here in full detail, making it easy to follow and verify. By resolving this question, the note clarifies a subtle but significant distinction between these two closely related graph invariants.
| [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., vol. 10, Springer, Budapest, Hungary, 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 II - Mathematics of László Lovász (I. Bárány, G. O. H. Katona and A. Sali, Eds.), Bolyai Soc. Math. Stud., vol. 28, Springer, Budapest, Hungary, 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] |
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
|
| [7] |
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
|
| [8] | R. J. McEliece, E. R. Rodemich, H. C. Rumsey, The Lovász bound and some generalizations, J. Combin. Inform. Syst. Sci., 3 (1978), 134–152. Available from: https://ipnpr.jpl.nasa.gov/progress_report2/42-45/45I.PDF. |
| [9] |
A. Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE T. Inform. Theory, 25 (1979), 425–429. https://doi.org/10.1109/TIT.1979.1056072 doi: 10.1109/TIT.1979.1056072
|
| [10] |
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
|
| [11] |
J. Zhou, Unified bounds for the independence number of graphs, Canad. J. Math., 77 (2025), 97–117, http://dx.doi.org/10.4153/S0008414X23000822 doi: 10.4153/S0008414X23000822
|
| [12] | The Sage Developers, SageMath, the Sage Mathematics Software System, version 9.3, August 2021. |
| [13] |
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
|
| [14] | M. Grant, S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, version 2.2, January 2020. Available from: http://cvxr.com/cvx. |
Igal Sason. An example showing that Schrijver's $ \vartheta $-function need not upper bound the Shannon capacity of a graph[J]. AIMS Mathematics, 2025, 10(7): 15294-15301. doi: 10.3934/math.2025685
DownLoad: