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

Обложка

Цитировать

Полный текст

Аннотация

Соответствие Робинсона-Шенстеда-Кнута (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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».