***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 2nd October, 3:00 in Fine Hall 224.
 
Speaker: Noga Alon, Tel Aviv University and IAS, Princeton

Ttile: Bipartite decomposition of graphs

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 false, and suggesting a modified version.

Partly based on joint work with Tom Bohman and Hao Huang.

                       -----------

Next week: Omri Ben Eliezer 

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)