Lecture 6: Borsuk-Ulam and some combinatorial applications


The Borsuk-Ulam Theorem













The Kneser conjecture


LS Lemma: Let {F_1, F_2, \ldots, F_{n+1}} be a cover of {S^n} by closed sets.  Then some {F_i} contains an antipodal pair.

Proof: Consider the continuous map {f : S^n \to \mathbb R^n} given by {f(x)=(\mathsf{dist}(x,F_1), \ldots, \mathsf{dist}(x, F_n))} , where {\mathsf{dist}} denotes e.g. the geodesic distance on {S^n} .  By the Borsuk-Ulam theorem, there exists a {y \in S^n} with {f(y)=f(-y)} .  Now if {f(y)_i = 0} for some {i} , then {y, -y \in F_i} .  Otherwise, if this holds for no {i = 1, \ldots, n} , then {y,-y \in F_{n+1}} .


Corollary 1: Let {F_1, \ldots, F_{n+1}} be a cover of {S^n} by open sets.  Then some {F_i} contains an antipodal pair.

Proof: This follows from the LS Lemma by choosing a family of closed sets {U_i \subseteq F_i} such that {\{U_i\}} forms a cover of {S^n} .  The existence of such sets follows from applying compactness to the following open cover of {S^n} :  For every {x \in S^n} , choose an open set {N_x} whose closure lies completely within some {F_i} .  By compactness, there is a finite subcover.  By piecing together elements of its closure, we can form the sets {\{U_i\}} .


Corollary 2: Let {F_1, \ldots, F_{n+1}} be a cover of {S^n} with each {F_i} open or closed.  Then some {F_i} contains an antipodal pair.

Proof: Suppose that {F_1, \ldots, F_k} are closed and {F_{k+1}, \ldots, F_{n+1}} are open.  Consider the open cover {(F_1)_{\varepsilon}, \ldots, (F_k)_{\varepsilon}, F_{k+1}, \ldots, F_{n+1}} , where {(F_i)_{\varepsilon}} denotes the {\varepsilon} -neighborhood of {F_i} .  Taking {\varepsilon \to 0} and applying Corollary 1 to each cover results in a sequence {\{x_j\} \subseteq S^n} .  If {x_j,-x_j \in F_i} for some {i \geq k+1} , we are done.  Thus we may pass to a subsequence for which {x_j,-x_j \in (F_i)_{\varepsilon}} for some fixed {i \leq k} .  Choose a convergent subsequence {\{x'_j\}} , and observe that since {F_i} is closed, we have {x = \lim x'_j \in F_i} .  We conclude that there exists an {x \in S^n} with {x,-x \in F_i} .

The Kneser graphs.

Now, we introduce the Kneser graphs {KG_{n,k}} .  The vertex set is {{[n] \choose k}} , i.e. the vertices are k-element subsets of {\lbrack n\rbrack = \{1,2, \ldots, n\}} .  There is an edge between two sets {S,S' \in {[n] \choose k}} if and only if {S} and {S'} are disjoint.  In 1955, Kneser posed the following conjecture.

Conjecture: For every {k > 0} and {n \geq 2k-1} , {\chi(KG_{n,k})=n-2k+2} , where {\chi} denotes the chromatic number.

First, we note that the upper bound is easy:  Construct a coloring {c : {[n] \choose k} \to \{1,2,\ldots,n-2k+2\}} by defining


Clearly if {c(S)=c(S') < n-2k+2} , then {S} and {S'} have the same minimum element, and thus they are not disjoint.  On the other hand, if {c(S)=c(S')=n-2k+2} , then {S,S' \subseteq \{n-2k+2, n-2k+3, \ldots, n\}} , and the latter set contains only {2k-1} elements.  Thus again {S \cap S' \neq \emptyset} .


Proof: Consider {KG_{n,k}} and let {d = n-2k+1} .  Let {X \subseteq S^d} be a set of {n} points in general position, so that no {(d-1)} -dimensional hyperplane through the origin contains more than {d} points of {X} .  Clearly we may assume that {KG_{n,k}} actually has vertex set {{X \choose k}} .  For every {x \in S^d} , let


denote the open hemisphere centered at {x} .

Now, suppose we have a proper coloring of {KG_{n,k}} , and define sets {A_1, A_2, \ldots, A_d \subseteq S^d} as follows:  {A_i} is the set of all points {x \in S^d} such that {H(x)} contains a k-set {S \subseteq X} colored {i} .  Finally, {A_{d+1} = S^d \setminus (A_1 \cup \cdots \cup A_d)} .

By Corollary 2 above, there must exist an {i} and a {x \in S^d} such that {x,-x \in A_i} .  If {i \leq d} , then since {H(x)} and {H(-x)} are disjoint, there must exist two disjoint k-sets colored {i} , which means we did not start with a proper coloring.

If, instead {x,-x \in A_{d+1}} , it implies that both {|H(x) \cap X|, |H(-x) \cap X| \leq k-1} .  But then the {(d-1)} -dimensional hyperplane {S^d \setminus (H(x) \cup H(-x))} contains {n-2k+2 = d+1} points, contradicting the fact that {X} was chosen in general position.

Appearances in TCS

One of the most useful properties of the Kneser graphs is that there is a large gap between their chromatic number {\chi(KG_{n,k})} and their fractional chromatic number {\chi_f(KG_{n,k})} .  The fractional chromatic number of graph {G} is the minimum value {\displaystyle \frac{a}{b}} such that {G} can be covered by {a} independent sets, where each vertex occurs in at least {b} of them.

It is easy to see that {\chi_f(KG_{n,k}) \leq n/k} by choosing the n independent sets


The Kneser graphs are a particularly natural family to have a large gap between {\chi} and {\chi_f} because we can define {\chi_f(G)} for an arbtirary G as the minimum ratio {n/k} such that G admits a homomorphism into {KG_{n,k}} .  One can also see that {\chi_f(KG_{n,k}) = n/k} using the Erdős–Ko–Rado theorem.


One thought on “Lecture 6: Borsuk-Ulam and some combinatorial applications

Leave a Reply


WordPress.com Logo


Twitter picture


Facebook photo


Google+ photo


Connecting to %s