An example showing that Schrijver's $ \vartheta $-function need not upper bound the Shannon capacity of a graph
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 Tanner 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.
Authors
- Igal Sason (ORCID: https://orcid.org/0000-0001-5681-1273)
Institutions
- Technion – Israel Institute of Technology (IL)
Publication Details
- Journal
- AIMS Mathematics
- Published
- 2025-01-01
- DOI
- https://doi.org/10.3934/math.2025685
- Citations
- 2
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 3.01