Brower不动点定理的组合证明

Brower 不动点定理 每一个从n 维球B n 到自身的连续映射f :B n !B n 都有不动点.

这里,实心球B n :=f (x 1;¢¢¢;x n )j x 21+¢¢¢+x 2n 61g . 给定R n 中n +1个向量x 1,x 2,¢¢¢,x n +1,

集合A :=(n +1X i =1

®i x i ¯¯

¯¯

n +1X i =1

®i =1)被称为n 维单形,这些向量的终点A 1,A 2,¢¢¢,A n +1被称为顶点,对任何S ½f 1;2;¢¢¢;n +1g ,集合

A S :=

(

X

i 2S

¸i x i ¯

¯¯¯

X i 2S

¸i =1) 被称为A 的一个低维表面. 单形的三角剖分是指将A 划分为若干小的n 维单形,使其中任两个单形或者不相

交,或者具有共同的整个低维表面. 现对三角剖分T 形成的顶点着色,其中可供选择的颜色集为C =f 1;2;¢¢¢;n +1g . 称这种着色方式是恰当的,如果

(1) 顶点A i 有颜色c (A i )=i ;

(2) 在低维表面A i 1¢¢¢A i k 上的点只能选择f i 1;¢¢¢;i k g 中的颜色. Sperner 引理 对n 维单形的三角剖分T 恰当着色,则存在一个T 中的单形,其不同顶点被着以不同的颜色,称之为“彩虹单形”.

证明 我们证明更强的结论:彩虹单形的个数是奇数. n =1的情形是显然的. 当n =2时,书中已有证明.

Brower不动点定理的组合证明

Brower不动点定理的组合证明

图1 彩虹三角形与对偶图

图2 多彩表面

对一般的情形,我们考虑对维数归纳. 令r 表示彩虹单形的个数;s 表示恰被染成n 种颜色的顶点的单形,即,它们的顶点颜色集为f 1;2;¢¢¢;n g ,其中恰有一种颜色被用了两次,其它颜色只用了一次;我们同样考虑被f 1;2;¢¢¢;n g 着色的n ¡1维表面,称为“多彩表面”. 其中,x 表示在A 边界上的多彩表面;y 表示在A 内部的多彩表面.

证明通过两个方向上的计数快速完成.

首先,每一个r 类单形恰包含一个多彩表面,s 类单形则包含两个多彩表面. 除此之外,其余种类的单形不包含多彩表面. 另一方面,在A 内部的多彩表面包含在两个单形中,在A 边界上的多彩表面则只在一个单形中. 这样就有等式r +2s =x +2y .

根据着色规则(1),边界上的多彩表面必定包含在低维表面A 1A 2¢¢¢A n 中,由归纳假设可断定x 为奇数,故r 亦为奇数. 特别地,r >1.

Brower 不动点定理的证明 相比于球体,我们考虑同维的单形¢,因为二者同胚. 令v 1=(1;0;¢¢¢;0),v 2=(0;1;0;¢¢¢;0),¢¢¢,v n +1=(0;¢¢¢;0;1)为¢的n +1个顶点. 定义染色方案

c (v )=min f i j f (v )i

如果c (v )不存在,即对816i 6n +1都有f (v )i >v i ,因为单形位于超平面x 1+x 2+¢¢¢+x n +1=1上,故

X

f (v )i =

X

v i ) f (v )i ´v i ,故v 即为所求不动点,证明便结束了. 不然,假设¢

内的每个点都被

相关推荐
相关主题
热门推荐