Namespaces
Variants
Actions

Difference between revisions of "Ramsey theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Category:Combinatorics)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 
The name of several theorems in discrete mathematics formulated and proved by F.P. Ramsey [[#References|[1]]].
 
The name of several theorems in discrete mathematics formulated and proved by F.P. Ramsey [[#References|[1]]].
  
The first of these theorems was formulated by Ramsey as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772401.png" /> be an infinite class and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772402.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772403.png" /> be positive integers; let all the subclasses of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772404.png" /> which have <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772405.png" /> elements, in other words, all the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772406.png" />-tuples of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772407.png" />, be separated in some way into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772408.png" /> disjoint classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r0772409.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724010.png" />, so that each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724011.png" />-tuple is an element of one and only one class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724012.png" />; then, assuming the [[Axiom of choice|axiom of choice]], the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724013.png" /> must contain an infinite subclass <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724014.png" /> such that all the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724015.png" />-tuples of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724016.png" /> belong to the same class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724017.png" />. The finite analogue of this Ramsey theorem was also established by Ramsey and can be formulated in the following way.
+
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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724018.png" /> be a set containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724019.png" /> elements and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724020.png" /> be the family of all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724021.png" /> containing precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724022.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724023.png" />. Let the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724024.png" /> be decomposed into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724025.png" /> (non-intersecting) subfamilies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724026.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724027.png" /> be integers, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724029.png" />. Then there exists a minimal number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724030.png" />, depending only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724031.png" /> and not depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724032.png" />, such that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724033.png" />, then for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724035.png" />, there exists a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724036.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724037.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724038.png" /> elements which has all its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724039.png" />-subsets in the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724040.png" /> (a proof of this theorem is also contained in [[#References|[2]]], [[#References|[3]]]).
+
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 [[#References|[2]]], [[#References|[3]]]).
  
The latter theorem can be illustrated by an example in which the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724041.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724042.png" /> with the five other points there are three edges of one colour (for example, red). Let these be the edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724043.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724045.png" />. If one of the edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724048.png" /> is red, then it and the two others joining its ends with the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724049.png" /> form a red triangle, if they are all blue, then they themselves form a blue triangle. This means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724050.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724053.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724055.png" /> be red and the remaining blue. This shows that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724056.png" />. Thus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724057.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724058.png" /> there exists an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724059.png" /> such that among any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724060.png" /> points in the plane, no three of each lying on the same line, there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724061.png" /> points forming a convex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077240/r07724062.png" />-gon (see [[#References|[4]]]).
+
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 [[#References|[4]]]).
  
 
====References====
 
====References====
Line 18: Line 19:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.L. Graham,  B.L. Rothschild,  J.H. Spencer,  "Ramsey theory" , Wiley  (1980)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdös,  A. Hajnal,  A. Mate,  R. Rado,  "Combinatorial set theory: partition relations for cardinals" , North-Holland  (1984)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R.L. Graham,  B.L. Rothschild,  J.H. Spencer,  "Ramsey theory" , Wiley  (1980)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdös,  A. Hajnal,  A. Mate,  R. Rado,  "Combinatorial set theory: partition relations for cardinals" , North-Holland  (1984)</TD></TR>
 +
</table>
 +
 
 +
[[Category:Combinatorics]]

Latest revision as of 17:33, 1 November 2014

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)
How to Cite This Entry:
Ramsey theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ramsey_theorem&oldid=17790
This article was adapted from an original article by M.P. Mineev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article