О случайных блужданиях на графах Кэли групп комплексных отражений

  • Максим Михайлович Васьковский Белорусский государственный университет, пр. Независимости 4, 220030, г. Минск, Беларусь https://orcid.org/0000-0001-5769-3678
DOI: https://doi.org/10.33581/2520-6508-2021-3-51-56

Аннотация

Исследуются асимптотические свойства случайных блужданий на минимальных графах Кэли групп комплексных отражений. Основным результатом является теорема о быстром перемешивании для случайных блужданий на графах Кэли групп комплексных отражений. В частности, ключевую роль играют оценки диаметров и изопериметрических постоянных таких графов, а также известный результат о быстром перемешивании для случайных блужданий на экспандерах. Приводится конструктивный способ доказательства частного случая гипотезы Бабаи о логарифмическом порядке диаметров для графов групп комплексных отражений. На основании оценки диаметров и неравенства Чигера получена нетривиальная оценка снизу для спектральных пробелов минимальных графов Кэли групп комплексных отражений.

Биография автора

Максим Михайлович Васьковский, Белорусский государственный университет, пр. Независимости 4, 220030, г. Минск, Беларусь

доктор физико-математических наук, доцент; заведующий кафедрой высшей математики факультета прикладной математики и информатики

Литература

  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.
Опубликован
2021-11-19
Ключевые слова: группы комплексных отражений, графы Кэли, случайные блуждания, экспандеры
Как цитировать
Васьковский, М. М. (2021). О случайных блужданиях на графах Кэли групп комплексных отражений. Журнал Белорусского государственного университета. Математика. Информатика, 3, 51-56. https://doi.org/10.33581/2520-6508-2021-3-51-56
Выпуск
№ 3 (2021): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

Copyright (c) 2021 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).