An example showing that Schrijver's $\vartheta$-function need not upper bound the Shannon capacity of a graph
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918079898845184 |
|---|---|
| author | Sason, Igal |
| author_facet | Sason, Igal |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07778 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An example showing that Schrijver's $\vartheta$-function need not upper bound the Shannon capacity of a graph Sason, Igal Combinatorics Information Theory 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. |
| title | An example showing that Schrijver's $\vartheta$-function need not upper bound the Shannon capacity of a graph |
| topic | Combinatorics Information Theory |
| url | https://arxiv.org/abs/2505.07778 |