Ultrafilters V: Ramsey Theory

Ramsey theory is an area of the mathematical field of combinatorics. Its slogan could be, “In a large enough structure, order must arise.” It is named after Frank Ramsey, student of Keynes, friend of Wittgenstein, brother of the future Archbishop of Canterbury, who did seminal work in the area before tragically dying at the age of 26.

ramsey
Frank Ramsey

You may have heard this one. Suppose you’re throwing a party. You don’t really know whether the people you’re thinking of inviting know one another, and you want to make sure that, at the party, there are either three people who mutually know one another or three people who mutually do not know one another (as everyone knows, a party is doomed to be a failure if this doesn’t happen). What is the least number of people you need to invite to make sure this happens?

The answer is 6. We need to prove two things. First, 5 is not enough. To see this, consider the following picture. Suppose each of the dots is a person at your party, and two people are connected with a red edge if they know one another and a blue edge if they do not know one another. If you get unlucky enough to invite exactly such a configuration of five guests, you will not have a group of three that mutually know one another nor a group of three that mutually do not know one another.

2000px-RamseyTheory_K5_no_mono_K3.svg
A disastrous party.

We next need to show that 6 is indeed sufficient. I’ll leave this as an exercise for the reader. It’s fun! You should do it.

(What is the least number of people you need to invite to ensure a group of four people who mutually know one another or a group of four people who mutually do not know one another? 18. What about for groups of five? Nobody knows (or, if they do, they haven’t told me), but it’s between 43 and 49.)

This is the standard introductory theorem in Ramsey theory. To state more general results, it will be helpful to have some notation.

Notation: Suppose X is a set and n is a natural number. Then [X]^n denotes the set of all n-element subsets of X, i.e. [X]^n = \{Y \subseteq X \mid |Y| = n\}.

Definition: Suppose X, Y are sets, n is a natural number, and f:[X]^n \rightarrow Y. If H \subseteq X, then we say H is homogeneous for f if there is a single element y \in Y such that, for all A \in [H]^n, f(A) = y.

The existence of a large homogeneous set for a given function f:[X]^n \rightarrow Y is an example of a certain amount of order existing in f. Therefore, a typical theorem in Ramsey theory may be something like this: If X is sufficiently large with respect to Y, n is a certain natural number, and f is any function from [X]^n to Y, then there is a large homogeneous set for f. Of course, ‘sufficiently large’ and ‘large’ would need to be made precise in the statement of an actual theorem.

With this language, we can restate our party theorem as follows: Suppose |X| = 6, |Y| = 2, and f:[X]^2 \rightarrow Y. Then f has a homogeneous set of size 3. Moreover, this is no longer true if we just assume |X| = 5.

Finite Ramsey theory is a fascinating and rich subject, and I encourage readers to learn more about it. Given the domain of this blog though, we want to consider Ramsey theory on infinite sets. The seminal result in this direction is, naturally, the Infinite Ramsey Theorem, proven by Ramsey in 1930.

Infinite Ramsey Theorem: Suppose n,k \in \mathbb{N} and f:[\mathbb{N}]^n \rightarrow \{1, \ldots, k\}. Then there is an infinite homogeneous set H \subseteq \mathbb{N} for f.

Proof: If either n or k is equal to 1, then the theorem is trivial. We prove the theorem for the case n = 2 and an arbitrary value of k. The general statement is proven in a similar way (with some additional care taken at certain points) by induction on n.

Let \mathcal{U} be a non-principal ultrafilter on \mathbb{N}. We will consider elements of [\mathbb{N}]^2 as ordered pairs (i,j) such that i < j. For each i \in \mathbb{N} and \ell \leq k, let A_{i, \ell} be the set of j \in \mathbb{N} such that i < j and f(i,j) = \ell. Since \mathcal{U} is a non-principal ultrafilter and \bigcup_{\ell \leq k} A_{i, \ell} = \mathbb{N} \setminus \{0, \ldots, i\}, we may fix a natural number \ell_i \leq k such that A_{i, \ell_i} \in \mathcal{U}. Again using the fact that \mathcal{U} is a non-principal ultrafilter, we may find a set B \in \mathcal{U} and a fixed natural number \ell^* \leq k such that, for all i \in B, i_\ell = i^*.

