Переписка Робинсона-Шенстеда

В математике соответствие Робинсона -Шенстеда представляет собой биективное соответствие между перестановками и парами стандартных таблиц Юнга одинаковой формы. У него есть различные описания, все из которых имеют алгоритмическую природу, он обладает множеством замечательных свойств и имеет приложения в комбинаторике и других областях, таких как теория представлений . частности Кнутом до так называемого соответствия Робинсона-Шенстеда-Кнута , а также дальнейшее обобщение на изображения Зелевинского Соответствие было обобщено многими способами, в .

Простейшим описанием соответствия является использование алгоритма Шенстеда (Schensted 1961 ), процедуры, которая строит одну таблицу путем последовательной вставки значений перестановки в соответствии с определенным правилом, в то время как другая таблица фиксирует эволюцию формы во время построения. Соответствие было описано в несколько иной форме гораздо раньше Робинсоном ( Robinson 1938 ) в попытке доказать правило Литтлвуда-Ричардсона . Соответствие часто называют алгоритмом Робинсона-Шенстеда , хотя процедура, используемая Робинсоном, радикально отличается от алгоритма Шенстеда и почти полностью забыта. Другие методы определения соответствия включают недетерминированный алгоритм в терминах jeu de taquin .

Биективный характер соответствия связывает его с перечислительным тождеством.

\sum _{\lambda \in {\mathcal {P}}_{n}}(t_{\lambda })^{2}=n!

где ${\mathcal {P}}_{n}$ обозначает множество разбиений n $t$ (или диаграмм Юнга с $n$ квадратами), а $λ обозначает$ количество стандартных таблиц Юнга формы $λ$ .

Алгоритм Шенстеда

Алгоритм Шенстеда начинается с перестановки $σ,$ записанной в двухстрочной записи.

\sigma ={\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}&\sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}

где $σ i = σ (i)$ и продолжается путем последовательного построения последовательности (промежуточных) упорядоченных пар таблиц Юнга одной и той же формы:

(P_{0},Q_{0}),(P_{1},Q_{1}),\ldots ,(P_{n},Q_{n}),

где $P 0 = Q 0$ — пустые таблицы. Выходные таблицы: $P = P n$ и $Q = Q n$ . После $P i -1$ построения $формируется P i$ путем вставки $σ i$ в $P i -1$ , а затем $Q i$ путем добавления элемента $i$ к $Q i -1$ в квадрате, добавленном к форме вставкой (так что $P i$ и $Q i$ имеют одинаковую форму для всех $i$ ). Из-за более пассивной роли таблиц $Q i$ последняя таблица $Q n$ предыдущие $Q i$ , которая является частью выходных данных и из которой легко считываются , называется таблицей записи ; таблицы $Pi, напротив ,$ называются таблицами вставки .

Вставка

Основная процедура, используемая для вставки каждого $σ i,$ называется вставкой Шенстеда или вставкой строки (чтобы отличить ее от варианта процедуры, называемой вставкой столбца). Его простейшая форма определяется как «неполные стандартные таблицы»: как и стандартные таблицы, они имеют отдельные записи, образующие увеличивающиеся строки и столбцы, но некоторые значения (которые еще предстоит вставить) могут отсутствовать в качестве записей. Процедура принимает в качестве аргументов такую таблицу $T$ и значение $x,$ которого нет в качестве записи $T$ ; на выходе он выдает новую таблицу, обозначенную $T \leftarrow x$ , и квадрат $s,$ на который выросла ее форма. Значение $x$ появляется в первой строке $T \leftarrow x$ , либо будучи добавленным в конце (если не было записей больше $x$ ), либо иным образом заменяя первую запись $y > x$ в первой строке $T$ . В первом случае $s$ — это квадрат, в который $добавляется x$ и вставка завершается; в последнем случае замененная запись $y$ аналогичным образом вставляется во вторую строку $T$ и так далее, пока на каком-то этапе не применяется первый случай (что, безусловно, происходит, если пустая строка $Т$ достигнуто).

Более формально, следующий псевдокод описывает вставку строки нового значения $x$ в $T$ . ^[1]

