The minrank over a field $\mathbb{ F}$ of a graph $G$ on the vertex set $\{ 1,2,\ldots,n\}$ is the minimum possible rank of a matrix $M \in \mathbb{ F}^{ n \times n}$ such that $M_{ i,i} \neq 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}) \geq n^\delta$ for some $\delta = \delta(H)>0$. As a by-product of this construction, we disprove a conjecture of Codenotti, Pudl\'ak, and Resta. The results are motivated by questions in information theory, circuit complexity, and geometry.
Categories: cs.DS cs.IT math.CO math.IT