ディルワースの定理

数学の順序論と組合せ論の分野におけるディルワースの定理は、任意の有限半順序集合において、比較不可能な要素の反鎖の最大サイズは、すべての要素をカバーするために必要な鎖の最小数に等しいことを述べています。この数は半順序の幅と呼ばれます。この定理は、1950年に発表した数学者ロバート・P・ディルワースにちなんで名付けられました。 ^[1]

無限部分順序集合の定理のバージョンは、有限個のチェーンへの分解が存在する場合、または反チェーンのサイズに有限の上限が存在する場合、最大の反チェーンのサイズと最小のチェーン分解のサイズが再び等しくなることを述べています。

半順序集合の反連鎖は、どの 2 つも互いに比較できない要素の集合であり、連鎖は、2 つすべてが比較できる要素の集合です。連鎖分解は、順序の要素を互いに素な連鎖に分割することです。ディルワースの定理によれば、任意の有限半順序集合では、最大の反連鎖は最小の連鎖分解と同じサイズになります。ここで、反連鎖のサイズはその要素の数であり、連鎖分解のサイズはその連鎖の数です。半順序の幅は、反連鎖と連鎖分解の共通サイズとして定義されます。

部分順序集合の大きさに関する以下の帰納法による証明は、Galvin (1994)の証明に基づいています 。 ${\displaystyle P}$

を有限半順序集合とします。 が空の場合、定理は自明に成り立ちます。 したがって、 には少なくとも 1 つの要素があると仮定し、を の最大要素とします。 ${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle a}$${\displaystyle P}$

帰納法によって、ある整数に対して、半順序集合は互いに素な連鎖で覆われ、サイズ の反連鎖を少なくとも 1 つ持つと仮定します。明らかに、に対して が成り立ちます。 に対して、内のサイズ の反連鎖に属する 内の最大元をとし、 と設定します。が反連鎖であると主張します。を含むサイズ の反連鎖をとします。任意の相異なるインデックスと を固定します。次にとします。次にの定義により となります。これはであるため、 であることを意味します。この議論でとの役割を入れ替えるとも得られます。これは が反連鎖であることを証明します。 ${\displaystyle k}$${\displaystyle P':=P\setminus \{a\}}$${\displaystyle k}$${\displaystyle C_{1},\dots ,C_{k}}$${\displaystyle A_{0}}$${\displaystyle k}$${\displaystyle A_{0}\cap C_{i}\neq \emptyset }$${\displaystyle i=1,2,\dots ,k}$${\displaystyle i=1,2,\dots ,k}$${\displaystyle x_{i}}$${\displaystyle C_{i}}$${\displaystyle k}$${\displaystyle P'}$${\displaystyle A:=\{x_{1},x_{2},\dots ,x_{k}\}}$${\displaystyle A}$${\displaystyle A_{i}}$${\displaystyle k}$${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle A_{i}\cap C_{j}\neq \emptyset }$${\displaystyle y\in A_{i}\cap C_{j}}$${\displaystyle y\leq x_{j}}$${\displaystyle x_{j}}$${\displaystyle x_{i}\not \geq x_{j}}$${\displaystyle x_{i}\not \geq y}$${\displaystyle i}$${\displaystyle j}$${\displaystyle x_{j}\not \geq x_{i}}$${\displaystyle A}$

ここで に戻ります。まず、ある に対して であると仮定します。をチェーンとします。すると の選択により、にはサイズ の反チェーンがありません。すると帰納法により、 は内のサイズ の反チェーンであるため、は互いに素なチェーンでカバーできることが示されます。したがって、は必要に応じて互いに素なチェーンでカバーできます。次に、各 に対して である場合、 は内のサイズ の反チェーンです(は 内で最大であるため)。これで はチェーンでカバーでき、証明が完了します。 ${\displaystyle P}$${\displaystyle a\geq x_{i}}$${\displaystyle i\in \{1,2,\dots ,k\}}$${\displaystyle K}$${\displaystyle \{a\}\cup \{z\in C_{i}:z\leq x_{i}\}}$${\displaystyle x_{i}}$${\displaystyle P\setminus K}$${\displaystyle k}$${\displaystyle P\setminus K}$${\displaystyle k-1}$${\displaystyle A\setminus \{x_{i}\}}$${\displaystyle k-1}$${\displaystyle P\setminus K}$${\displaystyle P}$${\displaystyle k}$${\displaystyle a\not \geq x_{i}}$${\displaystyle i\in \{1,2,\dots ,k\}}$${\displaystyle A\cup \{a\}}$${\displaystyle k+1}$${\displaystyle P}$${\displaystyle a}$${\displaystyle P}$${\displaystyle P}$${\displaystyle k+1}$${\displaystyle \{a\},C_{1},C_{2},\dots ,C_{k}}$

組合せ論における他の多くの結果と同様に、ディルワースの定理は、二部グラフマッチングに関するケーニッヒの定理や、ホールの結婚定理を含むいくつかの他の関連する定理と同等である。^[2]

