Namespaces
Variants
Actions

Difference between revisions of "Ramsey number"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
Ramsey theory has been described as a branch of mathematics which  "implies that complete disorder is an impossibility"  [[#References|[a3]]], [[#References|[a1]]]. In Ramsey theory one wishes to know how large a collection of objects must be in order to guarantee the existence of a particular substructure [[#References|[a3]]]. Thus, Ramsey theory can be viewed as a vast generalization of the Dirichlet pigeon-hole principle (or [[Dirichlet box principle|Dirichlet box principle]]).
 
Ramsey theory has been described as a branch of mathematics which  "implies that complete disorder is an impossibility"  [[#References|[a3]]], [[#References|[a1]]]. In Ramsey theory one wishes to know how large a collection of objects must be in order to guarantee the existence of a particular substructure [[#References|[a3]]]. Thus, Ramsey theory can be viewed as a vast generalization of the Dirichlet pigeon-hole principle (or [[Dirichlet box principle|Dirichlet box principle]]).
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100301.png" /> be a [[Graph|graph]], i.e., a set of vertices, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100302.png" />, together with a set of edges, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100303.png" />, where each member of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100304.png" /> is a subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100305.png" /> consisting of exactly two elements. The complete graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100306.png" /> is the graph for which all pairs of its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100307.png" /> vertices are connected by an edge. A [[Hypergraph|hypergraph]] is a set of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100308.png" /> together with a family of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r1100309.png" /> called faces. If a face contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003010.png" /> vertices, it is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003011.png" />-face. If every face of a hypergraph has the same cardinality, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003012.png" />, then the hypergraph is called a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003014.png" />-graph.
+
Let $G$ be a [[Graph|graph]], i.e., a set of vertices, $V$, together with a set of edges, $E$, where each member of $E$ is a subset of $V$ consisting of exactly two elements. The complete graph $k_r$ is the graph for which all pairs of its $r$ vertices are connected by an edge. A [[Hypergraph|hypergraph]] is a set of vertices $V$ together with a family of subsets of $V$ called faces. If a face contains $k$ vertices, it is a $k$-face. If every face of a hypergraph has the same cardinality, $k$, then the hypergraph is called a $k$-graph.
  
Intuitively, a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003016.png" />-colouring is obtained by simply painting each edge of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003017.png" /> with any one of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003018.png" /> colours. The analogue of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003019.png" />-colouring for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003020.png" />-graphs is obtained by painting each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003021.png" />-face with any one of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003022.png" /> colours. In a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003023.png" />-colouring the colours are usually taken to be red and blue. A monochromatic graph is a graph whose edges have all been painted the same colour.
+
Intuitively, a $t$-colouring is obtained by simply painting each edge of $G$ with any one of $t$ colours. The analogue of a $t$-colouring for $k$-graphs is obtained by painting each $k$-face with any one of $t$ colours. In a $2$-colouring the colours are usually taken to be red and blue. A monochromatic graph is a graph whose edges have all been painted the same colour.
  
Consider the minimum integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003024.png" /> such that no matter how the edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003025.png" /> are coloured with two colours, red and blue, there is always a monochromatic subgraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003026.png" /> that is red, or a monochromatic subgraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003027.png" /> that is blue. The integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003028.png" /> is called a Ramsey number. It is easy to show that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003029.png" />, [[#References|[a8]]].
+
Consider the minimum integer $r=R(p,q)$ such that no matter how the edges of $k_r$ are coloured with two colours, red and blue, there is always a monochromatic subgraph $k_p$ that is red, or a monochromatic subgraph $k_q$ that is blue. The integer $r=R(p,q)$ is called a Ramsey number. It is easy to show that $R(3,3)=6$, [[#References|[a8]]].
  
The following two popular problems (which are really the same) simply assert that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003030.png" />:
+
The following two popular problems (which are really the same) simply assert that $R(3,3)=6$:
  
 
1) Take six points in general position in space (no three in a line, nor four in a plane). Draw the fifteen line segments joining them in pairs, and then paint them all, some segments red, some blue. Prove that some triangle has all its sides the same colour. (William Lowell Putnam Mathematical Competition, 1953.)
 
1) Take six points in general position in space (no three in a line, nor four in a plane). Draw the fifteen line segments joining them in pairs, and then paint them all, some segments red, some blue. Prove that some triangle has all its sides the same colour. (William Lowell Putnam Mathematical Competition, 1953.)
Line 13: Line 14:
 
2) Prove that at a gathering of any six people some three of them are either mutual acquaintances or complete strangers to one another. (The American Mathematical Monthly, June–July 1958.)
 
2) Prove that at a gathering of any six people some three of them are either mutual acquaintances or complete strangers to one another. (The American Mathematical Monthly, June–July 1958.)
  
The definition of a Ramsey number can be generalized to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003031.png" />-colourings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003032.png" />-graphs. Stated more generally, the Ramsey number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003033.png" /> is the smallest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003034.png" /> such that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003035.png" />-colouring of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003036.png" />-faces of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003037.png" />, with colours <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003038.png" />, there is either a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003039.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003042.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003043.png" />. Thus, with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003044.png" />-colourings, a Ramsey number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003045.png" /> is the smallest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003046.png" /> such that no matter how the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003047.png" />-faces of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003048.png" /> are coloured red or blue, there is either a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003049.png" /> subgraph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003050.png" /> with all its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003051.png" />-faces red, or a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003052.png" /> subgraph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003053.png" /> with all its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003054.png" />-faces blue.
+
The definition of a Ramsey number can be generalized to $t$-colourings of $k$-graphs. Stated more generally, the Ramsey number $R_k(p_1,\dots,p_t)$ is the smallest $r$ such that for any $t$-colouring of the $k$-faces of $Y$, with colours $c_1,\dots,c_t$, there is either a $c_1$-$k_{p_1}$, $\dots$, $c_t$-$k_{p_t}$. Thus, with respect to $2$-colourings, a Ramsey number $R_k(p,q)$ is the smallest $r$ such that no matter how the $k$-faces of $k_r$ are coloured red or blue, there is either a $k_p$ subgraph of $k_r$ with all its $k$-faces red, or a $k_q$ subgraph of $k_r$ with all its $k$-faces blue.
  
 
Very few Ramsey numbers are known. The known Ramsey numbers are [[#References|[a7]]]:
 
Very few Ramsey numbers are known. The known Ramsey numbers are [[#References|[a7]]]:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003055.png" /></td> </tr></table>
+
$$R(3,3)=6,R(3,4)=9,R(3,5)=14,$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003056.png" /></td> </tr></table>
+
$$R(3,6)=18,R(3,7)=23,R(3,8)=28,R(3,9)=36,R(4,4)=18,R(4,5)=25.$$
  
The only Ramsey number for hypergraphs that has been computed is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r110/r110030/r11003057.png" /> [[#References|[a4]]].
+
The only Ramsey number for hypergraphs that has been computed is $R_3(4,4)=13$ [[#References|[a4]]].
  
 
F.P. Ramsey's combinatorial contribution, which is now known as Ramsey's theorem, was originally needed in [[#References|[a8]]], a paper that focused on mathematical logic. In the mid 1930s, P. Erdös rediscovered Ramsey's theorem [[#References|[a5]]] and in the mid 1950s research in Ramsey theory started to take hold. By the 1970s, Ramsey theory was firmly established [[#References|[a6]]].
 
F.P. Ramsey's combinatorial contribution, which is now known as Ramsey's theorem, was originally needed in [[#References|[a8]]], a paper that focused on mathematical logic. In the mid 1930s, P. Erdös rediscovered Ramsey's theorem [[#References|[a5]]] and in the mid 1950s research in Ramsey theory started to take hold. By the 1970s, Ramsey theory was firmly established [[#References|[a6]]].

Revision as of 12:45, 11 October 2014

Ramsey theory has been described as a branch of mathematics which "implies that complete disorder is an impossibility" [a3], [a1]. In Ramsey theory one wishes to know how large a collection of objects must be in order to guarantee the existence of a particular substructure [a3]. Thus, Ramsey theory can be viewed as a vast generalization of the Dirichlet pigeon-hole principle (or Dirichlet box principle).

Let $G$ be a graph, i.e., a set of vertices, $V$, together with a set of edges, $E$, where each member of $E$ is a subset of $V$ consisting of exactly two elements. The complete graph $k_r$ is the graph for which all pairs of its $r$ vertices are connected by an edge. A hypergraph is a set of vertices $V$ together with a family of subsets of $V$ called faces. If a face contains $k$ vertices, it is a $k$-face. If every face of a hypergraph has the same cardinality, $k$, then the hypergraph is called a $k$-graph.

Intuitively, a $t$-colouring is obtained by simply painting each edge of $G$ with any one of $t$ colours. The analogue of a $t$-colouring for $k$-graphs is obtained by painting each $k$-face with any one of $t$ colours. In a $2$-colouring the colours are usually taken to be red and blue. A monochromatic graph is a graph whose edges have all been painted the same colour.

Consider the minimum integer $r=R(p,q)$ such that no matter how the edges of $k_r$ are coloured with two colours, red and blue, there is always a monochromatic subgraph $k_p$ that is red, or a monochromatic subgraph $k_q$ that is blue. The integer $r=R(p,q)$ is called a Ramsey number. It is easy to show that $R(3,3)=6$, [a8].

The following two popular problems (which are really the same) simply assert that $R(3,3)=6$:

1) Take six points in general position in space (no three in a line, nor four in a plane). Draw the fifteen line segments joining them in pairs, and then paint them all, some segments red, some blue. Prove that some triangle has all its sides the same colour. (William Lowell Putnam Mathematical Competition, 1953.)

2) Prove that at a gathering of any six people some three of them are either mutual acquaintances or complete strangers to one another. (The American Mathematical Monthly, June–July 1958.)

The definition of a Ramsey number can be generalized to $t$-colourings of $k$-graphs. Stated more generally, the Ramsey number $R_k(p_1,\dots,p_t)$ is the smallest $r$ such that for any $t$-colouring of the $k$-faces of $Y$, with colours $c_1,\dots,c_t$, there is either a $c_1$-$k_{p_1}$, $\dots$, $c_t$-$k_{p_t}$. Thus, with respect to $2$-colourings, a Ramsey number $R_k(p,q)$ is the smallest $r$ such that no matter how the $k$-faces of $k_r$ are coloured red or blue, there is either a $k_p$ subgraph of $k_r$ with all its $k$-faces red, or a $k_q$ subgraph of $k_r$ with all its $k$-faces blue.

Very few Ramsey numbers are known. The known Ramsey numbers are [a7]:

$$R(3,3)=6,R(3,4)=9,R(3,5)=14,$$

$$R(3,6)=18,R(3,7)=23,R(3,8)=28,R(3,9)=36,R(4,4)=18,R(4,5)=25.$$

The only Ramsey number for hypergraphs that has been computed is $R_3(4,4)=13$ [a4].

F.P. Ramsey's combinatorial contribution, which is now known as Ramsey's theorem, was originally needed in [a8], a paper that focused on mathematical logic. In the mid 1930s, P. Erdös rediscovered Ramsey's theorem [a5] and in the mid 1950s research in Ramsey theory started to take hold. By the 1970s, Ramsey theory was firmly established [a6].

References on Ramsey theory are [a2] and [a6].

References

[a1] D.J. Albers, "A nice genius" Math Horizons , November (1996) pp. 18–23
[a2] R.L. Graham, B.L. Rothschild, J.H. Spencer, "Ramsey theory" , Wiley (1990)
[a3] R.L. Graham, J.H. Spencer, "Ramsey theory" Scientific Amer. , July (1990) pp. 112–117
[a4] B.D. McKay, S.P. Radziszowski, "The first classical Ramsey number for hypergraphs is computed" , Proc. 2nd ACM–SIAM Symp. on Discrete Algebra (San Francisco, 1991) , SIAM (1991) pp. 304–308
[a5] J. Spencer, "Paul Erdös: The art of counting" , MIT (1973)
[a6] J. Spencer, "Ramsey theory and Ramsey theoreticians" J. Graph Th. , 7 (1983) pp. 15–23
[a7] D.B. West, "Introduction to graph theory" , Prentice-Hall (1996)
[a8] J.A. Winn, "Asymptotic bounds for classical Ramsey numbers" , Polygonal (1988)
How to Cite This Entry:
Ramsey number. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ramsey_number&oldid=33529
This article was adapted from an original article by J.A. Winn (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article