Ramsey theorem

The name of several theorems in discrete mathematics formulated and proved by F.P. Ramsey [1].

The first of these theorems was formulated by Ramsey as follows. Let $\Gamma$ be an infinite class and let $\mu$ and $r$ be positive integers; let all the subclasses of $\Gamma$ which have $r$ elements, in other words, all the $r$-tuples of $\Gamma$, be separated in some way into $\mu$ disjoint classes $C_i$, $i=1,\dots,\mu$, so that each $r$-tuple is an element of one and only one class $C_i$; then, assuming the axiom of choice, the class $\Gamma$ must contain an infinite subclass $\Delta$ such that all the $r$-tuples of $\Delta$ belong to the same class $C_i$. The finite analogue of this Ramsey theorem was also established by Ramsey and can be formulated in the following way.

Let $S$ be a set containing $N$ elements and let $T$ be the family of all subsets of $S$ containing precisely $r$ elements of $S$. Let the family $T$ be decomposed into $t$ (non-intersecting) subfamilies $T_1,\dots,T_t$ and let $q_1,\dots,q_t,r$ be integers, $q_i\geq r\geq1$, $i=1,\dots,t$. Then there exists a minimal number $n(q_1,\dots,q_t,r)$, depending only on $q_1,\dots,q_t,r$ and not depending on $S$, such that if $N\geq n(q_1,\dots,q_t,r)$, then for some $i$, $i=1,\dots,t$, there exists a subset $A_i$ of $S$ with $q_i$ elements which has all its $r$-subsets in the family $T_i$ (a proof of this theorem is also contained in [2], [3]).

The latter theorem can be illustrated by an example in which the number $n(3,3,2)$ is calculated. Consider six points in the plane which are connected in pairs by edges, each of which is coloured either red or blue. Then three points exist such that the edges joining them are coloured by the same colour. From the five edges joining a certain point $P_0$ with the five other points there are three edges of one colour (for example, red). Let these be the edges $P_0P_1$, $P_0P_2$, $P_0P_3$. If one of the edges $P_1P_2$, $P_1P_3$, $P_2P_3$ is red, then it and the two others joining its ends with the point $P_0$ form a red triangle, if they are all blue, then they themselves form a blue triangle. This means that $n(3,3,2)\leq6$. However, five points on the plane can be joined in pairs by red and blue edges so that no triangle of one colour can be found. To do this, let the edges $P_1P_2$, $P_1P_3$, $P_2P_4$, $P_3P_5$, $P_4P_5$ be red and the remaining blue. This shows that $n(3,3,2)>5$. Thus $n(3,3,2)=6$.

Ramsey's theorem implies the following result: For a given integer $n\geq3$ there exists an integer $N=N(n)$ such that among any $N$ points in the plane, no three of each lying on the same line, there are $n$ points forming a convex $n$-gon (see [4]).

References

[1]	F.P. Ramsey, "On a problem of formal logic" Proc. London Math. Soc. Ser. 2 , 30 (1930) pp. 264–285
[2]	H.J. Ryser, "Combinatorial mathematics" , Math. Assoc. Amer. (1963)
[3]	M. Hall, "Combinatorial theory" , Blaisdell (1967)
[4]	P. Erdös, G. Szekeres, "A combinatorial problem in geometry" Compos. Math. , 2 (1935) pp. 463–470
[5]	P. Erdös, R. Rado, "A partition calculus in set theory" Bull. Amer. Math. Soc. , 62 (1956) pp. 427–489

Comments

Nowadays, the study of Ramsey-like theorems has grown into a separate branch of combinatorics, called Ramsey theory.

References

[a1]	R.L. Graham, B.L. Rothschild, J.H. Spencer, "Ramsey theory" , Wiley (1980)
[a2]	P. Erdös, A. Hajnal, A. Mate, R. Rado, "Combinatorial set theory: partition relations for cardinals" , North-Holland (1984)