ケーニッヒの定理を用いてn個の要素を持つ半順序Sに対するディルワースの定理を証明するために、 U = V = Sかつ( u , v ) がSでu < v のときのGの辺であるような二部グラフG = ( U , V , E ) を定義します。ケーニッヒの定理により、 Gには対応するMと、 Gの頂点集合C が存在し、グラフの各辺にはCの頂点が少なくとも 1 つ含まれ、MとCの濃度は同じmになります。A をCのどの頂点にも対応しないSの要素の集合とします。すると、Aには少なくともn - m 個の要素があり (二分割の両側で同じ要素に対応する頂点がCに含まれる場合はさらに多くなる可能性があります)、 Aのどの 2 つの要素も互いに比較できません。P を、 Mに辺 ( x、y )がある場合に常にxとy を同じチェーンに含めることによって形成されるチェーンのファミリとします。このとき、P にはn - m 個のチェーンがあります。したがって、同じ基数を持つチェーンへのアンチチェーンと分割を構築しました。

ディルワースの定理からケーニッヒの定理を証明するには、二部グラフG = ( U , V , E ) について、uがUにあり、v がVにあり、Eにuからvへの辺が存在する場合に、 u < vとなるようなGの頂点の半順序を形成します。ディルワースの定理により、反鎖Aと、同じサイズの鎖Pへの分割が存在します。しかし、半順序における唯一の非自明な鎖は、グラフの辺に対応する要素のペアであるため、 Pの非自明な鎖はグラフ内でマッチングを形成します。Aの補鎖は、このマッチングと同じ濃度でG内の頂点カバーを形成します。

^{この二部マッチングとの関連により、}任意の半順序の幅を多項式時間で計算することができる。より正確には、幅kのn要素半順序は時間O ( kn2 )で認識できる。 ^[3]

無限半順序集合に関するディルワースの定理によれば、半順序集合の幅が有限であるためには、 w個の連鎖に分割できる必要がある。たとえば、無限半順序P の幅が w であるとする。これは、どの反連鎖にも最大で有限個のw個の要素があることを意味する。 Pの任意の部分集合Sについて、 w個の連鎖への分解(存在する場合) は、Sの比較不可能グラフ( Sの要素を頂点とし、比較不可能な 2 つの要素の間に 1 辺を持つグラフ) をw色で彩色することで記述できる。比較不可能グラフを適切に彩色した場合、すべての色クラスは連鎖でなければならない。 Pの幅がwであるという仮定と、ディルワースの定理の有限バージョンにより、Pのすべての有限部分集合S には、 w彩色可能な比較不可能グラフが存在する。したがって、ド・ブリュイン・エルデシュの定理により、P自体もw色可能な比較不可能グラフを持ち、したがって望ましいチェーンへの分割を持つ。^[4]

しかし、この定理は、集合の基数だけでなく幅も無限である半順序集合にはそれほど単純には適用されない。この場合、最大の反鎖の大きさと半順序をカバーするために必要な鎖の最小数は、互いに大きく異なる可能性がある。特に、すべての無限基数κ に対して、幅ℵ ₀の無限半順序集合が存在し、これを最小の鎖に分割すると κ 個の鎖になる。^[4]

Perles (1963) は、無限設定における Dilworth の定理の類似物について論じています。

ディルワースの定理の双対は、半順序（有限の場合）における最大の連鎖の大きさは、その順序を分割できる反連鎖の最小の数に等しいと述べている。^[5]これはミルスキーの定理と呼ばれる。その証明はディルワースの定理自体の証明よりもはるかに簡単である。任意の要素xについて、 x を最大要素とする連鎖を考え、これらのx最大連鎖の最大のサイズをN ( x ) で表すとしよう。すると、 Nの値が等しい要素からなる各集合N ⁻¹ ( i )は反連鎖であり、これらの反連鎖は半順序を最大連鎖のサイズに等しい数の反連鎖に分割する。

比較可能性グラフは、部分順序から、順序の要素ごとに頂点を作成し、比較可能な任意の 2 つの要素を接続する辺を作成することによって形成される無向グラフです。したがって、比較可能性グラフ内のクリークはチェーンに対応し、比較可能性グラフ内の独立セットはアンチチェーンに対応します。比較可能性グラフの誘導サブグラフは、それ自体が比較可能性グラフであり、部分順序をその要素のサブセットに制限することで形成されます。

無向グラフが完全であるとは、すべての誘導サブグラフにおいて、彩色数が最大クリークのサイズに等しい場合を言う。すべての比較可能グラフは完全である。これは本質的にはミルスキーの定理をグラフ理論の用語で言い直したものにすぎない。^[6] Lovász (1972) の完全グラフ定理によれば、任意の完全グラフの補グラフも完全である。したがって、任意の比較可能グラフの補グラフも完全である。これは本質的にはディルワースの定理そのものをグラフ理論の用語で言い直したものにすぎない (Berge & Chvátal 1984)。したがって、完全グラフの補数特性は、ディルワースの定理の別の証明を提供することができる。

