Sperner`s lemma

얼마 전에 Sperner`s lemma를 쓴 일이 있어서 proof from the book에 있던 lemma의 응용이 생각났다. 처음 읽었을 때도 포스팅 감으로 괜찮겠다고 생각했고, 이제 쓰게 되었다.

Sperner`s lemma.

큰 삼각형 가 triangulate되었다고 하자. 각각의 작은 삼각형의 각 꼭지점에 세 가지 색 1, 2, 3으로 칠하자. 그리고 꼭지점 를 순서대로 i로 칠했다. 그리고 변 에는 색이 i와 j밖에 없다.

그러면 반드시 색 123을 모두 가지고 있는 작은 삼각형이 존재한다.

증명은 간단하다(물론 읽는 사람 입장에서... 다음의 아이디어를 떠올리려면 약간의 감이 필요할 듯). dual graph의 subgraph를 생각하는데 edge를 줄때 본래의 graph G의 edge의 양 꼭지점의 색이 다르면 dual graph에 edge를 준다. 자 그럼 이제 이 새로 생성된 그래프에서 exterior face에 해당하는 꼭지점은 각 대변 마다 홀수개의 edge로 연결되어있다(V_1에서 V_2로 갈때 색이 1에서 1,2를 교대하다가 결국 2로 바뀌니...). degree가 홀수인 꼭지점은 반드시 짝수개 있어야 하니 본래의 삼각형 안에 odd degree vertex가 하나 이상 무조건 더 있다. 얘가 바로 그놈이다. 삼각형 세 꼭지점의 각 coloring case마다 나올 수 있는 변의 수는 0, 2, 3뿐이다.

Sperner는 Brower fixed point theorem(n=2)을 증명했다. 이 theorem은 커피잔을 숟가락으로 휘저을 때에도 각 연속변환에는 무조건 고정점이 있다는 것이다.

Brower fixed point theorem(n=2).

모든 연속함수 는 고정점을 가진다.

증명.

일단 아니라고 하자. closed unit ball B^2대신 (1,0,0), (0,1,0), (0,0,1)을 꼭지점으로 하는 정삼각형 에 대해서 증명하자(저 고정점 성질은 topological property이다. 사실 이 모든게 당연하지 않다. 보면 공간의 성질을 얘기하기 위해 open set의 모임을 생각한다는 것부터가 참 신기하다. 그리고 저 고정점 성질은 공간의 특성이다.). 어떤 주어진 triangulation T에 대해 를 T의 edge의 길이 중 최대값이라고 하자. 라 하고 T_(k+1)을 T_k의 barycentric division이라고 하자. 그러면 이 infinite sequence의 델타값은 0으로 수렴한다.

각 triangulation의 꼭지점 v에 대해서 coloring \lambda를 라 하자. 여기서 i첨자는 i번째 좌표를 말한다. 항상 저 i 집합은 nonempty이다. 이제 각 triangulation T_k는 큰 삼각형을 로 해서 Sperner lemma의 가정을 만족시킨다. 따라서 각 T_k 마다 를 만족시키는 삼각형 가 있다.

수열 는 반드시 수렴할 필요는 없지만, 큰 삼각형 는 compact하므로 어차피 수렴하는 subsequence를 가질 것이다. 그러므로 그냥 저 v^(k:1)가 로 수렴한다고 해도 되겠다. 그러면 v^(k:2), v^(k:3)도 v로 수렴해야 한다(저 델타라는 큰 삼각형은 complete하다).

이제 f(v)는 무엇일까. 우선 각 모든 k에 대해 가 음수이다. 연속함수는 limit을 보존하므로 는 양이 아니다. 이 것이 모든 i=1,2,3에 대해서 참이다. 이므로 f(v)=v이어야 한다. 모순! 

참... 이런 증명이 어떻게 나온거지...

lemma는 유한에 관한 것인데 theorem은 무한에 관한 것이다. 유한에 극한을 취했다. 초기치가 정해져 있고 recursive algorithm이 있으면 그에 맞는 infinite set 그 자체가 있다는 것이다. 요게 Brower가 의심한 건가? 이 쪽은 잘 모르겠다.

생각해보면 이 우주에 무한한 양은 뭐가 있을까. 깊게 생각해보진 않았지만 딱 생각나는 것은 없다. 양자역학은 선도 분해해버린다. 무한은 우주를 잘 근사하면서도 매력적이고, 또 그만큼 논란이 많고 역사가 깊다. 종교는 유한과 무한이 인간과 신의 경계라고 하기도 하며, 누군가는 인간은 무한을 상상할 수 있으므로 인간의 능력은 무한하다고 주장했다(그 당시엔 받아들여지지 않았다). 어떤 스승과 제자에게는 그 사이에 해소되지 않는 갈등을 주었다. 하지만 후에 Hilbert는 "그 누구도 칸토어가 창조한 낙원에서 우리를 추방할 수 없다"는 명언을 남겼다. 괴델 이후로 절대 진리에 대한 믿음이 약해진 것은 사실이다. 현대 대부분의 수학자들도 ZFC 공리계에 크게 신경을 쓰지 않고 받아들인다(나도 그렇다. 상상하고 이해할 수 있으니까. 근데 ㅇㅅㄴ은 다른 생각을 가지고 있고, 이에 대해서 대화하는 동안 즐거웠다. 재밌는 친구다.). 하지만 여전히 한편에서는 끊임없이 토론이 벌어지고 있다.

이번에 열리는 과목 중에 Discrete and Computational Topology라고 열리는데 아마 저런 논의하고 관련있나 생각해본다. 재밌겠다.