On Minrank and Forbidden Subgraphs

Abstract

The minrank over a field $\mathbb{F}$ of a graph $G$ on the vertex set $\{1,2,\dots ,n\}$ is the minimum possible rank of a matrix $M\in {\mathbb{F}}^{n\times n}$ such that $M_{i,i}\ne 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 $\mathbb{F}$, let $g(n,H,\mathbb{F})$ denote the maximum possible minrank over $\mathbb{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 $\mathbb{F}$. For finite fields, we prove by a probabilistic argument a general lower bound on $g(n,H,\mathbb{F})$, which yields a nearly tight bound of $\Omega (\sqrt{n}/\log 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,\mathbb{R})\ge n^{\delta }$ for some $\delta =\delta (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.

arXiv comment15 pages