AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (215.4 KB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Letter | Open Access

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

The Viterbi Faculty of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa 3200003, Israel
The Department of Mathematics, Technion – Israel Institute of Technology, Haifa 3200003, Israel
Show Author Information

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.

CLC number: 05C30, 05C60, 05C80, 94A15

References

【1】
【1】
 
 
AIMS Mathematics
Pages 15294-15301

{{item.num}}

Comments on this article

Go to comment

< Back to all reports

Review Status: {{reviewData.commendedNum}} Commended , {{reviewData.revisionRequiredNum}} Revision Required , {{reviewData.notCommendedNum}} Not Commended Under Peer Review

Review Comment

Close
Close
Cite this article:
Sason I. An example showing that Schrijver's ϑ-function need not upper bound the Shannon capacity of a graph. AIMS Mathematics, 2025, 10(7): 15294-15301. https://doi.org/10.3934/math.2025685

95

Views

1

Downloads

2

Crossref

2

Web of Science

2

Scopus

Received: 11 May 2025
Revised: 24 June 2025
Accepted: 27 June 2025
Published: 15 July 2025
©2025 the Author(s), licensee AIMS Press.

This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0)