クナスター・クラトフスキ・マズルキェヴィチの補題

Knaster -Kuratowski-Mazurkiewicz の補題は、 1929 年にKnaster、Kuratowski、Mazurkiewiczによって発表された数学的固定点理論の基本的な結果です。^[1]

KKM 補題は、スペルナーの補題から証明することができ、ブラウワーの不動点定理を証明するために使用できます。

を とラベル付けされたn 個の頂点を持つ次元単体とします。 ${\displaystyle \Delta _{n-1}}$${\displaystyle (n-1)}$ ${\displaystyle 1,\ldots ,n}$

KKM被覆は、任意の に対して、に対応する頂点の凸包が によって覆われるような閉集合の集合として定義されます。 ${\displaystyle C_{1},\ldots ,C_{n}}$${\displaystyle I\subseteq \{1,\ldots ,n\}}$${\displaystyle I}$${\displaystyle \bigcup _{i\in I}C_{i}}$

KKM 補題によれば、すべての KKM 被覆において、すべてのn個の集合の共通集合は空でない、つまり次のようになります。

${\displaystyle \bigcap _{i=1}^{n}C_{i}\neq \emptyset .}$

のとき、KKM 補題は三角形の単体を考慮します。三角形の頂点には 1、2、3 のラベルが付けられます。次のような 3 つの閉集合が与えられます。 ${\displaystyle n=3}$${\displaystyle \Delta _{2}}$${\displaystyle C_{1},C_{2},C_{3}}$

• ${\displaystyle C_{1}}$頂点 1 をカバーし、頂点 2 をカバーし、頂点 3 をカバーします。${\displaystyle C_{2}}$${\displaystyle C_{3}}$
• 辺 12 (頂点 1 から頂点 2) は集合および によってカバーされ、辺 23 は集合および によってカバーされ、辺 31 は集合およびによってカバーされます。${\displaystyle C_{1}}$${\displaystyle C_{2}}$${\displaystyle C_{2}}$${\displaystyle C_{3}}$${\displaystyle C_{3}}$${\displaystyle C_{1}}$
• 3つの集合の和集合は三角形全体を覆う。

KKM 補題は、集合には少なくとも 1 つの共通点があることを示します。 ${\displaystyle C_{1},C_{2},C_{3}}$

補題は右の図に示されています。セット #1 は青、セット #2 は赤、セット #3 は緑です。次の理由により、KKM 要件は満たされています。

• 各頂点は固有の色で覆われています。
• 各辺は、その 2 つの頂点の 2 つの色で覆われます。
• 三角形は3つの色すべてで覆われています。

KKM 補題は、3 つの色すべてが同時に覆う点が存在することを述べています。そのような点は画像で明確に確認できます。

すべての集合が閉じていること、つまり境界が含まれていることが重要であることに注意してください。たとえば、赤い集合が閉じていない場合、中心点が青と緑の集合にのみ含まれ、3 つの集合すべての交差が空になる可能性があります。

不動点定理には、代数的位相変種、組み合わせ変種、集合被覆変種の 3 つの同等の変種があります。各変種は、まったく異なる議論を使用して個別に証明できますが、各変種は同じ行の他の変種に還元することもできます。さらに、最上行の各結果は、同じ列のその下の行の結果から演繹できます。^[2]

デイビッド・ゲイルは、 KKM補題の次の一般化を証明した。^[3] 1つのKKM被覆の代わりに、n個の異なるKKM被覆があるとする: 。すると、空でない交差を持つ被覆の順列が存在する。 ${\displaystyle C_{1}^{1},\ldots ,C_{n}^{1},\ldots ,C_{1}^{n},\ldots ,C_{n}^{n}}$${\displaystyle \pi}$

${\displaystyle \bigcap _{i=1}^{n}C_{i}^{\pi (i)}\neq \emptyset }$。

「レインボー KKM 補題」という名前は、ゲイルの補題の説明に由来しています。

「この結果を口語的に述べると、3人がそれぞれKKMルールに従って赤、白、青の三角形を塗ると、1人の人の赤のセット、別の人の白のセット、3人目の人の青のセットに含まれる点が存在することになります」^[3]

