Expansion and lack thereof in randomly perturbed graphs

This paper studies the expansion properties of randomly perturbed graphs. These graphs are formed by, for example, adding a random 1-out or very sparse Erdos-Renyi to an arbitrary connected graph. It is shown that when any connected n-vertex base graph is perturbed by adding a random 1-out then, with high probability, the resulting graph has expansion properties. The analogous statement for perturbations by a sparse Erdos-Renyi graph is also considered, and under this perturbation, the expansion of the perturbed graph depends on the structure of the base graph. A necessary condition for the base graph is given in order for the resulting graph to be an expander with high probability. These techniques are also applied to study expansion and rapid mixing in the small worlds graphs described by Watts and Strogatz in [Nature 292 (1998), 440–442] and by Kleinberg in [Proc. of 32nd ACM Symposium on Theory of Computing (2000), 163–170]. Analysis of Kleinberg’s model shows that the graph stops being an expander exactly at the point where a decentralized algorithm is effective in constructing a short path. The proofs of expansion rely on a way of summing over subsets of vertices which allows an argument based on the First Moment Method to succeed.