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


Date: Thursday 13th November, 3:00 in Fine Hall 224.
 
Speaker: Alex Scott (University of Oxford)

Title: Saturation in the hypercube

A subgraph of the d-dimensional cube Qd is (Qd,Qm)-saturated if it does not 
contain a copy of Qm, but adding any missing edge creates a copy of Qm.  The 
subgraph is weakly (Qd,Qm)-saturated if we can add the missing edges one at a 
time, creating a new copy of Qm at each step.

Answering a question of Johnson and Pinto, we show that for every fixed m, the 
minimum number of edges in a (Qd,Qm)-saturated graph is \Theta(2^d).
We also determine exactly the minimum number of edges in a weakly 
(Qd,Qm)-saturated subgraph of Qd, and raise some further questions.

Joint work with Natasha Morrison and Jonathan Noel.


                       -----------

Next week:  No seminar

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