پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شمارهها | 1,682 |
| تعداد مقالات | 13,758 |
| تعداد مشاهده مقاله | 32,156,412 |
| تعداد دریافت فایل اصل مقاله | 12,732,029 |
Replacement and zig-zag products, Cayley graphs and Lamplighter random walk | ||
| International Journal of Group Theory | ||
| مقاله 3، دوره 2، شماره 1، خرداد 2013، صفحه 11-35 اصل مقاله (569.56 K) | ||
| نوع مقاله: Ischia Group Theory 2012 | ||
| شناسه دیجیتال (DOI): 10.22108/ijgt.2013.1932 | ||
| نویسنده | ||
| Alfredo Donno* | ||
| 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. | ||
| کلیدواژهها | ||
| Replacement and zig-zag product؛ Expander graph؛ Lamplighter random walk؛ Cayley graph؛ Semidirect and wreath product | ||
| مراجع | ||
|
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{http://www.pmf.ni.ac.rs/filomat}{http://www.pmf.ni.ac.rs/filomat}
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{http://www.math.ucsd.edu/$sim$jjcummings/RP$_{-}$Submission$_{-}$Final.pdf}
{http://www.math.ucsd.edu/$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
| ||
|
آمار تعداد مشاهده مقاله: 6,278 تعداد دریافت فایل اصل مقاله: 3,883 |
||