Mirskyの定理

同義語：ミルスキーの定理Mirsky's theoremDilworthの双対定理dual of Dilworth's theorem

概要

前提知識: 半順序集合, 鎖(順序集合), 反鎖

Mirsky の定理（Mirsky's theorem）とは、有限半順序集合 $P$ について、最も長い鎖の元の個数と、$P$ を反鎖に分割するときに必要な反鎖の最小の個数が等しい、という定理である。L. Mirsky が 1971 年に Dilworthの定理の双対として示した（MS12 p. 4 とその文献表の [19]）。Dilworth の定理が「最大の反鎖の元の個数＝鎖への分割の最小個数」を述べるのに対し、Mirsky の定理は鎖と反鎖の役割を入れ替えたものである。
たとえば $36$ の正の約数の全体 $\{1,2,3,4,6,9,12,18,36\}$ を「割り切る」で順序づける（整除関係）。$1\mid2\mid4\mid12\mid36$ は元の個数 $5$ の鎖で、これより長い鎖はない。一方、素因数の個数（重複を数える）ごとに約数を集めた
$$ \{1\},\quad\{2,3\},\quad\{4,6,9\},\quad\{12,18\},\quad\{36\} $$
はどれも反鎖であり（素因数の個数が同じ相異なる 2 数は一方が他方を割り切らない）、全体を $5$ 個の反鎖に分けている。$4$ 個以下の反鎖には分けられない。元の個数 $5$ の鎖の $5$ 個の元は、どの 2 つも同じ反鎖に入れないからである。
Mirsky の定理は Dilworth の定理よりずっと易しく、各元に「その元で終わる最長の鎖の元の個数」を割り当てるだけで分割が作れる（KT17 §6.3、p. 122）。この記事では、この高さ関数による証明を与え、極小元を取り除いていく手順との関係、無限の半順序集合への拡張、Dilworth の定理との双対の関係を述べる。最後に、両方の定理を同時に含む Greene–Kleitman の定理を紹介する。

定義

$(P,\le)$ を半順序集合とし、$x< y$ は「$x\le y$ かつ $x\ne y$」を表す。$x\le y$ または $y\le x$ のとき $x$ と $y$ は 比較可能 であるといい、そうでないとき 比較不能 であるという。$P$ の部分集合 $C$ のどの 2 元も比較可能なとき $C$ を鎖、部分集合 $A$ の相異なるどの 2 元も比較不能なとき $A$ を反鎖という。空集合と 1 元集合は鎖でも反鎖でもある。

高さと反鎖分割

有限半順序集合 $P$ の鎖の元の個数の最大値を $P$ の高さといい $h(P)$ と書く（$P=\emptyset$ なら $h(P)=0$）。$P$ を互いに交わらない空でない反鎖の和集合に表すことを 反鎖分割 といい、その反鎖の個数を分割の個数という。

鎖の「長さ」を元の個数から $1$ を引いた数で測る流儀もある（鎖(順序集合) の記事はこの流儀である）。その流儀では、Mirsky の定理の等式は「最長の鎖の長さ $+1$ ＝反鎖分割の最小個数」となる。この記事では Dilworthの定理の記事と同じく、元の個数で数える。

高さ関数

$P$ を有限半順序集合とする。$x\in P$ について、$x$ を最大元とする鎖の元の個数の最大値を $\ell(x)$ と書き、$\ell$ を $P$ の 高さ関数 という。

$\{x\}$ が $x$ を最大元とする鎖なので $\ell(x)\ge1$ であり、$\ell(x)\le h(P)$ である。$\ell(x)=1$ となるのは、$y< x$ となる $y$ がないとき、すなわち $x$ が $P$ の極小元のときである。

主定理

鎖と反鎖は高々1元を共有する

鎖 $C$ と反鎖 $A$ について $|C\cap A|\le1$ である。したがって、有限半順序集合 $P$ の反鎖分割の個数は $h(P)$ 以上である。

$C\cap A$ が相異なる 2 元 $x,y$ を含めば、$x,y\in C$ から比較可能、$x,y\in A$ から比較不能となり矛盾する。$P=A_1\cup\cdots\cup A_m$ を反鎖分割とし、$C$ を元の個数 $h(P)$ の鎖とすると、$h(P)=|C|=\sum_i|C\cap A_i|\le m$ である。$\square$

高さ関数の性質

$P$ を空でない有限半順序集合とする。

$x< y$ なら $\ell(x)< \ell(y)$ である。
$\ell$ のとる値の集合はちょうど $\{1,2,\dots,h(P)\}$ である。

$x$ を最大元とする元の個数 $\ell(x)$ の鎖 $C$ をとる。$C$ の元はすべて $x$ 以下なので、推移律により $y$ より小さく、$C\cup\{y\}$ は $y$ を最大元とする元の個数 $\ell(x)+1$ の鎖である。よって $\ell(y)\ge\ell(x)+1$ である。
値が $1$ 以上 $h(P)$ 以下であることは上で見た。逆に、元の個数 $h:=h(P)$ の鎖 $c_1< c_2< \cdots< c_h$ をとる。1 により $1\le\ell(c_1)< \ell(c_2)< \cdots< \ell(c_h)\le h$ であり、$h$ 個の相異なる整数が $1$ 以上 $h$ 以下にあるので $\ell(c_j)=j$ である。$\square$

Mirskyの定理

有限半順序集合 $P$ について、反鎖分割の個数の最小値は $h(P)$ に等しい。実際、$j=1,\dots,h(P)$ について
$$ A_j:=\{x\in P\mid\ell(x)=j\} $$
とおくと、$A_1,\dots,A_{h(P)}$ は $P$ の反鎖分割である。

$P=\emptyset$ なら $0$ 個の反鎖で分割できる。$P\ne\emptyset$ とする。各元はちょうど 1 つの $A_j$ に属し、lem-mirsky-ell の 2 により各 $A_j$ は空でない。$x,y\in A_j$ で $x< y$ なら、lem-mirsky-ell の 1 により $\ell(x)< \ell(y)$ となり $\ell(x)=\ell(y)=j$ に反する。よって $A_j$ の相異なる 2 元は比較不能で、$A_j$ は反鎖である。こうして $h(P)$ 個の反鎖への分割が得られ、lem-mirsky-meet によりこれより少ない個数の反鎖分割はない。$\square$

言い換え

有限半順序集合 $P$ と整数 $k\ge0$ について、次は同値である。

$P$ は $k$ 個以下の反鎖の和集合である。
$P$ の鎖の元の個数はすべて $k$ 以下である。
写像 $f\colon P\to\{1,\dots,k\}$ で、$x< y$ なら $f(x)< f(y)$ となるものがある。

1⇒2：$k$ 個以下の反鎖の和集合なら、各元を最初に属する反鎖に割り当てて $k$ 個以下の反鎖分割が得られ（空になった反鎖は捨てる）、lem-mirsky-meet により $h(P)\le k$ である。2⇒3：$f:=\ell$ とすれば、値は $h(P)\le k$ 以下であり、lem-mirsky-ell の 1 が条件を与える。3⇒1：各 $j$ について $f^{-1}(j)$ は反鎖である。$x,y\in f^{-1}(j)$ で $x< y$ なら $f(x)< f(y)$ となるからである。$P=f^{-1}(1)\cup\cdots\cup f^{-1}(k)$ である。$\square$

3 の写像は「順序を狭義に保つ $\{1,\dots,k\}$ への写像」で、各元に階を割り当てることにあたる。高さ関数 $\ell$ は、そのような写像のうち値がいちばん小さいものである。実際、3 の $f$ について、$x$ を最大元とする鎖 $c_1< \cdots< c_{\ell(x)}=x$ をとれば $1\le f(c_1)< \cdots< f(c_{\ell(x)})$ なので $f(x)\ge\ell(x)$ となる。

極小元を取り除く手順

thm-mirsky-main の分割は、極小元をまとめて取り除く操作を繰り返しても得られる。

極小元による分割

有限半順序集合 $P$ について $P_1:=P$ とし、$P_j\ne\emptyset$ のとき $P_j$ の極小元の全体を $M_j$、$P_{j+1}:=P_j\setminus M_j$ とおく。このとき $j=1,\dots,h(P)$ について $M_j=A_j$（thm-mirsky-main の記号）であり、$P_{h(P)+1}=\emptyset$ である。

