The minrank of a graph G on the set of vertices [n] over a field F is the minimum possible rank of an n by n matrix M over F with nonzero diagonal entries such that M_i,j = 0 whenever ij is not an edge of G. We show that the minrank of the random graph G(n, p) over any field F is on the order of n log(1/p) / log(n) with high probability. For the field of real numbers, this 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. 

Joint work with Noga Alon, Lior Gishboliner, Adva Mond, and Frank Mousset.