Feeds:
Posts

Ultrafilters in Ramsey theory

We continue our exploration of ultrafilters. Today we’ll discuss the infinite Ramsey theorem, which is the following classical result:

Theorem: Suppose the complete graph $K_{\infty}$ on countably many vertices has its edges colored in one of $k$ colors. Then there is a monochromatic $K_{\infty}$ (i.e. an infinite subgraph all of whose edges are the same color).

The finite Ramsey theorem implies that there is a monochromatic $K_n$ for every positive integer $n$, but this is a strictly stronger result; it implies not only the finite Ramsey theorem but the “strengthened” finite Ramsey theorem, and by the Paris-Harrington theorem this is independent of Peano arithmetic (although Peano arithmetic can prove the finite Ramsey theorem). Indeed, while the standard proof of the finite Ramsey theorem uses the finite pigeonhole principle, the standard proof of the infinite Ramsey theorem uses the infinite pigeonhole principle, which is stronger; this is part of the subject of a post by Terence Tao which is quite enlightening.

Given a non-principal ultrafilter $F$ on $\mathbb{N}$, any partition of $\mathbb{N}$ into finitely many disjoint subsets (that is, any coloring) has the property that exactly one of the subsets is in $F$ (that is, has “full measure”), and this subset must be infinite. This subset can, in turn, be colored (partitioned), and exactly one of the blocks of the partition is in $F$, and it must again be infinite, and so forth. It follows that a non-principal ultrafilter lets us use the infinite pigeonhole principle repeatedly (in fact this is in some sense what a non-principal ultrafilter is), and since this is exactly what is needed to prove the infinite Ramsey theorem we might expect that we could use a non-principal ultrafilter to prove the infinite Ramsey theorem. Today we’ll describe this proof, and then describe how the infinite Ramsey theorem implies the finite Ramsey theorem, which involves a different use of a non-principal ultrafilter on $\mathbb{N}$.

The standard proof

Pick a vertex $v_1 \in K_{\infty}$. By infinite pigeonhole, there exists a color $c_1$ such that $v_1$ has infinitely many neighbors of color $c_1$; call these neighbors $W_1$. Pick a vertex $v_2 \in W_1$. Again by infinite pigeonhole, there exists a color $c_2$ such that $v_2$ has infinitely many neighbors in $W_1$ of color $c_2$; call these neighbors $W_2$. And so forth. By induction we define a sequence of vertices $v_1, v_2, v_3, ...$ such that the edge $v_i v_j$ has color $c_i$ for all $i < j$. By a final application of infinite pigeonhole, infinitely many of the colors $c_i$ are the same, so we are done.

I was worried about whether this proof uses some form of dependent choice, but it does not; one only has to put a total order on the set of colors, and at each step where we invoke infinite pigeonhole we can take the unique infinite subset with minimal color.

Using ultrafilters

This proof is substantially the same as the above proof, but I think it’s a nice application of ultrafilters nonetheless.

Fix a non-principal ultrafilter $F$ on the vertex set of $K_{\infty}$. The coloring on the edges of $K_{\infty}$ give a coloring of the vertices as follows: to each vertex $v \in K_{\infty}$ we associate a partition of the remaining vertices by the color of the corresponding edges, so exactly one of the blocks of this partition is in $F$, corresponding to the color $c_v$. In probabilistic terms, $v$ is adjacent to an edge of color $c_v$ almost surely.

The colors $c_v$ define a partition of the vertex set, and exactly one of the blocks is in $F$, corresponding to some color $c$. In probabilistic terms, $v$ is (adjacent to an edge of color $c$ almost surely) almost surely. But now it is straightforward to define by induction a sequence of vertices all connected to each other by an edge of color $c$.

Of course, this proof can be carried out without the ultrafilter $F$, but it’s interesting to see how the ultrafilter $F$ encodes the infinitely many choices one would have to make if one did not place a total order on the set of colors.

The finite Ramsey theorem

Recall that the finite Ramsey theorem says the following.

Theorem: Fix positive integers $k, m$. There exists a positive integer $n$ such that, if the edges of $K_n$ are colored with $k$ colors, there is a monochromatic $K_m$.

Proof. Suppose there are $k, m$ for which the theorem is false. Then for every positive integer $n$, there exists a coloring of the edges of $K_n$ by $k$ colors with no monochromatic $K_m$. These colorings can be described as functions $\omega_n : { [n] \choose 2} \to [k]$ where $[n] = \{ 1, 2, ... n \}$ and ${S \choose 2}$ is the set of subsets of $S$ of size $2$. We will use these colorings to construct a coloring of the edges of $K_{\infty}$ by $k$ colors with no monochromatic $K_m$, which contradicts the infinite Ramsey theorem.

We do this as follows. Let $F$ be a non-principal ultrafilter on $\mathbb{N}$. Our graph will have vertex set $V = \prod_n [n] / F$, the quotient of $\prod_n [n]$ by the equivalence relation $\prod x_i \sim \prod y_i$ if $\{ n : x_n = y_n \} \in F$; in probabilistic terms, if $x_i = y_i$ almost surely. There is also an edge from $\prod x_i$ to $\prod y_i$ of color $c$ if $\{ n : \omega_n(x_n, y_n) = c \} \in F$; in probabilistic terms, if $x_i$ is connected to $y_i$ by an edge of color $c$ almost surely. This construction is known as an ultraproduct in logic and model theory. It is not hard to see that the resulting graph $G$ is indeed a $K_{\infty}$ equipped with a $k$-coloring on its edges. This follows from Łoś’s theorem, although it is not hard to see directly.

