TY - JOUR

T1 - The Minrank of Random Graphs

AU - Golovnev, Alexander

AU - Regev, Oded

AU - Weinstein, Omri

N1 - Funding Information:
Manuscript received July 12, 2017; revised December 30, 2017; accepted February 20, 2018. Date of publication February 28, 2018; date of current version October 18, 2018. This paper was presented at the Proceedings of the 2017 21st International Workshop on Randomization and Computation. This work was supported in part by the Simons Collaboration on Algorithms and Geometry and in part by the National Science Foundation under Grant CCF-1320188. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. O. Weinstein was supported by a Simons Junior Fellowship.

PY - 2018/11

Y1 - 2018/11

N2 - 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 G(n,p). This bound gives a near quadratic improvement over the previous best lower bound of Ω (√n) (Haviv and Langberg), 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.

AB - 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 G(n,p). This bound gives a near quadratic improvement over the previous best lower bound of Ω (√n) (Haviv and Langberg), 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.

KW - Index coding

KW - linear index coding

KW - minrank

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

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

U2 - 10.1109/TIT.2018.2810384

DO - 10.1109/TIT.2018.2810384

M3 - Article

AN - SCOPUS:85042872000

VL - 64

SP - 6990

EP - 6995

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 11

M1 - 8304633

ER -