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‎, ‎and‎ ‎with Markov chains‎, ‎via the Lamplighter random walk‎. ‎Many examples‎ ‎are provided‎.