Spernerの補題
概要
Spernerの補題（Sperner's lemma）とは、$n$ 単体の三角形分割（単体複体になる分割）の各頂点に、その点を含む最小の面の頂点の番号のどれか 1 つを色として塗ると、$n+1$ 色すべてが頂点に現れる小単体の個数が奇数になり、とくに 1 つ以上ある、という組合せ論の補題である。色 $1,\dots,n$ の面を小単体ごとと面ごとに二重に数え、次元についての帰納法で証明できる。閉集合の被覆についての KKM の補題と、単体からそれ自身への連続写像が不動点をもつこと（Brouwer の不動点定理）がここから導かれる。
Spernerの補題（Sperner's lemma）とは、$n$ 次元の単体を有限個の小さな単体に分割し（分割は単体複体になっているとする）、分割の各頂点に「その点を含む最小の面の頂点の番号」のどれか 1 つを色として塗ると、$n+1$ 色すべてが頂点に現れる小単体の個数は奇数であり、とくに 1 つ以上ある、という組合せ論の補題である。
三角形 $[e_1,e_2,e_3]$ で言えば、頂点 $e_i$ には色 $i$ を、辺 $e_ie_j$ の上の点には色 $i$ か $j$ を塗り、内部の点には好きな色を塗る。どう塗っても、3 色そろった小三角形が奇数個できる。1 次元では、線分の両端に色 $1$ と $2$ を塗り、間の点に好きな色を塗ると、色が切り替わる小区間が奇数個ある、という当たり前の事実になる。Sperner の補題は、この「両端で色が違えばどこかで切り替わる」という中間値の定理型の事実の、高次元への組合せ的な一般化である。
この補題は、数え上げと次元についての帰納法だけで証明でき、連続写像についての位相的な定理を組合せ論に帰着させる道具になる。この記事では、任意の三角形分割についてこの補題を証明し、そこから閉集合の被覆についての KKM の補題と、単体からそれ自身への連続写像の不動点の存在（Brouwerの不動点定理）を導く。集合族についての Spernerの定理 とは別の主張である。
設定と定義
$n\ge0$ とし、$[n+1]:=\{1,\dots,n+1\}$ と書く。$\mathbb{R}^{n+1}$ の標準基底を $e_1,\dots,e_{n+1}$ とし、
$$
\Delta^n:=\Bigl\{x\in\mathbb{R}^{n+1}\Bigm| x_i\ge0\ (i\in[n+1]),\ \sum_{i=1}^{n+1}x_i=1\Bigr\}
$$
を $n$ 次元の標準単体とする（単体複体 の定義「単体と重心座標」の意味の $n$ 単体で、点 $x$ の重心座標は座標 $x_i$ そのものである）。空でない $S\subset[n+1]$ について、$\Delta_S:=\{x\in\Delta^n\mid x_i=0\ (i\notin S)\}$ は $\{e_i\mid i\in S\}$ が張る面である。$x\in\Delta^n$ の台を $\operatorname{supp}x:=\{i\mid x_i>0\}$ とすると、$\Delta_{\operatorname{supp}x}$ は $x$ を含む最小の面である。$j\in[n+1]$ について
$$
G_j:=\{x\in\Delta^n\mid x_j=0\}=\Delta_{[n+1]\setminus\{j\}}
$$
を $e_j$ の対面（$n\ge1$ のとき $n-1$ 次元の面）とする。$\Delta^n$ の境界は $G_1\cup\dots\cup G_{n+1}$ である。
$\mathbb{R}^{n+1}$ の有限な幾何的単体複体 $K$（単体複体 の定義「幾何的単体複体」。単体の面はまた $K$ に属し（条件 (R1)）、2 つの単体の共通部分は空か両者の共通の面である（条件 (R2)））で、その単体の和集合 $\bigcup_{\sigma\in K}\sigma$ が $\Delta^n$ に等しいものを、$\Delta^n$ の三角形分割という。$K$ の頂点の全体を $V(K)$ と書き、単体の直径の最大値を $K$ の網目といい $\operatorname{mesh}K$ と書く。
$\Delta^n$ の面の全体は、それ自身 1 つの三角形分割である。その重心細分を $r$ 回繰り返したものも三角形分割であり（細分(単体複体) の定理「重心細分は単体複体の細分である」）、その網目は $r\to\infty$ で $0$ に近づく（同じ記事の系「反復した重心細分の網目」）。
$K$ を $\Delta^n$ の三角形分割とする。写像 $\lambda\colon V(K)\to[n+1]$ が、どの頂点 $v$ についても
$$
\lambda(v)\in\operatorname{supp}v
$$
を満たすとき、$\lambda$ を Sperner の色塗りといい、$\lambda(v)$ を $v$ の色という。頂点の色が $1,\dots,n+1$ のすべてになる $K$ の $n$ 単体を全色単体という。
条件 $\lambda(v)\in\operatorname{supp}v$ は、「$v$ を含む最小の面 $\Delta_{\operatorname{supp}v}$ の頂点の番号を色にする」と言い換えられる。とくに頂点 $e_i$ の色は $i$ に決まり、面 $\Delta_S$ の上の頂点の色は $S$ に属し、$G_j$ の上の頂点に色 $j$ は塗られない。内部の頂点（すべての座標が正）の色は自由である。
分割の面の隣接
次節の証明の要は、三角形分割の $n-1$ 単体が、内部にあれば 2 つの $n$ 単体に、境界にあれば 1 つの $n$ 単体にはさまれることである。
$n\ge1$ とし、$K$ を $\Delta^n$ の三角形分割とする。
- $K$ の $n-1$ 単体 $\tau$ を面にもつ $K$ の $n$ 単体の個数は、$\tau$ がある $G_j$ に含まれれば $1$、どの $G_j$ にも含まれなければ $2$ である。
- 各 $j$ について、$K_j:=\{\sigma\in K\mid\sigma\subset G_j\}$ は $K$ の部分複体であり、その単体の和集合は $G_j$ に等しい。
要点：$\tau$ の重心 $x$ の近くでは、$\tau$ を面にもつ $n$ 単体は $\tau$ の張る超平面の片側を半球ずつ埋め、同じ側に 2 つは入らない。$x$ が $\Delta^n$ の内部にあれば両側が、境界にあれば片側だけが $\Delta^n$ に入る。
詳しい証明を開く
$A:=\{x\in\mathbb{R}^{n+1}\mid\sum_ix_i=1\}$ を $\Delta^n$ を含む $n$ 次元のアフィン部分空間とし、以下、内部・開集合は $A$ の中で考える。
段 0（アフィン関数の事実）．単体 $\sigma=[v_0,\dots,v_k]$ の上で $0$ 以上のアフィン関数 $h$ が、すべての重心座標が正の点 $y=\sum_it_iv_i$ で $0$ になるなら、$0=\sum_it_ih(v_i)$ と $h(v_i)\ge0$ から $h(v_i)=0$ がすべての $i$ で成り立ち、$h$ は $\sigma$ の上で $0$ である。$h=x_j$ に当てると：$\Delta^n$ に含まれる単体が、開単体の点を $G_j$ にもてば、単体全体が $G_j$ に含まれる。
段 1（主張 2）．$\sigma\subset G_j$ の面も $G_j$ に含まれ、(R2) は $K$ から受け継がれるので、$K_j$ は部分複体である。$y\in G_j$ をとると、$y$ はある $\sigma\in K$ の開単体に属し（単体複体 の補題「各点の台」）、段 0 により $\sigma\subset G_j$ である。よって $K_j$ の単体の和集合は $G_j$ である。
段 2（$\Delta^n$ は $n$ 単体の和）．次元が $n$ より小さい単体は $A$ の超平面に含まれるので、その有限和 $L$ は内部が空の閉集合である。$n$ 単体の和 $M$ は閉集合である。$y\in\Delta^n\setminus M$ があるとすると、$y$ のある近傍は $M$ と交わらない。$\Delta^n$ の重心 $b$ について $(1-s)y+sb$（$0< s\le1$）はすべての座標が正なので、$s$ を小さくとると、この近傍の中に $\Delta^n$ の内部の点 $z$ がとれ、$z$ の小さい近傍は $\Delta^n$ に含まれて $M$ と交わらないので $L$ に含まれる。これは $L$ の内部が空であることに反する。よって $\Delta^n=M$ である。
段 3（$\tau$ を含む $n$ 単体）．$\tau$ の重心を $x$、$\tau$ の張る $A$ の超平面を $H$ とする。$n$ 単体 $\sigma\in K$ が $x$ を含めば、$\sigma\cap\tau$ は (R2) により $\tau$ の面で、開単体の点 $x$ を含むので $\tau$ 自身であり、$\tau$ は $\sigma$ の面である。$\tau$ を面にもつ $n$ 単体 $\sigma$ の残りの頂点を $w$ とし、$w$ の重心座標を $A$ の上のアフィン関数 $\beta_\sigma$ に延ばすと、$\beta_\sigma$ は $H$ の上でちょうど $0$ になり、$\beta_\sigma(w)=1$ である。$x$ での $\tau$ の頂点の重心座標は $\frac1n>0$ なので、連続性からある $r>0$ について $\{y\in A\mid\lvert y-x\rvert< r,\ \beta_\sigma(y)\ge0\}\subset\sigma$ が成り立つ。$H$ の上でちょうど $0$ になる 2 つのアフィン関数は定数倍の違いしかないので、$\beta_\sigma>0$ の側を $w$ の側と呼べば意味が定まる。
段 4（各側に高々 1 つ）．$\tau$ を面にもつ $n$ 単体 $\sigma,\sigma'$ の残りの頂点が同じ側にあれば、段 3 の半球の共通部分は内部が空でないので、$\sigma\cap\sigma'$ は内部が空でない。$\sigma\cap\sigma'$ は (R2) により $\sigma$ の面であり、$\sigma$ の真の面は超平面に含まれるので $\sigma\cap\sigma'=\sigma$ である。同様に $=\sigma'$ であり、$\sigma=\sigma'$ である。
段 5（どちらの側にあるか）．$H$ に平行でない $A$ の方向 $u$ をとる。$t$ を $0$ に近づけたとき $x+tu\in\Delta^n$ となる $t>0$ の列があれば、段 2 と単体の有限性から、ある $n$ 単体がその無限個を含み、閉なので $x$ も含む。段 3 によりそれは $\tau$ を面にもち、$H$ の外の点 $x+tu$ を含むので、残りの頂点は $u$ の側にある。$t< 0$ の側も同様である。$\tau$ がどの $G_j$ にも含まれなければ、段 0 により $x$ のすべての座標は正で、$x$ は $\Delta^n$ の内部にあるので、両側に 1 つずつ、合わせて $2$ つある。$\tau\subset G_j$ なら、$H$ と $G_j$ の張る超平面はともに $n-1$ 次元なので一致する。$\Delta^n\subset\{x_j\ge0\}$ なので $x_j< 0$ の側に $n$ 単体はない。$i\ne j$ について $x_i=0$ なら段 0 により $\tau\subset G_i\cap G_j$ となり、これは $n-2$ 次元なので起こらない。よって $(1-t)x+te_j$（$0\le t\le1$）は $\Delta^n$ に属し、$x_j>0$ の側にはちょうど 1 つある。$\square$
主張と証明
$n\ge0$ とし、$K$ を $\Delta^n$ の三角形分割、$\lambda$ を Sperner の色塗りとする。このとき全色単体の個数は奇数である。とくに全色単体が少なくとも 1 つある。
$n$ についての帰納法で示す。$n=0$ では $\Delta^0=\{e_1\}$、$K=\{\{e_1\}\}$ で、$\lambda(e_1)=1$ なので全色単体はちょうど 1 つである。
$n\ge1$ とし、$n-1$ では主張が成り立つとする。$K$ の $n-1$ 単体で、頂点の色が $1,\dots,n$ のすべてになるものを扉と呼ぶ（$n$ 個の頂点に $n$ 色が 1 回ずつ現れる）。$K$ の $n$ 単体 $\sigma$ について、$\sigma$ の $n+1$ 個の面（$n-1$ 単体）のうち扉であるものの個数を $d(\sigma)$ とし、
$$
D:=\sum_{\sigma}d(\sigma)
$$
（和は $K$ の $n$ 単体の全体にわたる）を 2 通りに数える。
$n$ 単体ごとに数える。 $\sigma$ の頂点の色の集合を $C$ とする。$C=[n+1]$ なら、扉になるのは色 $n+1$ の頂点を除いた面だけで、$d(\sigma)=1$ である。$C=\{1,\dots,n\}$ なら、$n+1$ 個の頂点に $n$ 色が現れるので、ちょうど 1 つの色が 2 つの頂点に現れ、扉はそのどちらかを除いた 2 つの面で、$d(\sigma)=2$ である。それ以外の場合は $1,\dots,n$ のどれかの色が $\sigma$ に現れないので $d(\sigma)=0$ である。よって、全色単体の個数を $N$ とすると
$$
D\equiv N\pmod 2
$$
である。
扉ごとに数える。 $D$ は、扉 $\tau$ ごとに「$\tau$ を面にもつ $n$ 単体の個数」を足したものである。lem-sperner-facets の 1 により、この個数は、$\tau$ がどの $G_j$ にも含まれなければ $2$、ある $G_j$ に含まれれば $1$ である。扉 $\tau$ が $G_j$ に含まれるとき、$\tau$ の頂点はどれも第 $j$ 座標が $0$ なので色 $j$ をもたない。扉には色 $1,\dots,n$ が現れるので $j=n+1$ である。したがって
$$
D\equiv(\text{$G_{n+1}$ に含まれる扉の個数})\pmod 2
$$
である。
底面で帰納法の仮定を使う。 lem-sperner-facets の 2 により、$K_{n+1}$ は単体の和集合が $G_{n+1}$ の部分複体である。最後の座標を落とす写像 $\pi\colon G_{n+1}\to\Delta^{n-1}$、$(x_1,\dots,x_n,0)\mapsto(x_1,\dots,x_n)$ は距離を保つアフィンな全単射で、単体を単体に写し、台を変えない。よって $\pi(K_{n+1})$ は $\Delta^{n-1}$ の三角形分割であり、$\lambda\circ\pi^{-1}$ はその Sperner の色塗りである（$G_{n+1}$ の頂点の台は $[n]$ に含まれる）。$G_{n+1}$ に含まれる扉は、$\pi$ で写すと、この色塗りの全色単体とちょうど対応する。帰納法の仮定により、その個数は奇数である。
以上より $N\equiv D\equiv1\pmod2$ であり、$N$ は奇数である。$\square$
全色単体の個数は奇数であればよく、1 とは限らない（ex-sperner-one-dim）。主張は Sperner の 1928 年の論文による（Eng89 §7.3 の注、p. 410）。Eng89 は $l$ 回の重心細分について、BM76 は三角形の任意の三角形分割について、この記事と同じ二重数えで証明している。この記事の lem-sperner-facets は、任意の三角形分割について面の隣接を示したもので、重心細分の組合せ的な記述には頼らない。
扉による数え方は、扉を「通り抜けられる壁」と見ると、全色単体を実際に探す手順にもなる（rem-sperner-path）。
例
$n=1$ では $\Delta^1$ は $e_1$ と $e_2$ を結ぶ線分で、三角形分割は線分の上に点 $e_1=p_0,p_1,\dots,p_m=e_2$ を順に並べ、隣り合う 2 点を結ぶ小区間に分けたものである。Sperner の色塗りでは $p_0$ の色は $1$、$p_m$ の色は $2$ で、間の点の色は自由である。全色単体は両端の色が異なる小区間、すなわち色が切り替わる箇所で、色 $1$ から始まって色 $2$ で終わるので、切り替わりの回数は奇数である。たとえば $m=3$ で色を順に $1,2,1,2$ と塗ると、3 つの小区間はすべて全色単体で、個数は $3$ である。全色単体は奇数個であって、1 個とは限らない。
$n=2$ とし、$\Delta^2$ の重心 $g$ と 3 頂点を結んで、$\Delta^2$ を 3 つの三角形 $[e_1,e_2,g]$、$[e_2,e_3,g]$、$[e_3,e_1,g]$ に分ける（これらとその面の全体は三角形分割である）。Sperner の色塗りでは $e_i$ の色は $i$ で、$g$ の色 $c$ は $1,2,3$ のどれでもよい。三角形 $[e_i,e_j,g]$ が全色単体になるのは $\{i,j,c\}=\{1,2,3\}$ のとき、すなわち $\{i,j\}=[3]\setminus\{c\}$ のときだけである。よって $c$ をどう選んでも全色単体はちょうど 1 つである。
応用：KKM の補題と不動点
Sperner の補題を、細かい三角形分割の列に当てて極限をとると、連続的な主張が得られる。
$n\ge1$ とし、$F_1,\dots,F_{n+1}$ を $\Delta^n$ の閉集合とする。空でないどの $S\subset[n+1]$ についても
$$
\Delta_S\subset\bigcup_{i\in S}F_i
$$
が成り立つなら、$F_1\cap\dots\cap F_{n+1}\neq\emptyset$ である。
共通部分が空だとして矛盾を導く。$U_i:=\Delta^n\setminus F_i$ とおくと、$U_1,\dots,U_{n+1}$ はコンパクトな距離空間 $\Delta^n$ の開被覆である。Lebesgue数の補題 により $\varepsilon>0$ があって、直径が $\varepsilon$ 未満の $\Delta^n$ の空でない部分集合は、どれかの $U_i$ に含まれる。
$\Delta^n$ の面の全体の重心細分を十分多く繰り返して、網目が $\varepsilon$ 未満の三角形分割 $K$ をとる（節「設定と定義」の段落）。$v\in V(K)$ について、$v\in\Delta_{\operatorname{supp}v}\subset\bigcup_{i\in\operatorname{supp}v}F_i$ なので、$v\in F_i$ となる $i\in\operatorname{supp}v$ がある。そのような $i$ を 1 つ選んで $\lambda(v)$ とすると、$\lambda$ は Sperner の色塗りである。thm-sperner-main により全色単体 $\sigma$ がある。$\sigma$ の色 $i$ の頂点は $F_i$ に属するので、$\sigma$ はすべての $F_i$ と交わる。一方、$\operatorname{diam}\sigma< \varepsilon$ なので $\sigma$ はある $U_i$ に含まれ、$F_i$ と交わらない。これは矛盾である。$\square$
この補題と証明は Knaster・Kuratowski・Mazurkiewicz の 1929 年の論文による（Eng89 §7.3 の付録の Theorem 4、p. 416 と、p. 410 の注）。
$n\ge1$ とする。連続写像 $f\colon\Delta^n\to\Delta^n$ は不動点をもつ。
$f=(f_1,\dots,f_{n+1})$ と座標で書き、$F_i:=\{x\in\Delta^n\mid f_i(x)\le x_i\}$ とおく。$f_i$ と $x_i$ は連続なので $F_i$ は閉集合である。空でない $S$ と $x\in\Delta_S$ について、$\sum_{i\in S}x_i=1$ である。どの $i\in S$ でも $f_i(x)>x_i$ だとすると $\sum_{i\in S}f_i(x)>1$ となるが、$f(x)\in\Delta^n$ の座標は $0$ 以上で和が $1$ なのでこれは起こらない。よって $x$ はある $F_i$（$i\in S$）に属し、KKM の補題の仮定が成り立つ。thm-sperner-kkm により、すべての $i$ で $f_i(x)\le x_i$ となる $x$ がある。両辺の和はどちらも $1$ なので、すべての $i$ で等号が成り立ち、$f(x)=x$ である。$\square$
$\Delta^n$ は閉球体 $D^n$ と同相なので（単体複体 の命題「単体は閉球体と同相」）、この系から $D^n$ からそれ自身への連続写像も不動点をもつことが従う。これが Brouwerの不動点定理 で、その記事では格子状に分けた小単体について同じ補題を証明し、点列の極限で不動点を作っている。
反例の表
どの行も、1 つの条件だけを外している。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 色塗りの条件 $\lambda(v)\in\operatorname{supp}v$（1 頂点だけで破る） | $\Delta^2$ の面の全体、$e_1,e_2,e_3$ の色を $1,2,1$ | 全色単体が奇数個（実際は $0$ 個） |
| 単体の和集合が $\Delta^n$ に等しいこと | 重心 $g$ をとり、$[e_1,e_2,g]$ の面の全体、$e_1,e_2,g$ の色を $1,2,1$ | 全色単体が奇数個（実際は $0$ 個） |
| 分割が単体複体であること（(R2)） | 辺 $e_1e_2$ の中点 $m$ と $p:=\frac12(m+e_3)$ をとり、$[e_1,m,p]$、$[e_1,p,e_3]$、$[m,e_2,e_3]$ に分ける。$m$ の色は $2$、$p$ の色は $1$ | 全色単体が奇数個（実際は $0$ 個） |
| KKM の補題で $F_i$ が閉であること | $n=1$、$\Delta^1$ を $t\mapsto(1-t,t)$（$0\le t\le1$）で表し、$F_1$ を $0\le t< \frac12$、$F_2$ を $\frac12\le t\le1$ の部分 | $F_1\cap F_2\neq\emptyset$ |
1 行目：$e_3$ の台は $\{3\}$ なので色 $1$ は条件を破り、ほかの頂点は条件を満たす。ただ 1 つの $2$ 単体 $\Delta^2$ の色は $\{1,2\}$ で全色でない。
2 行目：$[e_1,e_2,g]$ の面の全体は単体複体で、各頂点の色は台に属する（$g$ の台は $[3]$）。ただ 1 つの $2$ 単体の色は $\{1,2\}$ で全色でない。単体の和集合は $\Delta^2$ の一部分だけである。
3 行目：3 つの三角形の和は $\Delta^2$ で、$m$ の台は $\{1,2\}$、$p$ の台は $[3]$ なので色塗りの条件は満たされる。$[e_1,p,e_3]$ と $[m,e_2,e_3]$ の共通部分は線分 $[p,e_3]$ で、これは $[m,e_2,e_3]$ の面でないので (R2) が破れる。3 つの三角形の色は $\{1,2,1\}$、$\{1,1,3\}$、$\{2,2,3\}$ で、どれも全色でない。lem-sperner-facets の 1 が破れ、たとえば辺 $[m,e_3]$ の一部 $[m,p]$ は三角形 $[e_1,m,p]$ の辺だが、$[m,e_2,e_3]$ の辺ではない。
4 行目：$t=0$ の点 $e_1$ は $F_1$ に、$t=1$ の点 $e_2$ は $F_2$ に属し、$F_1\cup F_2=\Delta^1$ なので被覆の条件は満たされる。$F_2$ は閉だが $F_1$ は閉でなく、$F_1\cap F_2=\emptyset$ である。
補足
要点：境界の扉から入り、全色でない単体ではもう 1 つの扉から出て隣へ進むと、道は全色単体で止まるか境界から出る。
詳しい説明を開く
prf-sperner-main の数え方から、全色単体を探す手順が得られる。$n$ 単体 $\sigma$ の扉の個数 $d(\sigma)$ は $0,1,2$ のどれかで、$1$ になるのは全色単体のときだけである。扉を共有する 2 つの $n$ 単体を隣どうしとし、$G_{n+1}$ の上の扉から $\Delta^n$ に入る。入った単体が全色でなければ扉はもう 1 つだけあるので、そこから隣の単体へ進む。どの単体も扉は 2 つ以下なので、同じ単体に 2 度入ることはなく、単体は有限個なので、道は全色単体で止まるか、$G_{n+1}$ の上の別の扉から外へ出る。$G_{n+1}$ の上の扉は奇数個なので、外から入って外へ出る道で組にならない扉が残り、そこから入った道は全色単体で止まる。$G_{n+1}$ の上の扉を見つける段で同じ手順を 1 つ下の次元で使えば、全体が帰納的な探索の手順になる。
cor-sperner-fixed-point の証明は、補題が「連続写像の不動点」という位相的な主張を、有限の数え上げと Lebesgue 数による極限で置き換えることを示している。境界で対称な三角形分割と $\pm1,\dots,\pm n$ のラベルについての Tuckerの補題 は、同じ意味で Borsuk–Ulamの定理 の組合せ的な対応物である。
関連項目
- 前提: 単体複体, 重心座標, 細分(単体複体)
- 応用: Brouwerの不動点定理, Lebesgue数の補題
- 比較: Tuckerの補題, Borsuk–Ulamの定理, 中間値の定理
- 名前の似た別の定理: Spernerの定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
