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 即为所求不动点,证明便结束了 . 不然,假设 ¢

内的每个点都被

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