Replacement and zig-zag products, Cayley graphs and lamplighter random walk. (English) Zbl 1300.05123
Summary: 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.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 20E22 | Extensions, wreath products, and other compositions of groups |
| 37A30 | Ergodic theorems, spectral theory, Markov operators |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 05C81 | Random walks on graphs |
