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.
Publisher Copyright:
© 2018 IEEE.
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
SN - 0018-9448
VL - 64
SP - 6990
EP - 6995
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 11
M1 - 8304633
ER -