間隔順序

数学、特に順序論において、実数直線上の区間の集合に対する区間順序は、それらの左から右への優先関係に対応する半順序です。つまり、ある区間I _{1は、別の区間}I ₂よりも小さいと見なされるのは、I _{1 が}I ₂の完全に左側にある場合です。より正式には、可算な半 順序集合 が区間順序であるためには、 から実数区間の集合への一対一写像が存在する必要があり、したがって の場合に限ります。 任意のに対して、のときちょうどでが成り立ちます 。${\displaystyle P=(X,\leq )}$${\displaystyle X}$${\displaystyle x_{i}\mapsto (\ell _{i},r_{i})}$${\displaystyle x_{i},x_{j}\in X}$${\displaystyle x_{i}$${\displaystyle P}$${\displaystyle r_{i}$

このような poset は、2 元チェーンのペアに同型な誘導部分 poset を持たないもの、つまり -free poset として同等に特徴付けられる場合があります。^[1]完全に書き出すと、これは、任意の 2 組の元とに対して、またはがなければならないことを意味します。 ${\displaystyle (2+2)}$${\displaystyle a>b}$${\displaystyle c>d}$${\displaystyle a>d}$${\displaystyle c>b}$

区間を単位長さの区間に制限して、すべての区間が という形式になるようにすることで得られる区間順序のサブクラスは、まさに半順序です。 ${\displaystyle (\ell _{i},\ell _{i}+1)}$

区間順序 ( , ≤)の比較可能性グラフの補グラフは区間グラフです。 ${\displaystyle X}$ ${\displaystyle (X,\cap )}$

区間順序は、実数直線上の区間の包含順序（つまり、次元≤ 2 の順序）である区間包含順序と混同しないでください。

間隔順序の実際的な応用としては、種の進化のモデル化や陶器の様式の考古学的歴史などがある。^{[2] [例が必要]}

半順序の重要なパラメータは順序次元である。半順序の次元は、交差が である線形順序の最小の数である。区間順序の場合、次元は任意の大きさにすることができる。一般的な半順序の次元を決定する問題はNP困難であることが知られているが、区間順序の次元を決定する問題は計算複雑性が不明な問題である。^[3]${\displaystyle P}$${\displaystyle P}$

関連するパラメータとして、区間次元があります。これは同様に定義されますが、線形順序ではなく区間順序で定義されます。したがって、部分順序集合の区間次元は、および のときに上の区間順序が存在する最小の整数です。順序の区間次元は、順序次元よりも大きくなることはありません。^[4]${\displaystyle P=(X,\leq )}$ ${\displaystyle k}$${\displaystyle \preceq _{1},\ldots ,\preceq _{k}}$${\displaystyle X}$${\displaystyle x\leq y}$${\displaystyle x\preceq _{1}y,\ldots ,}$${\displaystyle x\preceq _{k}y}$

自由半集合と同型であることに加えて、 上のラベルなし区間順序は、濃度 の順序 付き集合上の固定小数点自由反転のサブセットとも一対一である 。^[5] これらは、いわゆる左隣接または右隣接の入れ子を持たない反転であり、 上の任意の反転について 、左の入れ子は となるような であり、右の入れ子は となるような で ある。 ${\displaystyle (2+2)}$${\displaystyle [n]}$ ${\displaystyle 2n}$${\displaystyle f}$${\displaystyle [2n]}$${\displaystyle i\in [2n]}$${\displaystyle i<i+1<f(i+1)<f(i)}$${\displaystyle i\in [2n]}$${\displaystyle f(i)<f(i+1)<i<i+1}$

このような反転は、半長に応じて、通常の生成関数を持つ^[6]

${\displaystyle F(t)=\sum _{n\geq 0}\prod _{i=1}^{n}(1-(1-t)^{i}).}$

の展開におけるの係数は、大きさ のラベルなし区間順序の数を与える。これらの数の列（OEISの列A022493） は、${\displaystyle t^{n}}$${\displaystyle F(t)}$${\displaystyle n}$

1、2、5、15、53、217、1014、5335、31240、201608、1422074、10886503、89903100、796713190、7541889195、75955177642、…

• Bousquet-Mélou, Mireille ; Claesson, Anders; Dukes, Mark; Kitaev, Sergey (2010)、「(2+2) 自由ポセット、上昇シーケンス、およびパターン回避順列」、Journal of Combinatorial Theory、シリーズ A、117 (7): 884–909、arXiv : 0806.0666、doi :10.1016/j.jcta.2009.12.007、MR  2652101、S2CID  8677150。
• Felsner, S. (1992)、Interval Orders: Combinatorial Structure and Algorithms (PDF)、Ph.D.ベルリン工科大学博士論文。
• Felsner, S.; Habib, M.; Möhring, RH (1994)、「区間次元と次元の相互作用について」(PDF)、SIAM Journal on Discrete Mathematics、7 (1): 32–40、doi :10.1137/S089548019121885X、MR  1259007。
• フィッシュバーン、ピーター C. (1970)、「不等無差別区間を持つ非推移的無差別」、数学心理学ジャーナル、7 (1): 144–149、doi :10.1016/0022-2496(70)90062-3、MR  0253942。
• ザギエ、ドン（2001）、「ヴァシリエフ不変量とデデキントイータ関数に関連する奇妙な恒等式」、トポロジー、40（5）：945–960、doi：10.1016/s0040-9383（00）00005-7、MR  1860536。
• Davey, BA; Priestley, HA (2002) [1990].格子と秩序入門（第2版）. ケンブリッジ大学出版局. ISBN 9780521784511。

• フィッシュバーン、ピーター（1985）、区間順序と区間グラフ：部分順序集合の研究、ジョン・ワイリー