Установите $i = 1$ и $j$ на единицу больше, чем длина первой строки $T$ .
Пока $j > 1$ и $x < T i, j -1$ , уменьшите $j$ на 1. (Теперь $(i, j)$ — это первый квадрат в строке $i,$ в котором либо запись больше $x$ в $T$ , либо вообще нет записи.)
Если квадрат $(i, j)$ пуст в $T$ , завершите операцию после добавления $x$ к $T$ в квадрате $(i, j)$ и установки $s = (i, j)$ .
Поменяйте местами значения $x$ и $Ti, j$ . (При этом старый $x$ вставляется в строку $i$ и сохраняет заменяемое им значение для вставки в следующую строку.)
Увеличьте $i$ на 1 и вернитесь к шагу 2.

Форма $T$ увеличивается ровно на один квадрат, а именно $на s$ .

Корректность

Тот факт, что $T \leftarrow x$ имеет возрастающие строки и столбцы, если то же самое верно для $T$ , не является очевидным из этой процедуры (записи в одном и том же столбце никогда даже не сравниваются). Однако это можно увидеть следующим образом. В любое время, кроме сразу после шага 4, квадрат $(i, j)$ либо пуст в $T$ , либо содержит значение больше $x$ ; Шаг 5 восстанавливает это свойство, потому что $(i, j)$ теперь является квадратом, расположенным непосредственно под тем, который первоначально $x$ в $T.$ содержал Таким образом, эффект замены на этапе 4 на значение $Ti, j$ заключается в уменьшении его; в частности, он не может стать больше, чем его правый или нижний сосед. С другой стороны, новое значение также не меньше, чем его левый сосед (если он присутствует), что подтверждается сравнением, которое только что завершило шаг 2. Наконец, чтобы увидеть, что новое значение больше, чем его верхний сосед $T i -1, j,$ если оно присутствует, обратите внимание, что $T i -1, j$ сохраняется после шага 5, и что уменьшение $j$ на шаге 2 только уменьшает соответствующее значение $T i - 1, ж$ .

Построение таблиц

Полный алгоритм Шенстеда, примененный к перестановке $σ,$ работает следующим образом.

Установите $P$ и $Q$ в пустую таблицу
Для $увеличения i$ от $1$ до $n$ вычислите $P \leftarrow σ i$ и квадрат $s$ с помощью процедуры вставки; затем замените $P$ на $P \leftarrow σ i$ и добавьте запись $i$ в таблицу $Q$ в квадрате $s$ .
Завершить, вернув пару $(P, Q)$ .

Алгоритм создает пару стандартных таблиц Юнга.

Инвертируемость конструкции

Можно видеть, что для любой пары $(P, Q)$ стандартных таблиц Юнга одинаковой формы существует обратная процедура, которая производит перестановку, которая приведет к $(P, Q)$ алгоритмом Шенстеда. По сути, он состоит из прослеживания шагов алгоритма в обратном направлении, каждый раз с использованием записи $Q$ для поиска квадрата, где должна начаться обратная вставка, перемещения соответствующей записи $P$ на предыдущую строку и продолжения вверх по строкам до тех пор, пока не появится запись заменяется первая строка, представляющая собой значение, вставленное на соответствующем шаге алгоритма построения. Эти два обратных алгоритма определяют взаимно однозначное соответствие между перестановками $n$ с одной стороны и парами стандартных таблиц Юнга одинаковой формы, содержащими $n$ квадратов с другой стороны.

Характеристики

Одним из наиболее фундаментальных свойств, но не очевидным из алгоритмической конструкции, является симметрия:

Если соответствие Робинсона-Шенстеда связывает таблицы $(P, Q)$ с перестановкой $σ$ , то оно сопоставляет $(Q, P)$ с обратной перестановкой $σ -1$ .

Это можно доказать, например, обратившись к геометрической конструкции Вьенно .

Дальнейшие свойства, все при условии, что соответствие связывает таблицы $(P, Q)$ с перестановкой $σ = (σ 1, ..., σ n)$ .

