Дразнящая игра

В математической области комбинаторики ) , jeu de taquin — это конструкция Марселя-Поля Шютценбергера ( 1977 которая определяет отношение эквивалентности на множестве асимметричных стандартных таблиц Юнга . Слайд «Игры с такином» — это трансформация, при которой числа в таблице перемещаются аналогично тому, как движутся части головоломки « Пятнадцать» . Две таблицы эквивалентны jeu de taquin, если одну можно преобразовать в другую с помощью последовательности таких слайдов.

«Jeu de taquin» (буквально «дразнящая игра») — французское название головоломки «пятнадцать» .

Определение слайд-дразнящей игры

Учитывая перекос стандартной таблицы Юнга T косой формы $\lambda /\mu$ , выберите соседнюю пустую ячейку c , которую можно добавить на диаграмму перекоса $\lambda \setminus \mu$ ; это означает, что c должно иметь общее хотя бы одно ребро с некоторой ячейкой в T и $\{c\}\cup \lambda \setminus \mu$ также должна быть диаграмма перекоса. Существует два типа слайда, в зависимости от того, находится ли c слева вверху от T или справа внизу. Предположим для начала, что c лежит вверху слева. Переместите число из соседней ячейки в c ; если у c есть соседи как справа, так и снизу, то выберите наименьшее из этих двух чисел, отдав предпочтение нижнему. (Это правило разработано таким образом, чтобы сохранялось свойство таблицы, заключающееся в увеличении числа строк и столбцов.) Если у только что опустошенной ячейки нет соседей справа или снизу, то слайд считается завершенным. В противном случае вставьте число в эту ячейку по тому же правилу, что и раньше, и продолжайте таким же образом, пока слайд не будет завершен. После этого преобразования результирующая таблица (с удалением теперь уже пустой ячейки) по-прежнему представляет собой косую (или, возможно, прямую) стандартную таблицу Юнга.

Другой вид слайда, когда c находится справа внизу от T , просто движется в противоположном направлении. В этом случае в пустую ячейку помещаются числа от соседа слева или сверху, выбирая большее число всякий раз, когда есть выбор. Два типа слайдов взаимно обратны: слайд одного типа можно отменить, используя слайд другого типа.

Два слайда, описанные выше, называются слайдами в ячейку c . Первый вид скольжения (когда c лежит вверху слева от T ) называется скольжением внутрь ; второй вид называется скольжением наружу .

Слово «слайд» является синонимом французского слова «glissement», которое иногда также используется в английской литературе.

Тонкости

Слайды «Же-де-Такен» меняют не только относительный порядок элементов таблицы, но и ее форму. В приведенном выше определении результат слайда jeu-de-taquin представлен в виде диаграммы перекоса вместе со стандартной таблицей перекоса, имеющей ее в качестве формы. Зачастую лучше работать с перекошенными фигурами, а не с перекошенными диаграммами. (Напомним, что каждая перекошенная форма $\lambda /\mu$ приводит к перекосу диаграммы $\lambda \setminus \mu$ , но это не инъективное соответствие, потому что, например, отчетливые формы перекоса $(2,1)/(2)$ и $(1,1)/(1)$ дают ту же самую диаграмму перекоса.) По этой причине полезно изменить приведенное выше определение слайда «же-де-такен» таким образом, чтобы при задании формы перекоса вместе со стандартной таблицей перекоса и добавляемой ячейкой в качестве на входе он дает четко определенную форму асимметрии вместе со стандартной таблицей асимметрии на выходе. Это делается следующим образом: Скольжение внутрь наклонной таблицы T косой формы. $\lambda /\mu$ в ячейку c определяется, как указано выше, когда c является углом $\mu$ (то есть когда $\mu \setminus \left\{c\right\}$ является диаграммой Юнга), а результирующая форма асимметрии устанавливается равной $(\lambda \setminus \left\{d\right\})/(\mu \setminus \left\{c\right\})$ где d — пустая ячейка в конце процедуры скольжения. Скольжение перекошенной таблицы T перекошенной формы наружу. $\lambda /\mu$ в ячейку c определяется, как указано выше, когда c является уголком $\lambda$ (то есть когда $\lambda \cup \left\{c\right\}$ является диаграммой Юнга), а результирующая форма асимметрии устанавливается равной $(\lambda \cup \left\{c\right\})/(\mu \cup \left\{d\right\})$ где d — пустая ячейка в конце процедуры скольжения.

Обобщение для искажения полустандартных таблиц

Слайды Jeu de Taquin обобщаются, искажая полустандартные (в отличие от искажающих стандартные) таблицы и сохраняя большую часть своих свойств в этой общности. Единственное изменение, которое необходимо внести в определение внутреннего слайда, чтобы оно обобщалось, — это правило о том, как действовать, когда (временно) пустая ячейка имеет соседей снизу и справа от нее, и эти соседи заполнены. с равными числами. В этой ситуации соседа снизу (а не того, что справа) нужно вставить в пустую ячейку. Аналогичное изменение необходимо и в определении скольжения наружу (где нужно выбрать соседа выше). Эти изменения могут показаться произвольными, но на самом деле они делают «единственно разумный выбор» — то есть единственный выбор, который обеспечивает строгое увеличение столбцов таблицы (без учета пустой ячейки) (а не просто слабое увеличение).

Исправление

Учитывая наклонную стандартную или полустандартную таблицу T , можно итеративно применять внутренние слайды к T до тех пор, пока таблица не станет прямой (что означает, что внутренние слайды больше невозможны). Обычно это можно сделать разными способами (можно свободно выбирать, в какую ячейку скользить первой), но известно, что результирующая таблица прямой формы одинакова для всех возможных вариантов. называется выпрямлением T Эта таблица .

игра-дразнилка на эквивалентность

Две косые полустандартные таблицы T и S называются игровыми эквивалентами , если можно преобразовать одну из них в другую, используя последовательность (возможно, пустую) слайдов (допускаются как внутренние, так и внешние слайды). Эквивалентно, две косые полустандартные таблицы T и S эквивалентны в игре тогда и только тогда, когда они имеют одно и то же исправление.

Чтение слов и эквивалентность Кнута

Существуют различные способы связать слово (в смысле комбинаторики, т. е. конечную последовательность элементов алфавита — здесь набор натуральных чисел) с каждой таблицей Юнга. Мы выбираем тот, который, по-видимому, наиболее популярен: мы связываем с каждой таблицей Янга T слово, полученное путем объединения строк T из нижней строки в верхнюю строку. (Каждая строка T рассматривается как слово, просто читая ее записи слева направо, и мы рисуем таблицы Янга в английских обозначениях так, чтобы самая длинная строка таблицы прямой формы находилась вверху.) Это слово будет упоминаться. to как слово для чтения кратко слово Т. или как

Затем можно показать, что две косые полустандартные таблицы T и S эквивалентны по игре в игре тогда и только тогда, когда слова чтения T и S эквивалентны по Кнуту . Как следствие, исправление перекошенной полустандартной таблицы T также может быть получено как таблица вставки считывающего слова T в соответствии с соответствием Робинсона-Шенстеда .

Инволюция Шютценбергера

Jeu de taquin можно использовать для определения операции над стандартными таблицами Юнга любой заданной формы, которая оказывается инволюцией , хотя это не очевидно из определения. Начинаем с очистки квадрата в верхнем левом углу, превращая таблицу в перекошенную, в которой на один квадрат меньше. Теперь примените слайд jeu de taquin, чтобы превратить эту наклонную таблицу в прямую, что освободит один квадрат на внешней границе. Затем заполните этот квадрат отрицательным значением, которое изначально было удалено в верхнем левом углу; это отрицательное значение считается частью новой таблицы, а не исходной таблицы, и его положение не изменится в дальнейшем. Теперь, пока в исходной таблице осталось несколько записей, повторите операцию удаления записи x из верхнего левого угла, выполнения слайда jeu de taquin на том, что осталось от исходной таблицы, и помещения значения − x в квадрат таким образом освободился. Когда все записи исходной таблицы обработаны, их отрицательные значения располагаются таким образом, что строки и столбцы увеличиваются. Наконец, можно добавить подходящую константу ко всем записям, чтобы получить таблицу Юнга с положительными записями.

Приложения

Jeu de taquin тесно связана с такими темами, как соответствие Робинсона-Шенстеда-Кнута , правило Литтлвуда-Ричардсона и эквивалентность Кнута .

Ссылки

Дезармениен, Ж. (2001) [1994], «Дразнила игра» , Энциклопедия математики , EMS Press
Саган, Брюс Э. (2001), Симметричная группа: представления, комбинаторные алгоритмы и симметричные функции , Тексты для аспирантов по математике 203 (2-е изд.), Нью-Йорк: Springer, ISBN 0-387-95067-2
Фултон, Уильям (1997), Young Tableaux , Тексты студентов Лондонского математического общества 35 (1-е изд.), Мельбурн: Cambridge University Press, ISBN 0-521-56144-2
Хайман, доктор медицины (1992). «Двойная эквивалентность с приложениями, включая гипотезу Проктора» . Дискретная математика . 99 : 79–113. дои : 10.1016/0012-365X(92)90368-P .
Шютценбергер, Марсель-Поль (1977), «Переписка Робинсона», в Фоате, Доминике (редактор), Комбинаторика и представление симметричной группы (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Страсбург, 1976) , Чтение заметок по математике, вып. 579, Берлин: Шпрингер, стр. 59–113 , номер домена : 10.1007/BFb0090012 , ISBN. 978-3-540-08143-2

Стэнли, Ричард П. (1999), Перечислительная комбинаторика , Кембриджские исследования по высшей математике 62, том. 2, Издательство Кембриджского университета, ISBN 0-521-56069-1