Georgia Institute of Technology College of Sciences

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: - its edge expansion is at least c/log n; - its diameter is O(log n); - its vertex expansion is at least c/log n; - it has a linearly long path; - its mixing time is O(log^2n) All of the above estimates are asymptotically tight. Joint work with Michael Krivelevich (Tel Aviv) and Wojciech Samotij (Tel Aviv/Cambridge).