Dr. Sarah's Notes on Erdos

Erdos made very fundamental contributions to modern mathematics including the field of Ramsey theory. In fact, he was an inventor of this branch of combinatorics. This branch of mathematics has applications to scheduling problems. An example of the type of thinking in Ramsey theory follows:

You're one of six people at a dinner party. You look across the table at your five companions. You would undoubtedly find that the dinner party includes either a group of at least three people who all know one another or a group of at least three people who don't know one another. The reason for this certainty lies in a mathematical proof that any gathering of six people will always automatically include one or the other of these two groupings.
No such guarantee is possible when five or fewer people are present. Let a dashed line connecting 2 people mean that they have not met before and let a solid line connecting 2 people mean that they know each other already. Then, a group of three people who all know each other will be represented by a solid triangle connecting the three, while a group of three people who have never met before will be represented by a dashed triangle connecting the three. The following picture is an example of a five-person party in which we cannot find such a group of three people because we cannot find any completely dashed or solid triangles connecting the three people.
While there are other five-person parties in which I can find such a group of three people, I can not do so for every five-person party (such as the one given above).

Here is an example of a six-person party, where red represents people who have never met before while blue represents people who already know each other. Notice that in this six person party, Charles, Diana, and Edith are an example of a group of three people who have never met before since they connect to each other via a red triangle.

A game related to this idea is played with a partner. You and your opponent take turns coloring in the uncolored edges of a complete graph laid out as a hexagon, with each player using a different color. The first person to build a triangle with all three edges of the same color loses. Here is an example of plays in the game:

There will always be a winner/loser because no matter what 6 people party one is at, there will always be a triangle of the same color representing a group of three people who either all know each other or a group of three people who have never met before.

The Proof

To prove that any party of six must contain at least three acquaintances or at least three strangers, you could write down all the possible combinations, starting with a group in which everyone knows one another. However, there are 32,768 such possibilities and so this would take a very long time (The picture above with Alice, Barry, ... represents just one of the 32,768 possibilities).

Reducing the Number of People

Instead, we reduce the problem to looking at just 4 of the 6 people as follows. Given any 6 person party, we check to see who person 1 has met before. There are 5 people to check and so there must be 3 people that are connected to person 1 by the same type of line (dashed or solid). For example, in the following picture, if person 1 knows person 6 (solid line) then person 1 knows person 3, 5 and 6 (3 people). If instead, person 1 has never met person 6 (dashed line) then person 1 has never met person 2, 4 and 6 (3 people). No matter what group of people, there must be at least 3 who person 1 is connected to by the same type of line.

So now we reduce to looking at person 1 and the three people that are connected to them by the same type of line. We want to show that we can find some triangle between three of these 4 people that is the same type.

Case 1: person 1 knows 3 people

If we are in this case, then we proceed as follows by looking at the connections between the others.

If person 3 and 5 know each other then I have a solid triangle between person 1, 3 and 5.
If person 3 and 6 know each other then I have a solid triangle between person 1, 3 and 6.
If person 5 and 6 know each other then I have a solid triangle between person 1, 5 and 6.
Otherwise, if none of the above 3 cases is true, then person 3, 5 and 6 must have never met before. In this case, I have a dashed triangle between the three of them.

Notice that I have listed all of the possibilities and in everyone of them I can find a triangle of the same color.

Case 2: person 1 had never met 3 people

This is very similar to above - use similar reasoning to show that no matter what the possibilities, one can always find a triangle of the same color.

The Conclusion

Since we know that person 1 must either have known 3 people, or must have never met 3 of the people before, and that in either of these cases one can always find a triangle of the same color within the possibilities that arise, then we have proven that party problem.

The result represents a special case stemming from a branch of mathematics known as Ramsey theory. Instead of talking about six people, you could consider groups consisting of any number of people. Instead of specifying just two relationships (acquaintances and strangers), you could have any number of mutually exclusive relations. For example, you could consider people (or nations) who are allies, foes, and neutral parties--representing three mutually exclusive relationships--embroiled in a widespread conflict. In general, Ramsey theory concerns the existence of highly regular patterns in sufficiently large sets of randomly selected objects, whether they are gatherings of people, sequences of randomly generated numbers, randomly placed points in the plane, or even stars in the night sky.

Some parts are taken from Ivars Peterson's Party Games