【筆記】不動點定理（一）斯達訥引理 Sperners Lemma

05-21

來自專欄不求甚解學經濟

這一部分是Sperner引理。沿「Sperner引理→KKM引理→Brouwer定理→Kakutani定理」的推進思路目前是諸多證明拓撲不動點定理的思路中最易懂的一種。

一些概念

1.仿射無關：如果 $X_{0},...,X_{m}$ 為線性無關，則 $X_{1}-X_{0},...,X_{m}-X_{0}$ 便是仿射無關的。（亦可仿照線性無關來定義仿射無關，即若任何一組標量 $a_{0},...,a_{n}$ ，在滿足不全為0但 $sum_{i=0}^{n}a_{i}=0$ 的條件下，都無法使得 $sum_{i=0}^{n}a_{i}X_{i}=0$ ，則稱這組向量 $X_{0},...,X_{n}$ 為仿射無關的。）

2.單純形：n維單純形就是n+1個仿射無關點的凸包，記為 $S=coleft{X_{0},...,X_{n} ight}$ ，意即Simplex。單純形可以定義為開集，然後於其上定義閉單純形，而閉單純形是最簡單的非空緊凸集。或者可以直接將其定義為 $n+1$ 個仿射無關點的閉凸包， $S=cl(coleft{X_{0},...,X_{n} ight})$ 。我們將採用第二種定義方式。

3.單位單純形，記為 $Delta$ ，單位單純形凸組合的各係數在0與1之間，加總和為1。比如2維單純形，就是3個點的凸組合，表現為一個三角形，這3個點就是三角形的3個頂點。（而單純形因其性質，可以作為在博弈論中混合策略的理解方式，各坐標之和為1也就是各種情況下的概率之和為1。）

4.標號：將 $n$ 維單純形的 $n+1$ 個頂點賦以標號，如 $0,1,…,n$ 或 $1,2,…,n+1$ ，各頂點的標號互不相同。

5.簡單剖分：將 $n$ 維單純形劃分為一大堆小 $n$ 維單純形。簡單剖分有兩種，分別為重心剖分與等距剖分。剖分裡面的小單純形之間要麼共點，要麼碰不上，要麼共面。剖多細緻無所謂。對於Sperner引理所要求的來說，這兩種都是可以的。我們約定，原先的單純形稱為母單純形，而剖分之後得出的小單純形稱為子單純形。

6.好標號：母單純形各邊上的子單純形節點不能使用對面頂點上的數字，但使用兩端中的哪個無所謂。比如三角形三頂點標為 $0,1,2$ ，那麼 $0,1$ 那條邊上可以有 $0$ 或者 $1$ ，但不能用該變正對面那點上的 $2$ 。而母單純形內部的子單純形怎麼標無所謂，比如三角形內部隨意選擇 $0,1,2$ 。

7.好子形：如果原先單純形內部有個剖出來的小單純形，其各頂點恰好使用了所有標號，不重不漏。那這個小單純形就是好子形。

Sperner引理

Sperner引理：不管怎麼剖分，內部一定存在奇數個好子形。

證明

可用遞推法。 $n=1$ 時的結論是證明 $n=2$ 時的條件，以此類推。

$n=1$ 時，1維單純形，就是兩個點的凸組合，即一條線段。標號為一端點為 $0$ ，另一端點為 $1$ 。

剖分就是把線段為成幾小節，小節的標號可以從兩端點的標號任意選。比如算上端點可以依次為 $0,0,1,0,1,0,1,0,0,1$ ，而且前面說過剖多細緻無所謂，所以 $0,1,0,0,0,0,1,1,1,0,0,1,1,0,1$ 什麼的也行。不過必須遵守兩端點標號是不同的，即一邊為 $0$ ，另一邊為 $1$ 。

記 $F(0,0)$ 為兩端都是 $0$ 的小節的個數， $F(0,1)$ 為一邊為 $0$ 而另一邊為 $1$ 的小節的個數，具體哪邊是 $0$ 哪邊是 $1$ 無所謂。（這時候要算只能算剖分之後的，不能把長的和內部細分之後的都算在一起。舉個不恰當的例子（因為這個例子有數值），一個兩厘米的線段，如果剖成兩節，一厘米一節，那麼就只能按兩條小線段算。不能把剖之前的和剖之後的加在一起成了三條線段。） $F(0,0)$ 和 $F(0,1)$ 都是小節的個數，下面再看標號的個數。每個滿足 $F(0,0)$ 的小節都貢獻了兩個 $0$ ，每個滿足 $F(0,1)$ 的小節都貢獻了一個0，但是有一個問題，在算 $F(0,0)$ 和 $F(0,1)$ 時，我們把除了最原始端點之外的0都算了兩次，為了把全部的點都算兩次，還得加1。因此 $2 imes F(0,0)+F(0,1)+1$ 等於線段上所有 $0$ 的個數的二倍。而 $2 imes F(0,0)$ 當然為偶數，所有0個數的二倍為偶數，1為奇數，因此 $F(0,1)$ 必為奇數。所以得證。

$n=2$ 時，三角形。母單純形三個頂點標號為 $0,1,2$ 。把小單純形中三個頂點為 $(0,1,1)$ 或者 $(0,0,1)$ 的個數設為A，把好子形個數設為 $G$ ， $n=1$ 時我們算的是 $0$ 的個數（當然其實算1也一樣），這裡 $n=2$ 我們算邊為 $(0,1)$ 的個數（當然算 $(1,2)$ 或者 $(0,2)$ 也一樣）。每個A貢獻了兩個 $(0,1)$ 的邊，每個 $G$ 貢獻了一個這樣的邊。 $A$ 和 $G$ 都是子單純形。我們再來算邊，上述方法里，每條內部端點為 $(0,1)$ 的小邊算了兩次，內部 $(0,1)$ 邊設為 $B$ ，每條邊界端點為 $(0,1)$ 的小邊算了一次，邊界 $(0,1)$ 邊設為 $C$ 。因此2A+G=2B+C。而我們在 $n=1$ 時已經知道了 $C$ 是奇數，所以 $G$ 也是奇數，得證。

同理，往下遞推。可有 $n$ 維情形。 $square$