Brendan Murphy

Navigating Cayley Graphs

An important problem in combinatorics and theoretical computer science is constructing explicit families of expanding graphs. Most constructions use Cayley graphs, which are defined by a group and a choice of generators. Selberg's theorem on spectral gaps gives two examples of generating sets in $SL_2(\mathbb{Z})$ that produce expander families. Recently, Bourgain and Gamburd gave necessary and sufficient conditions for this construction to produce expanders.

Any two points in a (finite) expander graph are connected by a short path. The Navigation Problem asks for a fast algorithm for finding this path. For expander families constructed from $SL_2(\mathbb{Z})$, the navigation problem has been solved only for the two examples given by Selberg's theorem. We will explain the simplest example where short paths are known to exist, but we do not know how to find them.

This talk will be self-contained, so no background in combinatorics is necessary.