Applications of infinite Ramsey's Theorem (on N)? - MathOverflow

Applications of infinite Ramsey's Theorem (on N)?

2010-01-18T17:52:32Z

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?

Answer by Kristal Cantwell for Applications of infinite Ramsey's Theorem (on N)?

2010-01-18T18:33:18Z

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.

Answer by HaH for Applications of infinite Ramsey's Theorem (on N)?

2010-01-18T19:13:45Z

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.

Answer by François G. Dorais for Applications of infinite Ramsey's Theorem (on N)?

2010-01-18T20:27:04Z

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.

Answer by Yemon Choi for Applications of infinite Ramsey's Theorem (on N)?

2010-01-18T20:56:09Z

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.

Answer by Joel David Hamkins for Applications of infinite Ramsey's Theorem (on N)?

2010-01-19T01:57:33Z

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.

Answer by Vladimir Dotsenko for Applications of infinite Ramsey's Theorem (on N)?

2010-03-27T22:27:14Z

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".

Answer by Péter Komjáth for Applications of infinite Ramsey's Theorem (on N)?

2010-06-26T14:45:14Z

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.

Answer by Chris for Applications of infinite Ramsey's Theorem (on N)?

2011-02-25T13:20:02Z

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.

Answer by Stefan Geschke for Applications of infinite Ramsey's Theorem (on N)?

2011-07-30T09:52:51Z

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.

Answer by T.Karageorgos for Applications of infinite Ramsey's Theorem (on N)?

2012-10-17T18:50:07Z

I think it gives the most beautiful proof of the bolzano - weirstrass theorem.It's a very easy but beautiful "application" of Ramsey's theorem.