段階的ポセット

数学において、組合せ論の分野における次数付き順序集合は、Pからすべての自然数の集合Nへのランク関数ρを備えた半順序集合(順序集合) Pです。ρは次の 2 つの特性を満たす必要があります。

• ランク関数は順序付けと互換性があり、順序付けされたすべてのxとyについて、 x  <  yであればρ ( x ) <  ρ ( y )であり、
• ランクは順序付けの被覆関係と一致しており、すべてのxとyについて、y がx を被覆する場合、ρ ( y ) =  ρ ( x ) + 1 となります。

poset の要素のランク関数の値は、そのランクと呼ばれます。段階的poset はランク付きposetと呼ばれることもありますが、この語句には他の意味もあります。ランク付きposetを参照してください。段階的poset のランクまたは ランクレベルは、poset のすべての要素のうち、特定のランク値を持つ要素の部分集合です。 ^{[1] [2]}

次数付きポセットは組合せ論において重要な役割を果たし 、ハッセ図によって視覚化することができます。

段階的ポセットの例（ランク関数は括弧内）を以下に示します。

• 自然数Nの通常の順序（階数：数自体）、またはこの半順序集合の区間[0,  N ]
• N ^{n の}積の順序（成分の和）、または区間の積であるその部分集合
• 割り切れる順（重複度で数えた素因数の数）の正の整数、または固定されたNの約数によって形成されるその部分相似集合
• 包含関係（部分集合の要素数）によって順序付けられた集合の有限部分集合のブール格子
• 別の半順序集合の有限下集合の分配格子（要素数）
  • 特に、任意の有限分配格子
• （要素数）上のすべてのラベルなしポセットのポセット^[3]${\displaystyle \{1,...,n\}}$
• ヤングの格子（ヤング図のボックスの数）
• ベクトル空間の部分空間の格子などの任意の幾何学的格子（部分空間の次元）
• 逆細分化（部分数）の順に並べられた、集合を有限個の部分に分割した格子
• 有限集合Xの分割の格子。細分化度（ Xの要素数から部分の数を引いた値）で順序付けられている。
• 凸多面体の面格子（面の次元に1を加えたもの）
• 抽象多面体（最小面からの「距離」から 1 を引いたもの）
• 抽象単体複体（単体の要素数）
• 生成集合、またはそれと同等のケイリーグラフを持つグループで、弱いまたは強いブルハット順序で順序付けられ、単語の長さ（最短の簡約語の長さ） によってランク付けされます。
  • 特にコクセター群、例えば弱または強ブルハ順序（隣接する反転の数）を持つ、完全に順序付けられたn元集合の順列

有界ポセット^[4]は、 P内のすべての極大連鎖が同じ長さである場合にのみ、次数付けを許可します。 ^[5]最小要素のランクを0に設定すると、ランク関数が完全に決定されます。これは多くの興味深い有限ケースをカバーします。負の例については図を参照してください。ただし、非有界ポセットはより複雑になる可能性があります。

候補ランク関数は、順序付けと互換性があり、ランクn + 1 のzでx  <  zがある場合に、ランクnの 要素yがx  ≤  y  <  zで見つかる場合に限り、 poset を次数付き poset にします。この条件は、 z がxの被覆とされる場合、 xとzのランクが 1 異なることを示すy  =  xのみが可能なため十分であり、次数付き poset では、 yに対して、常に存在し、 zによって被覆されるx  ≤  y  <  zの最大ランクの任意の要素を取ることができるため必要です。

多くの場合、poset にはランク関数の自然な候補が伴います。たとえば、その要素が何らかの基本集合Bの有限部分集合である場合、それらの部分集合の要素の数を取ることができます。その場合、先ほど示した基準は、被覆について言及しないため、定義よりも実用的です。たとえば、B自体がposet であり、P がその有限の下側集合(その要素のすべてとともに、より小さな要素もすべて部分集合に含まれる部分集合) で構成されている場合、下側集合x  ⊊  zに対して、 xにはないzの最大要素が常に存在し、それをzから削除してy を形成できるため、基準は自動的に満たされます。

凸多面体の面格子などの一般的な poset には、次元による自然な等級付けがあり、これを階数関数として使用すると、最小の要素である空の面の階数が −1 になります。このような場合、上記の定義を曲げて、階数関数に許可される値の集合に値 −1 を追加すると便利な場合があります。ただし、任意の整数を階数として許可すると、根本的に異なる概念になります。たとえば、最小の要素の存在は保証されなくなります。

