On Minrank and the Lovász Theta Function

2018/02/12 by Haviv, Ishay · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1802.03920

Abstract

Two classical upper bounds on the Shannon capacity of graphs are the ϑ-function due to Lovász and the minrank parameter due to Haemers. We provide several explicit constructions of n-vertex graphs with a constant ϑ-function and minrank at least n^δ for a constant δ>0 (over various prime order fields). This implies a limitation on the ϑ-function-based algorithmic approach to approximating the minrank parameter of graphs. The proofs involve linear spaces of multivariate polynomials and the method of higher incidence matrices.

Cited by

• Kernelization for H-Coloring

Related

• The Minrank of Random Graphs over Arbitrary Fields
• An example showing that Schrijver's ϑ-function need not upper bound the Shannon capacity of a graph
• On Minrank and Forbidden Subgraphs
• The Shannon capacity of graph powers
• Shannon capacity, Lovász theta number and the Mycielski construction