***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Michael Krivelevich (Tel Aviv)
Thursday 21st February, 3:00 in Fine Hall 224.
Title: Complete minors in graphs without sparse cuts.
We show that if G is a graph on n vertices with all degrees comparable
to d and without sparse cuts, in an appropriately defined quantitative
sense, then G contains a complete minor of order \sqrt{nd/log d}.
As a corollary we determine the order of a largest complete minor one
can guarantee in d-regular graphs with large eigenvalue gap, in random
d-regular graphs, and in jumbled graphs.
Joint work with Rajko Nenadov.
----------------------------------
Next week: Omri Ben-Eliezer
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)