RSK-соответствие и массивы. Семинар 1

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

• Теорема Эрдеша-Секереша. Стандартные и полустандартные таблицы Юнга, игра в 15, вставка Кнута. RS- и RSK-соответствие.
  
• Массивы Данилова-Кошевого. Операции над массивами. Связь с RSK-соответствием.
  
• Симметрические функции как суммы по орбитам массивов. Многочлены Шура, тождество Коши, правило Литтлвуда-Ричардсона.