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

Date: Thursday 24th March, 3:00 in Fine Hall 224.
 
Speaker: Alex Scott (Oxford)

Title: Maximising the number of induced cycles

How many holes can a graph on n vertices contain?  How many induced 
cycles? For sufficiently large n, we determine the maximum number of 
induced cycles, the maximum number of holes, and the maximum number of 
even or odd induced cycles, and in each case characterize the graphs 
achieving this bound. This answers a question of Tuza, and a conjecture of 
Chvatal and Tuza from 1988.  Joint work with Natasha Morrison.

                       -----------

Next week: Avi Wigderson

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