Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in Ramsey theory typically ask a question of the form: *‘how many elements of some structure must there be to guarantee that a particular property will hold?’*

Suppose, for example, that we know that *n* pigeons have been housed in *m* pigeonholes. How big must *n* be before we can be sure that at least *one pigeonhole* houses at least *two pigeons*? The answer is the *pigeonhole principle*: if *n > m*, then at least one pigeonhole will have at least two pigeons in it.

The photograph on the right shows a number of pigeons in holes. Here there are *n* = 10 pigeons in *m* = 9 holes, so by the pigeonhole principle, at least one hole has more than one pigeon: in this case, both of the top corner holes contain two pigeons. The principle says nothing about which holes are empty: for *n* = 10 pigeons in *m* = 9 holes, it simply says that at least one hole here will be over-full; in this case, the bottom-left hole is empty. Ramsey’s theory generalizes this principle as explained below.

A typical result in Ramsey theory starts with some mathematical structure that is then cut into pieces. *How big must the original structure be in order to ensure that at least one of the pieces has a given interesting property?*

For example, consider a complete graph of order *n*; that is, there are *n* vertices and each vertex is connected to every other vertex by an edge. A complete graph of order 3 is called a triangle. Now colour every edge red or blue. How large must *n* be in order to ensure that there is either a blue triangle or a red triangle? It turns out that the answer is 6.

Another way to express this result is as follows: at any party with at least* six people*, there are *three people* who are all either *mutual acquaintances* (each one knows the other two) or *mutual strangers* (each one does not know either of the other two).

A comic result of the pigeonhole principle is the “proof” that in the city of New York (or any other city with a population over a million) at least two people have the same number of hairs on their head. The reasoning is as follows: an average human being has about 150.000 hairs on the scalp; it is reasonable to assume that no human being has more than 1.000.000 hairs on the scalp. Over a million people live in New York. The population of *n* people (exceeding a million) has to be arranged in *m* (1.000.000 or less) collections; one collection is possible for each number of hairs on the scalp. Because *n* population > *m* different numbers of hairs on the scalp, there are at least two people in one of these collections – at least two people with the same number of hairs.

**See other:** Admin’s Choice Posts