For a graph G, let bc(G) denote the minimum possible number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to (exactly) one of them. The study of this quantity and its variants received a considerable amount of attention and is related to problems in communication complexity and geometry. After a brief discussion of the background and earlier results on the subject I will focus on the problem of determining the typical value of bc(G) for the binomial random graph G=G(n,p), showing that a conjecture of Erdos about it is false, and suggesting a modified version.

This is partly based on joint work with Tom Bohman and Hao Huang.