RSK-соответствие и массивы

Евгений Смирнов / ЛШСМ 2022

Известная многим теорема Эрдеша—Секереша утверждает:

В любой перестановке rs+1 элементов есть либо монотонно возрастающая подпоследовательность из r+1 числа, либо монотонно убывающая подпоследовательность из s+1 числа.

Мы приведём “концептуальное” доказательство этой теоремы, построив по последовательности n элементов пару таблиц Юнга из n клеточек. Полученное соответствие между перестановками и парами стандартных таблиц называется соответствием Робинсона-Шенстеда-Кнута, или сокращенно RSK. Мы изучим некоторые его замечательные свойства и постараемся их объяснить. Для этого нам потребуется еще одно комбинаторное понятие: массивы Данилова-Кошевого. Массивы — это, неформально говоря, прямоугольные доски, клеточки которых заполнены шариками, которые можно перемещать по некоторым правилам. Помимо объяснения разных феноменов, связанных с RSK-соответствием, массивы позволяют доказать множество интересных фактов о симметрических функциях.

Примерный план лекций:

1. Теорема Эрдеша—Секереша. Стандартные и полустандартные таблицы Юнга, игра в 15, вставка Кнута. RS- и RSK-соответствие.

2. Массивы Данилова—Кошевого. Операции над массивами. Связь с RSK-соответствием.

3. Симметрические функции как суммы по орбитам массивов. Многочлены Шура, тождество Коши, правило Литтлвуда—Ричардсона.

Основная часть курса будет совершенно элементарной и доступной для школьников.

Смирнов Евгений Юрьевич — кандидат физико-математических наук.

Летняя школа «Современная математика», г. Дубна

25-29 июля 2022 г.

Источник: vk.com

Комментарии: