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


Date: Thursday 22nd October, 3:00 in Fine Hall 224.
 
Speaker: Hao Huang (Emory)

Title: On graphs decomposable into induced matchings of linear size

A ``Ruzsa-Szemeredi graph'' is a graph on n vertices whose edge set can be
partitioned into induced matchings of size cn. The study of these graphs 
goes back more than 35 years and has connections with number theory, 
combinatorics, complexity theory and information theory. In this talk 
we will discuss the history and some recent developments in this
area. In particular, we show that when c>1/4, there can be only
constantly many matchings. On the other hand, for c=1/4, the maximum
number of induced matchings is logarithmic in n.

This is joint work with Jacob Fox and Benny Sudakov.

                       -----------

Next week: Jeff Kahn

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