О сходимости путей выталкиваний в алгоритме RSK к их предельной форме: численные эксперименты
Ключевые слова:
алгоритм RSK, соответствие RSK, диаграмма Юнга, таблица Юнга, мера Планшереля, кривая Вершика-Керова, путь выталкиваний, предельная форма, линейно упорядоченное множество, численный эксперимент, асимптотическая комбинаторикаАннотация
Введение: алгоритм Робинсона — Шенстеда — Кнута (RSK) преобразует последовательность элементов линейно упорядоченного множества в пару таблиц Юнга P, Q одинаковой формы. Это преобразование основано на выталкивании и вставке элементов в таблице P по специальным правилам. Траектория, которую образуют последовательно выталкиваемые клетки таблицы P в алгоритме RSK, называется путем выталкиваний. Явная формула предельной формы пути выталкиваний, которая определяется его начальным элементом, была получена Д. Ромиком и П. Сняды в 2016 г. Однако скорость сходимости путей выталкиваний к предельной форме ранее не исследовалась ни теоретически, ни с помощью численных экспериментов. Цель: проведение компьютерных экспериментов в целях изучения динамики путей выталкиваний, порождаемых алгоритмом RSK в таблицах Юнга, с ростом их размера; вычисление статистических средних и дисперсий отклонений путей выталкиваний от их предельных форм в метрике L2 для различных значений, подаваемых на вход алгоритма RSK. Результаты: проведена серия компьютерных экспериментов над таблицами Юнга размера до 10 млн клеток. Использовалось по 300 таблиц каждого размера. В каждую такую таблицу с помощью алгоритма RSK добавлялись различные входные значения (0,1; 0,3; 0,5; 0,7; 0,9) и были вычислены отклонения путей выталкиваний, построенных от этих значений, от соответствующих предельных форм. Построены графики средних значений и дисперсий этих отклонений. Замечено, что отклонения убывают пропорционально корню четвертой степени из размера таблицы n. Получена аппроксимация зависимости средних значений отклонений от n с помощью метода наименьших квадратов.
