Sperner 引理

Sperner 引理是个组合学定理, 描述单形的单纯剖分在特定染色下的性质. 它是代数拓扑中 Brouwer 不动点定理的组合类比, 它们亦可互相推出.

1陈述

以下固定 $n$ 维单形 ${\Delta }^n$ 及其单纯剖分 $T$. 以 $0,1,\dots ,n$ 记 ${\Delta }^n$ 的顶点.

定义 1.1 (Sperner 染色). 称 $T$ 的一种顶点染色为 Sperner 染色, 意思是其颜色取值在 $\{0,1,\dots ,n\}$, 且对于子集 $S\subseteq \{0,1,\dots ,n\}$, 单形 ${\Delta }^n$ 的面 $S$ 上的点, 其颜色都取值在 $S$ 中. 特别地, ${\Delta }^n$ 的顶点 $i$ 的颜色须为 $i$.

定理 1.2 (Sperner 引理). ${\Delta }^n$ 的任一单纯剖分的任一 Sperner 染色中, 都有顶点颜色互异的 $n$-单形.

2证明

这里呈现两个证明, 一个是纯组合的, 一个使用代数拓扑中的胞腔同调.

组合方法

用数学归纳法. 需加强命题如下:

定理 2.1. ${\Delta }^n$ 的任一单纯剖分 $T$ 的任一 Sperner 染色中, 顶点颜色互异的 $n$-单形个数为奇数.

证明. 对 $n$ 归纳. $n=0$ 时为显然. 现设 $n>0$, 命题对 $n-1$ 维成立, 来证明 $n$ 维情形. 考虑图 $G$, 其顶点为 $T$ 中所有 $n$-单形, 再加一个代表 ${\Delta }^n$ 外部的顶点 $\ast$; 两顶点间有边, 当且仅当它们代表的区域沿着一个各顶点颜色为 $0,1,\dots ,n-1$ 的 $(n-1)$-单形相邻. 依定义, 对单形 $t\in T$, 设其顶点颜色集合为 $S(t)$, 则其在图 $G$ 中的度 $d(t)$ 与 $S(t)$ 关系如下: $$d(t)=\{\begin{array}{ll}0,& S(t)⊉\{0,1,\dots ,n-1\};\\ 1,& S(t)=\{0,1,\dots ,n\};\\ 2,& S(t)=\{0,1,\dots ,n-1\};\end{array}$$而对 ${\Delta }^n$ 的面 $\{0,1,\dots ,n-1\}$ 用归纳假设, 知 $\ast$ 的度为奇数. 由于图的顶点度数之和总是偶数, 所以除 $\ast$ 之外的奇度点的个数为奇数, 也即顶点颜色互异的 $n$-单形个数为奇数.

$\square$

注 2.2. 这一证明相当于使用拓扑中的模 $2$ 度. 如考虑单形的定向, 并改用有向图, 则可归纳证明, 顶点颜色互异的 $n$-单形中, 与 ${\Delta }^n$ 有相同定向者比相反定向者多一个.

代数拓扑方法

还是加强命题归纳.

定理 2.3. 设 CW 复形 $X$ 满足其每个胞腔的闭包都可缩. 设 $f:X\to X$ 是其自映射, 把每个胞腔都映到自身的闭包内. 则 $f$ 在各胞腔链群上诱导的映射都是 $\mathrm{id}$.

证明. 只需对单个胞腔证明. 取一个 $n$ 维胞腔 $e^n$, 可设 $X=\overline{e^n}$. 对 $n$ 归纳. $n=0$ 时为显然. 现设 $n>0$, 命题对 $n-1$ 维成立, 来证明 $n$ 维情形. 写出 $f$ 诱导的胞腔链复形映射$$0C_n(X)C_{n-1}(X)\cdots C_0(X)00C_n(X)C_{n-1}(X)\cdots C_0(X)0f_n{f}_{n-1}{f}_0$$由条件, $X=\overline{e^n}$ 可缩, $n>0$, 故 $H_n(X)=0$, $C_n(X)\hookrightarrow C_{n-1}(X)$. 由归纳假设, $f_0,\dots ,f_{n-1}$ 都是 $\mathrm{id}$. 所以 $f_n$ 也是 $\mathrm{id}$.

$\square$

回到原命题. 取 $X={\Delta }^n$ 附带标准胞腔结构, $f$ 取为将 $T$ 中各个顶点打到其颜色, 各个单形分别线性地打到 ${\Delta }^n$. 则由 Sperner 染色的定义, $f$ 将 ${\Delta }^n$ 的各个面映到自身. 故由以上定理, $f$ 在各胞腔链群上诱导的映射都是 $\mathrm{id}$, 特别地其在相对同调 $H_n({\Delta }^n,\partial {\Delta }^n)$ 上诱导的映射为 $\mathrm{id}$. 如果没有顶点颜色互异的 $n$-单形, $f$ 就会把 ${\Delta }^n$ 映射到 $\partial {\Delta }^n$, 矛盾.

3推广

4相关条目

•	Brouwer 不动点定理
•	Monsky 定理

术语翻译

Sperner 引理 • 英文 Sperner’s lemma