Speaker: Abie Flaxman
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Expansion and lack thereof in perturbed random graphs
Abstract:
Whenever the CMU Theory Lunch has a talk about "real-world" random graphs, someone in the
audience asks if the graphs under consideration are expanders. This talk will address the
question directly with respect to perturbed random graphs, which are formed by starting with an
arbitrary base graph and adding a sparse random graph. The techniques used also reveal a
suprising fact about the small-world graphs studied by Jon Kleinberg [Proc. of 32nd ACM STOC
(2000), 163--170]: the expansion undergoes a phase transition exactly at the point where the
graph is efficiently navigable by a decentralized algorithm.