Consider an $m$-element subset of $V$; for concreteness consider representatives $\prod x_{n,m}$ of its elements. This subset is monochromatic if and only if almost all of the graphs $\{ x_{n,1}, ... x_{n,m} \}$ are monochromatic, but by assumption this does not occur. (This also follows from Łoś’s theorem.) Hence $V$ does not have a monochromatic $K_m$, and this contradicts the infinite Ramsey theorem.

Of course this proof is completely nonconstructive! Nevertheless, I think it is valuable to know that ultraproducts provide a machinery for automatically constructing infinitary results to nonconstructive but finitary ones. There is a post by Terence Tao discussing similar applications of ultraproducts as the one above; we will have more to say about ultraproducts in a later post. One can also regard the above argument as an application of the compactness theorem for first-order logic; we will also have more to say about this in a later post.

17 Responses

1. […] answer. First a link to some course notes on Ramsey theory, to know what I am speaking about. Also this post might be helpful (the link to the notes is from a comment there). The proof of Ramsey theorem uses […]

2. Told you!

On clicking your link I find that the lecturer must have been taking the course the same year I did – he clearly understood it much better, though! I think my own hand-written notes got lost a few years ago; perhaps I may read Paul Russell’s, and this time actually understand some more of what’s going on. (The attempt at the time to learn by osmosis from all the brighter people around me didn’t really work…)

• Sorry, that should have been a reply to a particular comment; could you please move it onto the appropriate thread? Thanks.

• Not actually sure how to do that, unfortunately.

3. You probably know that it’s easy to deduce the finite Ramsey theorem from the infinite one using the lemma “an infinite tree with finite branching has an infinite path”; perhaps this is what you are alluding to in the last comment about compactness?

Also, are you planning to do the ultrafilter proof of Hindman’s Theorem? A bloggy presentation of that would be something I’d be thrilled to see.

• No, I didn’t know that; that’s interesting. I can’t readily find a clear statement of the relationship between König’s lemma and the ultrafilter lemma, but the argument I’m thinking of is the following: there is a first-order theory whose models are k-colorings of a complete graph with no monochromatic K_m. By the compactness theorem for first-order logic (which is equivalent to the ultrafilter lemma), if this theory has finite models of arbitrarily large cardinality, it has an infinite model; contradiction.

• This boils down to the same thing, I think; consider the tree whose nodes are k-colored graphs which contain no monochromatic K_m, with edges given by conclusion. There is an infinite path; unioning along it gives an infinite k-colored graph with no K_m. Contradiction.

• I think the argument via König’s lemma is a little different. For one thing it gives a very different construction of the contradictory infinite graph. König’s lemma and the ultrafilter lemma are both weak choice principles but they don’t look equivalent to me.

• The relationship I had in mind is via compactness.

• Also, I wasn’t planning on talking about Hindman’s theorem, but if I can find a nice presentation of the proof I might try.

• I might get around writing about Hindman’s Theorem later this week… In case you don’t get around 😉

• You could always see if someone on the Part III lecture course on Ramsey Theory (I am assuming there is one this year) has some notes. I certainly remember $\beta\mathbb N$ (in its guise as the space of ultrafilters) being introduced and equipped with a semigroup structure, but can’t recall if we actually went on to do the (Galvin and Glazer?) proof of Hindman’s theorem.

• @Yemon: nice tip. There are such notes on Paul Russell’s page: http://www.dpmms.cam.ac.uk/~par31/notes/ramsey.pdf

4. You can make the ultrafilter argument in the second section only apply its measure once by considering the tensor product of ultrafilters defined by X ∈U⊗V ⇐⇒ {i ∈ I | {j ∈ J | (i, j) ∈ X}∈V}∈U (where U lives on I, V on J)

In this case, the complete graph can be identified with those pairs in NxN (pairs of natural numbers that is) that lie above the diagonal. This set “above the diagonal” is easily shown to be a set in the tensor product of any free ultrafilters on N.

Now if U is free and you color/partition the graph, one part is in U⊗U — that’s the measure argument.

Then you exploit the natural basis of U⊗U and get a subset of the form $\bigcup_{i \in A} \{i \} x B_i$ with A and all the $B_i$ coming from U.

Pick inductively from A intersected with all $B_i$ with indices chosen so far and -bam- you get a pseudo-intersection that does the job.

• I’m having trouble parsing the definition of the tensor product. I considered a similar construction but forgot I had – is it the ultrafilter generated by the set of pairs of elements in U and in V?

• Yep. It’s easier to look at the following base: sets of the form

$\bigcup_{ i \in A} \{ i \} \times B_i$

where $A\in U$ and the $B_i \in V$ for $i\in A$.

In other words, the projection to the first coordinate is a set in U and U-almost all fibers are in V.

• ah, I just realized, you might mean “Is U⊗V generated by AxB for $A\in U, B\in V$?”

Those sets are all in the product — but that won’t give you an _ultra_filter (in general at least). You need that more complicated form of sets I gave just above, where the B’s can vary per element from A.