次数付き poset (正の整数階数を持つ) は、最大元x を持つ任意に長い連鎖が存在する元x を持つことはできません。そうしないと、任意に小さい (最終的には負の) 階数の元を持つ必要があるためです。たとえば、整数 (通常の順序) は次数付き poset にはなれませんし、有理数または実数の区間 (複数の元を持つ) も次数付き poset にはなれません。(特に、次数付き poset はwell-foundedであり、つまり降順連鎖条件(DCC) を満たします。つまり、無限降順連鎖は含まれません。^[6] ) したがって、今後は、これが起こらない poset のみを検討します。これは、x  <  yの場合は常に、被覆を有限回繰り返し選択することでxからyに到達できることを意味します。また、(正の整数階数関数の場合) ρと順序の互換性は被覆に関する要件に従うことも意味します。次数付き poset の定義の変形として、Birkhoff ^{[7] は}ランク関数が任意の整数値 (非負の値だけではなく) を持つことを許可しています。この変形では、整数は (恒等関数によって) 次数付けすることができ、ランクと順序の互換性は冗長ではありません。3 番目の変形として、Brightwell と West ^{[8] は}ランク関数を整数値であると定義していますが、順序との互換性は要求していません。したがって、この変形では、たとえば実数でも任意の関数で次数付けできます。これは、この例では 被覆に関する要件が空であるためです。

次数付き半順序集合は昇順連鎖条件(ACC)を満たす必要がないことに注意してください。たとえば、自然数には無限の昇順連鎖が含まれます。 ${\displaystyle 0<1<2<\dots }$

poset は、その比較可能性グラフのすべての接続コンポーネントが段階付けされている場合にのみ段階付けされるため、さらに特徴付けると、この比較可能性グラフが接続されていると想定されます。各接続コンポーネントでは、ランク関数は均一なシフトまでのみ一意です (したがって、ランク関数は常に、接続コンポーネント内の最小ランクの要素がランク 0 になるように選択できます)。

P が最小元Ô を持つ場合、等級付けされるということは、任意の元xについて区間[Ô,  x ]内のすべての極大連鎖の長さが同じであるという条件と同等です。この条件が必要なのは、極大連鎖のすべてのステップが被覆関係であり、ランクが 1 ずつ変化するためです。また、この条件が成立する場合、前述の長さを使用してxのランクを定義できるため、条件は十分です(有限連鎖の長さは「ステップ」の数であるため、要素数より 1 少なくなります)。また、x がy を覆う場合は常に、x を[Ô, y ]内の極大連鎖に接続すると、[Ô, x ]内の極大連鎖が生成されます。

Pにも最大元Î がある場合（つまり、 P が有界な posetである場合）、前の条件は、P内のすべての極大連鎖が同じ（有限の）長さを持つという要件に簡略化できます。 [Ô, x ] 内の任意の極大連鎖のペアは [ x , Î]内の極大連鎖によって拡張され、P内の極大連鎖のペアが得られるため、これで十分です。

注記: スタンレーは、すべての極大連鎖の長さが nである場合に、その poset は長さnの次数付きであると定義しています(Stanley 1997、p.99)。この定義は、関心が主に有限 poset にある文脈で与えられており、この本ではその後「長さnの」という部分がしばしば省略されていますが、これを一般 poset の「次数付き」の定義として使用するのは適切ではないと思われます。なぜなら、(1) 最大連鎖が無限である poset については何も述べておらず、特に (2)ヤングの格子のような重要な poset を除外しているからです。また、次数付き poset では、すべての極小要素とすべての極大要素が同じ長さであることが要求される理由も明らかではありません。たとえスタンレーが、そのように要求することを意図していることを示す例を挙げているとしても (同書、pp.216 および 219)。

組合せ論の多くの著者は、Pのすべての最小要素がランク 0 を持つ必要があり、さらに任意の最大要素のランクである最大ランクrが存在するような方法で、次数付き poset を定義します。次に、次数付きであるということは、上記のように、すべての最大チェーンの長さがrであることを意味します。この場合、P はランクr を持つと言えます。

さらに、この場合、ランクレベルにはランク数またはホイットニー数 が関連付けられます。これらの数は、 =ランクi を持つP の要素の数によって定義されます。 ${\displaystyle W_{0},W_{1},W_{2},...}$${\displaystyle W_{i}}$

ホイットニー数は多くの重要な組合せ定理と関連しています。典型的な例はスペルナーの定理で、次のように定式化できます。

あらゆる有限集合の冪集合 について、スペルナー族の最大濃度は最大ホイットニー数に等しくなります。${\displaystyle {\mathcal {P}}(S)}$ ${\displaystyle S}$

これはつまり：

すべての有限冪集合はスペルナー性質を持つ

• 成績評価（数学）
• プレウェル順序付け– ノルムを持つプレウェル順序付けは、整数への写像を順序数への写像に置き換えた、次数付き順序集合に類似している。
• スター積、2つの次数付きポセットを組み合わせる方法

• スタンレー、リチャード(1997)。列挙的組合せ論 (第 1 巻、ケンブリッジ高等数学研究 49)。ケンブリッジ大学出版局。ISBN 0-521-66351-2。
• アンダーソン、イアン（1987）。有限集合の組合せ論。オックスフォード、イギリス：クラレンドン・プレス。ISBN 0-19-853367-5。
• エンゲル、コンラッド (1997)。シュペルナー理論。ケンブリッジ、英国 (他): Cambridge University Press。ISBN 0-521-45206-6。
• クン、ジョセフ PS; Rota, ジャン・カルロ;ヤン、キャサリン H. (2009)。組み合わせ論: ロタ流。ケンブリッジ、英国 (他): Cambridge University Press。ISBN 978-0-521-73794-4。