シュペルナーの補題

一次元の場合、スペルナーの補題は中間値の定理の離散版とみなすことができます。この場合、本質的には、離散関数が0と1の値のみを取り、0から始まり1で終わる場合、その関数は奇数回値を切り替える必要があることを示しています。

最も頻繁に言及されるのは二次元の場合である。それは次のように述べられている。

三角形ABC を、辺同士が接する小さな三角形からなる三角形分割に任意に分割します。次に、三角形分割の Sperner 彩色を、三角形分割の頂点に 3 つの色を割り当てることで定義します。

1. 初期三角形の3つの頂点A、B、Cはそれぞれ異なる色をしている。
2. 三角形ABCの​​任意の辺上に位置する頂点は、その辺の両端の色、つまり2色のみを持つ。例えば、AC上の各頂点は、 AまたはCと同じ色でなければならない。

すると、あらゆる三角形分割のあらゆるスペルナー彩色には、少なくとも１つの「虹色の三角形」が存在する。虹色の三角形とは、三角形分割内の小さな三角形で、その頂点が３つの異なる色で彩色されている三角形のことである。より正確には、虹色の三角形の数は奇数でなければならない。

一般的には、この補題はn次元単体に関するものである。

$\displaystyle {\mathcal {A}}=A_{1}A_{2}\ldots A_{n+1}.}$

三角形分割Tは、${\displaystyle {\mathcal {A}}}$より小さなn次元単体に分割し、再び面と面を合わせる。彩色関数を次のように表す。

${\displaystyle f:S\to \{1,2,3,\dots ,n,n+1\},}$

ここで、SはTの頂点の集合である。彩色関数は、以下の条件を満たす場合にスペルナー彩色を定義する。

1. 大きな単体の頂点は異なる色で着色されている。つまり、一般性を失うことなく、1 ≤ i ≤ n + 1に対してf ( A _i ) = i となる。
2. 大きな単体の任意のk次元部分面上に位置するTの頂点

${\displaystyle A_{i_{1}}A_{i_{2}}\ldots A_{i_{k+1}}}$

色のみで着色されています

${\displaystyle i_{1},i_{2},\ldots ,i_{k+1}.}$

すると、 n次元単体のあらゆる三角形分割のあらゆるスペルナー彩色には、虹単体（頂点がn +1色すべてで彩色された単体）が奇数個含まれる。特に、少なくとも1つの虹単体が存在する。

まず、2次元の場合について考えてみましょう。三角形分割Tから構築されたグラフGを以下のように考えます。

Gの頂点は、 Tの要素に加えて三角形の外側の領域です。2つの頂点は、対応する領域が共通の境界を共有し、一方の端点が色1、もう一方の端点が色2である場合に、辺で結ばれます。

区間ABには、色 1-2 の境界が奇数個あることに注意してください (A は色 1、B は色 2 であり、ABに沿って移動すると、最初と最後で異なる色を得るためには、色の変化が奇数個必要になります)。区間 BC と CA には、色 1-2 の境界は全くありません。したがって、外側の領域に対応するGの頂点の次数は奇数です。握手補題により、G には次数が奇数の頂点が偶数個あります。したがって、外側の領域を除いた残りのグラフには、 Tの要素に対応する次数が奇数の頂点が奇数個あります。

Tから作られる三角形の次数は 0、1、または 2 のいずれかであり、次数 1 は 1、2、3 の 3 色で着色された三角形に対応することが容易にわかります。

こうして、三角形分割Tには奇数個（かつ少なくとも1個）の完全に着色された三角形が存在するという、やや強い結論が得られた。

多次元の場合については、単体の次元に関する帰納法によって証明できます。2次元の場合と同様の推論を適用することで、n次元三角形分割において、完全に彩色された単体の数が奇数であることを結論づけることができます。

グラフ理論を初めて学ぶ読者のために、先に述べた証明をさらに詳しく説明します。

この図は、前述の例の頂点の色を番号で示したものです。頂点に異なる番号が付けられた小さな三角形は、グラフ上で網掛けされています。それぞれの小さな三角形は、三角形分割から得られる新しいグラフのノードになります。小文字は領域を表しており、図の内側の8つの領域と、外側の領域iを示しています。

前述のとおり、端点が1と2の番号を持つエッジを共有するノードは、派生グラフで結合されます。例えば、ノードdは外側領域iとエッジを共有しており、その頂点はすべて異なる番号を持つため、網掛けされます。ノードbは2つの頂点が同じ番号を持つため網掛けされませんが、外側領域に結合されます。

例えば、ノードaの 1 と 1 の間の辺に番号 3 のノードを挿入し、そのノードをaのもう一方の頂点に接続することで、新しい番号付き三角形を追加できます。そうすると、ノードfとgの場合のように、新しいノードのペアが作成されます。

アンドリュー・マクレナンとラビー・トゥルキーは、単体の体積を用いた別の証明を提示した。これは帰納法を用いず、1ステップで進む。^{[ 2 ] [ 3 ]}

三角形分割の各頂点に複数の色をラベル付けできると仮定すると、彩色関数はF  : S → 2 ^{[ n +1]}となります。

