О случайных блужданиях на графах Кэли групп комплексных отражений
Ключевые слова:
группы комплексных отражений, графы Кэли, случайные блуждания, экспандерыАннотация
Исследуются асимптотические свойства случайных блужданий на минимальных графах Кэли групп комплексных отражений. Основным результатом является теорема о быстром перемешивании для случайных блужданий на графах Кэли групп комплексных отражений. В частности, ключевую роль играют оценки диаметров и изопериметрических постоянных таких графов, а также известный результат о быстром перемешивании для случайных блужданий на экспандерах. Приводится конструктивный способ доказательства частного случая гипотезы Бабаи о логарифмическом порядке диаметров для графов групп комплексных отражений. На основании оценки диаметров и неравенства Чигера получена нетривиальная оценка снизу для спектральных пробелов минимальных графов Кэли групп комплексных отражений.
Библиографические ссылки
- 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.
- 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.
- 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.
- Sauerwald T. Randomized protocols for information dissemination. Padeborn: University of Padeborn; 2008. 146 p.
- Shephard GC, Todd JA. Finite unitary reflection groups. Canadian Journal of Mathematics. 1954;6:274–304. DOI: 10.4153/CJM-1954-028-3.
- Boalch P. Painleve equations and complex reflections. Annales de l’Institut Fourier. 2003;53(4):1009–1022. DOI: 10.5802/aif.1972.
- 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).
- 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.
- 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.
- Krebs M, Shaheen A. Expander families and Cayley graphs: a beginner’s guide. New York: Oxford University Press; 2011. 258 p.
- 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.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Авторы, публикующиеся в данном журнале, соглашаются со следующим:
- Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).
