Геометрическая конструкция Вьенно

В математике геометрическая конструкция Вьенно (названная в честь Ксавье Жерара Вьенно ) дает схематическую интерпретацию соответствия Робинсона-Шенстеда в терминах теневых линий . Оно имеет обобщение соответствия Робинсона-Шенстеда-Кнута , известное как конструкция матричного шара .

Строительство

Начиная с перестановки $\sigma \in S_{n}$, записанный в двухстрочной записи , скажем:

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

к этой перестановке можно применить соответствие Робинсона-Шенстеда, получив две таблицы Юнга одинаковой формы, P и Q. стандартные P получается путем выполнения последовательности вставок, а Q представляет собой таблицу записи, указывающую, в каком порядке были заполнены поля.

Построение Вьенно начинается с нанесения точек. $(i,\sigma _{i})$ на плоскости и воображая, что есть свет, который сияет от начала координат, отбрасывая тени прямо вверх и вправо. Это позволяет учитывать точки, которые не затенены какой-либо другой точкой; тогда граница их теней образует первую линию тени. Удалив эти точки и повторив процедуру, получим все теневые линии для этой перестановки. Идея Вьенно состоит в том, что эти теневые линии считывают первые строки P и Q (на самом деле, даже больше; эти теневые линии образуют «временную шкалу», указывающую, какие элементы сформировали первые строки P и Q после последовательных вставок). ). Затем можно повторить построение, используя в качестве новых точек предыдущие непомеченные углы, что позволяет считать остальные строки P и Q .

Анимация

Например, рассмотрим перестановку

$\sigma ={\begin{pmatrix}1&2&3&4&5&6&7&8\\3&8&1&2&4&7&5&6\end{pmatrix}}.$

Тогда конструкция Вьенно выглядит следующим образом:

Приложения

Можно использовать геометрическую конструкцию Вьенно, чтобы доказать, что если $\sigma$ соответствует паре таблиц P , Q при соответствии соответствия Робинсона–Шенстеда, тогда $\sigma ^{-1}$ соответствует коммутируемой Q , P. паре Действительно, взяв $\sigma$ к $\sigma ^{-1}$ отражает конструкцию Вьенно в $y=x$ точно меняет роли P и Q. -ось, и это

См. также

• Пластиковый моноид
• Дразнящая игра

Ссылки

• Брюс Э. Саган . Симметричная группа . Спрингер, 2001.