Applications of infinite Ramsey's Theorem (on N)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T09:12:31Z http://mathoverflow.net/feeds/question/12211 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n Applications of infinite Ramsey's Theorem (on N)? alexod 2010-01-18T17:52:32Z 2012-10-17T18:50:07Z <p>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.</p> <p>I searched in the literature for applications of infinite Ramsey's theorem and only found </p> <ul> <li>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,</li> <li>Ramsey factorization for \omega-words,</li> <li>the original applications of Ramsey to Logic.</li> </ul> <p>Where else is infinite Ramsey's theorem used? Especially are there applications to analysis?</p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/12215#12215 Answer by Kristal Cantwell for Applications of infinite Ramsey's Theorem (on N)? Kristal Cantwell 2010-01-18T18:33:18Z 2010-01-18T20:03:45Z <p>The strengthened finite Ramsey theorem:</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/12221#12221 Answer by HaH for Applications of infinite Ramsey's Theorem (on N)? HaH 2010-01-18T19:13:45Z 2010-01-18T19:13:45Z <p>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.</p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/12228#12228 Answer by François G. Dorais for Applications of infinite Ramsey's Theorem (on N)? François G. Dorais 2010-01-18T20:27:04Z 2010-03-27T20:44:29Z <p>The following fact has been called "Ramsey's Theorem for Analysts" by H. P. Rosenthal.</p> <blockquote> <p><strong>Theorem.</strong> 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) &lt; k(1) &lt; k(2) &lt; \cdots$ such that <code>$a = {\displaystyle\lim_{i&lt;j} a_{k(i),k(j)}}$</code>.</p> </blockquote> <p>The last limit means that for every $\varepsilon > 0$ there is an $n$ such that $n &lt; i &lt; j$ implies $|a-a_{k(i),k(j)}| &lt; \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. </p> <p>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.</p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/12234#12234 Answer by Yemon Choi for Applications of infinite Ramsey's Theorem (on N)? Yemon Choi 2010-01-18T20:56:09Z 2010-01-18T20:56:09Z <p>One example which I find quite cute, although I'm not enough of a specialist/connoisseur to know how important it is:</p> <p>MR1045291 (91b:46013) The Banach space $B(l^2)$ is primary.</p> <p>G. Blower, <a href="http://dx.doi.org/10.1112/blms/22.2.176" rel="nofollow">Bull. London Math. Soc. 22 (1990), no. 2, 176--182.</a> </p> <p>To quote the Math Review:</p> <blockquote>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.</blockquote> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/12265#12265 Answer by Joel David Hamkins for Applications of infinite Ramsey's Theorem (on N)? Joel David Hamkins 2010-01-19T01:57:33Z 2010-01-19T02:23:37Z <p>Beyond the infinite Ramsey's theorem on N, there is, of course, a kind of super-infinite extension of it to the concept of <a href="http://en.wikipedia.org/wiki/Ramsey%5Fcardinal" rel="nofollow">Ramsey cardinals</a>, one of many <a href="http://en.wikipedia.org/wiki/Large%5Fcardinal" rel="nofollow">large cardinal</a> concepts. </p> <p>Most of the large cardinal concepts, including Ramsey cardinals, generalize various mathematical properties of the countably infinite cardinal &omega; to uncountable cardinals. For example, an uncountable cardinal &kappa; is a <em>Ramsey cardinal</em> if every coloring of finite subsets of kappa into 2 colors (or indeed, less than &kappa; many colors) admits a homogeneous set of size &kappa;. 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 &kappa; to 2 colors has a homogeneous set, is equivalent to &kappa; being <a href="http://en.wikipedia.org/wiki/Weakly%5Fcompact%5Fcardinal" rel="nofollow">weakly compact</a>, a provably weaker notion, since every Ramsey cardinal is a limit of weakly compact cardinals. Similarly, the concept of <a href="http://en.wikipedia.org/wiki/Measurable%5Fcardinal" rel="nofollow">measurable cardinals</a> generalize the existence of ultrafilters on &omega;, for an uncountable cardinal &kappa; is said to be a <em>measurable cardinal</em> if there is a nonprincipal &kappa;-complete ultrafilter on &kappa;. </p> <p>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 <a href="http://en.wikipedia.org/wiki/Zero%5Fsharp" rel="nofollow">0<sup>#</sup> exists</a>. Indeed, this latter argument proceeds as a pure Ramsey style argument, using a coloring. Namely, if &kappa; 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 &kappa;, 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<sup>#</sup> exists.</p> <p>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 &omega;, 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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Axiom%5Fof%5Fdeterminacy" rel="nofollow">Axiom of Determinacy</a>, there are a great number of cardinals realizing an <a href="http://www.jstor.org/pss/2271873" rel="nofollow">infinite exponent paritition relation</a>. </p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/19549#19549 Answer by Vladimir Dotsenko for Applications of infinite Ramsey's Theorem (on N)? Vladimir Dotsenko 2010-03-27T22:27:14Z 2010-03-27T22:27:14Z <p>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".</p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/29618#29618 Answer by Péter Komjáth for Applications of infinite Ramsey's Theorem (on N)? Péter Komjáth 2010-06-26T14:45:14Z 2010-06-26T14:45:14Z <p>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. </p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/56629#56629 Answer by Chris for Applications of infinite Ramsey's Theorem (on N)? Chris 2011-02-25T13:20:02Z 2011-02-25T13:20:02Z <p>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.</p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/71646#71646 Answer by Stefan Geschke for Applications of infinite Ramsey's Theorem (on N)? Stefan Geschke 2011-07-30T09:52:51Z 2011-07-30T09:52:51Z <p>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.</p> http://mathoverflow.net/questions/12211/applications-of-infinite-ramseys-theorem-on-n/109937#109937 Answer by T.Karageorgos for Applications of infinite Ramsey's Theorem (on N)? T.Karageorgos 2012-10-17T18:50:07Z 2012-10-17T18:50:07Z <p>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.</p>