|国家预印本平台
首页|An example showing that Schrijver's $\vartheta$-function need not upper bound the Shannon capacity of a graph

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

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

来源:Arxiv_logoArxiv
英文摘要

This letter addresses an open question concerning a variant of the Lov\'{a}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\'{a}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.

Igal Sason

数学

Igal Sason.An example showing that Schrijver's $\vartheta$-function need not upper bound the Shannon capacity of a graph[EB/OL].(2025-05-12)[2025-06-30].https://arxiv.org/abs/2505.07778.点此复制

评论