$P_j=\{x\in P\mid\ell(x)\ge j\}$ のとき $M_j=A_j$ となることを示せば、$j$ についての帰納法で全体が従う（$P_1=P$ は $j=1$ の場合で、$M_j=A_j$ なら $P_{j+1}=\{x\mid\ell(x)\ge j+1\}$ である。$\ell$ の値は $h(P)$ 以下なので $P_{h(P)+1}=\emptyset$）。
$\ell(x)=j$ とし、$y< x$ とすると lem-mirsky-ell の 1 により $\ell(y)< j$ なので $y\notin P_j$ である。よって $x$ は $P_j$ の極小元である。逆に $x\in P_j$ で $\ell(x)>j$ とし、$x$ を最大元とする元の個数 $\ell(x)$ の鎖 $c_1< \cdots< c_{\ell(x)}=x$ をとる。$c_1< \cdots< c_{\ell(x)-1}$ は $c_{\ell(x)-1}$ を最大元とする鎖なので $\ell(c_{\ell(x)-1})\ge\ell(x)-1\ge j$ であり、$c_{\ell(x)-1}\in P_j$ かつ $c_{\ell(x)-1}< x$ だから $x$ は $P_j$ の極小元でない。$\square$

この手順は分割を計算する簡単なアルゴリズムを与える（KT17 §6.3、p. 122）。上下を入れ替えて、極大元をまとめて取り除いても $h(P)$ 個の反鎖分割が得られる。冒頭の $36$ の約数の例では、$M_1=\{1\}$、$M_2=\{2,3\}$、$M_3=\{4,6,9\}$、$M_4=\{12,18\}$、$M_5=\{36\}$ である。

無限の半順序集合

thm-mirsky-main の証明は、鎖の元の個数に上限があれば無限の半順序集合でもそのまま通る。

鎖の長さが有界な場合

$P$ を半順序集合（無限でもよい）とし、$k\ge0$ とする。$P$ のどの鎖も元の個数が $k$ 以下ならば、$P$ は $k$ 個以下の反鎖の和集合である。

各 $x$ について、$x$ を最大元とする鎖の元の個数は $1$ 以上 $k$ 以下の整数なので、その最大値 $\ell(x)$ が定まる。prf-mirsky-ell の 1 の議論は $P$ の有限性を使っていないので、$x< y$ なら $\ell(x)< \ell(y)$ である。よって prf-mirsky-main と同じく、各 $j=1,\dots,k$ について $\{x\mid\ell(x)=j\}$ は反鎖であり、$P$ はこれら $k$ 個の和集合である。$\square$

この証明は選択公理を使わない。これに対し、無限の半順序集合についての Dilworth の定理（反鎖の元の個数が $k$ 以下なら $k$ 個の鎖の和集合）の証明には、Dilworthの定理の記事の注意「無限の場合の出典」で述べられているように、超限的な議論が使われる。

Dilworth の定理との双対

	Dilworth の定理	Mirsky の定理
最大を測るもの	反鎖の元の個数（幅 $w(P)$）	鎖の元の個数（高さ $h(P)$）
分割に使うもの	鎖	反鎖
主張	鎖への分割の最小個数 $=w(P)$	反鎖への分割の最小個数 $=h(P)$
易しい向き	鎖と反鎖は高々 1 元を共有する	同じ
分割の作り方	帰納法、または二部グラフのマッチング	高さ関数の値で分ける

2 つの定理は「鎖」と「反鎖」を入れ替えた形をしているが、この入れ替えは半順序の上下を逆にする操作では起こらない。上下を逆にしても鎖は鎖、反鎖は反鎖のままだからである。そのため、一方の定理を上下の反転だけで他方から導くことはできない。両方を同時に含む主張が、下の Greene–Kleitman の定理である。
比較可能グラフで見る. $P$ の元を頂点とし、相異なる比較可能な 2 元を辺で結んだグラフを $P$ の 比較可能グラフ $G(P)$ という。$P$ の鎖は $G(P)$ のクリーク（どの 2 頂点も隣接する頂点集合）、反鎖は独立集合（どの 2 頂点も隣接しない頂点集合）である。反鎖分割は隣接する頂点が同じ色にならない塗り分けと同じなので、Mirsky の定理は
$$ \chi(G(P))=\omega(G(P)) $$
（彩色数＝最大クリークの頂点数）と言い換えられる。$P$ の部分集合 $S$ の上の誘導部分グラフは、順序を $S$ に制限した半順序集合の比較可能グラフ $G(S)$ なので、この等式は $G(P)$ のすべての誘導部分グラフでも成り立つ。すべての誘導部分グラフで彩色数と最大クリークの大きさが等しいグラフを perfect なグラフというので、比較可能グラフは perfect である。同じように、Dilworth の定理は比較可能グラフの補グラフで同じ等式が成り立つことを述べており、比較可能グラフの補グラフも perfect である。
数列への応用. 相異なる実数の列 $a_1,\dots,a_N$ の添字に「$i\le j$ かつ $a_i\le a_j$」で半順序を入れると、鎖は増加部分列、反鎖は減少部分列になる。Mirsky の定理を当てると、添字の集合は最長の増加部分列の長さと同じ個数の減少部分列に分けられ、項数は最長の増加部分列の長さと最長の減少部分列の長さの積以下になる。これが Erdős–Szekeresの定理(単調部分列) である。

