Expanders via Random Spanning Trees

Navin Goyal, Luis Rademacher, Santosh Vempala

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-de…