The Minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the (linear) Index Coding problem (Bar-Yossef et al., FOCS'06), network coding and distributed storage, and to Valiant's approach for proving superlinear circuit lower bounds. 

We prove sharp bounds on the Minrank of random Erdos-Renyi graphs $G(n,p)$ for all regimes of $pin[0,1]$. In particular, for any constant $p$, we show that $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, ISIT'12), and partially settles an open problem raised by Lubetzky and Stav (FOCS '07). 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. 

Joint work with Oded Regev and Sasha Golovnev.