Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

A graph $G = (V,E)$ is a $\beta$-expander iff for every $A \subseteq V$ with $|A| \leq |V|/2$ we have $A$ has at least $\beta |A|$ neighbors. An infinite family of graphs is an expander iff every graph of the family is a $\beta$-expander for some constant $\beta>0$, universal over the family.

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a {\em splicer}, the union of spanning trees of a graph. We prove that for any bounded-degree $n$-vertex graph, the union of two {\em random} spanning trees approximates the size of every cut of the graph to within a factor of $O(\log n)$. 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. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary; each spanning tree can be produced independently using an algorithm by Aldous and Broder: A random walk in the graph with edges leading to previously unvisited vertices included in the tree. Splicers also turn out to have applications to graph cut-sparsification where the goal is to approximate every cut using only a small subgraph of the original graph. For random graphs, splicers provide simple algorithms for sparsifiers of size $O(n)$ that approximate every cut to within a factor of $O(\log n)$.

This is joint work with Navin Goyal and Santosh Vempala.