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
Joint work with Michael Krivelevich (Tel Aviv) and Wojciech
Samotij (Tel Aviv/Cambridge).
- 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).