Ramsey number

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)