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

Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) also seems to be a very basic and powerful tool but it is apparently not as widely used.

I searched in the literature for applications of infinite Ramsey's theorem and only found

  • straight forward generalization of statements that follow from finite Ramsey's theorem (example: Erdos-Szekeres ~> every infinite sequence of reals contains a monotonic subsequence) and some other basic combinatorial applications,
  • Ramsey factorization for \omega-words,
  • the original applications of Ramsey to Logic.

Where else is infinite Ramsey's theorem used? Especially are there applications to analysis?

share|improve this question
    
Is there a real difference between infinite Ramsey theorem and general finite Ramsey theorem for arbitrary large number of colors? The infinite version implies the finite one is easy. I am under the impression that we can get the former from the later by some compactness argument. –  Tran Chieu Minh Mar 28 '10 at 7:52
8  
@Tran The compactness argument only proves the finite version of Ramsey's theorem from the infinite one. The infinite Ramsey's theorem is proof-theoretically stronger than the finite version. For instance finite Ramsey is provable in PA, where infinite Ramsey implies the Paris-Harrington variant, which is not provable there. –  alexod May 8 '10 at 8:50
add comment

10 Answers 10

up vote 19 down vote accepted

The following fact has been called "Ramsey's Theorem for Analysts" by H. P. Rosenthal.

Theorem. Let $(a_{i,j})_{i,j=0}^\infty$ be an infinite matrix of real numbers such that $a_i = {\displaystyle\lim_{j\to\infty} a_{i,j}}$ exists for each $i$ and $a = {\displaystyle\lim_{i\to\infty} a_i}$ exists too. Then there is an infinite sequence $k(0) < k(1) < k(2) < \cdots$ such that $a = {\displaystyle\lim_{i<j} a_{k(i),k(j)}}$.

The last limit means that for every $\varepsilon > 0$ there is an $n$ such that $n < i < j$ implies $|a-a_{k(i),k(j)}| < \varepsilon$. When the matrix is symmetric and ${\displaystyle\lim_{i\to\infty} a_{k(i),k(i)}} = a$ too, this is just an ordinary double limit.

The proof is a straightforward applications of the two-dimensional Ramsey's Theorem. The obvious higher dimensional generalizations are also true and they can be established in the same way using the corresponding higher dimensional Ramsey's Theorem. These are used to construct "spreading models" in Banach Space Theory.

share|improve this answer
add comment

The strengthened finite Ramsey theorem:

For any positive integers n, k, m we can find N with the following property: if we color each of the n element subsets of S = {1, 2, 3,..., N} with one of k colors, then we can find a subset Y of S with at least m elements, such that all n element subsets of Y have the same color, and the number of elements of Y is at least the smallest element of Y.

The Paris–Harrington theorem states that the strengthened finite Ramsey theorem is not provable in Peano arithmetic. See the Wikipedia article on the Paris-Harrington theorem.

share|improve this answer
add comment

Ramsey's theorem (and other generalizations such as the Erdos-Rado theorem) are used in many standard model theoretic arguments which are involved in finding (models with) indiscernibles. The most basic example is perhaps the Ehrenfeucht-Mostowski theorem.

share|improve this answer
add comment

One example which I find quite cute, although I'm not enough of a specialist/connoisseur to know how important it is:

MR1045291 (91b:46013) The Banach space $B(l^2)$ is primary.

G. Blower, Bull. London Math. Soc. 22 (1990), no. 2, 176--182.

To quote the Math Review:

The author proves that if $A$ is an infinite-dimensional injective operator system on $l^2$ and $P$ is a completely bounded projection on $A$, then either $PA$ or $(I-P)A$ is completely boundedly isomorphic to $A$. The author also proves that if $B(l^2)$ is linearly isomorphic to a direct sum of two Banach spaces, then it is linearly isomorphic to one of these spaces. An interesting component of his proof is the use of Ramsey theory.
share|improve this answer
    
This is a nice application of Ramsey's theorem, but as far as I can see they are could have used finite Ramsey's theorem if they would have calculated the size of the sets $\sigma_i$. –  alexod Jan 19 '10 at 10:42
add comment

Beyond the infinite Ramsey's theorem on N, there is, of course, a kind of super-infinite extension of it to the concept of Ramsey cardinals, one of many large cardinal concepts.

Most of the large cardinal concepts, including Ramsey cardinals, generalize various mathematical properties of the countably infinite cardinal ω to uncountable cardinals. For example, an uncountable cardinal κ is a Ramsey cardinal if every coloring of finite subsets of kappa into 2 colors (or indeed, less than κ many colors) admits a homogeneous set of size κ. Such cardinals are necessarily inaccessible, Mahlo, and much more. The somewhat weaker property, that every coloring of pairs (or for any fixed finite size) from κ to 2 colors has a homogeneous set, is equivalent to κ being weakly compact, a provably weaker notion, since every Ramsey cardinal is a limit of weakly compact cardinals. Similarly, the concept of measurable cardinals generalize the existence of ultrafilters on ω, for an uncountable cardinal κ is said to be a measurable cardinal if there is a nonprincipal κ-complete ultrafilter on κ.

