The Minrank of Random Graphs

Alexander Golovnev, Oded Regev, Omri Weinstein

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish (US)
Article number8304633
Pages (from-to)6990-6995
Number of pages6
JournalIEEE Transactions on Information Theory
Volume64
Issue number11
DOIs
StatePublished - Nov 2018

Keywords

  • Index coding
  • linear index coding
  • minrank

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'The Minrank of Random Graphs'. Together they form a unique fingerprint.

Cite this