Oct. 3, 3:30pm, Wean 8220

Michael Krivelevich, Tel Aviv University

Smoothed analysis on connected graphs

Michael Krivelevich, Tel Aviv University

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.
*G* has bounded degrees). All of the above estimates are asymptotically tight.

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 ε*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*)

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