The minrank of random graphs over arbitrary fields

Autor: Noga Alon, Frank Mousset, Adva Mond, Lior Gishboliner, Igor Balla
Rok vydání: 2019
Předmět:
Zdroj: Israel Journal of Mathematics. 235:63-77
ISSN: 1565-8511
0021-2172
Popis: 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}}$$ with nonzero diagonal entries such that Mi,j = 0 whenever i and j are distinct nonadjacent vertices of G. This notion, over the real field, arises in the study of the Lovasz 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)$$ and every p = p(n) satisfying n-1 ≤ p ≤ 1 - n-0.99, the minrank of G = G(n, p) over $$\mathbb{F}$$ is $$\Theta(\frac{n {\rm{log}}(1/p)}{{\rm{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 nO(1), with tools from linear algebra, including an estimate of Ronyai, Babai and Ganapathy for the number of zero-patterns of a sequence of polynomials.
Databáze: OpenAIRE
Externí odkaz: