The Minrank of Random Graphs
Alexander Golovnev, Oded Regev, Omri Weinstein · IEEE Transactions on Information Theory · 2018
The minrank of a directed graph G is the minimum rank of a matrix M that can be obtained from the adjacency matrix of G by switching some ones to zeros (i.e., deleting edges) and then setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of (linear) index coding (Bar-Yossef et al.), network coding (Effros et al.), and distributed storage (Mazumdar, ISIT, 2014). We prove tight bounds on the minrank of directed Erdos- Rényi random graphs G(n, p) for all regimes of p ∈ [0, 1]. In particular, for any constant p, we show that minrk(G) = Θ(n/log n) with high probability, where G is chosen from the previous best lower bound of Ω(√(n)) (Haviv and Langberg), G(n, p). This bound gives a near quadratic improvement over and partially settles an open problem raised by Lubetzky and Stav. Our lower bound matches the well-known upper bound obtained by the “clique covering" solution and settles the linear index coding problem for random knowledge graphs.