注文ディメンション

数学において、半順序集合(poset)の次元とは、その交差によって半順序が生じる全順序の最小の数です。この概念は、半順序の順序次元またはDushnik–Miller 次元と呼ばれることもあります。Dushnik と Miller (1941) が最初に順序次元を研究しました。この主題に関する、ここでの説明よりも詳しい説明については、Trotter (1992) を参照してください。

半集合Pの次元は、族が存在する 最小の整数tである。

${\displaystyle {\mathcal {R}}=(<_{1},\dots ,<_{t})}$

Pの線型拡張の任意のxとyに対して、Pでxがyに先行するのは、すべての線型拡張でx がy に先行する場合のみである。つまり 、

${\displaystyle P=\bigcap {\mathcal {R}}=\bigcap _{i=1}^{t}}.}$

順序次元の別の定義は、P が成分ごとの順序付けで積に埋め込まれるような合計順序数の最小値、つまりすべてのiに対してとなる場合のみです(Hiraguti 1955、Milner & Pouzet 1990)。 ${\displaystyle x\leq y}$${\displaystyle x_{i}\leq y_{i}}$

X上の線型順序族は、次の場合、等式集合P = ( X , < _P ) の実現子と呼ばれる。${\displaystyle {\mathcal {R}}=(<_{1},\dots ,<_{t})}$

${\displaystyle <_{P}=\bigcap {\mathcal {R}}}$、

つまり、Xの任意のxとyに対して、 x < ₁ y、x < ₂ y、...、x < _t yのときに、 x < _P yとなります。したがって、 poset Pの次元の同等の定義は、 「 Pの実現子の最小の濃度」です。

線型拡大の任意の空でない族R は、有限半順序集合Pの実現子であるためには、Pのすべての臨界ペア( x、y )に対して、 R内の何らかの順序 < _iに対してy < _i x が成立することが示される。

n を正の整数とし、P を要素a _iおよびb _i (1 ≤ i ≤ n ) の部分順序とします。この部分順序において、 i ≠ j の場合は常にa _i ≤ b _jとなりますが、他のペアは比較できません。特に、a _iとb _{i は}Pでは比較できません。P はクラウングラフの有向形式と見なすことができます。図は、 n = 4の場合のこのタイプの順序を示しています。

すると、各iについて、どの実現子も、 a _{i を}除くすべてのa _jで始まり(ある順序で)、b _i、a _iを含み、残りのすべてのb _jで終わる線形順序を含んでいなければなりません。これは、そのような順序を含まない実現子があった場合、その実現子の順序の共通部分ではa _{i が}b _iに先行することになり、 Pにおけるa _iとb _iの比較不可能性と矛盾するからです。また逆に、各iについてこのタイプの順序を 1 つ含む線形順序の族は、共通部分としてP を持ちます。したがって、 P の次元はちょうどnです。実際、P は次元nの poset の標準的な例として知られており、通常はS _nと表記されます。

順序次元が 2 の部分順序は、比較可能性グラフが別の部分順序の比較可能性グラフの補グラフである部分順序として特徴付けられる (Baker、Fishburn、Roberts 1971)。つまり、 Pが順序次元が 2 の部分順序である場合、かつその場合のみ、同じ要素の集合に部分順序Qが存在し、異なる要素のすべてのペアx、yがこれら 2 つの部分順序のどちらか一方において比較可能である。P が2 つの線形拡張によって実現される場合、Pを補完する部分順序Q は、 2 つの線形拡張のいずれかを逆にすることで実現できる。したがって、次元が 2 の部分順序の比較可能性グラフは、まさに順列グラフであり、グラフ自体が比較可能性グラフであり、比較可能性グラフを補完するグラフである。

順序次元 2 の半順序には、直列並列半順序(Valdes、Tarjan、Lawler 1982) が含まれます。これらは、ハッセ図に優位描画がある半順序とまったく同じであり、実現子の 2 つの順列の位置を直交座標として使用して取得できます。

たとえば、半順序の比較可能性グラフが順列グラフであるかどうかをテストすることによって、与えられた有限半順序集合の順序次元が最大で 2 であるかどうかを多項式時間で判定することができます。ただし、任意のk ≥ 3 に対して、順序次元が最大でkであるかどうかをテストすることはNP 完全 です(Yannakakis 1982)。

任意の無向グラフGの接続ポセットは、 Gの頂点と辺を要素として持ちます。このポセットでは、x = yまたはxが頂点、yが辺、x がyの端点である場合、 x ≤ yです。ある種のグラフは、接続ポセットの順序次元によって特徴付けられる場合があります。接続ポセットの順序次元が最大で 2 の場合に限り、グラフはパス グラフであり、シュナイダーの定理によれば、接続ポセットの順序次元が最大で 3 の場合に限り、 グラフは平面グラフです(Schnyder 1989)。

n頂点の完全グラフの場合、接続ポーズトの順序次元は(Hoşten & Morris 1999) です。したがって、すべての単純なn頂点グラフには、順序次元の接続ポーズトがあります。 ${\displaystyle \Theta (\log \log n)}$${\displaystyle O(\log \log n)}$

次元の一般化はk次元（ と表記）の概念であり、これは、部分順序を積に埋め込むことができる長さが最大でkの連鎖の最小数です。特に、順序の 2 次元は、順序がこの集合の 包含順序に埋め込まれる最小の集合のサイズとして考えることができます。${\displaystyle {\textrm {dim}}_{k}}$

• 間隔次元

• ベイカー、KA;フィッシュバーン、P .;ロバーツ、FS (1971)、「2次元の部分順序」、ネットワーク、2 (1): 11–28、doi :10.1002/net.3230020103。
• ダシュニク、ベン; ミラー、EW (1941)、「部分順序集合」、アメリカ数学誌、63 (3): 600–610、doi :10.2307/2371374、JSTOR  2371374。
• 平口俊雄 (1955)、「順序の次元について」(PDF)、金沢大学学術報告、4 (1): 1–20、MR  0077500。
• Hoşten, Serkan; Morris, Walter D. Jr. (1999)、「完全グラフの順序次元」、離散数学、201 (1–3): 133–139、doi : 10.1016/S0012-365X(98)00315-X、MR  1687882。
• ミルナー、EC; プーゼット、M. (1990)、「ポセットの次元に関する注記」、Order、7 (1): 101–102、doi :10.1007/BF00383178、MR  1086132、S2CID  123485792。
• シュナイダー、W. (1989)、「平面グラフとポセット次元」、Order、5 (4): 323–343、doi :10.1007/BF00353652、S2CID  122785359。
• トロッター、ウィリアム・T.（1992）、組合せ論と部分順序集合：次元理論、ジョンズ・ホプキンス数学シリーズ、ジョンズ・ホプキンス大学出版局、ISBN 978-0-8018-4425-6。
• Valdes, Jacobo; Tarjan, Robert E .; Lawler, Eugene L. (1982)、「直列並列ダイグラフの認識」、SIAM Journal on Computing、11 (2): 298–313、doi :10.1137/0211023。
• ヤンナカキス、ミハリス(1982)、「半順序次元問題の複雑さ」、SIAM Journal on Algebraic and Discrete Methods、3 (3): 351–358、doi :10.1137/0603036。