Dolnikov Theorem

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$ 사이에 간선을 잇는다.

이렇게 정의된 graph가 Generalized Kneser Graph $\mar{KG}(F)$이다.

$\mar{cd}_{2}$는 무엇을 의미할까? 일반적으로 $\mar{cd}_{m}$은 $m$-colorability defect를 의미하는데, 칠하려는 그래프가 전혀 다르다. 정확히는 Hypergraph coloring을 해야 한다. 즉, $[n]$에서 크기 $k$인 집합 $S$를 제거하여, $[n] \setminus S$에만 온전히 포함되는 $F$의 원소들의 집합 $F’$을 생각하자. 이 때 $[n] \setminus S$를 $m$개의 색으로 잘 칠하여, $x \in F’$가 monochromatic이 될 수 없다면 hypergraph $([n] \setminus S, F’)$는 $m$-colorable이다. 이 때 $m$-colorability를 만족하기 위해 필요한 $\sz{S}$의 최솟값 $k$가 바로 $\mar{cd}_{m}(F)$이다.

Link to Lovasz-Kneser

우리가 보이고자 하는 부등식이 Lovasz-Kneser를 일반화함을 보이자.

$F = \binom{[n]}{k}$이라고 두면 $\mar{KG}(F)$가 이전 글에서 이야기한 $\mar{KG}(n, k)$가 된다. 이 때 $\mar{cd}_{2}(F) \ge n - 2k + 2$임을 보이면 된다. 아무 $n - 2k + 1$개의 정점을 제거하면, 사실상 $F’ = \binom{[2k-1]}{k}$가 된다. $[2k-1]$을 어떻게 두 색으로 칠하더라도 크기 $k$인 monochromatic 집합이 생기게 되므로, 무조건 $\mar{cd}_{2}(F) > n - 2k + 1$임을 알 수 있다. 따라서 원하는 부등식을 보이면 Lovasz-Kneser를 증명할 수 있다.

Lusternik–Schnirelmann theorem

L-S theorem은 Borsuk-Ulam theorem의 set covering analogy로 불린다. Borsuk-Ulam $\iff$ Tucker $\iff$ Lusternik–Schnirelmann 의 analogy가 유명한 모양. 여기서는 statement만 하고 끝내지만 증명이 어렵지 않다.

Theorem (Lusternik–Schnirelmann). $n$차원 구 $S^{n}$이 open cover $U_{1}, \cdots, U_{n+1}$을 가진다면, 이 중 antipodal point를 포함하는 $U_{i}$가 존재한다. (즉, $U_{i} \cap -U_{i} \neq \emptyset$)

Theorem’ (General L-S). $n$차원 구 $S^{n}$이 open or closed set $A_{1}, \cdots, A_{n+1}$에 의해 cover된다고 하자. 역시 $A_{i} \cap -A_{i} \neq \emptyset$인 $A_{i}$가 존재한다.

• 이 또한 $S^{n}$의 compactness로부터 유도할 수 있다.

Proof of the Theorem

$d := \chi(\mar{KG}(F))$로 두고, $[n]$의 점들을 $S^{d}$ 위의 point들로 생각하자. 이 때, 충분히 general position을 취해서 대원 위에 $d+1$개 이상의 점이 없도록 할 수 있다. 이는 원래 $\mab{R}^{d+1}$의 “general position”이 $d$차원의 hyperplane 위에 $d+1$개 이상의 점이 올라가지 않는 position임을 생각하면 자연스럽고, 또 무리 없이 만들어줄 수 있다.

이 때, 임의의 point $x \in S^{d}$에 대해 open hemisphere $H(x) := \set{y \in S^{d} \mid \ip{x}{y} > 0}$을 정의하자. 이 때 $H(x)$가 color $i$로 칠해진 $f \in F$를 포함하면 $x \in A_{i}$가 되도록 $A_{i}$를 정의하자. 자연스럽게 $1 \le i \le d$에 대해 $A_{i}$는 open이고, $A_{d+1} = S^{d} \setminus (A_{1} \cup \cdots \cup A_{d})$는 closed가 된다.

General L-S theorem에 의해 antipodal point를 포함하는 $A_{i}$가 존재한다. $1 \le i \le d$라면 $H(x)$와 $H(-x)$는 겹치지 않는 와중에 color $i$로 칠해진 집합 $f, g$를 포함하고, 이는 coloring 조건에 모순. 따라서 $i = d + 1$이어야 한다.

이제 $x, -x \in A_{d+1}$에 대해 $H(x)$의 점을 붉은색, $H(-x)$의 점을 푸른색으로 칠하고, $S^{d} \setminus H(x) \setminus H(-x)$ (대원) 위에 있는 점들을 제거하자. 제거되는 점은 최대 $d$개이고, $1 \le i \le d$에 대해 $x, -x \notin A_{i}$이기 때문에 어떤 $F$의 원소도 monochrmoatic일 수 없다.

증명 끝.