Ramsey cardinals figure in many arguments in set theory. For example, if there is a Ramsey cardinal, then V is not L, and Ramsey cardinals are regarded as a natural large cardinal notion just exceeding the V=L boundary. Another prominent result is the fact that every measurable cardinal is Ramsey (which is not obvious from first notions). Further, if there is a Ramsey cardinal, then 0# exists. Indeed, this latter argument proceeds as a pure Ramsey style argument, using a coloring. Namely, if κ is Ramsey, then we may color every finite increasing sequence of ordinals with the type that they realize in L. By the Ramsey property, there must be a set of size κ, all of whose increasing finite subsequences realize the same type. That is, there is a large class of order indiscernibles for L. By results of Silver, this is equivalent to the assertion that 0# exists.

The fact that Ramsey cardinals are strictly stronger than weakly compact cardinals suggests to my mind that there is something fundamentally more powerful about finding homogeneous sets for colorings of all finite subsets than just for pairs or for subsets of some fixed size. This difference is not revealed at ω, for which both are true by the infinite Ramsey theorem. But perhaps it suggests that we will get more power from Ramsey by using the more powerful colorings, since this is provably the case for higher cardinals.

Another point investigated by set theorists is that finding homogeneous sets in the case of infinite exponents---that is, coloring infinite subsets---is known to be inconsistent with the axiom of choice. However, in models of set theory where the Axiom of Choice fails, these infinitary Ramsey cardinals are fruitfully investigated. For example, under the Axiom of Determinacy, there are a great number of cardinals realizing an infinite exponent paritition relation.

share|improve this answer
4  
You write amazingly nice answers systematically. Thanks! –  Mariano Suárez-Alvarez Jan 19 '10 at 2:22
2  
Thanks very much for your kind remarks. I'm also very impressed by the range of your expertise, based on your numerous comments on diverse topics. –  Joel David Hamkins Jan 19 '10 at 2:40
add comment

That's probably too obvious, but still - applications to linear diophantine equations like (the simplest of all examples) "for every colouring of N in a finite number of colours the equation x+y=z has a monochrome solution".

share|improve this answer
    
Do we need the infinite Ramsey theorem to prove this? I am under the impression that if we fix the number of color the finite version will do. –  Tran Chieu Minh Mar 28 '10 at 7:48
    
You are right about that. I am not sure about the more general case of an equation though - and do not have Graham's book on Ramsey theory at hand to check it. –  Vladimir Dotsenko Mar 28 '10 at 12:32
add comment

Fred Galvin found the following corollary to Hindman's theorem. There are infinitely many natural numbers, so that any finite sum of them has an odd number of prime factors. Indeed, decompose the natural numbers into two classes according to the parity of the number of prime factors, then the quoted theorem states that there are infinitely many numbers so that any finite sum of them are in the same class, i.e., they have the same parity of the number of prime factors. If this parity is "even", then multiply all of them by 2.

share|improve this answer
add comment

There are, in fact, very deep uses of Ramsey-theoretic methods in analysis. As I recall, Gowers won a Fields medal for using this connection to answer most of the open conjectures about Banach space geometry. For example, he used these methods to show that there exists a Banach space with no unconditional Schauder basis. For a nice (though somewhat advanced) survey, there is a book "Ramsey Methods in Analysis" by Argyos and Todorcevic.

share|improve this answer
add comment

Matousek showed that for every $K\gneq 1$ every infinite metric space $X$ has an infinite subspace that either embeds into the real line by a $K$-bi-Lipschitz function or in which the distances of any two distinct points are the same up to a factor of $K$. The proof uses an iterated application of the infinite Ramsey theorem.

share|improve this answer
add comment

I think it gives the most beautiful proof of the Bolzano–Weierstrass theorem. It's a very easy but beautiful application of Ramsey's theorem.

Given a sequence $x=(x_n)$ of real numbers, colour the pairs of naturals $i < j$ by whether $x_i < x_j$ or $x_i \geq x_j$. Ramsey's theorem guarantees an infinite monochromatic set. This corresponds to a monotonic subsequence of $x$; if $x$ is bounded, then this subsequence converges.

share|improve this answer
    
+1. Coincidentally, I was recently working the other way, taking the "slick" proof of BW and seeing what kind of combinatorial argument made it work; and I think that one doesn't need the full force of Ramsey's theorem. We don't need an infinite monochromatic subset, so we have one less level of induction needed. –  Yemon Choi Oct 17 '12 at 19:37
    
Although, on rereading the original post, it already mentions the combinatorial result that underlies this proof of BW. In the original post this is attributed to Erdos and Szekeres –  Yemon Choi Oct 17 '12 at 19:40
1  
Would either one of you care to describe the argument? –  François G. Dorais Oct 18 '12 at 1:29
add comment

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.