Expanders via Random Spanning Trees

Abstract

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of a small number of spanning trees of a graph. We prove that for any bounded-degree $n$-vertex graph, the union of two uniformly random spanning trees approximates the expansion of the graph to within a factor of $O(\log n)$. For the complete graph, we prove that the union of two uniformly random spanning trees is an expander with high probability. For the random graph $G_{n,p}$, for $p = \Omega(\log{n}/n)$, we give a randomized algorithm for constructing two spanning trees whose union is an expander. A closely related construction, which we call a selector, has similar properties. A random selector of a graph is obtained by starting with any spanning tree of the graph and adding a small number of random edges at each vertex.