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

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

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

${\displaystyle p\trianglelefteq q{\text{ тогда и только тогда, когда }}p_{1}+\cdots +p_{k}\leq q_{1}+\cdots +q_{k}{\text{ для всех }}k\geq 1.}$

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

• Среди разбиений n наименьшим является (1,...,1), а наибольшим — (n).
• Упорядочение по доминированию подразумевает лексикографическое упорядочение , т.е. если p доминирует над q и p  ≠  q , то для наименьшего i, такого что p _i ≠ q _{i ,} имеем p _i > q _i .
• Посет разбиений 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 . Эта операция меняет порядок доминирования:

${\displaystyle p\треугольниклевыйq q}$если и только если${\displaystyle q^{\prime }\trianglelefteq p^{\prime }.}$

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

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

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

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

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

По определению порядка доминирования раздел p предшествует разделу q тогда и только тогда, когда ассоциированный ( n  + 1)-кортеж p почленно меньше или равен ассоциированному ( n  + 1)-кортежу q . Если p , q , r — разделы, то тогда и только тогда, когда Покомпонентный минимум двух неубывающих вогнутых целочисленных последовательностей также является неубывающим и вогнутым. Следовательно, для любых двух разделов n , p и q их встреча — это раздел n , ассоциированный ( n  + 1)-кортеж которого имеет компоненты. Естественная идея использовать аналогичную формулу для соединения терпит неудачу , поскольку покомпонентный максимум двух вогнутых последовательностей не обязательно должен быть вогнутым. Например, для 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 ′:${\displaystyle r\треугольниклевый_треугольник p,r\треугольниклевый_треугольник q}$${\displaystyle {\hat {r}}\leq {\hat {p}},{\hat {r}}\leq {\hat {q}}.}$${\displaystyle \operatorname {мин} ({\hat {p}}_{i},{\hat {q}}_{i}).}$

${\displaystyle 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 .

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

• решетка Юнга
• Мажоризация

• Macdonald, Ian G. (1979). "раздел I.1". Симметричные функции и многочлены Холла . Oxford University Press. стр. 5–7. ISBN 0-19-853530-9.
• Стэнли, Ричард П. (1999). Перечислительная комбинаторика. Том 2. Cambridge University Press. ISBN 0-521-56069-1.
• Brylawski, Thomas (1973). "Решетка целочисленных разбиений". Discrete Mathematics . 6 (3): 201–2. doi : 10.1016/0012-365X(73)90094-0 .