A Critical Probability for Biclique Partition of $G_{n,p}$

The biclique partition number of a graph $G=(V,E)$, denoted $bp(G)$, is the minimum number of pairwise edge disjoint complete bipartite subgraphs of $G$ so that each edge of $G$ belongs to exactly one of them. It is easy to see that $bp(G)\le n-\alpha (G)$, where $\alpha (G)$ is the maximum size of an independent set of $G$. Erdős conjectured in the 80’s that for almost every graph $G$ equality holds; i.e., if $G=G_{n,1\mathrm{/}2}$ then $bp(G)=n-\alpha (G)$ with high probability. Alon showed that this is false. We show that the conjecture of Erdős is true if we instead take $G=G_{n,p}$, where $p$ is constant and less than a certain threshold value $p_0\approx 0.312$. This verifies a conjecture of Chung and Peng for these values of $p$. We also show that if $p_0<p<1\mathrm{/}2$ then $bp(G_{n,p})=n-(1+\mathrm{\Theta }(1))\alpha (G_{n,p})$ with high probability.