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

Date: Thursday 4th May, 3:00 in Fine Hall 224.
 
Speaker:  Maya Stein (University of Chile)

Title: Tree embeddings

There are several conjectures trying to relate the average/minimum/median 
degree of a graph with it having all trees of a certain size as subgraphs. 
One example is the Erdos-Sos conjecture, and another is the Loebl-Komlos-Sos
conjecture. We will give a short overview of what is known for these 
conjectures and then investigate a new conjecture in the same direction. 
The new conjecture (due to Havet, Wood, Reed and Stein) says that a 
minimum degree of 2k/3 together with a maximum degree of k should be 
enough for having all trees of size k as subgraphs. The results we present 
are joint work with Havet, Reed and Wood, and with Reed.  


Next week: summer

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