Dec. 4, 3:30pm, Wean 8220

Hao Huang, Institute for Mathematics and its Applications, University of Minnesota

Biclique decomposition of random graphs

Hao Huang, Institute for Mathematics and its Applications, University of Minnesota

Biclique decomposition of random graphs

Abstract:

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.