Replacement and zig-zag products, Cayley graphs and Lamplighter random walk

Abstract

We investigate two constructions - the replacement and the zig-zag product of graphs - describing several fascinating connections with Combinatorics, via the notion of expander graph, Group Theory, via the notion of semidirect product and Cayley graph, andwith Markov chains, via the Lamplighter random walk. Many examples are provided.

Keywords

• Replacement and zig-zag product
• Expander graph
• Lamplighter random walk
• Cayley graph
• Semidirect and wreath product