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

Date: Thursday 25th September, 3:00 in Fine Hall 224.
 
Speaker: Chun-Hung Liu (Princeton)

Title: Excluding topological minors and well-quasi-ordering

Robertson and Seymour proved that graphs are well-quasi-ordered by the  
minor relation and the weak immersion relation. In other words, given  
infinitely many graphs, one graph contains another as a minor (or a  
weak immersion, respectively). Unlike the relation of minor and weak  
immersion, the topological minor relation does not well-quasi-order  
graphs in general. However, Robertson conjectured in the late 1980s  
that for every positive integer k, the topological minor relation  
well-quasi-orders graphs that do not contain a topological minor  
isomorphic to the path of length k with each edge duplicated. We will  
sketch the idea of our recent proof of this conjecture. In particular,  
we will give a structure theorem for excluding a fixed graph as a  
topological minor. Such structure theorems were previously obtained by  
Grohe and Marx and by Dvorak, but we push one of the bounds in their  
theorems to the optimal value. This improvement is needed for our  
proof of Robertson's conjecture. This work is joint with Robin Thomas.


                       -----------

Next week: Noga Alon

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