The Minrank of Random Graphs over Arbitrary Fields

The minrank of a graph $G$ on the set of vertices $[n]$ over a field $\mathbb{F}$ is the minimum possible rank of a matrix $M\in$\mathbb{F}$^{n\times n}$withnonzerodiagonalentriessuchthat$M_{i,j}=0$whenever$i$and$j$aredistinctnonadjacentverticesof$G$. This notion, over the real field, arises in the study of the Lov'asz theta function of a graph. We obtain tight bounds for the typical minrank of the binomial random graph $G(n,p)$ over any finite or infinite field, showing that for every field $$\mathbb{F}$=\mathbb F(n)$andevery$p=p(n)$satisfying$n^{-1} \leq p \leq 1-n^{-0.99}$, the minrank of $G=G(n,p)$ over $\mathbb{F}$ is $\Theta(\frac{n \log (1/p)}{\log n})$ with high probability. The result for the real field settles a problem raised by Knuth in 1994. The proof combines a recent argument of Golovnev, Regev, and Weinstein, who proved the above result for finite fields of size at most $n^{O(1)}$, with tools from linear algebra, including an estimate of R'onyai, Babai, and Ganapathy for the number of zero-patterns of a sequence of polynomials.