Back to Search
Start Over
The Minrank of Random Graphs.
- Source :
- IEEE Transactions on Information Theory; Nov2018, Vol. 64 Issue 11, p6990-6995, 6p
- Publication Year :
- 2018
-
Abstract
- 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 Erdős–Rényi random graphs $G(n,p)$ for all regimes of $p\in [{0,1}]$. In particular, for any constant $p$ , we show that $\mathsf {minrk}(G) = \Theta (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 $\Omega (\sqrt {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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 64
- Issue :
- 11
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 132546130
- Full Text :
- https://doi.org/10.1109/TIT.2018.2810384