Ramsey and The Pigeonhole Principle


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?’

Illustration of The Pigeonhole Principle

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s