The zig-zag product and its expander families

Speaker: Andrew Brown , ALGO+LMA


The zig-zag is a graph product enabling the recursive construction of explicit expander families. These graphs are remarkable in that the proof of expansion relies on combinatorial rather than algebraic arguments, and is considerably simpler than that of other known constructions.

We will first present the zig-zag product, its expansion properties and the constructions it yields. We will then explore the link with the semi-direct product of groups, which was used to show that expansion of Cayley graphs is not a group property (i.e. it depends on the choice of generators).