On a fractional version of Haemers' bound

2018/02/01 by Bukh, Boris, Cox, Christopher · 4 citations
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1802.00476

Abstract

In this note, we present a fractional version of Haemers' bound on the Shannon capacity of a graph, which is originally due to Blasiak. This bound is a common strengthening of both Haemers' bound and the fractional chromatic number of a graph. We show that this fractional version outperforms any bound on the Shannon capacity that could be attained through Haemers' bound. We show also that this bound is multiplicative, unlike Haemers' bound.

Cited by

• Universality of asymptotic graph homomorphism
• The Shannon capacity of graph powers
• Advances in the Shannon Capacity of Graphs
• A group-theoretic approach to Shannon capacity of graphs and a limit theorem from lattice packings

Related

• The Fractional Haemers Bound of the Mycielski Construction
• On a tracial version of Haemers bound
• A group-theoretic approach to Shannon capacity of graphs and a limit theorem from lattice packings
• Advances in the Shannon Capacity of Graphs
• On the Ratio of Shannon Numbers of Graphs