Smoothed analysis on connected graphs

Seminar: 
Combinatorics Seminar
Event time: 
Friday, September 27, 2013 - 10:00am to 11:00am
Location: 
215 LOM
Speaker: 
Michael Krivelevich
Speaker affiliation: 
Tel Aviv
Event description: 

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 $\epsilon 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)$
(the last three items assuming the base graph $G$ has bounded degrees).
All of the above estimates are asymptotically tight.

Joint work with Daniel Reichman (Weizmann Institute) and
Wojciech Samotij (Tel Aviv/Cambridge).