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


Date: Thursday 23rd February, 3:00 in Fine Hall 224.
 
Speaker: Misha Lavrov (CMU)

Title: Distance-uniform graphs with large diameter

We say that a graph is epsilon-distance-uniform if there is a value d
(called the critical distance) such that, for every vertex v, all but an
epsilon fraction of the other vertices are at distance exactly d from v.
Random graphs are distance-uniform with logarithmic critical distance,
and it was conjectured by Alon, Demaine, Hajiaghayi, and Leighton that 
the critical distance (equivalently, the diameter) of a distance-uniform
graph must always be logarithmic.  In this talk, we use a generalization 
of the Towers of Hanoi puzzle to construct distance-uniform graphs with 
a much larger diameter: for constant epsilon, as large as n^O(1/log log n). 
We show that this construction is more or less worst possible for 
sufficiently small epsilon, leaving open the possibility that for large 
epsilon, much worse cases exist. This is joint work with Po-Shen Loh.


                       -----------

Next week:  Shira Zerbib

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