Random walks on Cayley graphs of complex reflection groups

DOI: https://doi.org/10.33581/2520-6508-2021-3-51-56

Abstract

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.

Author Biography

Maksim M. Vaskouski, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

doctor of science (physics and mathematics), docent; head of the department of higher mathematics, faculty of applied mathematics and computer science

References

  1. Jao D, Miller SD, Venkatesan R. Expander graphs based on GRH with an application to elliptic curve cryptography. Journal of Number Theory. 2009;129(6):1491–1504. DOI: 10.1016/j.jnt.2008.11.006.
  2. Charles DX, Lauter KE, Goren EZ. Cryptographic hash functions from expander graphs. Journal of Cryptology. 2009;22(1):93–113. DOI: 10.1007/s00145-007-9002-x.
  3. Spielman DA. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory. 1996;42(6):1723–1731. DOI: 10.1109/18.556668.
  4. Sauerwald T. Randomized protocols for information dissemination. Padeborn: University of Padeborn; 2008. 146 p.
  5. Shephard GC, Todd JA. Finite unitary reflection groups. Canadian Journal of Mathematics. 1954;6:274–304. DOI: 10.4153/CJM-1954-028-3.
  6. Boalch P. Painleve equations and complex reflections. Annales de l’Institut Fourier. 2003;53(4):1009–1022. DOI: 10.5802/aif.1972.
  7. Aldous DJ. Random walks on finite groups and rapidly mixing Markov chains. In: Azéma J, Yor M, editors. Séminaire de probabilités de Strasbourg. Volume 17. Berlin: Springer; 1983. p. 243–297 (Lecture notes in mathematics; 986).
  8. Vaskouski M, Zadorozhnyuk A. Resistance distances in Cayley graphs on symmetric groups. Discrete Applied Mathematics. 2017;227:121–135. DOI: 10.1016/j.dam.2017.04.044.
  9. Jian-yi Shi. Formula for the reflection length of elements in the group G m( ) , , p n . Journal of Algebra. 2007;316(1):284–296. DOI: 10.1016/j.jalgebra.2007.06.031.
  10. Krebs M, Shaheen A. Expander families and Cayley graphs: a beginner’s guide. New York: Oxford University Press; 2011. 258 p.
  11. Babai L. Local expansion of vertex-transitive graphs and random generation in finite groups. In: Proceedings of the 23rd annual ACM symposium on theory of computing; 1991 May 5–8; New Orleans, Louisiana, USA. New York: ACM Press; 1991. p. 164–174. DOI: 10.1145/103418.103440.
Published
2021-11-19
Keywords: complex reflection groups, Cayley graphs, random walks, expander graphs
How to Cite
Vaskouski, M. M. (2021). Random walks on Cayley graphs of complex reflection groups. Journal of the Belarusian State University. Mathematics and Informatics, 3, 51-56. https://doi.org/10.33581/2520-6508-2021-3-51-56
Issue
No 3 (2021): Journal of the Belarusian State University. Mathematics and Informatics
Section
Discrete Mathematics and Mathematical Cybernetics

Copyright (c) 2021 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)