LAUSR

The minrank of a graph G on the set of vertices [ n ] over a field $$\mathbb{F}$$ F is the minimum possible rank of a matrix $$M \in \mathbb{F}^{{n}\times{n}}$$ 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 $$\mathbb{F}=\mathbb{F}(n)$$ F = F ( n ) and every p = p ( n ) satisfying n -1 ≤ p ≤ 1 - n -0.99 , the minrank of G = G ( n , p ) over $$\mathbb{F}$$ F is $$\Theta(\frac{n {\rm{log}}(1/p)}{{\rm{log}} n})$$ Θ ( n l o g ( 1 / p ) l o g 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ónyai, Babai and Ganapathy for the number of zero-patterns of a sequence of polynomials.