RSK-соответствие и массивы. Семинар 3 // Евгений Смирнов / ЛШСМ 2022

Известная многим теорема Эрдеша—Секереша утверждает: В любой перестановке rs 1 элементов есть либо монотонно возрастающая подпоследовательность из r 1 числа, либо монотонно убывающая подпоследовательность из s 1 числа. Мы приведём “концептуальное” доказательство этой теоремы, построив по последовательности n элементов пару таблиц Юнга из n клеточек. Полученное соответствие между перестановками и парами стандартных таблиц называется соответствием Робинсона-Шенстеда-Кнута, или сокращенно RSK. Мы изучим некоторые его замечательные свойства и постараемся их объяснить. Для этого нам потребуется еще одно комбинаторное понятие: массивы Данилова-Кошевого. Массивы — это, неформально говоря, прямоугольные доски, клеточки которых заполнены шариками, которые можно перемещать по некоторым правилам. Помимо объяснения разных феноменов, связанных с RSK-соответствием, массивы позволяют доказать множество интересных фактов о симметрических функциях. Примерный план лекций: 1. Теорема Эрдеша—Секереша. Стандартные и полустандартные таблицы Юнга, игра в 15, вставка Кнута. RS- и RSK-соответствие. 2. Массивы Данилова—Кошевого. Операции над массивами. Связь с RSK-соответствием. 3. Симметрические функции как суммы по орбитам массивов. Многочлены Шура, тождество Коши, правило Литтлвуда—Ричардсона. Основная часть курса будет совершенно элементарной и доступной для школьников. Смирнов Евгений Юрьевич — кандидат физико-математических наук. Летняя школа «Современная математика», г. Дубна 25-29 июля 2022 г.