Michael Krivelevich: Smoothed analysis on connected graphs

PRACTICALITIES
- Lunch is served at 12:00 noon (register  here   by Sunday at 8 pm).
- The presentation starts at 12:10 pm and ends at 1 pm.
- Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

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

DESCRIPTION OF FORMAT OF THE LUNCH SEMINAR + READING GROUP SERIES
The lunch seminar + reading group meetings are intended to run for 3 hours plus minus, during which time we will have the possibility to first get an overview of some interesting research results and then study them in some depth.

We start at noon with a light lunch, and at 12:10 pm there is a presentation which ends at 1 pm sharp. This should be an accessible talk,
not requiring any particular prerequisites. Then there is a short break. Up to this point the whole exercise should be pretty much
indistinguishable from a regular (lunch) seminar.

After the break, we return for ca two hours of more technical discussions. Now we open up the hood, look at the formal definitions, and prove at least some of the key ingredients in the results including all (or at least some of) the gory technical details glossed over in a polished seminar presentation. If the first part of the seminar was with slides, we now switch to the board, and there is usually a lot of interaction (making this into more of a discussion than a presentation at times).

However, for those who feel that the first one-hour regular seminar was enough for today, it is perfectly fine to just discretely drop out during
the break. No excuses needed; no questions asked.