Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia named after Patrice Lumumba (RUDN University)2291410.22363/2658-4670-2019-27-4-316-324Computer ScienceИнформатика и вычислительная техникаResearch ArticleInvestigation of insertion tableau evolution in the Robinson-Schensted-Knuth correspondenceИсследование эволюции записывающей таблицы в соответствии Робинсона-Шенстеда-КнутаDuzhinVasilii S.ДужинВ. С.

assistant of Department of Algorithmic Mathematics

Кафедра алгоритмической математики

vsduzhin@etu.ruSaint Petersburg Electrotechnical University “LETI”Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»15122019274VOL 27, NO4 (2019)ТОМ 27, №4 (2019)31632419022020Copyright ©; 2019, Duzhin V.S.Copyright ©; 2019, Дужин В.С.2019Duzhin V.S.Дужин В.С.http://creativecommons.org/licenses/by/4.0https://journals.rudn.ru/miph/article/view/22914

Robinson-Schensted-Knuth (RSK) correspondence occurs in different contexts of algebra and combinatorics. Recently, this topic has been actively investigated by many researchers. At the same time, many investigations require conducting the computer experiments involving very large Young tableaux. The article is devoted to such experiments. RSK algorithm establishes a bijection between sequences of elements of linearly ordered set and the pairs of Young tableaux of the same shape called insertion tableau and recording tableau . In this paper we study the dynamics of tableau and the dynamics of different concrete values in tableau during the iterations of RSK algorithm. Particularly, we examine the paths within tableaux called bumping routes along which the elements of an input sequence pass. The results of computer experiments with Young tableaux of sizes up to 108 were presented. These experiments were made using the software package for dealing with 2D and 3D Young diagrams and tableaux.

Соответствие Робинсона-Шенстеда-Кнута (RSK) встречается в различных контекстах алгебры и комбинаторики. В последнее время данная тема активно исследуется специалистами из различных областей науки. В то же время многие такие исследования требуют проведения компьютерных экспериментов с таблицами Юнга чрезвычайно больших размеров. Эта статья посвящена таким численным экспериментам. Алгоритм RSK устанавливает биекцию между множеством последовательностей элементов из линейно упорядоченного множества и множеством пар таблиц Юнга одинаковой формы, называемых записывающей таблицей и нумерующей таблицей . В настоящей работе изучается динамика таблицы , а также динамика позиций различных значений, перемещающихся по таблице в течение итераций алгоритма RSK. В частности, исследовались пути в таблице , называемые путями выталкиваний, вдоль которых перемещаются значения из входной последовательности в процессе работы алгоритма RSK. Приводятся результаты компьютерных экспериментов над таблицами Юнга с размерами до 108. Эти эксперименты были проведены с помощью программного пакета для работы с двумерными и трёхмерными диаграммами и таблицами Юнга.

Robinson-Schensted-Knuth correspondenceYoung tableauxYoung graphMarkov processcentral measurePlancherel measureasymptotic representation theoryсоответствие Робинсона-Шенстеда-Кнутатаблицы Юнгаграф Юнгамарковские процессыцентральная мерамера Планшереляасимптотическая теория представленийN. O’Connell, “A path-transformation for random walks and the Robinson - Schensted correspondence,” Transactions of the American Mathematical Society, vol. 355, no. 9, pp. 3669-3697, 2003. eprint: www.jstor.org/stable/1194859.D. Dauvergne, “The Archimedean limit of random sorting networks,” 2018. arXiv: arXiv:abs/1802.08934 [math.PR].O. Angel, A. E. Holroyd, D. Romik, and B. Virág, “Random sorting networks,” Advances in Mathematics, vol. 215, no. 2, pp. 839-868, 2007. DOI: 10.1016/j.aim.2007.05.019.S. V. Kerov and A. M. Vershik, “The characters of the infinite symmetric group and probability properties of the Robinson-Schensted-Knuth algorithm,” SIAM J. Algebraic Discrete Methods, vol. 7, no. 1, pp. 116- 124, 1986. DOI: 10.1137/0607014.D. Romik and P. Śniady, “Jeu de taquin dynamics on infinite Young tableaux and second class particles,” Annals of Probability: An Official Journal of the Institute of Mathematical Statistics, vol. 43, no. 2, pp. 682- 737, 2015. DOI: 10.1214/13-AOP873.N. N. Vassiliev, V. S. Duzhin, and A. D. Kuzmin, “Investigation of properties of equivalence classes of permutations by inverse Robinson - Schensted - Knuth transformation [Issledovaniye svoystv klassov ekvivalentnosti perestanovok s pomoshch’yu obratnogo preobrazovaniya Robinsona],” Informatsionno-upravliaiushchie sistemy [Information and Control Systems], no. 1, pp. 11-22, 2019, in Russian. DOI: 10.31799/ 1684-8853-2019-1-11-22. eprint: https://elibrary.ru/item.asp? id=36930159.A. M. Vershik and S. V. Kerov, “Asymptotic of the largest and the typical dimensions of irreducible representations of a symmetric group,” Functional Analysis and Its Applications, vol. 19, no. 1, pp. 21-31, 1985. DOI: 10.1007/BF01086021.A. M. Vershik and S. V. Kerov, “Asymptotic theory of characters of the symmetric group,” Functional Analysis and Its Applications, vol. 15, no. 4, pp. 246-255, 1981. DOI: 10.1007/BF01106153.G. E. Andrews, The Theory of Partitions, ser. Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 1984. DOI: 10.1017/CBO9780511608650.C. Moore. (2006). Flows in young diagrams. online resource, [Online]. Available: http://tuvalu.santafe.edu/~moore/gallery.html.D. Romik and P. Śniady, “Limit shapes of bumping routes in the Robinson-Schensted correspondence,” Random Structures & Algorithms, vol. 48, no. 1, pp. 171-182, Sep. 2014. DOI: 10.1002/rsa.20570.V. Duzhin, A. Kuzmin, and N. Vassiliev, “RSK bumping trees and a fast RSK algorithm,” in International Conference Polynomial Computer Algebra ‘2019; St. Petersburg, April 15-20, 2019 / Euler International Mathematical Institute, Ed. by N. N. Vassiliev, VVM Pubishing, 2019. eprint: https://elibrary.ru/item.asp?id=41320890.