Technique: Compactness => (Finite -> Reals)

Question

Context

I'm studying a classical results of Erdos and Lovasz, on colorings of the real line.

The theorem to be proved is as follows:

Let $m, k$ be two positive integers satisfying:

$$e(m(m-1)+1)k\left(1-\frac{1}{k}\right)^m \leq 1$$

Then, for any set $S$ of real numbers with $|S| = m$ (note, $S$, has a finite number of elements, this here does not denote length of segment) and any set $X \subset R$ (possibly infinite), there is a k-coloring of $R$ such that the tranlates $x+S$ o $S$ are colorful for every $x \in X$.

Standard Proof

The standard way to prove this is to use the Lovasz Local Lemma. (not detailed here)

Hoever, the proof claims that it will only prove the statement for $X$ finite, then use a standard technique for going from a finite statement to an infinite one using a compact ness argument.

The general idea is that the space of colorings of $R$ can be identified with the product space $[1,k]^R$, which is compact by the product topology by Tychonoff's theorem.

Then, for each $x \in R$, $K_x$, the set of all k-colorings such taht $x+S$ is colorful is closed, then since finite intersections are non-empty, infinite intersections are non-empty.

Question

This is the first time I'm seeing this proof technique. Can someone rigorize / expand out this last part? (the standard technique for going from a finite statement to an infinite one using a compactness argument.)

Thanks!

Answer 1

Our situation: We have the assertion we want to prove, let us call it $P_A$ , depending on a set $A$. We know already $A$ is true for all finite $A$ and now want to show it for all infinite sets, too. [If I understood correctly you are not inetrested in further details for the proof of finite sets, so I say we know it for finite sets.]

A $k$-coloring of $\mathbb{R}$ is a map from $\mathbb{R}$ to $\lbrace 1, \dots, k \rbrace$ (or whatever $k$ element set). The toplogogy on the set of colors will be the discrete topology so every set is open (and closed). Since the set is finite this is compact.

The set of all colorings is, by defnition, $K = \lbrace 1, \dots, k \rbrace^{\mathbb{R}}$ . As a product of compact sets this is compact with respect to the product/Tychonoff toplogy, as you say.

Now, for some $x$ you denote $K_x$ the subset of $K$ such that $x+ S$ is colorful in this coloring; let us say such a coloring 'works for $x$'.

Now for a set $X$ to show $P_X$ we need to show there is some coloring such that $x+S$ is colorful for each $x \in X$. In other words, we need a coloring that works for each $x \in X$, which is nothing but saying the intersection of $K_x$ over $x \in X$ is nonempty.

Since we know $P_A$ for finite $A$ we know that the intersection of $K_x$ for $x \in A$ is nonempty.

Suppose for a moment we know that $K_x$ is closed. Then the complements are open. Now, if we find an infinite set $X$ such that the intersection $K_x$ over $x \in X$ is empty, we can say equivalently the union of the complements (open sets!) is the full space, and by compactness, we get that there is a finite subunion that already convers the full space. Yet, then the finite intersection of the $K_x$ corresponding to this subunion would be empty. A contradition to the fact we know the result for finite sets.

So what remains to assert is that $K_x$ is closed, for each $x$. To see this perhaps it is easier to show that the complement is open (if only as the open sets of product topology are possibly more familiar). So, we show the set of all colorings that do not work for $x$ is open.

Now we note that whether a coloring works or does not work for some $x$ depends only on the values it has for the elements of $x+S$, a finite set. For every other point we can have any value. So the set of colorings that do not work is certainly of the form $$ N \times \prod_{y \notin x+S} \lbrace 1, \dots, k \rbrace $$ where $N$ is a subset of $\prod_{y \in x+S} \lbrace 1, \dots, k \rbrace $. Yet, since $x+S$ is finite the space $\prod_{y \in x+S} \lbrace 1, \dots, k \rbrace $ is also finite and the topology is the discrete topology, so that $N$ is certainly open (like any set). So that $$ N \times \prod_{y \notin x+S} \lbrace 1, \dots, k \rbrace $$ will be open whatever the $N$.

Thus we just showed that the complement of $K_x$ is open and so $K_x$ ` is closed, completing the argument.

Hope this is about what you were looking for.