Greene–Kleitman の定理

$P$ を $p$ 個の元をもつ有限半順序集合とする。$k\ge1$ について、$k$ 個の鎖の和集合の元の個数の最大値を $c_k$、$k$ 個の反鎖の和集合の元の個数の最大値を $a_k$ とし、$c_0=a_0=0$ とおく。
$$ \lambda_k:=c_k-c_{k-1},\qquad\mu_k:=a_k-a_{k-1}\qquad(k\ge1) $$
と定める。$c_1=h(P)$、$a_1=w(P)$（最大の反鎖の元の個数、幅）である。

Greene–Kleitmanの定理

$\lambda_1\ge\lambda_2\ge\cdots$ かつ $\mu_1\ge\mu_2\ge\cdots$ であり、$\lambda=(\lambda_1,\lambda_2,\dots)$ と $\mu=(\mu_1,\mu_2,\dots)$ はどちらも $p$ の分割である。さらに $\mu$ は $\lambda$ の共役な分割である。すなわち、すべての $j\ge1$ について $\mu_j=\#\{i\mid\lambda_i\ge j\}$ が成り立つ。

所在

この記事では証明しない。主張は Sta11 Exercise 3.77 (a)–(c)（p. 422）にあり、同 p. 485 の解答の注によれば、C. Greene と D. J. Kleitman（1976 年）および C. Greene（1976 年）が展開した鎖と反鎖の理論の一部である。後にネットワークフローや線形代数による別の証明も与えられた（同 p. 485）。

共役な分割は Young図形で見ると分かりやすい。$\lambda_i$ 個の箱を第 $i$ 行に左詰めで並べた図形の列の長さを左から読んだものが $\mu$ である。

Mirsky と Dilworth を導く

$m$ を $P$ の反鎖分割の最小個数、$n$ を鎖分割の最小個数とする。このとき $\mu_k>0$ となる $k$ はちょうど $1,\dots,m$ であり、$\lambda_k>0$ となる $k$ はちょうど $1,\dots,n$ である。したがって thm-mirsky-greene-kleitman から、$h(P)=\lambda_1=m$（Mirsky の定理）と $w(P)=\mu_1=n$（Dilworth の定理）が従う。

$k$ 個の反鎖の和集合が $P$ 全体になるのは、cor-mirsky-equivalent の証明の 1⇒2 と同じく各元を最初に属する反鎖に割り当てれば、$k\ge m$ のときに限る。よって $k\ge m$ なら $a_k=p$、$k< m$ なら $a_k< p$ である。$k< m$ のとき、和集合の元の個数が $a_k$ の $k$ 個の反鎖に、和集合に入っていない 1 元からなる反鎖を加えると $a_{k+1}\ge a_k+1$ である。したがって $k\le m$ で $\mu_k\ge1$、$k>m$ で $\mu_k=0$ である。鎖についても同じである。
thm-mirsky-greene-kleitman により $\mu$ は $\lambda$ の共役であり、共役を 2 回とると元に戻るので $\lambda$ も $\mu$ の共役である。よって $\lambda_1=\#\{j\mid\mu_j\ge1\}=m$、$\mu_1=\#\{i\mid\lambda_i\ge1\}=n$ である。$\lambda_1=c_1=h(P)$、$\mu_1=a_1=w(P)$ なので主張が従う。$\square$

Mirsky の定理そのものは thm-mirsky-main のように直接示せるが、Greene–Kleitman の定理は $k$ 個の鎖・反鎖について同時に成り立つ精密な主張であり、Mirsky と Dilworth の 2 つの定理が 1 つの等式 $\mu=\lambda'$ の $1$ 行目と $1$ 列目にあたることを示している（Sta11 Exercise 3.77 (d)（p. 422）、(e)（p. 423）とその解答（p. 485））。
相異なる実数の列の添字の半順序集合（上の「数列への応用」）では、$k$ 個の鎖の和集合は $k$ 個の増加部分列の和集合、$k$ 個の反鎖の和集合は $k$ 個の減少部分列の和集合である。この場合の thm-mirsky-greene-kleitman は、Robinson–Schensted–Knuth対応の記事の定理「Greeneの定理」で、行挿入で作った盤の形 $\lambda$ を使って証明されている。

