  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) \leq n - \alpha(G)$, where $\alpha(G)$ is the maximum size of an
independent set of $G$. Erd\H{o}s conjectured in the 80's that for almost every
graph $G$ equality holds; i.e., if $ G=G_{n,1/2}$ then $bp(G) = n - \alpha(G)$
with high probability. Alon showed that this is false. We show that the
conjecture of Erd\H{o}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/2$ then $bp(G_{n,p}) = n - (1 + \Theta(1)) \alpha(G_{n,p})$
with high probability.
