ホーム >> 場合の数 >> Spernerの補題

組合せ数学における一風変わった命題を紹介します.



Spernerの補題とは

Spernerの補題とは,ブラウワーの不動点定理の組合せ的なアナロジーとして知られている命題です. 本記事ではブラウワーの不動点定理との関連は解説せずに,Spernerの補題の主張と証明を紹介します.
Spernerの補題はそれ自体面白い命題で,意味と証明を理解するために特別な知識は使いません. より一般化された形でのSpernerの補題も存在しますが,この記事では簡単のために $1$ 次元版と $2$ 次元版に限って紹介します.

Spernerの補題(1次元版)

はじめに,$1$ 次元版のSpernerの補題を紹介します.
次のような状況を考えてみましょう. 直線上に $2$ 個以上の有限個の点が与えられているとします.
Spernerの補題

これらすべての点に対して,次のルールを満たすようにまたはの色を割り当てます.
$Rule~1$ : 両端は相異なる色を割り当てる.
$Rule~2$ : 両端以外の点はまたはを割り当てる.

Spernerの補題

つまり両端だけ異なる色を割り当て,それ以外の点は好きなように $2$ 色を割り当てます. このとき,異なる色が割り当てられた隣り合う $2$ 点が必ず存在します.これが $1$ 次元版のSpernerの補題の主張です.
Spernerの補題

まとめると,次のようになります.

Spernerの補題(1次元版):直線上に有限個の点集合 $S$ が与えられる.ただし,$|S|\ge 2$ とする.$S$ の各点に対して,次のルールを満たすような $2$ 色 () の色割り当てを考える.
$Rule~1$ : 両端は相異なる色を割り当てる.
$Rule~2$ : 両端以外の点はまたはを割り当てる.
このとき,異なる色が割り当てられた隣り合う $2$ 点が必ず存在する.


いくつかの具体例をみてみると,確かにこの補題の主張が成り立っていることが確認できます.

具体例

Spernerの補題

Spernerの補題

Spernerの補題

証明

さて,この補題はつぎのように簡単に示すことができます.

Spernerの補題(1次元版)の証明: 有限個の頂点を左端から順に $x_1,...,x_n$ とする. 左端から順に点をみていき,はじめてが割り当ている点を $x_i$ とする.$x_n$ が青色なので,このような点 $x_i$ は必ず存在する.また,$x_1$ は赤色なので,$2\le i \le n$ である.さらに $x_i$ ははじめて青色となる点であるから,$x_{i-1}$ は赤色である.したがって,$2$ 点 $x_{i-1},x_{i}$ は異なる色が割り当てられた隣り合う $2$ 点である.


さらに,このような異なる色が割り当てられた隣り合う $2$ 点のペアは奇数個であることもすぐに示せます.(興味のある人は証明をチャレンジしてみてください!) この事実は $2$ 次元版のSpernerの補題の証明の際に利用します.
Spernerの補題

Spernerの補題(2次元版)

つぎに,$2$ 次元版のSpernerの補題を紹介します.ここからが本題です.$2$ 次元版は $1$ 次元版よりも非自明で,より不思議な感じがすると思います.

今度は平面上の三角形 $ABC$ を考えます.この $\triangle ABC$ 上 ($\triangle ABC$ の境界と内部) に $A,B,C$ を含む有限個の点集合 $S$ が与えられます.
Spernerの補題

下図のように,$S$ によって $\triangle ABC$ は必ず三角形分割することができます.(これがなぜなのかは省略します.)
Spernerの補題

さてここで,有限個の点集合 $S$ のすべての点に対して,次のルールを満たすように $3$ 色の色 () を割り当てます.
$Rule~1$ : 頂点 $A$ は,頂点 $B$ は,頂点 $C$ はを割り当てる.
$Rule~2$ : 線分 $AB$ 上の頂点はまたは,線分 $BC$ 上の頂点はまたは,線分 $CA$ 上の頂点はまたはを割り当てる.
$Rule~3$ : 内部の頂点はまたはまたはを割り当てる.

このとき,$3$ 頂点に割り当てられた色が相異なるような三角形 (小三角形) が必ず存在します.(下図でオレンジ色の三角形) これが $2$ 次元版のSpernerの補題の主張です.
Spernerの補題

まとめると,つぎのようになります.

Spernerの補題(2次元版): $\triangle ABC$ 上に $A,B,C$ を含む有限個の点集合 $S$ と $S$ による三角形分割が与えられる.$S$ の各点に対して,次のルールを満たすような $3$ 色 () の色割り当てを考える.
$Rule~1$ : 頂点 $A$ は,頂点 $B$ は,頂点 $C$ はを割り当てる.
$Rule~2$ : 線分 $AB$ 上の頂点はまたは,線分 $BC$ 上の頂点はまたは,線分 $CA$ 上の頂点はまたはを割り当てる.
$Rule~3$ : 内部の頂点はまたはまたはを割り当てる.

このとき,$3$ 頂点に割り当てられた色が相異なるような三角形が必ず存在する.

Spernerの補題(2次元版)の証明

$2$ 次元版のSpernerの補題を証明してみましょう.$1$ 次元版よりもやや議論が必要ですが,特別な知識は用いません.証明のポイントは有限性です.

証明: 端点にが割り当てられたすべての辺に対し,その辺を交差するように矢印を引くことを考える.ただし,矢の向きは赤い頂点が左に,青い頂点が右にくるようにつける.(下図参照)
Spernerの補題

これによって,三角形分割の上にいくつかの矢印が描かれる.ひとつの三角形に着目すると,それに入ってくる矢印の数は $1$ つ以下で,それから出る矢印の数も $1$ つ以下である.$\triangle ABC$ の境界をまたぐ矢印は,辺 $AB$ 上にのみ存在しうる.さらに,$1$ 次元版のSpernerの補題のときの議論より,辺 $AB$ 上で外から内に入るような矢印が必ず存在する. そのような矢印を一つ選び.矢印を順にたどって三角形分割の中の三角形を次々に訪れると,矢印がそれ以上続かない三角形で止まるか,辺 $AB$ をまたいで外へ出るか,どちらかが起きる.

前者の場合は,矢印がそれ以上続かない三角形の $3$ 頂点はとなる.後者の場合は,辺 $AB$ 上での $2$ 色が割り当てられた隣接する $2$ 点組の数が必ず奇数であることから,辺 $AB$ 上で外から内に入るような別の矢印が存在する.したがって,前者の場合が必ず発生することが従う.