レインボーKKM補題は、スペルナーの補題のレインボー一般化を使って証明できる。^[4]

元の KKM 補題は、 n 個の同一の被覆を選択するだけで、レインボー KKM 補題から導かれます。

単体のコネクタは、単体の n面すべてに接する連結集合です。

コネクタフリーカバーとは、コネクタが 一切含まれていないカバーのことです。${\displaystyle C_{1},\ldots ,C_{n}}$${\displaystyle C_{i}}$

KKM 被覆はどれもコネクタのない被覆です。なぜなら、KKM 被覆では、どの面もn面すべてに接しないからです。ただし、KKM 被覆ではないコネクタのない被覆もあります。右に例を示します。ここでは、赤い集合は 3 つの面すべてに接していますが、その連結成分は 3 つの面すべてに接していないため、コネクタは含まれていません。 ${\displaystyle C_{i}}$

ラヴィンドラ・バパットによる定理は、スペルナーの補題を一般化したものである^{[5] ：第16章、257～261ページは、} KKM補題がコネクタフリー被覆に拡張されることを意味している（彼は に対する定理を証明した）。 ${\displaystyle n=3}$

コネクタフリーのバリアントには順列バリアントもあるため、これら 2 つの一般化を同時に使用できます。

KKMS定理はロイド・シャプレーによるKKM補題の一般化であり、経済学、特に協力ゲーム理論で有用である。^[6]

KKM 被覆にはn 個の閉集合が含まれますが、KKMS 被覆には の空でない部分集合(と同等: の空でない面)によってインデックス付けされた閉集合- が含まれます。任意の に対して、に対応する頂点の凸包はの部分集合に対応する集合の和集合によって覆われる必要があります。つまり、${\displaystyle 2^{n}-1}$ ${\displaystyle [n]}$${\displaystyle \Delta _{n-1}}$${\displaystyle I\subseteq [n]}$${\displaystyle I}$${\displaystyle I}$

${\displaystyle \operatorname {conv} (\{v_{i}:i\in I\})\subseteq \bigcup _{J\subseteq I}C_{J}}$。

任意の KKM 被覆は KKMS 被覆の特殊なケースです。KKM 被覆では、シングルトンに対応するn 個の集合は空ではなく、その他の集合は空です。ただし、他にも多くの KKMS 被覆が存在します。

一般に、 KKMS 被覆内のすべての集合の共通集合が空でないというのは正しくありません。これは、ほとんどの集合が空である KKM 被覆の特殊なケースによって示されます。 ${\displaystyle 2^{n}-1}$

KKMS定理は、あらゆるKKMS被覆において、 のバランスの取れた集合が存在し、 でインデックス付けされた集合の共通部分は空でない ${\displaystyle B}$${\displaystyle 2^{[n]}}$${\displaystyle B}$ということを述べている：^[7]

${\displaystyle \bigcap _{J\in B}C_{J}\neq \emptyset }$

「バランスのとれたコレクション」とは何かを説明する必要があります。のサブセットのコレクションは、 に重み関数 (すべての に重みを割り当てる)があり、各要素 について、 を含むすべてのサブセットの重みの合計がちょうど 1 になる場合、バランスがとれていると呼ばれます。たとえば、 とします。次のようになります。 ${\displaystyle B}$${\displaystyle [n]}$${\displaystyle B}$${\displaystyle w_{J}\geq 0}$${\displaystyle J\in B}$${\displaystyle i\in [n]}$${\displaystyle i}$${\displaystyle n=3}$

• コレクション {{1}, {2}, {3}} はバランスが取れています。つまり、すべての重みが 1 になるように選択します。コレクション {{1,2},{3}} やコレクション { {1,2,3} } など、各要素が 1 回だけ出現するコレクションの場合も同様です。
• コレクション {{1,2}, {2,3}, {3,1}} はバランスが取れています。つまり、すべての重みが 1/2 になるように選択します。各要素が正確に 2 回出現するコレクションの場合も同様です。
• コレクション {{1,2}, {2,3}} はバランスが取れていません。正の重みを任意に選択した場合、要素 2 の合計は要素 1 または 3 の合計よりも大きくなり、すべての合計が 1 になることは不可能だからです。
• コレクション {{1,2}, {2,3}, {1}} はバランスが取れています。 を選択してください。${\displaystyle w_{1,2}=0,w_{2,3}=1,w_{1}=1}$

