Geodesic
Random walks on cayley graphs of complex reflection groups
Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2021), pp. 51-56.

Voir la notice de l'article provenant de la source Math-Net.Ru

Asymptotic properties of random walks on minimal Cayley graphs of complex reflection groups are investigated. The main result of the paper is theorem on fast mixing for random walks on Cayley graphs of complex reflection groups. Particularly, bounds of diameters and isoperimetric constants, a known result on fast fixing property for expander graphs play a crucial role to obtain the main result. A constructive way to prove a special case of Babai’s conjecture on logarithmic order of diameters for complex reflection groups is proposed. Basing on estimates of diameters and Cheeger inequality, there is obtained a non-trivial lower bound for spectral gaps of minimal Cayley graphs on complex reflection groups.
Keywords: complex reflection groups; Cayley graphs; random walks; expander graphs. 
@article{BGUMI_2021_3_a3,
     author = {M. M. Vas'kovskii},
     title = {Random walks on cayley graphs of complex reflection groups},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {51--56},
     publisher = {mathdoc},
     volume = {3},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2021_3_a3/}
}
TY  - JOUR
AU  - M. M. Vas'kovskii
TI  - Random walks on cayley graphs of complex reflection groups
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2021
SP  - 51
EP  - 56
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2021_3_a3/
LA  - ru
ID  - BGUMI_2021_3_a3
ER  - 
%0 Journal Article
%A M. M. Vas'kovskii
%T Random walks on cayley graphs of complex reflection groups
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2021
%P 51-56
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2021_3_a3/
%G ru
%F BGUMI_2021_3_a3
M. M. Vas'kovskii. Random walks on cayley graphs of complex reflection groups. Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2021), pp. 51-56. http://geodesic.mathdoc.fr/item/BGUMI_2021_3_a3/

[1] D. Jao, S. D. Miller, R. Venkatesan, “Expander graphs based on GRH with an application to elliptic curve cryptography”, Journal of Number Theory, 129(6) (2009), 1491–1504 | DOI | MR | Zbl

[2] D. X. Charles, K. E. Lauter, E. Z. Goren, “Cryptographic hash functions from expander graphs”, Journal of Cryptology, 22(1) (2009), 93–113 | DOI | MR | Zbl

[3] D. A. Spielman, “Linear-time encodable and decodable error-correcting codes”, IEEE Transactions on Information Theory, 42(6) (1996), 1723–1731 | DOI | MR | Zbl

[4] T. Sauerwald, “Randomized protocols for information dissemination”, University of Padeborn, Padeborn, 2008, 146

[5] G. C. Shephard, J. A. Todd, “Finite unitary reflection groups”, Canadian Journal of Mathematics, 6 (1954), 274–304 | DOI | MR | Zbl

[6] P. Boalch, “Painleve equations and complex reflections”, Annales de l’Institut Fourier, 53(4) (2003), 1009–1022 | DOI | MR | Zbl

[7] D. J. Aldous, “Random walks on finite groups and rapidly mixing Markov chains”, Lecture notes in mathematics, 17, Springer, Berlin, 1983, 243–297 | MR

[8] M. Vaskouski, A. Zadorozhnyuk, “Resistance distances in Cayley graphs on symmetric groups”, Discrete Applied Mathematics, 227 (2017), 121–135 | DOI | MR | Zbl

[9] Shi. Jian-yi, “Formula for the reflection length of elements in the group G(m, p, n)”, Journal of Algebra, 316(1) (2007), 284–296 | DOI | MR | Zbl

[10] M. Krebs, A. Shaheen, “Expander families and Cayley graphs: a beginner’s guide”, Oxford University Press, New York, 2011, 258 | MR

[11] L. Babai, “Local expansion of vertex-transitive graphs and random generation in finite groups”, Proceedings of the 23rd annual ACM symposium on theory of computing (New Orleans, Louisiana, USA), ACM Press, New York, 1991, 164–174 | DOI | MR