Sort:
Open Access Letter Issue
An example showing that Schrijver's ϑ-function need not upper bound the Shannon capacity of a graph
AIMS Mathematics 2025, 10(7): 15294-15301
Published: 15 July 2025
Abstract PDF (215.4 KB) Collect
Downloads:1

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.

Open Access Research Article Issue
On H -intersecting graph families and counting of homomorphisms
AIMS Mathematics 2025, 10(3): 6355-6378
Published: 15 March 2025
Abstract PDF (309.7 KB) Collect
Downloads:1

This work derives an upper bound on the maximum cardinality of a family of graphs on a fixed number of vertices, in which the intersection of every two graphs in that family contains a subgraph that is isomorphic to a specified graph H . Such families are referred to as H -intersecting graph families. The bound is derived using the combinatorial version of Shearer's lemma, and it forms a nontrivial extension of the bound derived by Chung, Graham, Frankl, and Shearer (1986), where H is specialized to a triangle. The derived bound is expressed in terms of the chromatic number of H , while a relaxed version, formulated using the Lovász ϑ-function of the complement of H , offers reduced computational complexity. Additionally, a probabilistic version of Shearer's lemma, combined with properties of Shannon entropy, are employed to establish bounds related to the enumeration of graph homomorphisms, providing further insights into the interplay between combinatorial structures and information-theoretic principles.

Total 2