The minrank of random graphs over arbitrary fields

DOI10.1007/S11856-019-1945-8MaRDI QIDQ2303679zbMATH OpenOpenAlexWikidataFDO

Authors Noga Alon, Igor Balla, Lior Gishboliner, Adva Mond, Frank Mousset

Publication date 4 March 2020

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.01873

zbMATH Keywords

asymptotic behavior of the minrank of a binomial random graphorthogonal representations of graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Asymptotic enumeration (05A16) Polynomials in general fields (irreducibility, etc.) (12E05)

Abstract: The minrank of a graph $G$ on the set of vertices $[n]$ over a field $mathbbF$ is the minimum possible rank of a matrix $Minmathbb{F}^{nimesn}$ 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'asz 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 $mathbbF=mathbbF(n)$ and every $p=p(n)$ satisfying $n^{-1}leqpleq1-n^{-0.99}$, the minrank of $G=G(n,p)$ over $mathbbF$ is $Theta(fracnlog(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'onyai, Babai, and Ganapathy for the number of zero-patterns of a sequence of polynomials.

Recommendations

• On minrank and forbidden subgraphs
• On minrank and forbidden subgraphs
• The minrank of random graphs
• On the minimum rank of a graph over finite fields
• On minrank and the Lovász theta-function

Cites work

• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Almost all matroids are nonrepresentable
• Index Coding With Side Information
• Lovász, vectors, graphs and codes
• Nonlinear Index Coding Outperforming the Linear Optimum
• On minrank and forbidden subgraphs
• On the Shannon capacity of a graph
• On the number of zero-patterns of a sequence of polynomials
• The Shannon capacity of a union
• The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
• The chromatic number of random graphs
• The minrank of random graphs
• The sandwich theorem
• Two notions of unit distance graphs
• \(\mathbb F_p\) is locally like \(\mathbb C\)

Cited in

(13)

• The (minimum) rank of typical fooling-set matrices
• On the rank of a random binary matrix
• On minrank and forbidden subgraphs
• On minrank and forbidden subgraphs
• On the rank of a random binary matrix
• Perfect and nearly perfect separation dimension of complete and random graphs
• On the minimum rank of a graph over finite fields
• Nonvanishing minors of eigenvector matrices and consequences
• The Minrank of Random Graphs
• On minrank and the Lovász theta-function
• The minrank of random graphs
• Minimal functions on the random graph
• Expected values of parameters associated with the minimum rank of a graph

This page was built for publication: The minrank of random graphs over arbitrary fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2303679)