On Minrank and Forbidden Subgraphs
share
The minrank over a field F of a graph G on the vertex set {1,2,...,n} is the minimum possible rank of a matrix M ∈F^n × n such that M_i,i≠ 0 for every i, and M_i,j=0 for every distinct non-adjacent vertices i and j in G. For an integer n, a graph H, and a field F, let g(n,H,F) denote the maximum possible minrank over F of an n-vertex graph whose complement contains no copy of H. In this paper we study this quantity for various graphs H and fields F. For finite fields, we prove by a probabilistic argument a general lower bound on g(n,H,F), which yields a nearly tight bound of Ω(√(n)/ n) for the triangle H=K_3. For the real field, we prove by an explicit construction that for every non-bipartite graph H, g(n,H,R) ≥ n^δ for some δ = δ(H)>0. As a by-product of this construction, we disprove a conjecture of Codenotti, Pudlák, and Resta. The results are motivated by questions in information theory, circuit complexity, and geometry.
READ FULL TEXT