摘要：Two classical upper bounds on the Shannon capacity of graphs are the theta-function due to Lovász and the minrank parameter due to Haemers. We provide several explicit constructions of n-vertex graphs with a constant theta-function and minrank at least n^delta for a constant delta>0 (over various prime order fields). This implies a limitation on the theta-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.
