Bipartite Decomposition of Graphs

Tuesday, September 9, 2014 - 11:30am - 12:20pm
Keller 3-180
Noga Alon (Tel Aviv University)
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 (slightly) false, and suggesting an alternative one.
MSC Code: