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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

An example showing that Schrijver's $ \vartheta $-function need not upper bound the Shannon capacity of a graph

Igal Sason
2 citations
AIMS Mathematics
Computability, Logic, AI Algorithms
3.01
article

An example showing that Schrijver's $ \vartheta $-function need not upper bound the Shannon capacity of a graph

Igal Sason
article en
2 citations

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.

AIMS MathematicsVol. 10(7)
Technion – Israel Institute of Technology (IL)
Reduced inequalities
Openalex Percentile: Top 8%
Computability, Logic, AI Algorithms
3.01
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

An example showing that Schrijver's $ \vartheta $-function need not upper bound the Shannon capacity of a graph — Igal Sason · AIMS Mathematics (2025) | TGRS Research Map | TGRS