The minrank of random graphs over arbitrary fields

The minrank of a graph G on the set of vertices [n] over a field F is the minimum possible rank of a matrix M∈ F^{n × n} with nonzero diagonal entries such that M_i,j = 0 whenever i and j are distinct nonadjacent vertices of G. This notion, over the real field, arises in the study of the Lovász 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 F=F(n) and every p = p(n) satisfying n^-1 ≤ p ≤ 1 - n^-0.99, the minrank of G = G(n, p) over F is Θ(nlog(1/p)logn) 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ónyai, Babai and Ganapathy for the number of zero-patterns of a sequence of polynomials.