Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Michael Krivelevich Tel Aviv University 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 - 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*)
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). |