๐ฎ
๐ฎ
The Ethereal
An example showing that Schrijver's $\vartheta$-function need not upper bound the Shannon capacity of a graph
May 12, 2025 ยท The Ethereal ยท ๐ AIMS Mathematics
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Igal Sason
arXiv ID
2505.07778
Category
math.CO: Combinatorics
Cross-listed
cs.IT
Citations
2
Venue
AIMS Mathematics
Last Checked
3 months ago
Abstract
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.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal