Доступ открыт Открытый доступ  Доступ закрыт Только для подписчиков

Исследование свойств классов эквивалентности перестановок с помощью обратного преобразования Робинсона — Шенстеда — Кнута


https://doi.org/10.31799/1684-8853-2019-1-11-22

Полный текст:


Аннотация

Введение: вся информация о перестановке, т. е. об элементе симметрической группы S(n), содержится в паре таблиц Юнга, сопоставляемых ей преобразованием RSK. Если же вместо перестановки рассматривать бесконечную последовательность натуральных или вещественных чисел, то вся информация о ней содержится только в записывающей бесконечной таблице Юнга. В недавней работе Д. Ромика и П. Сняды была получена явная формула, выражающая первый элемент бесконечной последовательности равномерно распределенных случайных величин через предельный угол наклона нерва нумерующей таблицы. Однако до сих пор не было произведено массовых численных экспериментов, посвященных восстановлению начала такой последовательности по началу записывающей таблицы Юнга. При этом очень важна точность такого восстановления, потому что значение даже первого элемента последовательности может быть определено только по бесконечной таблице.

Цель: разработка программного пакета для операций над диаграммами и таблицами Юнга и его применение для компьютерных экспериментов с большими таблицами Юнга. Изучение свойств классов эквивалентности по Кнуту и двойственной эквивалентности по Кнуту на множестве перестановок посредством численных экспериментов с использованием прямого и обратного преобразования RSK.

Результаты: разработан программный пакет на языке C++, включающий в себя функции для работы с диаграммами и таблицами Юнга. С помощью массовых численных экспериментов изучена зависимость значений первого элемента перестановки, получаемой обратным преобразованием RSK, от координат конца нерва нумерующей таблицы. Вычислены среднеквадратические отклонения этих значений для перестановок различной длины. Определялись возможные положения единицы в перестановках, принадлежащих одному и тому же классу эквивалентности по Кнуту. Выявлено, что количество этих положений не превышает количества угловых клеток соответствующей диаграммы Юнга. Экспериментально установлено, что при фиксированной записывающей таблице значение первого элемента перестановки зависит только от координат конца нерва нумерующей таблицы.


Об авторах

Н. Н. Васильев
Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН; Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»
Россия

Васильев Николай Николаевич, кандидат физико-математических наук, старший научный сотрудник лаборатории теории представлений и динамических систем Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН

наб. р. Фонтанки, 27, Санкт-Петербург, 191023,

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

 



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

Дужин Василий Сергеевич, соискатель при лаборатории алгоритмической математики и логики

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



А. Д. Кузьмин
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»
Россия

Кузьмин Артем Дмитриевич, студент факультета компьютерных технологий и информатики

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



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

1. Robinson G. de B. On the representations of the symmetric group. American Journal of Math., 1938, vol. 60, pp. 745–760.

2. Schensted C. Longest increasing and decreasing subsequences. Canadian Journal of Math., 1961, vol. 13, pp. 179–191.

3. Knuth Donald E. Permutations, matrices, and generalized Young tableaux. Pacific J. Math. , 1970, vol. 34, iss. 3, pp. 709–727.

4. O’Connell N. A path-transformation for random walks and the Robinson — Schensted correspondence. Trans. Amer. Math. Soc., 2003, vol. 355, pp. 3669–3697. Available at: https://www.ams.org/journals/tran/2003-355-09/S0002-9947-03-03226-4/S0002-9947-0303226-4.pdf (accessed 15 November 2018).

5. Dauvergne D. The Archimedean limit of random sorting networks. Available at: arxiv.org/abs/1802.08934 (accessed 11 November 2018).

6. Angel O., Holroyd A. E., Romik D., Virag B.. Random sorting networks. Advances in Mathematicsvol. , 2007, 215, iss. 2, pp. 839–868. doi.org/10.1016/j.aim.2007.05.019

7. Kerov S. V. and Vershik A. M. The characters of the infinite symmetric group and probability properties of the Robinson — Schensted — Knuth algorithm. SIAM J. Algebraic Discrete Methods, 1986, vol. 7, iss. 1, pp. 116–124.

8. Romik D. and Śniady P.Jeu de taquin dynamics on infinite Young tableaux and second class particles. Annals of Probability: An Official Journal of the Institute of Mathematical Statisticsiss. 2, pp. 682–737.

9. Vershik A., Pavlov D. problems of asymptotic representation theory. Journal of Mathematical Sciencespp. , 2010, vol. 168, iss. 3, pp 351–361.

10. Васильев Н. Н., Дужин В. С. Построение неприводимых представлений симметрической группы S(n) с большими и максимальными размерностями. Информационно-управляющие системы, 2015, № 3, с. 17–22. doi:10.15217/issn1684-8853.2015.3.17

11. Vasiliev N. N., Duzhin V. S. A study of the growth of the maximum and typical normalized dimensions of strict Young diagrams. Journal of Mathematical Sciences, 2016, vol. 216, iss. 1, pp 53–64. doi:10.1007/s10958-016-2887-x

12. Duzhin V. S., Vasilyev N. N. Asymptotic behavior of normalized dimensions of standard and strict Young diagrams — growth and oscillations. Journal of Knot Theory and its Ramifications, 2016, vol. 25, iss. 12. doi:10.1142/S0218216516420025

13. Duzhin V., Vasilyev N. Modeling of an asymptotically central Markov process on 3D Young graph. Mathemat ics in Computer Science, 2017, vol. 11, iss. 3–4, pp. 315– 328. doi:10.1007/s11786-017-0314-4

14. Vasiliev N. N., Duzhin V. S. Numerical study of the asymptotics of path probabilities in a Markov process close to a central one on the 3D Young graph. Journal of Mathematical Sciences, 2017, vol. 224, iss. 2, pp. 214–220. doi:10.1007/s10958-017-3406-4

15. Fulton W. Young diagrams, with applications to representation theory and geometry. Cambridge Univer sity Press, 1996. 272 p.

16. Вершик А. М., Керов С. В. Асимптотическая теория характеров симметрической группы. Функциональный анализ и его приложения, 1981, т. 15, вып. 4, с. 15–27.

17. Śniady P. Robinson — Schensted — Knuth algorithm, jeu de taquin and Kerov — Vershik measures on infinite tableaux. SIAM Journal on Discrete Mathematics, 2013, vol. 28, iss. 2. doi:10.1137/130930169

18. Romik D., Śniady P. Limit shapes of bumping routes in the Robinson — Schensted correspondence. Available at: arXiv:1304.7589v2 (accessed 11 November 2018).

19. Fomin S. V. Knuth equivalence, jeu de taquin, and the Littlewood — Richardson rule. Appendix 1 to Chapter 7. In: Stanley R. P. Enumerative Combinatorics. Vol. 2. Cambridge University Press, 1999. 595 p.

20. Schützenberger M. P. Quelques remarques sur une construction de Schensted. Math. Scandinavica, 1963, vol. 12, pp. 117–128.

21. Duzhin V., Vasilyev N. Schützenberger transformation on graded graphs: Implementation and numerical experiments. International Conf. “Polynomial Computer Algebra 2018”, Saint-Petersburg, 16–21 April 2018, ed. by N. N. Vassiliev, VVM Publishing, Saint-Petersburg, 2018, pp. 41–46.


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

Для цитирования: Васильев Н.Н., Дужин В.С., Кузьмин А.Д. Исследование свойств классов эквивалентности перестановок с помощью обратного преобразования Робинсона — Шенстеда — Кнута. Информационно-управляющие системы. 2019;(1):11-22. https://doi.org/10.31799/1684-8853-2019-1-11-22

For citation: Vassiliev N.N., Duzhin V.S., Kuzmin A.D. Investigation of properties of equivalence classes of permutations by inverse Robinson — Schensted — Knuth transformation. Information and Control Systems. 2019;(1):11-22. (In Russ.) https://doi.org/10.31799/1684-8853-2019-1-11-22

Просмотров: 46


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-8853 (Print)
ISSN 2541-8610 (Online)