優位順序

離散数学において、優位順序（同義語：優位順序、マジョライゼーション順序、自然順序）は、正の整数nの分割集合上の半順序であり、代数的組合せ論や表現論、特に対称関数や対称群の表現論の文脈で重要な役割を果たします。

p = ( p ₁ , p ₂ ,...) およびq = ( q ₁ , q ₂ ,...) がnの分割であり、各部分が弱減少順に並んでいる場合、任意のk ≥ 1 について、 pの k 個の最大部分の合計がqのk 個の最大部分の合計以下であれば、優位順序でpはqに先行します。

${\displaystyle p\trianglelefteq q{\text{ }}p_{1}+\cdots +p_{k}\leq q_{1}+\cdots +q_{k}{\text{ すべての }}k\geq 1 に対して }}p_{1}+\cdots +p_{k}\leq q_{1}+\cdots +q_{k}{\text{ の場合に限ります。}$

この定義では、必要に応じて末尾にゼロ部分を追加することでパーティションが拡張されます。

• nの分割のうち、(1,...,1) が最小で、(n) が最大です。
• 優位順序は辞書式順序を意味します。つまり、p がqより優位で、p  ≠  qの場合、 p _i ≠ q _iとなる最小のiに対して、 p _i > q _iが成立します。
• nの分割の poset は、 n ≤ 5 の場合にのみ線形順序付けされます(辞書式順序付けと同等です)。n ≤ 6 の場合にのみ、次数付けされます。例については、右の画像を参照してください。
• パーティションp が パーティションqを覆うための必要十分条件は、すべてのj ≠ i、kに対して、 p _i = q _i + 1 、 p _k = q _k − 1、p _j = q _jであり、(1) k = i + 1 または (2) q _i = q _k (Brylawski、Prop. 2.3) のいずれかである。qのヤング図から始めて、 pのヤング図は、まず行kの最後のボックスを削除し、次に直前の行k − 1 の末尾に追加するか、qのヤング図の行iからkまでがすべて同じ長さである場合は行i < kの末尾に追加することによって得られる。
• すべてのパーティションp には共役（または双対）パーティションp ′があり、そのヤング図はpのヤング図の転置です。この操作により、優位性の順序が逆転します。

${\displaystyle p\trianglelefteq 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 は、ステップ 1 の差分を適用することで、関連付けられた ( n +1) タプルから復元できます。さらに、nのパーティションに関連付けられた( n +1) タプルは、長さn + 1のすべての整数シーケンスの中で、 次の 3 つのプロパティによって特徴付けられます。 ${\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の関連する ( n  + 1) タプルがqの関連する ( n  + 1) タプルより項ごとに小さいか等しい場合に限り、パーティションp はパーティションqに先行します。p、q、r がパーティションである場合、次の場合に限ります。 2 つの非減少凹整数シーケンスの成分ごとの最小値は、非減少かつ凹でもあります。したがって、n、p、qの任意の 2 つのパーティションについて、それらの接合は、関連する ( n  + 1) タプルが成分を持つnのパーティションです。 同様の式を結合に使用するという自然な考えは、2 つの凹シーケンスの成分ごとの最大値が凹である必要はないため、うまくいきません。たとえば、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の任意の 2 つの分割に結合があることを示すには、共役反自己同型を使用します。pとqの結合は、 p ′ とq ′ の交わりの共役分割です。${\displaystyle r\trianglelefteq p,r\trianglelefteq q}$${\displaystyle {\hat {r}}\leq {\hat {p}},{\hat {r}}\leq {\hat {q}}.}$${\displaystyle \operatorname {min} ({\hat {p}}_{i},{\hat {q}}_{i}).}$

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

前の例の2 つのパーティションpとqの場合、それらの共役パーティションは [4,1,1] と [3,3] であり、これらは [3,2,1] と合致し、これは自己共役であるため、 pとqの結合は[3,2,1] になります。

Thomas Brylawski は、最小の高さや最大被覆数など、格子L _nの多くの不変量を決定し、短い長さの区間を分類しました。L n は n ≥ 7 に対して分配的ではありませんが、_分配格子といくつか の特性を共有しています。たとえば、そのメビウス関数は 0、1、-1 の値のみを取ります。

nの分割は、 n 個のボックス上のヤング図によってグラフィカルに表現できます。標準ヤング図は、ヤング図を数字で埋める特定の方法であり、その部分順序 (ヤング図の優位順序と呼ばれることもある) は、ヤング図の優位順序によって定義できます。ヤング図T が別のヤング図Sを支配するには、分割としてTの形状がSの形状を支配している必要があり、さらに、 kの各選択に対して、 TとSが最初に特定の値kまでのエントリを含むサブ図に切り捨てられるときはいつでも、同じことが成り立つ必要があります。

同様に、標準ヤングのビタブル集合にも優位順序があり、これは標準単項式の理論で役割を果たします。

• ヤングの格子
• メジャー化

• マクドナルド、イアン G. (1979)。「セクション I.1」。対称関数とホール多項式。オックスフォード大学出版局。pp. 5–7。ISBN 0-19-853530-9。
• スタンレー、リチャード P. (1999)。列挙的組合せ論。第 2 巻。ケンブリッジ大学出版局。ISBN 0-521-56069-1。
• Brylawski, Thomas (1973). 「整数分割の格子」.離散数学. 6 (3): 201–2. doi : 10.1016/0012-365X(73)90094-0 .