すべての部分単体について、その頂点上のラベル付けの集合は、色の集合[ n + 1]上の集合族です。この集合族はハイパーグラフと見なすことができます。

単体の面上のすべての頂点vに対して、 f ( v )の色が面の端点上の色の集合の部分集合である場合、バランスのとれたラベル付けを持つ部分単体が存在します。このラベル付けでは、対応するハイパーグラフが完全な分数マッチングを許容します。例として、 n = 2の場合のバランスのとれたラベル付けの例をいくつか示します。

• ({1}, {2}, {3}) - 重み(1, 1, 1)によってバランスが取られています。
• ({1,2}, {2,3}, {3,1}) - 重み (1/2, 1/2, 1/2)でバランスが取れています。
• ({1,2}, {2,3}, {1}) - 重み(0, 1, 1)でバランスが取れています。

これは1973年にシャプレーによって証明された。 ^{[ 5 ]}これはKKMS補題の組み合わせ論的類似物である。

n個の頂点を持つd次元多面体Pがあるとします。Pは三角形分割されており、三角形分割の各頂点には{1, …, n } のラベルが付けられています。すべての主頂点iにはi というラベルが付けられています。部分単体は、 d次元であり、そのd + 1個の頂点それぞれに異なるラベルが付けられている場合、完全ラベル付きと呼ばれます。Pの面Fのすべての頂点に、 Fの端点のラベルのいずれかが付けられている場合、少なくともn – d 個の完全ラベル付き単体が存在します。いくつかの特殊なケースは次のとおりです。

• d = n – 1。この場合、 Pは単体です。多面体スペルナーの補題は、少なくとも 1 つの完全ラベル付き単体が存在することを保証します。つまり、スペルナーの補題に帰着します。
• d = 2 。n 個の頂点を持つ2次元多角形が、ラベル1, …, nを使用して三角形分割され、頂点iと頂点i + 1 (mod n )の間の各面ではラベルiとi + 1のみが使用されるとします。このとき、 3 つの異なるラベルが使用される部分三角形が少なくともn – 2個存在します。

一般的な命題は、1996 年にAtanassovによって予想され、 d = 2の場合について証明されました。^{[ 6 ]} 一般的な場合の証明は、2002 年にde Loera、Peterson、およびSuによって初めて与えられました。 ^{[ 7 ]}彼らは 2 つの証明を提供しています。1 つ目は非構成的で、ペブル セットの概念を使用しています。2 つ目は構成的で、グラフ内のパスをたどる議論に基づいています。

ムニエ^{[ 8 ]は}、この定理を多面体から多面体ボディへと拡張した。多面体ボディは凸である必要も、単連結である必要もない。特に、Pが多面体である場合、その面の集合は多面体ボディである。頂点v1 , ..., vn_を持つ多面体ボディのあらゆるスペルナーラベル付けにおいて、少なくとも次のものが存在する_。

${\displaystyle nd-1+\left\lceil {\frac {\min _{i=1}^{n}\deg _{B(P)}(v_{i})}{d}}\right\rceil }$

完全にラベル付けされた単体とは、これらの単体の任意のペアが2つの異なるラベル付けを受けるような単体のことです。次数deg _{B ( P )} ( v _i )は、 v _iが属するB ( P )の辺の数です。次数は少なくともdなので、下限は少なくともn – dです。しかし、それより大きくなることもあります。例えば、n 個の頂点を持つ 4 次元の巡回多面体の場合、下限は次のようになります。

${\displaystyle n-4-1+\left\lceil {\frac {n-1}{4}}\right\rceil \approx {\frac {5}{4}}n.}$

ムシン^{[ 9 ]}はさらに、境界の有無にかかわらず、d次元区分線形多様体に定理を拡張した。

浅田、フリック、ピシャロディ、ポレヴィ、ストーナー、ツァン、ウェルナー^{[ 10 ]}は、境界を持つ擬似多様体に定理をさらに拡張し、ペアワイズに異なるラベルを持つファセットの数の下限を改善した。

単体を部分単体に分割するのではなく、n次元立方体をより小さなn次元立方体に分割したものを考えてみましょう。

ハロルド・W・クーン^{[ 11 ]}は次の補題を証明した。ある整数Mに対して、立方体[0, M ] ^nがMn個^の単位立方体に分割されているとする。分割の各頂点に{1, …, n + 1}のラベルが付けられており、すべての頂点vについて次の条件が満たされているとする。(1) v _i = 0の場合、 vのラベルは最大でiである。(2) v _i = Mの場合、 vのラベルはiではない。すると、すべてのラベル{1, …, n + 1}を持つ単位立方体が存在する（一部は複数回）。n = 2の特別なケースは次のとおりである。正方形が部分正方形に分割され、各頂点に{1,2,3}のラベルが付けられているとする。左辺には1（=最大で1）が付けられ、下辺には1または2（=最大で2）が付けられ、上辺には1または3（=2ではない）が付けられる。そして右端には2または3（1ではない）のラベルが付いています。次に、1、2、3のラベルが付いた正方形があります。

