Combinatorics Seminar

When: Sunday, December 8, 10am
Where: Schreiber 309
Speaker: Daniel Reichman, Weizmann Institute of Science
Title: Smoothed Analysis on Connected Graphs


The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much nicer properties. In this talk we discuss smoothed analysis on trees, or equivalently on connected graphs. A connected graph G on n vertices can be a very bad expander, can have very large diameter, very high mixing time, and possibly has no long paths. The situation changes dramatically when \eps n random edges are added on top of G, the so obtained graph G* has with high probability the following properties:

(For some of the above results we also assume that the maximum degree of G is bounded.) All of the above estimates are asymptotically tight.

Joint work with Michael Krivelevich (Tel Aviv) and Wojciech Samotij (Tel Aviv/Cambridge).