Геометрическая конструкция венноц - Viennots geometric construction - Wikipedia

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

Конструкция

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

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

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

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

Анимация

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

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

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

Приложения

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

Смотрите также

• Plactic monoid
• Jeu de Taquin

Рекомендации

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