ACO The ACO Seminar (2014–2015)

Dec. 4, 3:30pm, Wean 8220
Hao Huang, Institute for Mathematics and its Applications, University of Minnesota
Biclique decomposition of random graphs


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.

Back to the ACO home page