On Minrank and the Lov\'asz Theta Function.

Two classical upper bounds on the Shannon capacity of graphs are the$\vartheta$-function due to Lov\'asz 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^\delta$ for a constant $\delta>0$(over various prime order fields). This implies a limitation on the$\vartheta$-function-based algorithmic approach to approximating the minrankparameter of graphs. The proofs involve linear spaces of multivariatepolynomials and the method of higher incidence matrices.