Dol’nikov theorem이란 일반화된 Kneser graph의 chromatic number에 대한 정리이다. statement만 빌려 쓰면, 적절한 유한집합 $[n]$과 $F \subseteq 2^{[n]}$에 대해 다음이 성립한다: $ \chi(\mar{KG}(F)) \ge \mar{cd}_{2}(F) $ 이 글에서는 Borsuk-Ulam theorem을 이용하여 이를 증명한다. Problem analysis Lovasz-Kneser theorem에서 다루었던 Kneser graph의 coloring 문제를 일반화해보자. 적당한 ground set $[n]$이 있다. 이 $n$의 값은 오늘 전혀 중요하지 않다. $F \subseteq 2^{[n]}$이 그래프의 정점 집합이 된다. 색은 이 정점 위에 칠할 것이다. $A, B \in F$에 대해 $A \cap B = \emptyset$이면 $A, B$ 사이에 간선을 잇는다....
Grundy Number는 PS에서 굉장히 자주 쓰이는 데 비해 그 증명이나 수학적 배경이 잘 알려져 있지 않다. 앞으로 일련의 포스팅에서는 Sprague-Grundy Theorem에 대해 공부한 것을 PS 스타일로 정리하려 한다. 그 중에서 이 글은 Grundy Number의 정의와 Sprague-Grundy theorem의 증명에 대해 다룬다. Nim-Game의 필승 전략에 대한 사전 지식이 필요하며, 문제풀이에 최적화된 글이기 때문에 statement가 실제 theorem의 내용과는 다소 차이가 있다. References sirkingnightingfail, “A Blog on Sprague-Grundy Theorem” Wikipedia: Sprague-Grundy theorem Definition of Game “게임”은 상당히 광범위한 용어이지만, Sprague-Grundy theorem의 영향 아래 있는 “Game”은 다음의 조건을 만족하는 일종의 state collection을 말한다....
Permutation $\pi : [n] \to [n]$에 대해 Displacement를 $D(\pi) = \sum_{i=1}^{n} \lvert i - \pi (i) \rvert$로 정의한다. 주어진 양수 $k$에 대해, $D(\pi) = 2k$를 만족하는 짝순열의 개수를 $E_{k}$, 홀순열의 개수를 $O_{k}$라 두면 $E_{k} - O_{k} = (-1)^{k}\binom{n-1}{k}$임을 보여라. ...
$[n] = \set{1, \cdots, n}$과 $2 \le 2k \le n$에 대해, Kneser graph $\mar{KG}(n, k)$는 $\binom{[n]}{k}$를 정점 집합으로 하고, $S \cap S’ = \emptyset$인 모든 $S, S’$에 대해 간선을 이어준 그래프로 정의된다. Lovasz-Kneser Theorem (Kneser’s conjecture)란 이 그래프의 chromatic number $\chi(\mar{KG}(n, k)) \ge n - 2k + 2$가 성립한다는 정리이다. 이 글에서는 Tucker’s lemma를 이용한 J. Matousek의 증명을 소개한다. ...
Space-filling curve는 일반적으로 $I := [0,1]$에서 $I \times I$로 가는 continuous onto function을 말한다. Hilbert’s curve, Sierpinski’s curve 등 여러 가지가 알려져 있다. 이런 curve들의 특징은 uniformly converge하는 연속함수열의 극한으로 정의된다는 점인데, 그렇지 않고는 Space Filling Curve를 만들기 굉장히 어렵기 때문이다. 이 포스팅에서는 $C^{1}$ class의 space-filling curve가 존재하지 않음을 보인다. ...