@article{Sason2025, 
author = {Igal Sason},
title = {An example showing that Schrijver's    ϑ-function need not upper bound the Shannon capacity of a graph},
year = {2025},
journal = {AIMS Mathematics},
volume = {10},
number = {7},
pages = {15294-15301},
keywords = {graph invariants, Lovász ϑ-function, Schrijver's ϑ-function, Shannon capacity of graphs, independence number, semidefinite programming},
url = {https://www.sciopen.com/article/10.3934/math.2025685},
doi = {10.3934/math.2025685},
abstract = {This letter addresses an open question concerning a variant of the Lovász    ϑ 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    ϑ 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.}
}