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

Document Type : Ischia Group Theory 2012


Università di Roma "La Sapienza"


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


Main Subjects

A. Abdollahi and A. Loghman On one-factorizations of replacement products. to appear in {\em Filomat}, Published by Faculty of Sciences and Mathematics, University of Ni\v{s}, Serbia, available at \href{}{}. N. Alon (1986). Eigenvalues and expanders. Combinatorica. 6 (2), 83-96 N. Alon, A. Lubotzky and A. Wigderson (2001). Semi-direct product in groups and zig-zag product in graphs. connections and applications (extended abstract), in: {\em \lq\lq $42$-nd IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, 2001\rq\rq}, {\em IEEE Computer Soc.}, Los Alamitos, CA. , 630-637 N. Alon and V. D. Milman (1985). $\lambda_1$, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B. 38 (1), 73-88 T. Austin, A. Naor and A. Valette (2010). The Euclidean Distortion of the Lamplighter Group. Discrete Comput. Geom.. 44 (1), 55-74 L. Bartholdi and W. Woess (2005). Spectral computations on lamplighter groups and Diestel-Leader graphs. 11 (2), 175-202 T. Ceccherini-Silberstein, F. Scarabotti and F. Tolli (2008). Harmonic Analysis on Finite Groups. Representation theory. Gelfand pairs and Markov chains, {em Cambridge Studies in Advanced Mathematics}, Cambridge University Press, Cambridge, xiv + 440 pp.. 180 J. J. Cummings and C. A. Kelley On the Independence and Domination Numbers of Replacement Product Graphs. submitted, available at href{$sim$jjcummings/RP$_{-}$Submission$_{-}$Final.pdf} {$sim$jjcummings/RP$_{-}$Submission$_{-}$Final.pdf}. D. D'Angeli and A. Donno (2009). Crested products of Markov chains. Ann. Appl. Probab.. 19 (1), 414-453 D. D'Angeli and A. Donno (2010). Markov chains on orthogonal block structures. European J. Combin.. 31 (1), 34-46 D. D'Angeli and A. Donno (2011). Generalized crested products of Markov chains. European J. Combin.. 32 (2), 243-257 G. Davidoff, P. Sarnak and A. Valette (2003). Elementary number theory, group theory, and Ramanujan graphs. London Mathematical Society Student Texts, Cambridge University Press, Cambridge, x + 144 pp.. 55 E. Dobson and J. Morris (2009). Automorphism Groups of Wreath Product Digraphs. Electron. J. Combin., RP 17.. 16 (1) J. Dodziuk (1984). Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc.. 284 (2), 787-794 A. Donno Generalized wreath products of graphs and groups. submitted. A. Erschler (2006). Generalized wreath products. IMRN Int. Math. Res. Notices, Article ID 57835. , 1-14 R. I. Grigorchuk and A. .{Z}uk (2001). The lamplighter group as a group generated by a $2$-state automaton, and its spectrum. Geom. Dedicata. 87 (1-3), 209-244 M. Gromov (1983). Filling Riemannian manifolds. J. Differential Geom.. 18 (1), 1-147 R. Hammack, W. Imrich and S. Klav\v{z}ar (2011). Handbook of product graphs. Second edition. Discrete Mathematics and its Applications (Boca Raton)}. CRC Press, Boca Raton, FL, xviii + 518 pp.. F. Harary (1959). On the group of the composition of two graphs. Duke Math. J.. 26, 29-34 S. Hoory, N. Linial and A. Wigderson (2006). Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.). 43 (4), 439-561 W. Imrich and H. Izbicki (1975). Associative Products of Graphs. Monatsh. Math.. 80 (4), 277-281 C. A. Kelley, D. Sridhara and J. Rosenthal (2008). Zig-zag and replacement product graphs and LDPC codes. Adv. Math. Commun.. 2 (4), 347-372 A. Lubotzky (2012). Expander graphs in pure and applied mathematics. Bull. Amer. Math. Soc. (N.S.). 49 (1), 113-162 A. Lubotzky and B. Weiss (1993). Groups and expanders. Expanding graphs (Princeton, NJ, 1992), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Providence, RI. 10, 95-109 G. A. Margulis (1973). Explicit constructions of expanders. Problemy Pereda\v{c}i Informacii, Russian. 9 (4), 71-80 Y. Peres and D. Revelle (2004). Mixing times for random walks on finite lamplighter groups. Electron. J. Probab.. 9 (26), 825-845 M. S. Pinsker (June 1973). On the complexity of a concentrator. $7$th International Teletraffic Conference, Stockolm, pages 318/1-318/4. , 1-4 O. Reingold, S. Vadhan and A. Wigderson (2002). Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders. Ann. of Math. (2). 155 (1), 157-187 G. Sabidussi (1959). The composition of graphs. Duke Math. J.. 26, 693-696 G. Sabidussi (1959/1960). Graph multiplication. Math. Z.. 72, 446-457 F. Scarabotti and F. Tolli (2009). Radon transforms and lamplighter random walks. J. Math. Sci. (N.Y.), translated from Sovrem. Mat. Prilozh. (Contemporary Mathematics and Its Applications), Vol. 50, Functional Analysis, 2007.. 156 (1), 109-122 F. Scarabotti and F. Tolli (2008). Harmonic Analysis on finite lamplighter random walks. J. Dyn. Control Syst.. 14 (2), 251-282 F. Scarabotti and F. Tolli (2010). Harmonic analysis on a finite homogeneous space. Proc. Lond. Math. Soc. (3). 100 (2), 348-376 W. Woess (2005). A note on the norms of transition operators on lamplighter graphs and groups. Internat. J. Algebra Comput.. 15 (5-6), 1261-1272