Алгоритм пошуку кількості рухомих точок підстановок із силовських 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.

Номер

Том 4 (2021): Могилянський математичний журнал

Розділ

Статті

Ліцензія

Авторське право (c) 2021 Vita Olshevska

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори, які публікуються у цьому журналі, погоджуються з такими умовами:

а) Автори зберігають за собою авторські права на твір на умовах ліцензії Creative Commons Attribution License CC BY 4.0, котра дозволяє іншим особам вільно поширювати (копіювати і розповсюджувати матеріал у будь-якому вигляді чи форматі) та змінювати (міксувати, трансформувати, і брати матеріал за основу для будь-яких цілей, навіть комерційних) опублікований твір на умовах зазначення авторства.

б) Журнал дозволяє автору (авторам) зберігати авторські права без обмежень.

в) Автори мають право укладати самостійні додаткові угоди щодо поширення твору (наприклад, розміщувати роботу в електронному репозитарії), за умови збереження посилання на його першу публікацію. (Див. Політика Самоархівування)

г) Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у репозитаріях) тексту статті, як до подання його до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).