Topological Combinatorics through Kneser Graph

Preliminaries

Graph Theory

Definition. A coloring is proper if no adjacent vertices are assigned the same color.

Definition. The chromatic number $\chi(G)$ is the smallest number of colours to colour a graph.

Complex Analysis

Definition. A curve $\gamma$ in open $U \subseteq \mathbb{C}$ is

Notation. The curve $\gamma$ could be expressed as a parameteric function $f(e^{2 \pi i t})$ for $0 \leq t \leq 1$.

Definition. The continuity of a complex-valued function is defined in an analogous manner to real-valued functions.

Definition. For continuous $F:[a,b] \rightarrow \mathbb{C}$, the integral of $[a,b]$ is

Definition. The winding number with respect to point $\alpha$ over closed path $\gamma$ is

Definition. The degree of a function $deg(f)$ is the wind number $W(f(e^{2 \pi it}))$.

Other

Fact. Vectors of d-dim sphere are exactly the vectors of the (d+1)-dim Euclidean space whose norm is $1$.

Fact. The equator of a d-dim sphere is a subspace of the d-dim Euclidean space.

Definition. The distance between a point $x$ and a closed set $C_i$ is $dist(x,C_i) = \inf_{y \in C_i} ||y-x||$, i.e the distance between $x$ and the closest point of $C_i$.

Fact. If point $p$ is in closed set $C_i$, then $dist(p, C_i) = 0$, and if not then $dist(p, C_i) > 0$.

Definition. Two points of a sphere are antipodal if they are diametrically opposite, i.e expressed as $p$ and $-p$.

Definition. The open hemisphere of pole $x$ is $H(x) = \{ y \in \mathbb{S}^d \mid \langle x,y \rangle > 0 \}$.

Topological Methods

Lemma 1. Given $f: S^1 \rightarrow S^1$, and $f(-z) = -f(z) \; \forall z \in S^1$, then $deg(f)$ is odd.

Proof. Recall by definition $deg(f) = wind(f(e^{2 \pi it}))$. Set $g:[0,1] \rightarrow S^1$ by $g(t) = f(e^{2 \pi it})$.

If $z = e^{2\pi it}$ then $-z = e^{\pi i} = e^{\pi i}z = e^{\pi i} e^{2 \pi it} = e^{\pi i + 2 \pi it} = e^{2 \pi i (t + 1/2)}$.

If $0 \leq t \leq \frac{1}{2}$ then $\frac{1}{2} \leq t+\frac{1}{2} \leq 1$. We have $g(t+\frac{1}{2}) = f(e^{2 \pi i (t + 1/2)}) = f(-z) = -f(z) = -f(e^{2\pi it}) = -g(t)$.

For a partition of $[0,1]$ into $[0,\frac{1}{2}] \cup [\frac{1}{2}, 1]$, partition $[0, \frac{1}{2}]$ into $\bigcup_{k=1}^n [t_{k-1}, t_k]$, where $|\theta_k| < \frac{\pi}{2}$ for $\frac{g(t_k)}{g(t_{k-1})} = e^{i \theta_k}$. Partition $[\frac{1}{2}, 1] = \bigcup_{k=1}^n [\frac{1}{2} + t_{k-1}, \frac{1}{2} + t_k]$.

It follows $\frac{g(\frac{1}{2} + t_k)}{g(\frac{1}{2} + t_{k-1})} = \frac{-g(t_k)}{-g(t_{k-1})} = e^{i \theta_k}$.

Observe an approximation of the integral of the winding number would be

Observe $g(\frac{1}{2}) = -g(0)$, and

But we know $e^{i \pi} = -1$. Hence $\theta_1 + \theta_2 + \dots + \theta_n = \pi + 2 \pi N$ for some integer $N$.

It follows the wind approximation is

which is an odd number.

Indeed, a sequence of odd numbers converges to an odd number. Therefore, the winding number is odd.

Lemma 2. No map $f:S^2 \rightarrow S^1$ such that $f(-p) = -f(p) \; \forall p \in S^2$.

Theorem. 2-dim Borsuk-Ulam. If $f: S^2 \rightarrow \mathbb{R}^2$ is continuous, then $\exists p \in S^2$ such that $f(-p) = f(p)$.

Proof. Suppose towards contradiction $f(x) \neq f(-x) \; \forall x \in S^2$. Construct map $g: S^2 \rightarrow S^1$ by

Observe

Contradicting lemma 2.

Theorem. Borsuk-Ulam. If $f: S^n \rightarrow \mathbb{R}^n$ is continuous, then $\exists p \in S^n$ such that $f(-p) = f(p)$.

The proof is a natural generalization but requires concepts beyond a first course in topology.

Theorem. Lyusternik & Shnirel’man. If $S^n$ is covered by closed sets $C_1, C_2, \dots, C_n, C_{n+1}$, then there $p \in S^n$ and $C_i$ such that $p,-p \in C_i$.

Proof. Assume towards contradiction that if $p \in C_i$ then $-p \not\in C_i$ for all $p \in S^n$. Define functions $f_1, f_2, \dots, f_{n+1}: S^n \rightarrow \mathbb{R}$ by $f_i(x) = dist(x, C_i)$. Construct $f: S^n \rightarrow \mathbb{R}^n$ by $f(x) = (f_1(x) - f_{n+1}(x), f_2(x) - f_{n+1}(x), \dots, f_n(x) - f_{n+1})$.

By Borsuk-Ulam there are $p, -p \in S^n$ such that $f(p) = f(-p)$. It follows for all $1 \leq i,j \leq n+1$

So $f_i(p) - f_j(p) = f_i(-p) - f_j(-p)$.

Since $p \in S^n = C_1 \cup \dots \cup C_{n+1}$, we get $p \in C_i$ for some $i$. Similarly $-p \in S^n$ so $-p \in C_j$ for some $j$. By hypothesis $i \neq j$. Clearly $f_i(p) = f_j(-p) = 0$. Then

But $f_j(p) > 0$ since $p \not\in C_j$, and similarly $f_i(p) > 0$. So we have an equality between a negative and a positive number. Contradiction.

Theorems

Definition. The Kneser graph $KG_{n,k}$ for $n \geq 2$, $k \geq 1$, has vertex set $C([n], k)$, and any two vertices $u,v \in C([n], k)$ are adjacent if and only if they are disjoint, i.e. $u \cap v = \phi$.

Theorem. The chromatic number of the Kneser graph $KG_{n,k}$ is $n-2k+2$.

Fix $n$ and $k$. Assume for the sake of contradiction, the chromatic number of Kneser graph $KG_{n,k}$ is less than $n-2k+2$. Then we have a proper coloring $c: C([n], k) \rightarrow \{ 1, \dots, n-2k+1 \}$ using at most $n-2k+1$ colors. Set $d = n-2k+1$ and take a set $X$ of $n$ vectors on the d-dim sphere $\mathbb{S}^d$ where any $d+1$ vectors are linearly independent.

Let $U_i = \{ x \in \mathbb{S}^d \mid \exists k\text{-set} \; S \subset X, c(S) = i, S \subset H(x) \}$ for $i=1,\dots,d$, and take complement $A = \mathbb{S}^d \setminus (U_1 \cup \dots \cup U_d)$. We claim each $U_i$ is open.

To see why, fix a point $y \in S^{d}$, and observe $U_{y} = \{ x \in S^{n-1} : \langle x, y \rangle > 0 \}$ is open as it is the preimage of the open set $(0, \infty)$ under the continuous map $f_y(x) = \langle x, y \rangle$.\ For finite k-subset $B = \{ y_1, \dots, y_k \}$, Observe

is an intersection of finitely many open sets, hence open.

Therefore $U_i = \bigcup_{\substack{B \in \binom{[n]}{k} \\ c(B)=i}} U_B$ is a union of open sets, hence open. Moreover complement $A$ is closed.

Clearly $A$ alongside $U_i$ do cover $\mathbb{S}^d$. So if none of them contains a pair of antipodal points, then neither does $\mathbb{S}^d$, hence contradicting the Lyusternik & Shnirel’man theorem. We aim to reach that contradiction. Consider $x \in \mathbb{S}^d$.

Case 1. $x \in U_i$, i.e $H(x)$ contains a k-subset colored with color $i$, corresponding to a vertex colored $i$. Since $H(x)$ and $H(-x)$ are disjoint, any k-subset in $H(-x)$, is disjoint from any k-subset in $H(x)$. Thereby, corresponding vertices are adjacent. Since the coloring is proper by hypothesis, $H(-x)$ does not contain a k-subset colored with $i$, hence $-x \not\in U_i$.

Case 2. $\pm x \in A$. By definition of $A$, neither $H(x)$ nor $H(-x)$ contains a k-subset of $X$. Hence each of $H(x)$ and $H(-x)$ contains at most $k-1$ vectors. It follows there is at least $n-2(k-1) = n-2k+2 = d+1$ points in the equator $\{ y \in \mathbb{S}^d \mid \langle x,y \rangle = 0 \}$, contained in a subspace of dim d, concluding they are linearly dependent. Contradiction.

Finally we show a valid constructive coloring of $KG_{n,k}$ using $n-2k + 2$ colors. Color each k-set with all elements in $[2k - 1]$ with one color, and every other k-set by their largest element. Thereby we use at most $n - (2k-1) + 1 = n - 2k + 2$ colors, where all k-sets of a given color intersect.

Resources

• Borsuk-Ulam Theorem by Nicolas Bourbaki
• Kneser’s Conjecture by Nicolas Bourbaki
• A Course in Topological Combinatorics, Chapter 2, by Longueville
• Lecture 14. Combinatorics by Jacob Fox