On Minrank and the Lovász Theta Function
Ishay Haviv · arXiv (Cornell University) · 2018
Two classical upper bounds on the Shannon capacity of graphs are the $\vartheta$-function due to Lovász and the minrank parameter due to Haemers. We provide several explicit constructions of $n$-vertex graphs with a constant $\vartheta$-function and minrank at least $n^δ$ for a constant $δ>0$ (over various prime order fields). This implies a limitation on the $\vartheta$-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.