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


Date: Thursday 18th September, 3:00 in Fine Hall 224.
 
Speaker: Doron Puder, IAS

Title: Expansion of Random Graphs - New Proofs, New Results

We present a new approach to showing that random graphs are nearly optimal 
expanders. This approach is based on deep results from combinatorial group 
theory. It applies to both regular and irregular random graphs. 

Let G be a random d-regular graph on n vertices. It was conjectured by Alon
(86) and proved by Friedman (08) in a ~100 page-long booklet that the 
highest non-trivial eigenvalue of G is a.a.s. arbitrarily close to 2\sqrt(d-1).
We give a new, substantially simpler proof, that nearly recovers Friedman’s 
result. This approach also has the advantage of applying to a more general 
model of random graphs, concerning also non-regular graphs. Friedman (2003) 
extended Alon’s conjecture to this general case, and we obtain new, nearly 
optimal results here too.

                       -----------

Next week: Chun-Hung Liu

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