Objednávka dominance - Dominance order

Příklad uspořádání dominance oddíly z n. Tady, n = 6, uzly jsou oddíly 6, hrany označují, že horní uzel dominuje spodnímu uzlu. Zatímco toto konkrétní částečné objednání je odstupňované, toto neplatí pro uspořádání dominance na oddílech libovolného číslan > 6.

v diskrétní matematika, pořadí dominance (synonyma: uspořádání dominance, objednávka majorizace, přirozené objednávání) je částečná objednávka na množině oddíly kladného celého čísla n která hraje důležitou roli v algebraická kombinatorika a teorie reprezentace, zejména v kontextu symetrické funkce a teorie reprezentace symetrické skupiny.

Definice

Li str = (str₁,str₂,…) a q = (q₁,q₂, ...) jsou oddíly n, s částmi uspořádanými ve slabě sestupném pořadí str předchází q v pořadí dominance, pokud existuje k ≥ 1, součet k největší části str je menší nebo roven součtu k největší části q:

{displaystyle p rianglelefteq q {ext {pokud a jen tehdy}} p_ {1} + cdots + p_ {k} leq q_ {1} + cdots + q_ {k} {ext {pro všechny}} kgeq 1.}

V této definici jsou oddíly rozšířeny připojením nulových částí na konec podle potřeby.

Vlastnosti uspořádání dominance

Mezi oddíly n, (1, ..., 1) je nejmenší a (n) je největší.
Z uspořádání dominance vyplývá lexikografické objednávání, tj. pokud str dominuje q a str ≠ q, pak pro nejmenší i takhle str_i ≠ q_i jeden má str_i > q_i.
Poset oddílů n je lineárně uspořádáno (a je ekvivalentní lexikografickému řazení) právě tehdy n ≤ 5. Je odstupňované kdyby a jen kdyby n ≤ 6. Příklad najdete na obrázku vpravo.
Oddíl str kryty oddíl q kdyby a jen kdyby str_i = q_i + 1, str_k = q_k − 1, str_j = q_j pro všechny j ≠ i,k a buď (1) k = i + 1 nebo (2) q_i = q_k (Brylawski, prop. 2.3). Počínaje Mladý diagram z q, Youngův diagram z str se z ní získá odebráním posledního pole řádku k a poté jej připojit buď na konec bezprostředně předcházejícího řádku k - 1, nebo na konec řádku i < k pokud řádky i přes k mladého diagramu q všechny mají stejnou délku.
Každý oddíl str má sdružené (nebo duální) oddíl str′, Jehož Youngův diagram je transpozicí Youngova diagramu z str. Tato operace obrací pořadí dominance:

{displaystyle p rianglelefteq q}

kdyby a jen kdyby

{displaystyle q ^ {prime} rianglelefteq p ^ {prime}.}

Pořadí dominance určuje inkluze mezi Zariski uzávěry tříd konjugace nilpotentní matice.

Příhradová struktura

Příčky n tvoří a mříž pod objednávkou dominance, označeno L_na operace konjugace je antiautomorfismus této mřížky. Chcete-li explicitně popsat mřížkové operace, pro každý oddíl str zvážit přidružené (n + 1) -tuple:

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

Oddíl str lze obnovit z přidruženého (n+1) -tuple použitím kroku 1 rozdíl, ${displaystyle p_ {i} = {hat {p}} _ {i} - {hat {p}} _ {i-1}.}$ Navíc (n+1) - n-tice spojené s oddíly n jsou charakterizovány mezi všemi celočíselnými sekvencemi délky n +1 o následující tři vlastnosti:

Neklesající, ${displaystyle {hat {p}} _ {i} leq {hat {p}} _ {i + 1};}$
Konkávní, ${displaystyle 2 {hat {p}} _ {i} geq {hat {p}} _ {i-1} + {hat {p}} _ {i + 1};}$
Počáteční termín je 0 a poslední termín je n, ${displaystyle {hat {p}} _ {0} = 0, {hat {p}} _ {n} = n.}$

Podle definice uspořádání dominance, rozdělení str předchází oddílu q jen a jen v případě, žen + 1) -tuple of str je termín po termínu menší nebo roven přidruženému (n + 1) -tuple of q. Li str, q, r jsou tedy oddíly ${displaystyle r rianglelefteq p, r rianglelefteq q}$ kdyby a jen kdyby ${displaystyle {hat {r}} leq {hat {p}}, {hat {r}} leq {hat {q}}.}$ Minimálně po částech dvou neklesajících konkávních celočíselných sekvencí je také neklesající a konkávní. Proto pro jakékoli dva oddíly n, str a q, jejich setkat je oddíl n jehož přidružené (n + 1) -tuple má komponenty ${displaystyle operatorname {min} ({hat {p}} _ {i}, {hat {q}} _ {i}).}$ Přirozený nápad použít podobný vzorec pro připojit se selže, protože komponentní maximum dvou konkávních sekvencí nemusí být konkávní. Například pro n = 6, oddíly [3,1,1,1] a [2,2,2] mají přidružené sekvence (0,3,4,5,6,6,6) a (0,2,4,6, 6,6,6), jehož komponentní maximum (0,3,4,6,6,6,6) neodpovídá žádnému oddílu. Chcete-li ukázat, že jakékoli dva oddíly n mít spojení, jeden používá konjugační antiautomorfismus: spojení str a q je konjugovaný oddíl setkání str' a q′:

{displaystyle plor q = (p ^ {prime} land q ^ {prime}) ^ {prime}.}

Pro dva oddíly str a q v předchozím příkladu jsou jejich konjugované oddíly [4,1,1] a [3,3] s meet [3,2,1], což je samo-konjugát; proto spojení str a q je [3,2,1].

Thomas Brylawski určila mnoho invarianty mřížky L_n, jako je minimální výška a maximální počet krytí, a klasifikoval intervaly malé délky. Zatímco L_n není distribuční pro n ≥ 7, sdílí některé vlastnosti s distribučními mřížemi: například jeho Möbiova funkce přebírá pouze hodnoty 0, 1, −1.

Zobecnění

Pořadí dominance na Young tableaux pro oddíl 6 = 4 + 2

Příčky n lze graficky znázornit pomocí Mladé diagramy na n krabice. standardní Mladé obrazy jsou určité způsoby, jak vyplnit Youngovy diagramy čísly a částečným pořadím na nich (někdy se tomu říká pořadí dominance na Young tableaux) lze definovat z hlediska pořadí dominance na Youngových diagramech. Pro mladé tablo T ovládnout další Young tablo S, tvar T musí dominovat tomu S jako oddíl a navíc to samé musí vždy platit T a S jsou nejprve zkráceny do svých dílčích obrazů obsahujících položky až do dané hodnoty k, pro každou volbu k.

Podobně existuje pořadí dominance na souboru standardních Young bitableaux, který hraje roli v teorii standardní monomials.

Viz také

Reference

Ian G. Macdonald, Symetrické funkce a Hallovy polynomy, Oxford University Press, 1979, ISBN 0-19-853530-9 (Viz část I.1, s. 5–7)
Richard P. Stanley, Enumerativní kombinatorika, Díl 2. Cambridge University Press, 1999 ISBN 0-521-56069-1
Thomas Brylawski, Mřížka celočíselných oddílů, Discrete Mathematics, roč. 6, č. 3, 1973, s. 201–219