Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum

Monthly Update sign up
Mailing List signup
Search
Follow The Annenberg Learner on LinkedIn Follow The Annenberg Learner on Facebook Follow Annenberg Learner on Twitter
MENU

Unit 2

Combinatorics Counts

2.6 Ramsey Theory

MORE PIGEONS THAN HOLES

• Dirichlet's box, better known as the pigeonhole principle, is a deceptively powerful concept that can be used to prove combinatorial results.

Of central importance in Ramsey Theory, and in combinatorics in general, is the "pigeonhole principle," also known as Dirichlet's box. This principle simply states that we cannot fit n+1 pigeons into n pigeonholes in such a way that only one pigeon is placed in each hole, with no pigeons left over.

The Pigeonhole Principle

The pigeonhole principle may seem to be too obvious and simple to be useful. It can, however, be used to demonstrate possibly surprising results. For example, in any big city, Los Angeles let's say, there must be at least two people with the same number of hairs on their heads. To see why this is a certainty, let's assume that a typical person has about 150,000 hairs on his head. Let's also assume that no one has more than a million head hairs.

There are significantly more than one million people in Los Angeles. If we consider each specific number of hairs on a head to be a pigeonhole and each person to be a pigeon, then we can assign the pigeons to the holes representing the number of hairs on their heads. To summarize, there are no more than a million pigeonholes, a million distinct possible numbers of hairs on a head, and more than a million people ("pigeons"). Consequently, there will be more than one person with a given number of hairs on their heads.

We'll see how this deceptively powerful concept plays out next in the field of Ramsey Theory.

back to top

THE PARTY PROBLEM

Phrased another way, the Party Problem reveals that in any group of six people, we are mathematically guaranteed to find either three mutual friends or three mutual strangers. This is not true in a group of five people, so why is six the magic number?

Let's say you attend a party and become engaged in a discussion with five other people. The six of you could be represented graphically by K6 , the complete graph on six nodes. In this discussion, the relationships between people will be represented by colored edges on the graph, with a blue edge indicating that the connected nodes are mutual friends and a red edge denoting mutual strangers.

k6

Notice that each vertex of the K6 graph has five connections. In the following analysis, we'll focus on vertex A.

A's Five Connections, Also Known as A's Neighbors

Each of A's five neighbors is either a friend or a stranger. Notice that, because there are five neighbors, at least three of them must be friends or at least three must be strangers. Let's focus on the case in which there are at least three blue edges.

Verticies B, C and D will be connected by either a red edge or a blue edge

Vertices B, C, and D will be connected by three edges, each of which will be either red or blue. Because we are attempting to disprove that at least one of the triangles formed has to have all edges of the same color, we can ignore the option in which the remaining edges would all be blue. We need to consider only the following cases for the colors of the edges connecting B, C, and D:

1. 2 blue, 1 red
2. 2 red, 1 blue
3. 3 red

If any of the edges connecting b, c and d are blue, a blue triangle is formed

Note that if any one of the edges connecting B, C, and D is blue, a blue triangle is formed, signifying three people who are all mutual friends. Conversely, a red triangle represents three mutual strangers (i.e., three people, none of whom knows either of the others).

Case 1: 2 Blue, 1 Red

Case 2: 2 Red, 1 Blue

Case 3: 3 Red

All three cases lead to the formation of either a blue triangle or a red triangle. Note that if edges AB, AC, and AD had been red instead of blue, a similar argument and similar demonstrations would have led to the same conclusion—it doesn't really matter which coloring situations we look at.

This proves that among the six party goers there will be at least a group of three friends or a group of three strangers. This Party Problem is a classic example of Ramsey Theory.

back to top

RAMSEY NUMBERS

Ramsey Theory is all about finding structure/organization in sets of data. The solution to the Party Problem is an example of this kind of structure, and the size of the party group, six, is known as a Ramsey number. Ramsey numbers tell you how large a group must be before you are guaranteed to see certain structures. For instance, the party problem is formally expressed as R(3,3) = 6. This means that six is the smallest number of people that guarantees that either three of them will be mutual friends or three will be mutual strangers. R(4,5) designates the smallest number of people that guarantees that either four of them are mutual friends or five are mutual strangers. It takes a group of twenty-five to guarantee this, so R(4,5) = 25.

The two examples of Ramsey numbers that we have discussed so far refer to situations in which there are only two types of relationship between people, friend or stranger. The application of Ramsey Theory is not limited to binary situations, however. For example, R(3,3,3) refers to a group in which three types of relationship are possible. These three relationship types might be friend, enemy, and neutral. In this case, R(3,3,3) represents the smallest number of people that guarantees that either three will be mutual friends, three will be mutual enemies, or three will be mutually neutral. In fact, it takes a group of seventeen people to ensure this, so R(3,3,3) = 17.

The ideas of Ramsey Theory apply to more than groups of people, however. For example, similar lines of reasoning can be used to show that if a certain number of dots are placed in a plane randomly, with no three dots collinear, a certain subset of the dots will form the vertices of a convex polygon. In fact, placing five dots randomly in a plane (no three dots collinear) ensures that at least four of them can be connected to make a quadrilateral. This partially explains why, when we see a star-filled sky, we see recognizable shapes that we call constellations.

Another interesting application of Ramsey Theory can be found in text analysis. Any sufficiently long string of letters will have unavoidable regularities, such as certain combinations or strings of letters that must appear. This can somewhat explain why people can find hidden messages in large bodies of text, such as the Bible.

Computing Ramsey numbers, as we saw when we analyzed the Party Problem, takes a fair amount of cleverness. To find the value of a Ramsey number, you have to show not only that the size of the collection is large enough to guarantee that the pattern of interest exists, but also that no smaller group provides the guarantee. The larger or more significant the pattern or structure, the more difficult it is to find the minimum group size that guarantees its existence. Finding an upper limit tends to be fairly easy; what is exceedingly difficult is showing that no smaller number suffices.

An example of a difficult Ramsey number is the value of R(5,5), the smallest number of people that guarantees that either five will be mutual friends or five will be mutual strangers. The value of R(5,5) is known to be somewhere between forty-three and forty-nine. After years of investigation, this is our best answer so far. To see why computing Ramsey numbers is so difficult, let's just say that we believe that R(5,5) is forty-nine exactly. This would mean that any collection of forty-nine people has either five mutual friends or five mutual strangers. To prove that forty-nine is actually the right number, we have to show that any group of forty-eight will not necessarily have the five strangers or five friends. A complete graph with forty-eight nodes has 1,128 edges—we can figure this out by computing C(48,2). Using two colors, one for edges between "friend" nodes and one for edges between "stranger" nodes, there are then 21128 (~ 10339) possible colorings of the 48-node complete graph. This is the largest combinatorial explosion we have seen yet! Each of these colorings has to be examined and determined not to contain the five mutual friends or five mutual strangers in order for forty-eight to be ruled out as a candidate value for R(5,5). The difficulty of computing Ramsey numbers was summed up quite nicely by the great Hungarian graph theorist, Paul Erdös when he said:

[…] imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5,5) or they will destroy our planet. In that case, […], we should marshal all our computers and our mathematicians and attempt to find the value. Suppose, instead, that they ask for R(6,6). In that case, […], we should attempt to destroy the aliens.

back to top

Next: 2.7 DNA Sequencing


HomeVideo CatalogAbout UsSearchContact Us

© Annenberg Foundation 2013. All rights reserved. Privacy Policy