ハイパーグラフの用語では、集合B がその基底集合Vに関してバランスが取れている場合と、頂点集合Vと辺集合Bを持つハイパーグラフが完全な分数マッチングを許容する場合とで同じです。

KKMS定理はKKM補題を意味する。^[7]に対してKKM被覆があるとする。次のように KKMS被覆を構築する。${\displaystyle C_{i}}$${\displaystyle i=1,\ldots ,n}$${\displaystyle C'_{J}}$

• ${\displaystyle C'_{J}=C_{i}}$( は要素のみを含むシングルトンです)。${\displaystyle J=\{i\}}$${\displaystyle J}$${\displaystyle i}$
• ${\displaystyle C'_{J}=\emptyset }$さもないと。

元の被覆に対する KKM 条件は、新しい被覆に対する KKMS 条件を意味します。したがって、新しい被覆内の対応するセットが空でない交差を持つようなバランスの取れたコレクションが存在します。ただし、唯一の可能なバランスの取れたコレクションは、すべてのシングルトンのコレクションです。したがって、元の被覆は空でない交差を持ちます。 ${\displaystyle C_{i}}$${\displaystyle C'_{J}}$

KKMS定理には様々な証明がある。^{[8] [9] [10]}

レニーとウッダーズは、バランスのとれたセットもパートナーとして選択できることを証明した。^[11]

周は、被覆が閉集合ではなく開集合で構成されるKKMS定理の変形を証明した。 ^[12]

小宮英俊は、KKMS定理を単体から多面体へと一般化した。^[9] P を任意のコンパクトな凸多面体とする。 をPの空でない面の集合とする。Pの小宮被覆は、すべての面に対して次の条件を満たす閉集合の族である。 小宮の定理によれば、 P のすべての小宮被覆に対して、均衡のとれた集合が存在し、 でインデックス付けされた集合の共通部分は空でない。^[7]${\displaystyle {\textrm {面}}(P)}$${\displaystyle \{C_{F}:F\in {\textrm {面}}(P)\}}$${\displaystyle F\in {\textrm {面}}(P)}$$F\subseteq \bigcup _{G\subseteq F,~G\in {\textrm {面}}(P)}C_{G}。$ ${\displaystyle B\subseteq {\textrm {面}}(P)}$${\displaystyle B}$

${\displaystyle \bigcap _{F\in B}C_{F}\neq \emptyset }$

小宮の定理は、バランスの取れたコレクションの定義も一般化します。つまり、 Pの各頂点の近くの重みの合計が 1 になるような重み関数がに存在することを要求するのではなく、任意の点の集合を選択することから始めます。コレクションは、に関してバランスが取れているとは、 、つまり、多角形P全体に割り当てられた点が、コレクションB内の面に割り当てられた点の凸結合である場合に限ります。 ${\displaystyle B}$${\displaystyle {\textbf {b}}=\{b^{F}:F\in {\textrm {面}}(P),b^{F}\in F\}}$${\displaystyle B\subseteq {\textrm {面}}(P)}$${\displaystyle {\textbf {b}}}$${\displaystyle b^{P}\in \operatorname {conv} \{b^{F}:F\in B\}}$

KKMS 定理は、多面体と が面 F の重心である(特に、は の重心であり、 は点 である) 小宮の定理の特殊なケースです。 ${\displaystyle P=\デルタ _{n-1}}$${\displaystyle b^{F}}$${\displaystyle b^{P}}$${\displaystyle \Delta _{n-1}}$${\displaystyle (1/n,\ldots ,1/n)}$

オレグ・R・ムシンは、被覆上の境界条件を用いて、KKM補題とKKMS定理のいくつかの一般化を証明した。境界条件はホモトピーと関連している。^{[13] [14]}

• KKMS定理とカラテオドリの定理の共通の一般化。^[15]

• KKM 補題の証明については Planet Math を参照してください。