Search for Young diagrams with large dimensions
Abstract
Search for Young diagrams with maximum dimensions or, equivalently, search for irreducible representations of the symmetric group $S(n)$ with maximum dimensions is an important problem of asymptotic combinatorics. In this paper, we propose algorithms that transform a Young diagram into another one of the same size but with a larger dimension. As a result of massive numerical experiments, the sequence of $10^6$ Young diagrams with large dimensions was constructed. Furthermore, the proposed algorithms do not change the first 1000 elements of this sequence. This may indicate that most of them have the maximum dimension. It has been found that the dimensions of all Young diagrams of the resulting sequence starting from the 75778th exceed the dimensions of corresponding diagrams of the greedy Plancherel sequence.
References
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.
This work is licensed under a Creative Commons Attribution 4.0 International License.