ポアンカレ・ミランダの定理[ ^{12 ]}に関連する別の変形は次のとおりである。立方体[0, M]nがMn個の単位立方体に分割されていると仮定する^。各頂点に^は長^さnのバイナリベクトルがラベル付けされており、すべての頂点vについて次のようになっていると仮定する。(1) v _i = 0の場合、 v上のラベルの座標iは0である。(2) v _i = Mの場合、 v上のラベルの座標iは1である。(3) 2つの頂点が隣接している場合、それらのラベルは最大で1つの座標だけ異なる。すると、すべての2n^個のラベルが異なる単位立方体が存在する。 2次元の場合、この定理を別の方法で定式化すると次のようになります。^{[ 13 ]}条件(1)と(2)を満たす任意のラベル付けにおいて、ラベルの合計が0となるセルが少なくとも1つ存在します[1次元セルで(1,1)と(-1,-1)のラベルを持つもの、または4つの異なるラベルを持つ2次元セル]。

ウォルジー^{[ 14 ]は、}完全にラベル付けされた立方体の数が奇数であることを証明することで、これら2つの結果を強化した。

ムシン^{[ 13 ]}はこれらの結果を一般的な四角形分割に拡張した。

単一のラベル付けではなく、n 個の異なるスペルナーラベル付けがあると仮定します。単体の各頂点のラベルが異なるラベル付けから選択されるようなペア (単体、順列) を考えます (したがって、各単体に対してn !個の異なるペアがあります)。すると、少なくともn !個の完全にラベル付けされたペアが存在します。これは、任意の三角形分割に対してRavindra Bapat ^{[ 15 ]}によって証明されました。特定の三角形分割に対してのみ有効な、より単純な証明が後に Su によって提示されました。^{[ 16 ]}

この補題を別の言い方で表現すると次のようになります。n人の人がいて、それぞれが同じ三角形分割に対して異なるスペルナーラベル付けを行うとします。すると、単体が存在し、各頂点には、所有者によって異なるラベルが付けられる（ある人は頂点に 1 を付け、別の人は頂点に 2 を付け、といった具合）ような、人々と頂点とのマッチングが存在します。さらに、そのようなマッチングは少なくともn !個存在します。これを利用して、連結したピースを持つ羨望のないケーキカットを見つけることができます。

浅田、フリック、ピシャロディ、ポレヴィ、ストーナー、ツァン、ウェルナー^{[ 10 ]}はこの定理を 境界を持つ擬多様体に拡張した。

より一般的に、m 個の異なるスペルナーラベル付けがあると仮定します。ここで、m はnと異なる場合があります。すると、次のようになります。 ^{[ 17 ]：定理 2.1}

1. 合計がm + n – 1となる任意の正の整数k ₁ , …, k _mに対して、任意のi ∈ {1, …, m } について、ラベル番号i がn個のうち少なくともk _i個の異なるラベルを使用するベビー単体が存在する。さらに、各ラベルはm 個のラベルのうち少なくとも 1 つによって使用される。
2. 合計がm + n – 1である任意の正の整数I ₁ , …, I _mに対して、すべてのj ∈ {1, …, n }に対して、ラベル jが少なくともl _j ( m個のうち) 個の異なるラベル付けによって使用されるベビーシンプレックスが存在する。

どちらのバージョンも、 m = 1の場合、またはm 個のラベルがすべて同じ場合、スペルナーの補題に帰着する。

^{同様の一般化については[ 18 ]}を参照のこと。

BrownとCairns ^{[ 19 ]}は単体の向きを考慮することでSpernerの補題を強化した。各部分単体は、+1または-1（完全にラベル付けされている場合）、あるいは0（完全にラベル付けされていない場合）のいずれかの向きを持つ。彼らは、単体のすべての向きの合計が+1であることを証明した。特に、これは完全にラベル付けされた単体の数が奇数であることを意味する。

n = 3の例として、三角形が{1,2,3} でラベル付けされているとします。三角形の境界上のラベルの循環シーケンスを考えます。ラベル付けの次数を、1 から 2 への切り替えの数から 2 から 1 への切り替えの数を引いた数として定義します。右の表の例を参照してください。2 から 3 への切り替えの数から 3 から 2 への切り替えの数を引いても、3 から 1 への切り替えの数から 1 から 3 への切り替えの数を引いても、次数は同じになることに注意してください。

ムシンは、完全にラベル付けされた三角形の数は、少なくともラベル付けの次数であることを証明した。^{[ 20 ]}特に、次数がゼロでない場合、少なくとも1つの完全にラベル付けされた三角形が存在する。

ラベル付けがスペルナー条件を満たす場合、その次数はちょうど1になります。1-2スイッチと2-1スイッチは頂点1と頂点2の間の辺にのみ存在し、1-2スイッチの数は2-1スイッチの数より1つ多くなければなりません（頂点1から頂点2へ移動する場合）。したがって、元のスペルナーの補題はムシンの定理から導かれます。

有限木と無限木、およびサイクルについても同様の補題がある。^{[ 21 ]}