Порядок доминирования

В дискретной математике порядок доминирования (синонимы: порядок доминирования , порядок мажорирования , естественный порядок ) — частичный порядок на множестве разбиений натурального числа n , играющий важную роль в алгебраической комбинаторике и теории представлений , особенно в контексте симметричных функции и теория представлений симметрической группы .

Определение

Если p = ( p ₁ , p ₂ ,...) и q = ( q ₁ , q ₂ ,...) являются разбиениями n с частями, расположенными в слабо убывающем порядке, то p предшествует q в доминировании порядок, если для любого k ≥ 1 сумма k крупнейших частей p меньше или равна сумме k крупнейших частей q :

p\trianglelefteq q{\text{ if and only if }}p_{1}+\cdots +p_{k}\leq q_{1}+\cdots +q_{k}{\text{ for all }}k\geq 1.

В этом определении разделы расширяются путем добавления нулевых частей в конце по мере необходимости.

Свойства порядка доминирования

Среди разбиений n (1,...,1) является наименьшим, а (n) — самым большим.
Упорядочение по доминированию подразумевает лексикографическое упорядочение , т.е. если доминирует над q и p ≠ q , то для наименьшего i такого, что pi _≠ , qi _i имеем p _i > q _. p
Частный набор разделов n ( линейно упорядочен и эквивалентен лексикографическому упорядочению) тогда и только тогда, когда n ≤ 5. Он градуируется тогда и только тогда, когда n ≤ 6. Пример см. на изображении справа.
Раздел p покрывает раздел q тогда и только тогда, когда p _i = q _i + 1, p _k = q _k - 1, p _j = q _j для всех j ≠ i , k и либо (1) k = i + 1, либо (2) q _i = q _k (Брылавский, предложение 2.3). Начиная с диаграммы Юнга для q , диаграмма Юнга для p получается из нее путем сначала удаления последнего квадрата строки k , а затем добавления его либо к концу непосредственно предшествующей строки k - 1, либо к концу строки i. < k , если все строки с i по k диаграммы Юнга q имеют одинаковую длину.
Каждое разбиение p имеет сопряженное (или двойственное) разбиение p , диаграмма Юнга которого является транспозицией диаграммы Юнга p . Эта операция меняет порядок доминирования:

p\trianglelefteq q

тогда и только тогда, когда

q^{\prime }\trianglelefteq p^{\prime }.

Упорядочение доминирования определяет включения между замыканиями Зарисского классов сопряженных нильпотентных матриц .

Решетчатая структура

Разбиения n образуют решетку с порядком доминирования, обозначаемым L _n , и операция сопряжения является антиавтоморфизмом этой решетки. Чтобы явно описать операции решетки, для каждого раздела p рассмотрим соответствующий ( n + 1)-кортеж :

{\hat {p}}=(0,p_{1},p_{1}+p_{2},\ldots ,p_{1}+p_{2}+\cdots +p_{n}).

Раздел p можно восстановить из связанного с ним ( n +1)-кортежа, применив разность шага 1 : $p_{i}={\hat {p}}_{i}-{\hat {p}}_{i-1}.$ Более того, ( n +1)-кортежи, связанные с разбиениями n, + 1 характеризуются среди всех целочисленных последовательностей длины n следующими тремя свойствами:

Неубывающая, ${\hat {p}}_{i}\leq {\hat {p}}_{i+1};$
Вогнутая, $2{\hat {p}}_{i}\geq {\hat {p}}_{i-1}+{\hat {p}}_{i+1};$
Начальный член равен 0, а последний член — n , ${\hat {p}}_{0}=0,{\hat {p}}_{n}=n.$

По определению порядка доминирования, раздел p предшествует разделу q тогда и только тогда, когда ассоциированный ( n + 1)-кортеж p почленно меньше или равен ассоциированному ( n + 1)-кортежу q. . Если p , q , r являются разделами, то $r\trianglelefteq p,r\trianglelefteq q$ тогда и только тогда, когда ${\hat {r}}\leq {\hat {p}},{\hat {r}}\leq {\hat {q}}.$ Покомпонентный минимум двух неубывающих вогнутых целочисленных последовательностей также является неубывающим и вогнутым. Следовательно, для любых двух разделов n , p и q их пересечением является раздел n, связанный с ним ( n + 1)-кортеж имеет компоненты $\operatorname {min} ({\hat {p}}_{i},{\hat {q}}_{i}).$ Естественная идея использовать аналогичную формулу для соединения терпит неудачу , поскольку покомпонентный максимум из двух вогнутых последовательностей не обязательно должен быть вогнутым. Например, для n = 6 разделам [3,1,1,1] и [2,2,2] соответствуют последовательности (0,3,4,5,6,6,6) и (0,2 ,4,6,6,6,6), покомпонентный максимум которого (0,3,4,6,6,6,6) не соответствует ни одному разбиению. Чтобы показать, что любые два раздела n имеют соединение, используется антиавтоморфизм сопряжения: соединение p и q является сопряженным разбиением пересечения p ′ и q ′:

p\lor q=(p^{\prime }\land q^{\prime })^{\prime }.

Для двух разделов p и q в предыдущем примере их сопряженными разделами являются [4,1,1] и [3,3] с пересечением [3,2,1], которое является самосопряженным; следовательно, соединение p и q равно [3,2,1].

Томас Брылавски определил многие инварианты решетки L _n , такие как минимальная высота и максимальное число покрытия, и классифицировал интервалы малой длины. Хотя L _n не является дистрибутивной при n ≥ 7, она разделяет некоторые свойства с дистрибутивными решетками: например, ее функция Мёбиуса принимает только значения 0, 1, −1.

Обобщения

Разделы n могут быть графически представлены диаграммами Юнга на n блоках.Стандартные таблицы Юнга — это определенные способы заполнения диаграмм Юнга числами, и частичный порядок в них (иногда называемый порядком доминирования в таблицах Юнга ) может быть определен в терминах порядка доминирования на диаграммах Юнга. Чтобы таблица Юнга T доминировала над другой таблицей Юнга S , форма T должна доминировать над формой S как разбиения, и, более того, то же самое должно выполняться всякий раз, когда T и S сначала усекаются до своих подтаблиц, содержащих записи до заданного значения. k для каждого выбора k .

Точно так же существует порядок доминирования на множестве стандартных битограмм Юнга, который играет роль в теории стандартных мономов .

См. также

Ссылки

Макдональд, Ян Г. (1979). «раздел I.1». Симметричные функции и полиномы Холла . Издательство Оксфордского университета. стр. 5–7. ISBN 0-19-853530-9 .
Стэнли, Ричард П. (1999). Перечислительная комбинаторика . Том. 2. Издательство Кембриджского университета. ISBN 0-521-56069-1 .
Брылавски, Томас (1973). «Решетка целочисленных разбиений» . Дискретная математика . 6 (3): 201–2. дои : 10.1016/0012-365X(73)90094-0 .