CMU Campus
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 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(log2n)
(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).

Date: Thursday, October 3, 2013
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Boris Bukh