Поиск диаграмм Юнга с большими размерностями
DOI:
https://doi.org/10.32603/2071-2340-2019-4-33-43Ключевые слова:
Диаграмма Юнга, граф Юнга, диаграмма Браттели-Вершика, процесс Планшереля, асимптотическая комбинаторика, неприводимое представление, симметрическая группаАннотация
Поиск диаграмм Юнга с максимальными размерностями или, что эквивалентно, поиск неприводимых представлений симметрической группы $S(n)$ с максимальными размерностями, является важной задачей асимптотической комбинаторики. В данной работе предложены алгоритмы, позволяющие преобразовывать диаграмму Юнга в другую диаграмму того же размера, но обладающую большей размерностью. В результате массивных численных экспериментов построена последовательность диаграмм Юнга с большими размерностями длины $10^6$. При этом первые 1000 членов данной последовательности не изменяются под воздействием применяемых алгоритмов, что может свидетельствовать о том, что подавляющее их число обладает максимальными размерностями. Установлено, что в построенной последовательности размерности всех диаграмм Юнга, начиная с 75778-й, превышают размерности соответствующих диаграмм из жадной планшерелевской последовательности.
Библиографические ссылки
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.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Материал публикуется под лицензией:
