Поиск диаграмм Юнга с большими размерностями

  • Василий Сергеевич Дужин Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), ул. Профессора Попова, д. 5, корп. 23, 197376, Санкт-Петербург, Росси https://orcid.org/0000-0001-8399-284X
  • Анастасия Андреевна Чудновская Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), ул. Профессора Попова, д. 5, корп. 23, 197376, Санкт-Петербург, Россия https://orcid.org/0000-0002-5704-4894
Ключевые слова: Диаграмма Юнга, граф Юнга, диаграмма Браттели-Вершика, процесс Планшереля, асимптотическая комбинаторика, неприводимое представление, симметрическая группа

Аннотация

Поиск диаграмм Юнга с максимальными размерностями или, что эквивалентно, поиск неприводимых представлений симметрической группы $S(n)$ с максимальными размерностями, является важной задачей асимптотической комбинаторики. В данной работе предложены алгоритмы, позволяющие преобразовывать диаграмму Юнга в другую диаграмму того же размера, но обладающую большей размерностью. В результате массивных численных экспериментов построена последовательность диаграмм Юнга с большими размерностями длины $10^6$. При этом первые 1000 членов данной последовательности не изменяются под воздействием применяемых алгоритмов, что может свидетельствовать о том, что подавляющее их число обладает максимальными размерностями. Установлено, что в построенной последовательности размерности всех диаграмм Юнга, начиная с 75778-й, превышают размерности соответствующих диаграмм из жадной планшерелевской последовательности.

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

Василий Сергеевич Дужин, Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), ул. Профессора Попова, д. 5, корп. 23, 197376, Санкт-Петербург, Росси

ассистент кафедры алгоритмической математики факультета компьютерных технологий и информатики СПбГЭТУ, vsduzhin@etu.ru

Анастасия Андреевна Чудновская, Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), ул. Профессора Попова, д. 5, корп. 23, 197376, Санкт-Петербург, Россия

студентка бакалавриата кафедры информационных систем факультета компьютерных технологий и информатики СПбГЭТУ, aachudnovskaya@stud.eltech.ru

Литература

Кнут Д. Э. Искусство программирования. М.: Мир, 978. T. 3.

McKay J. The Largest Degrees of Irreducible Characters of the Symmetric Group // Math. Comp. 1976.

Vol. 30. № 135. P. 624–631.

Baer R. M., Brock P. Natural Sorting over Permutation Spaces // Math. Comp. 1968. № 22. P. 385–410.

Вершик А. М., Павлов Д. А. Численные эксперименты в задачах асимптотической теории представлений // Записки научных семинаров ПОМИ. 2009. Т. 373. С. 77–93.

Эндрюс Г. Теория разбиений. М.: Наука. 1982.

Васильев Н. Н., Дужин В. С. Построение неприводимых представлений симметрической группы S(n) с большими и максимальными размерностями // Информационно-управляющие системы. 2015. № 3. С. 17–22. doi:10.15217/issn1684-8853.2015.3.17

Васильев Н. Н., Дужин В. С. Исследование роста максимальных и типичных размерностей

строгих диаграмм Юнга, Теория представлений, динамические системы, комбинаторные методы // Записки научных семинаров ПОМИ. 2015. Т. 437. С. 81–99.

Дужин В. С., Васильев Н. Н. Рандомизированное преобразование Шютценберже и вычисление

копереходных вероятностей центрального процесса на трехмерном графе Юнга // Записки

научных семинаров ПОМИ. 2019. Т. 485. С. 90–106.

Вершик А. М., Керов С. В. Асимптотика максимальной и типичной размерностей неприводимых представлений симметрической группы // Функциональный анализ и его приложения.

Т. 19. № 1. С. 25–36.

Frame J. S., Robinson G. de B., Thrall R. M. The hook graphs of the symmetric group // Canad J. Math.

№ 6. P. 316–325.

Опубликован
2019-12-28
Как цитировать
Дужин, В. С., & Чудновская, А. А. (2019). Поиск диаграмм Юнга с большими размерностями. Компьютерные инструменты в образовании, (4), 33-43. https://doi.org/10.32603/2071-2340-2019-4-33-43
Выпуск
Раздел
Алгоритмическая математика и математическое моделирование