The ACO Seminar (2014–2015)

The biclique partition number bp(G) is the minimum number of complete bipartite graphs needed to partition the edges of a graph G. It is not hard to see that bp(G) ≤ n-α(G), where α(G) is the independence number. Erdős conjectured that for the random graph G=G(n, 0.5), bp(G)=n-α(G) with high probability. In this talk I will discuss some recent progress and and remaining challenges in this area, and show that actually there exists an absolute constant c>0 such that for G=G(n, 0.5), bp(G) ≤ n-(1+c)α(G) with high probability. Joint work with Noga Alon and Tom Bohman.