On Minrank and the Lovász Theta Function
share
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.
READ FULL TEXT