### Abstract

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.

Original language | English (US) |
---|---|

Journal | Israel Journal of Mathematics |

DOIs | |

State | Accepted/In press - Jan 1 2019 |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Fingerprint Dive into the research topics of 'The minrank of random graphs over arbitrary fields'. Together they form a unique fingerprint.

## Cite this

*Israel Journal of Mathematics*. https://doi.org/10.1007/s11856-019-1945-8