Expanders via Random Spanning Trees

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 Gn,p, for p = Ω(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