В паре таблиц $(P', Q' )$ , связанных с обратной перестановкой $(σ n, ..., σ 1)$ , таблица $P'$ является транспонированной таблицей $P$ , а $Q'$ является таблицей, определяемой $Q$ , независимо от $P$ (а именно транспонирование таблицы, полученной из $Q$ с помощью инволюции Шютценбергера ).
Длина самой длинной возрастающей подпоследовательности σ $1, ..., σ n$ равна длине первой строки $P$ (и $Q$ ).
Длина самой длинной убывающей подпоследовательности $σ 1, ..., σ n$ равна длине первого столбца $P$ (и $Q$ ), как следует из двух предыдущих свойств.
Спусковое множество $i : σi > σi {+ 1}$ для $σ$ равно спусковому множеству $i : i} +1 находится в строке строго ниже строки i$ из $Q.$ {
Определите подпоследовательности $π$ по их наборам индексов. Это теорема Грина, согласно которой для любого $k \geq 1$ размер наибольшего множества, которое можно записать как объединение не более $k$ возрастающих подпоследовательностей, равен $λ 1 + ... + λ k$ . В частности, $λ 1$ соответствует наибольшей длине возрастающей подпоследовательности $π$ .
Если $σ$ — инволюция , то количество неподвижных точек $σ$ равно количеству столбцов нечетной длины в $λ$ .

Приложения

Приложение к теореме Эрдеша – Секереша

Соответствие Робинсона-Шенстеда можно использовать для простого доказательства теоремы Эрдеша-Секереша .

См. также

Геометрическая конструкция Вьенно , дающая схематическую интерпретацию соответствия.
Плактический моноид : процесс вставки может использоваться для определения ассоциативного произведения таблиц Юнга с записями от 1 до $n$ , который называется Плактическим моноидом порядка $n$ .

Примечания

^ Адаптировано из Д. Е. Кнут (1973), Искусство компьютерного программирования , вып. 3, стр. 50–51.

Ссылки

Фултон, Уильям (1997), Young Tableaux , Студенческие тексты Лондонского математического общества, том. 35, Издательство Кембриджского университета , ISBN 978-0-521-56144-0 , МР 1464693 .
Кнут, Дональд Э. (1970), «Перестановки, матрицы и обобщенные таблицы Юнга» , Pacific Journal of Mathematics , 34 : 709–727, doi : 10.2140/pjm.1970.34.709 , MR 0272654
Робинсон, Г. де Б. (1938), «О представлениях симметричной группы», American Journal of Mathematics , 60 (3): 745–760, doi : 10.2307/2371609 , JSTOR 2371609 , Zbl 0019.25102 .
Саган, Б.Е. (2001), Симметричная группа , Тексты для выпускников по математике, том. 203, Нью-Йорк: Springer-Verlag, ISBN. 0-387-95067-2 .
Шенстед, К. (1961), «Самые длинные возрастающие и убывающие подпоследовательности», Canadian Journal of Mathematics , 13 : 179–191, doi : 10.4153/CJM-1961-015-3 , MR 0121305 .
Стэнли, Ричард П. (1999), Перечислительная комбинаторика, Vol. 2 , Кембриджские исследования по высшей математике, том. 62, Издательство Кембриджского университета , ISBN 978-0-521-56069-6 , МР 1676282 .
Зелевинский, А.В. (1981), «Обобщение правила Литтлвуда-Ричардсона и соответствия Робинсона-Шенстеда-Кнута», Journal of Algebra , 69 (1): 82–94, doi : 10.1016/0021-8693(81)90128 -9 , МР 0613858 .

Дальнейшее чтение

Грин, Джеймс А. (2007). Полиномиальные представления GL _n . Конспект лекций по математике. Том. 830. С приложением К. Эрдмана, Дж. А. Грина и М. Шокера о соответствии Шенстеда и путях Литтельмана (2-е исправленное и дополненное изд.). Берлин: Springer-Verlag . ISBN 3-540-46944-3 . Збл 1108.20044 .

Внешние ссылки

ван Леувен, MAA (2001) [1994], «Переписка Робинсона-Шенстеда» , Энциклопедия математики , EMS Press
Уильямс Л., Интерактивная анимация алгоритма Робинсона-Шенстеда.

[1] Адаптировано из Д. Е. Кнут (1973), Искусство компьютерного программирования , вып. 3, стр. 50–51.

[1]