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.