ブール格子 B _nは、n要素集合X （本質的には{1, 2, …, n }）の包含順、または表記上は（2 ^{[ n ]} , ⊆）の冪集合である。シュペルナーの定理によれば、 B _nの最大反鎖の大きさは最大で

${\displaystyle \operatorname {width} (B_{n})={n \choose \lfloor {n/2}\rfloor }.}$

言い換えれば、Xの比較不可能な部分集合の最大族は、 Xの中間サイズの部分集合を選択することによって得られます。Lubell -Yamamoto-Meshalkin 不等式は、べき集合内の反連鎖にも関係し、Sperner の定理を証明するために使用できます。

区間 [1, 2 n ]内の整数を割り切れる数で順序付けると、部分区間 [ n  + 1, 2 n ] は濃度がnの逆連鎖を形成します。この部分順序をn 個の連鎖に分割するのは簡単です。 [1,2 n ] 内の奇数mごとに、 m 2 ⁱの形式の数の連鎖を形成します。したがって、ディルワースの定理により、この部分順序の幅はnです。

単調な部分列に関するエルデシュ・シェケレスの定理は、ディルワースの定理を2次元の部分順序に適用したものとして解釈できる。^[7]

反マトロイドの「凸次元」は、反マトロイドを定義するために必要なチェーンの最小数として定義され、ディルワースの定理を使用して、それが関連する半順序の幅に等しいことを示すことができます。この関係により、凸次元の多項式時間アルゴリズムが実現します。^[8]

• ベルジュ、クロード、ヴァツラフ・クヴァタル（1984）、完全グラフに関する話題、離散数学年報、第21巻、エルゼビア、p. viii、ISBN 978-0-444-86587-8
• ディルワース、ロバート P. (1950)、「部分的に順序付けられた集合の分解定理」、数学年報、51 (1): 161–166、doi :10.2307/1969503、JSTOR  1969503。
• エデルマン、ポール H.;サックス、マイケル E. (1988)、「凸形状の組合せ表現と凸次元」、Order、5 (1): 23–32、doi :10.1007/BF00143895、S2CID  119826035。
• フェルスナー、ステファン; ラガヴァン、ヴィジェイ; スピンラッド、ジェレミー (2003)、「小さな幅の順序と小さなディルワース数のグラフの認識アルゴリズム」、Order、20 (4): 351–364 (2004)、doi :10.1023/B:ORDE.0000034609.99940.fb、MR  2079151、S2CID  1363140。
• フルカーソン, DR (1956)、「部分的に順序付けられた集合に対するディルワースの分解定理に関する注記」、アメリカ数学会紀要、7 (4): 701–702、doi :10.2307/2033375、JSTOR  2033375。
• ガルビン、フレッド(1994)、「ディルワースの連鎖分解定理の証明」、アメリカ数学月刊誌、101 (4): 352–353、doi :10.2307/2975628、JSTOR  2975628、MR  1270960。
• グリーン、カーティス; クライトマン、ダニエル J. (1976)、「スペルナー族の構造」、組み合わせ理論ジャーナル、シリーズ A、20 (1): 41–68、doi : 10.1016/0097-3165(76)90077-7${\displaystyle k}$。
• Harzheim, Egbert (2005)、Ordered sets、Advances in Mathematics (Springer)、第 7 巻、ニューヨーク: Springer、Theorem 5.6、p. 60、ISBN 0-387-24219-8、MR  2127991。
• ロヴァース、ラースロー（1972）、「正規ハイパーグラフと完全グラフ予想」、離散数学、2（3）：253-267、doi：10.1016/0012-365X（72）90006-4。
• ミルスキー、レオン(1971)、「ディルワースの分解定理の双対」、アメリカ数学月刊誌、78 (8): 876–877、doi :10.2307/2316481、JSTOR  2316481。
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「定理 3.13」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Heidelberg: Springer、p. 42、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR  2920058。
• パールズ、ミカ A. (1963)、「無限の場合のディルワースの定理について」、イスラエル数学ジャーナル、1 (2): 108–109、doi : 10.1007/BF02759806、MR  0168497、S2CID  120943065。
• Steele, J. Michael (1995)、「Erdős と Szekeres の単調部分列テーマのバリエーション」、Aldous, David ; Diaconis, Persi ; Spencer, Joel ; et al. (eds.)、離散確率とアルゴリズム(PDF)、IMA Volumes in Mathematics and its Applications、vol. 72、Springer-Verlag、pp. 111–131。

• 組合せ論における7つの主要定理の同値性
• 「Dual of Dilworth's Theorem」、PlanetMath、2007-07-14 にオリジナルからアーカイブ
• Babai, László (2005)、Lecture Notes in Combinatorics and Probability、Lecture 10: Perfect Graphs (PDF) 、 2011-07-20 にオリジナル(PDF)からアーカイブ
• フェルスナー、S.; ラガヴァン、V. & スピンラッド、J. (1999)、小さな幅の順序と小さなディルワース数のグラフの認識アルゴリズム
• Weisstein, Eric W.「Dilworth の補題」。MathWorld。