Исследование эволюции записывающей таблицы в соответствии Робинсона-Шенстеда-Кнута

Обложка

Цитировать

Полный текст

Аннотация

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

Об авторах

В. С. Дужин

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

Автор, ответственный за переписку.
Email: vsduzhin@etu.ru

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

ул. Профессора Попова, д. 5, Санкт-Петербург, 197376, Россия

Список литературы

  1. 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.
  2. D. Dauvergne, “The Archimedean limit of random sorting networks,” 2018. arXiv: arXiv:abs/1802.08934 [math.PR].
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. G. E. Andrews, The Theory of Partitions, ser. Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 1984. doi: 10.1017/CBO9780511608650.
  10. C. Moore. (2006). Flows in young diagrams. online resource, [Online]. Available: http://tuvalu.santafe.edu/~moore/gallery.html.
  11. 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.
  12. 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.

© Дужин В.С., 2019

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах