Noncombinatorial proofs of Ramsey's Theorem? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:25:22Z http://mathoverflow.net/feeds/question/29427 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29427/noncombinatorial-proofs-of-ramseys-theorem Noncombinatorial proofs of Ramsey's Theorem? Daniel Litt 2010-06-24T20:52:26Z 2010-06-25T00:12:51Z <p>I know of 2(.5) proofs of Ramsey's theorem, which states (in its simplest form) that for all $k, l\in \mathbb{N}$ there exists an integer $R(k, l)$ with the following property: for any $n>R(k, l)$, any $2$-coloring of the edges of $K_n$ contains either a red $K_k$ or a blue $K_l$.</p> <p>Both the finite and the infinite versions (the latter being--a 2-coloring of the edges of $K_\mathbb{N}$ contains an infinite monochrome $K_\mathbb{N}$) are proven on <a href="http://en.wikipedia.org/wiki/Ramsey%2527s_theorem#Proof_of_the_theorem" rel="nofollow">Wikipedia</a>, and one may deduce the finite version from the infinite one by compactness, or equivalently using Konig's lemma. The infinitary proof does not give effective bounds on $R(k, l)$, but can be converted to one that does as follows (this is the .5 proof): </p> <p>Consider a $2$-coloring of the edges of a complete graph on $N=2^{k+l}$ vertices, $v_1, ..., v_N$. Let $V_0$ be the set of all vertices, and let $V_i$ be the largest subset of $V_{i-1}$ connected to $v_i$ by edges of a single color, $c_i$. After $k+l$ steps, at least $k$ of the $c_i$ are read or $l$ of the $c_i$ are blue by pigeonhole; let the set of indices for which this happens be denoted $S$. Then $(v_i)_{i\in S}$ is the desired subgraph.</p> <p>My question is:</p> <blockquote> <p>Does anyone have a fundamentally different proof of this theorem? In particular, I am curious to know if there are any of a less combinatorial flavor.</p> </blockquote> http://mathoverflow.net/questions/29427/noncombinatorial-proofs-of-ramseys-theorem/29436#29436 Answer by Pietro Majer for Noncombinatorial proofs of Ramsey's Theorem? Pietro Majer 2010-06-24T22:05:32Z 2010-06-24T22:12:00Z <p>I hope this is close to what you are asking. The following compactness principle turns out to be useful in certain construction in dynamical systems and in probability (in particular, in the theory of exchangeable random variables), and it may be seen as a topological version of the infinitary Ramsey theorem. </p> <blockquote> <p><strong>Lemma.</strong> Let $X,d$ a compact metric space, and $u:\mathbb{N}^2\to X$ a double sequence in $X$. Then, there exists a strictly increasing $\sigma:\mathbb{N}\to\mathbb{N}$ such that, denoting $v(i,j):=u(\sigma(i),\sigma(\, j)),$ the following limits exist, and coincide:</p> <p>$$\lim_{i\to\infty} \lim_{j\to\infty} v(i,j) \ = \lim_{ i&lt; j,\, (i,j)\to\infty} v(i,j).$$</p> </blockquote> <p>The proof is just routine (iterated) application of the usual diagonal argument for sequences. How does it implies the infinitary Ramsey theorem? Take $X$ a discrete space of colors and $u$ an $X$-coloring of the complete graph with vertices set $\mathbb{N}$. Then the existence of the limit in the RHS means that the set $\{\sigma(i):i> c\}$ for some c is a monocromatic complete subgraph.</p> <p>One can even state a more general version for multi-sequences $u(i)$ indicized on increasing $n$-ples $i:=(i_1&lt; i_2\dots &lt; i_n)$ of natural numbers; the game is that any parenthesization </p> <p>$$(i_1,\dots,i_{k_1}),(i_{k_1+1},\dots,i_{k_2}),\dots,(i_{k_r},\dots,i_n)$$</p> <p>produces a different iterated way of letting $i$ go to infinity (like when making the beads sliding from left to right in an abacus: in small clusters, one at a time, or all together ). The corresponding limits for u(i) may or may not exist and/or coincide; but, up to a selection of indices via a strictly increasing $\sigma:\mathbb{N}\to\mathbb{N}$, all these iterated limits do exist and coincide.</p> <p>Actually, it may be argued whether it really gives a <em>fundamentally</em> different proof of Ramsey theorem as you are asking. Nevertheless, if you try submitting it to an analyst or to a geometer, I think you are much more likely to obtain an immediate proof of it than with the original set theoretic version (please confirm my guess). On the other hand, it may sound quite weird to a pure set theorist (do not necessarily confirm this statement). </p> http://mathoverflow.net/questions/29427/noncombinatorial-proofs-of-ramseys-theorem/29445#29445 Answer by Terry Tao for Noncombinatorial proofs of Ramsey's Theorem? Terry Tao 2010-06-25T00:12:51Z 2010-06-25T00:12:51Z <p>One can prove Ramsey's theorem by using a minimal ultrafilter on the infinite permutation group to make a graph monochromatic, see</p> <p><a href="http://terrytao.wordpress.com/2008/01/21/254a-lecture-5-other-topological-recurrence-results/" rel="nofollow">http://terrytao.wordpress.com/2008/01/21/254a-lecture-5-other-topological-recurrence-results/</a></p> <p>(This proof was first discovered by Neil Hindman.) But this proof is somewhat idiosyncratic and might not be to most people's taste. (Also, on some level it is equivalent to the usual iterated pigeonhole proof, though heavily disguised through several applications of the axiom of infinity and axiom of choice.) It is also closely related to the proof that Pietro mentioned.</p>