***********************************
                * 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)