Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
Google "finite intersection property", and next time post questions of this sort on www.mathstackexchange.com. –  Nik Weaver Aug 28 '12 at 18:40
    
Use stackexchange in the future, but Terry Tao has some good blog posts explaining this sort of thing, like terrytao.wordpress.com/2007/05/23/… –  Will Sawin Aug 28 '12 at 18:54
3  
Re: previous two comments - Actually, I don't think compactness arguments in combinatorics are all that obvious without previous experience. To the OP: you could also try the exposition of a compactness argument for a different problem that's given in the last chapter of Bollobas's book "Combinatorics" –  Yemon Choi Aug 28 '12 at 19:11

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
This is perfect. Thanks! –  anon Aug 28 '12 at 22:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.