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

Василий Сергеевич Дужин; Анастасия Андреевна Чудновская

doi:10.32603/2071-2340-2019-4-33-43

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

DOI: https://doi.org/10.32603/2071-2340-2019-4-33-43

Ключевые слова: Диаграмма Юнга, граф Юнга, диаграмма Браттели-Вершика, процесс Планшереля, асимптотическая комбинаторика, неприводимое представление, симметрическая группа

Аннотация

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

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

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

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

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

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

Литература

D. E. Knuth, The art of computer programming, vol. 3, Moscow: Mir, 1978 (in Russian).

J. McKay, “The Largest Degrees of Irreducible Characters of the Symmetric Group,” Mathematics of Computation, vol. 30, no. 135, pp. 624–631, 1976; doi: 10.1090/S0025-5718-1976-0404414-X

R. M. Baer and P. Brock, “Natural Sorting over Permutation Spaces,” Mathematics of Computation, no. 22, pp. 385–410, 1968.

A. M. Vershik and D. A. Pavlov, “Numerical experiments in problems of asymptotic representation theory,” Zapiski Nauchnykh Seminarov POMI, vol. 373, pp. 77–93, 2009 (in Russian).

G. E. Andrews, The Theory of Partitions, Moscow: Nauka, Glavnaya redaktsiya fiziko-matematicheskoi literatury, 1982.

N. N. Vasil’ev and V. S. Duzhin, “Postroenie neprivodimykh predstavlenii simmetricheskoi gruppy S(n) s bol’shimi i maksimal’nymi razmernostyami” [Construction of irreducible representations of the symmetric group S (n) with large and maximal dimensions], Information and Control Systems, no. 3, pp. 17–22, 2015 (in Russian); doi: 10.15217/issn1684-8853.2015.3.17

N. N. Vasil’ev and V. S. Duzhin, “A Study of the Growth of the Maximum and Typical Normalized Dimensions of Strict Young Diagrams,” Journal of Mathematical Sciences, vol. 216, no. 1, pp. 53–64, 2016; doi: 10.1007/s10958-016-2887-x

N. N. Vasil’ev and V. S. Duzhin, “Randomized Schutzenberger transformation and uniformly random generator of Young tableaux,” Zapiski Nauchnykh Seminarov POMI, vol. 485, pp. 90–106, 2019 (in Russian).

A. M. Vershik and S. V. Kerov, “Asimptotika maksimal’noi i tipichnoi razmernostei neprivodimykh predstavlenii simmetricheskoi gruppy” [Asymptotics of the maximum and typical dimensions of irreducible representations of a symmetric group], Funktsional’nyi analiz i ego prilozheniya, vol. 19, no. 1, pp. 25–36, 1985 (in Russian).

J. S. Frame, G. de B. Robinson, and R. M. Thrall, “The hook graphs of the symmetric group,” Canad J. Math., no. 6, pp. 316–325, 1954; doi: 10.4153/CJM-1954-030-1

S. V. Kerov, “Transition Probabilities for Continual Young Diagrams and the Markov Moment Problem,”Funktsional. Anal. Prilozhen., vol. 27, no. 2, pp. 32–49, 1993.