We now construct an infinite set H \subseteq B such that, for every i < j with both i and j in H, we have f(i,j)  = \ell^*. We will do this one element at a time, enumerating H in increasing order as \{i_m \mid m \in \mathbb{N}\}. To start, let i_0 be the least element of B. Next, find i_1 > i_0 such that i_1 \in B \cap A_{i_0, \ell^*}. Since B and A_{i_0, \ell^*} are in \mathcal{U}, such an i_1 exists and, as i_1 \in A_{i_0, \ell^*}, we have f(i_0, i_1) = \ell^*. Next, find i_2 > i_1 such that i_2 \in B \cap A_{i_0, \ell^*} \cap A_{i_1, \ell^*}. As before, such an i_2 always exists and f(i_0, i_2) = f(i_1, i_2) = \ell^*. Keep going in this fashion. Namely, if m^* \in \mathbb{N} and we have already defined \{i_m \mid m \leq m^*\}, then find i_{m^*+1} > i_{m^*} such that i_{m^*+1} \in B \cap A_{i_0, \ell^*} \cap A_{i_1, \ell^*} \cap \ldots \cap A_{i_{m^*}, \ell^*}. Since this is an intersection of finitely many sets, all of which are in \mathcal{U}, we can always find such an i_{m^*+1} and, for all m \leq m^*, we have f(i_m, i_{m^*+1}) = \ell^*. Thus, we can continue for infinitely many steps, completing the definition of H and therefore the proof of the theorem.

Remarks: The use of an ultrafilter here is not really necessary but makes the proof a little slicker. It also raises an interesting question related to the notion that Ramsey theory is about finding large homogeneous sets. Recall that ultrafilters can be thought of as specifying which subsets of a given set should be considered to be ‘large.’ In the Infinite Ramsey Theorem, we were able to obtain an infinite homogeneous set, but can we always find a homogeneous set H \in \mathcal{U}? This question motivates the following definition.

Definition: Let \mathcal{U} be a non-principal ultrafilter on \mathbb{N}. \mathcal{U} is called a Ramsey ultrafilter if, for all natural numbers n,k and every function f:[\mathbb{N}]^n \rightarrow \{1, \ldots, k\}, there is a set H \in \mathcal{U} that is homogeneous for f.

So our question becomes: are all non-principal ultrafilters on \mathbb{N} Ramsey ultrafilters? The answer to this is: “No.” There are always non-principal ultrafilters on \mathbb{N} that are not Ramsey ultrafilters.

So the next question, of course, is: are there any Ramsey ultrafilters? This turns out to be the interesting question, and the answer is: “It depends.” The existence of Ramsey ultrafilters is independent of the usual axioms of set theory (the axioms of ZFC). Namely, it is consistent with the axioms of ZFC that Ramsey ultrafilters exist, but it is also consistent with ZFC that Ramsey ultrafilters do not exist.

Infinite Ramsey theory has been in the news lately due to a recent breakthrough in reverse mathematics by Ludovic Patey and Keita Yokoyama. Let me try to briefly (and therefore rather imprecisely) explain their result, with the caveat that I am in no way an expert in reverse mathematics.

As I mentioned, the standard proofs of the Infinite Ramsey Theorem are pretty similar for the cases n=2 and n=3. This should make a certain amount of sense, since the statements for n=2 and n=3 are quite similar. However, in another sense, this is somewhat misleading, as the standard proof of the Infinite Ramsey Theorem takes place in the setting of the axioms of set theory (ZFC), and these axioms may be much more powerful than necessary. Reverse mathematics attempts to classify theorems by exactly how much one needs to assume (beyond some fixed, very weak base system (known as \mathrm{RCA}_0)) to prove them. A hierarchy of systems extending \mathrm{RCA}_0 has been uncovered through the attempt to pin down the logical strengths of various theorems. An interesting dividing line in the set of these systems is between those that are ‘finitistic’ (essentially, those that do not rely on the existence of infinite sets) and those that are ‘infinitistic.’ The strongest finitistic system in widespread use is ‘primitive recursive arithmetic,’ or ‘PRA.’ A theorem is thus called ‘finitistically reducible’ if it is finitistically reducible to PRA (roughly, if it can be proven without the use of infinite sets).

It was known already that the instance of the Infinite Ramsey Theorem with n=3 and k=2 is not finitistically reducible. This makes a certain naive, intuitive sense, as the conclusion of the theorem asserts the existence of an infinite homogeneous set. Patey and Yokoyama’s surprising result is that the instance of the Infinite Ramsey Theorem with n=2 and k=2 is finitistically reducible. Unlike the infinite homogeneous set generated by the n=3 case, that generated by the n=2 case is, in a sense, simple enough that any consequence of its existence can be obtained purely finitistically.

For those of you who want to read more about this interesting result, there’s a decent article about it in Quanta Magazine, and Patey and Yokoyama’s paper can be found here.

 

Advertisements

3 thoughts on “Ultrafilters V: Ramsey Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s