Combinatorics Seminar

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

Abstract:

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^2 n).

(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).