Алгоритм пошуку кількості рухомих точок підстановок із силовських 2-підгруп Syl2(S2n) симетричних груп S2n

Автор(и)

  • Vita Olshevska Національний університет «Києво-Могилянська академія», Україна

DOI:

https://doi.org/10.18523/2617-70804202134-40

Ключові слова:

рухомі точки, симетричні групи, силовські підгрупи, алгоритм, складність алгоритму

Анотація

У статті запропоновано алгоритм пошуку кількості рухомих точок підстановок силовських 2-підгруп Syl2(S2n) симетричних груп S2n, n ∈ N. Для побудови цього алгоритму використано ізоморфізм між групою Syl2(S2n) та групою бінарних кореневих дерев з мітками. Також обчислено складність запропонованого алгоритму та його середню кількість кроків для силовської 2-підгрупи симетричної групи S2n. Обраховано кількість підстановок із Syl2(S2n), що мають максимальну кількість рухомих точок.

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

Vita Olshevska , Національний університет «Києво-Могилянська академія»

Аспірантка кафедри математики Національного університету “Києво-Могилянська академія”. Сфера наукових інтересів: теорія алгоритмів, теорія груп, теорія графів.

v.olshevska@ukma.edu.ua

Посилання

  1. Ian F. Blake, Gerard Cohen and Mikhail Deza, "Coding with permutations'', Information and Control, 43, 1--19 (1979).
  2. Peter J. Cameron, "Permutation codes'', European Journal of Combinatorics. 31 (2), 482-490 (2010).
  3. J. Dnes, "On some connections between permutations and coding'', Discrete Mathematics. 56, 141--146 (1985).
  4. R. Sobhani, A. Abdollahi, J. Bagherian and M. Khatami, "A note on good permutation codes from Reed-Solomon codes'', Designs, Codes and Cryptography. 87, 2335-2340 (2019).
  5. E. Irurozki, B. Calvo and J. A. Lozano. Sampling and learning the Mallows and Weighted Mallows models under the Hamming distance, in: Technical Report, University of the Basque Country., http://hdl.handle.net/10810/11240. 2014.
  6. С. Ленг, Алгебра (Наука, Москва, 1965).
  7. Ю. В. Боднарчук і Б. В. Олійник, Основи дискретної математики (Києво-Могилянська академія, 2009).
  8. Л. А. Калужнин, Избранные главы теории групп (Киевский государственный университет им. Т. Г. Шевченко, Киев, 1979), с.22--26.
  9. V. Nekrashevych, "Self-similar groups'', Mathematical Surveys and Monographs. 117, xi + 231 (2005).
  10. V. A. Olshevska, "Algorithms for computations with Sylow 2-subgroups of symetric groups'', Silesian Journal of Pure and Applied Mathematics. 10, 103--120 (2020).
  11. R. I. Grigorchuk, V. V. Nekrashevich and V. I. Sushchanskii, Automata, dynamical systems, and groups (MAIK Nauka/Interperiodica Publishing, Moscow, 2000), pp. 128-203.
  12. Reinhard Diestel, ``Graph theory'', Graduate Texts in Mathematics. 5th edition. 173, xviii + 428 (2017).

##submission.downloads##

Опубліковано

2022-05-19

Як цитувати

[1]
Olshevska , V. 2022. Алгоритм пошуку кількості рухомих точок підстановок із силовських 2-підгруп Syl2(S2n) симетричних груп S2n. Могилянський математичний журнал. 4, (Трав 2022), 34–40. DOI:https://doi.org/10.18523/2617-70804202134-40.