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