36 の約数

冒頭の $36$ の約数の半順序集合（$p=9$）では、$\lambda=(5,3,1)$、$\mu=(3,2,2,1,1)$ である。実際、鎖 $1\mid2\mid4\mid12\mid36$ が最長で $c_1=5$、これと鎖 $3\mid6\mid18$ の和集合は $9$ 以外の $8$ 元で $c_2=8$、$\{9\}$ を加えて $c_3=9$ である。反鎖では $\{4,6,9\}$ が最大で $a_1=3$、$\{2,3\}$ を加えて $a_2=5$、$\{12,18\}$ を加えて $a_3=7$、$\{1\}$、$\{36\}$ を加えて $a_4=8$、$a_5=9$ である。これらが最大であることは、$k$ 個の鎖の和集合が冒頭の $5$ 個の反鎖のそれぞれと高々 $k$ 元しか共有しないこと（$c_2\le1+2+2+2+1=8$）と、$k$ 個の反鎖の和集合が鎖 $1\mid2\mid4\mid12\mid36$、$3\mid6\mid18$、$\{9\}$ のそれぞれと高々 $k$ 元しか共有しないこと（$a_2\le2+2+1=5$、$a_3\le3+3+1=7$、$a_4\le4+3+1=8$）から分かる。行の長さ $5,3,1$ の Young 図形の列の長さは $3,2,2,1,1$ であり、$\mu=\lambda'$ が確かめられる。$\lambda_1=5=h(P)$ と、$\mu$ の $0$ でない項の個数 $5$（反鎖分割の最小個数）が一致するのが Mirsky の定理である。

反例

次の表の各行は、仮定や手順の 1 か所だけを替えると等号が成り立たなくなる例である。

外す条件	反例	成り立たなくなること
鎖が元の個数最大であること（極大な鎖に替える）	$a< b< c$、$d< c$ で生成される 4 元の半順序集合と極大な鎖 $\{d,c\}$	反鎖分割の最小個数が、その鎖の元の個数に等しいこと
取り除くのが極小元の全体であること（元の個数最大の反鎖に替える）	$a< c$、$a< d$、$b< c$ だけの 4 元の半順序集合	繰り返し取り除いて $h(P)$ 個の反鎖分割が得られること
分割に使うのが反鎖であること（鎖に替える）	3 元の反鎖 $\{a,b,c\}$	分割の最小個数が $h(P)$ に等しいこと
関係の推移律	$\{1,\dots,5\}$ に $1\prec2$、$2\prec3$、$3\prec4$、$4\prec5$、$1\prec5$ だけを入れた関係	どの 2 元も関係で結ばれる部分集合の元の個数の最大値が、どの 2 元も結ばれない部分集合への分割の最小個数に等しいこと

1 行目：$\{d,c\}$ にはどの元も加えられない（$a,b$ は $d$ と比較不能）が、$\{a,b,c\}$ は元の個数 $3$ の鎖なので、thm-mirsky-main により反鎖分割には $3$ 個が要る。
2 行目：高さは $2$（$a< c$ など）、幅は $2$ である。元の個数最大の反鎖の 1 つ $\{b,d\}$ を取り除くと鎖 $a< c$ が残り、さらに $2$ 個の反鎖が要るので、全体で $3$ 個になる。極小元の全体 $\{a,b\}$ を取り除けば $\{c,d\}$ が残り、$2$ 個で済む。
3 行目：高さは $1$ だが、鎖への分割には $3$ 個が要る。鎖への分割の最小個数は高さではなく幅に等しい（Dilworthの定理）。
4 行目：表の 5 対に各元の $x\preceq x$ を加えた関係 $\preceq$ では反射律と反対称律が成り立つが、$1\prec2\prec3$ でも $1\prec3$ でないので推移律が成り立たない。どの 2 つも関係で結ばれる元の集合は高々 $2$ 元である（5 角形の辺）。一方、どの 2 つも結ばれない元の集合は高々 $2$ 元で、$5$ 元を覆うには $3$ 個が要る。比較可能グラフの言葉では 5 角形 $C_5$ で、$\omega=2$、$\chi=3$ である。推移律は lem-mirsky-ell の 1 で使われている。