TY - JOUR

T1 - The minrank of random graphs over arbitrary fields

AU - Alon, Noga

AU - Balla, Igor

AU - Gishboliner, Lior

AU - Mond, Adva

AU - Mousset, Frank

N1 - Funding Information:
We thank Peter Nelson for telling us about his paper [16]. The research on this project was initiated during a joint research workshop of Tel Aviv University and the Free University of Berlin on Graph and Hypergraph Coloring Problems, held in Berlin in August 2018, and supported by a GIF grant number G-1347-304.6/2016. We would like to thank the German–Israeli Foundation (GIF) and both institutions for their support.
Funding Information:
The minrank of a graph G on the set of vertices [ n ] over a field F \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb{F}$$\end{document} is the minimum possible rank of a matrix M ∈ F n × n \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M \in \mathbb{F}^{{n}\times{n}}$$\end{document} 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 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb{F}=\mathbb{F}(n)$$\end{document} and every p = p ( n ) satisfying n -1 ≤ p ≤ 1 - n -0.99 , the minrank of G = G ( n , p ) over F \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb{F}$$\end{document} is Θ ( n l o g ( 1 / p ) l o g n ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Theta(\frac{n {\rm{log}}(1/p)}{{\rm{log}} n})$$\end{document} 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. publisher-imprint-name Hebrew University Magnes Press article-contains-esm No article-numbering-style Unnumbered article-registration-date-year 2019 article-registration-date-month 10 article-registration-date-day 30 article-toc-levels 0 journal-product ArchiveJournal numbering-style Unnumbered article-grants-type Regular metadata-grant OpenAccess abstract-grant OpenAccess bodypdf-grant Restricted bodyhtml-grant Restricted bibliography-grant Restricted esm-grant OpenAccess online-first true pdf-file-reference BodyRef/PDF/11856_2019_Article_1945.pdf target-type OnlinePDF article-type OriginalPaper journal-subject-primary Mathematics journal-subject-secondary Mathematics, general journal-subject-secondary Algebra journal-subject-secondary Group Theory and Generalizations journal-subject-secondary Analysis journal-subject-secondary Applications of Mathematics journal-subject-secondary Theoretical, Mathematical and Computational Physics journal-subject-collection Mathematics and Statistics open-access false Research supported in part by ISF grant No. 281/17, GIF grant No. G-1347-304.6/2016 and the Simons Foundation. Research supported by ERC Starting Grant 633509. Research supported by ISF grants 1028/16 and 1147/14, and ERC Starting Grant 633509.
Publisher Copyright:
© 2019, The Hebrew University of Jerusalem.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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∈ Fn × 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 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 nO(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.

AB - 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∈ Fn × 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 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 nO(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.

UR - http://www.scopus.com/inward/record.url?scp=85074861643&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85074861643&partnerID=8YFLogxK

U2 - 10.1007/s11856-019-1945-8

DO - 10.1007/s11856-019-1945-8

M3 - Article

AN - SCOPUS:85074861643

VL - 235

SP - 63

EP - 77

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

SN - 0021-2172

IS - 1

ER -