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

نویسندگان
doi
10.22108/ijgt.2013.1932
چکیده

‎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‎.

کلیدواژه‌ها
Alfredo Donno, Replacement and zig-zag product, Expander graph, Lamplighter random walk, Cayley graph, Semidirect and wreath product