Ramsey's Realm

NOTE: This post is also available on my wordpress blog linked immediately below. My equations are not playing nice with google sites, so please use the wordpress version.

Ramsey’s RealmIntroduction Below, you will find descriptions of five games that you can play by yourself. Each mainly follows the rules laid out in Game 1 but with variations introduced in the subsequent g…

Intro

In the pages that follow, you will find descriptions of five games that you can play by yourself. Each mainly follows the rules laid out in Game 1 but with variations introduced in the subsequent games. You’ll find that the variations grow progressively more challenging. In Games 1 and 2, I intend to provide a gentle introduction to both graph theory and Ramsey theory. At that point, you should feel free to skim through the other games and then read the final section on Ramsey numbers. Game 3 should provide a nice challenge if you wish. However, Game 4 is so difficult that the solution to Game 4, along with thorough proof and exposition, is the content of the 1965 paper by J. G. Kalbfleisch titled Construction of Special Edge-Chromatic Graphs and appears in volume 8, issue 5, of the Canadian Mathematics Bulletin. Finally, Game 5 should not be attempted.

Alright, maybe you’re wondering,

“What is the point of Game 5 if it’s too difficult to solve? And Game 4 if it takes a mathematician to solve it?”

Well, I want to share a very mathematical experience: encountering a deceptively simple question whose answer has eluded everyone that has attempted it.

But not everyone knows to ask the question and attempt a solution, and that’s exactly the point.

Frank Ramsey is the philosopher, economist, and mathematician for whom the game gets its name. In 1928, Frank Ramsey presented his paper On a Problem of Formal Logic to the London Mathematical Society at the age of 25. In 1930, the paper was accepted, and Frank Ramsey died. Contained within this paper was a lemma[1] that would, more than twenty years later, spawn a mathematical theory. While the paper succeeded in making progress on one leading problems of mathematical logic at the time[2], it wasn’t until Frank Harary, a professor of mathematics at the University of Michigan, visited Ramsey’s widow Lettice Ramsey[3], twenty years after Frank Ramsey’s death. Interested in combinatorics, Harary was drawn to learn more about this lemma in Ramsey’s work. Fortunately, Lettice had kept her husband’s notes and graciously shared these with Harary when he came to visit.

What Harary gained from these notes was a connection to the newly forming branch of mathematics known as graph theory, which Harary would later help to popularize with his book Graph Theory in 1969. In 1953, after returning from his visit to Lettice, Harary was asked to submit a problem to the 1953 Putnam Exam. The problem he submitted was the following:

The complete graph on 6 points and 15 edges has each edge colored red or blue. Show that we can find 3 points such that the 3 edges connecting them are the same color.

Since then, mathematicians encountering Ramsey-type problems like this have been left dumbfounded by how quickly the problems turn unmanageable. But don’t be too discouraged. Not all Ramsey-type problems are so difficult and many applications remain undiscovered. So, in the spirt of this problem, and in memory of Frank and Lettice Ramsey, I present the game: Ramsey’s Realm.

[1] A lemma is a “little theorem”, i.e., not a primary result of the paper. Often, a mathematical result is labeled a lemma when it is used to prove something grander.

[2] In German, it is called the Entscheidungsproblem. The problem of finding a regular procedure to determine the truth or falsity of any given logical formula. The following question is a rough analog, “can a computer be programmed to determine if any mathematical statement is true or false?” In the same year as Ramsey’s paper, Gödel would publish his famous Incompleteness Theorem which would tangentially contribute to this discussion in a disturbing way.

[3] After Frank’s death, Lettice took a course in photography so that she could support their two daughters. Partnering with photographer Helen Musprat, they started their own Cambridge based photography studio in 1932. She found enormous success in this career and eventually retired in 1978.

Game 1

You are the ruler of a realm in an alternate history of medieval Europe and Asia. Your realm consists of five kingdoms in the empire of Scandinavia: Denmark, Sweden, Norway, Lappland, and Finland. Because your realm is so large, it is too much to manage the daily minutia of the county-level, duchy-level, or even kingdom-level administration. Instead, you appoint vassals to manage each kingdom. These rulers pay taxes, contribute military levies, and ultimately report to you. In this way, you can control large portions on land and maintain your status as a powerful ruler. Unfortunately, your vassals do not always play nice with each other, and they may try to rise up against you.

Each pair of your vassals has a diplomatic relationship: Allies or Enemies. If too many of your vassals are all enemies with one another, then your diplomatic skills are not powerful enough to prevent all-out war between your vassals and your realm is ripped apart from within. On the other hand, if too many of your vassals are all allies with one another, then their collective power is stronger than your own, and they usurp your throne. If you can manage to find a goldilocks zone where neither of these things happen, then your realm is called stable.

Your goal is to manipulate the relationships between your vassals so that your realm is stable.

There are two ways in which you can lose control of your Realm:

If three of your vassals are all allied with one another (mutual allies)
If three of your vassals are all enemies with one another (mutual enemies).

Suggestion: You can diagram the relationships between your Vassals by drawing 5 dots on a blank page and then connecting each pair of dots with a line segment. The resulting diagram is called a graph or network. The dots represent vertices and the line segments, which connect pairs of vertices, are usually called edges or links. In this case, our graph has a special name because every pair of vertices is connected by an edge. If a graph has this property, it is called complete. In our case, we have five vertices, so we can say that our network is the complete graph on five vertices. This graph is denoted , and in general, complete graphs are denoted .

You can represent the type of relationship by designating two types of edges. You might use line type or color to visually distinguish the types. In the figures, let’s say blue/dashed edges represent alliances, while red/solid edges represent enemies. For example, you might try to choose the relationships seen in the figures below.

This figure depicts the graph model on top of a rough sketch of the realm. The position of the vertices is irrelevant, so the graph model depicted on the right is identical to the one above.

You can represent the type of relationship by designating two types of edges made distinct by line type or color. In the figures below, let’s say red/solid lines represent alliances, while blue/dashed lines represent enemies.

A red-blue (solid-dashed) edge coloring of which models the relationships in Ramsey’s Realm. The graph model depicted here is identical to the graph model on the left.

The edge-colored graph[1] seen in the examples serves as the “playing board” of the game. Since the example contains three vertices (Finland, Norway, and Sweden) such that all the edges between them are the same type (blue), we know that with the chosen relationships we have that Finland, Norway, and Sweden are mutual allies. This realm is not stable. The three ruling vassals’ will rise up against you and usurp your title.

While we represent the two types of edges with the colors red and blue with this naming convention, any two distinct colors could be used. One need not even use colors to distinguish the two groups. In the example, we used solid and dashed lines (along with the analogous colors) to do this. It is for simplicity and historical reasons that I use the term “red-blue coloring.” Don’t let this discourage you to imagine a game with three different types of relationship.

The complete graphs, K_n, play an important role in this puzzle. We seek an edge coloring of in which neither red nor blue subgraph contains a . The graph is commonly referred to as a triangle. A monochromatic triangle is a triangle whose edges are all the same type.

Can you find a red-blue coloring of K_5 that avoids a monochromatic triangle in each of its red and blue subgraphs?

Such a coloring would represent a stable realm and hence a solution to Game 1.

Solution and Analysis of Game 1

The diagram above depicts how you can choose the relationships between your vassals to avoid losing your realm.

Is your solution the same as this one? In what ways is it the same or different?

With respect to the graph theoretic structure, or topology, it does not matter which vassal each vertex is labeled with, so long as each appears in the diagram as a distinct vertex. It also does not matter whether you choose red (solid) edges to represent allies or enemies. In any of these cases, the underlying connections are the same.

In the context of the game, this one solution is representative of all solutions.

You can check to see if your solution is the same as this one by first ignoring the names on the vertices and then rearranging the position of your vertices (while maintaining the edges incident with each vertex) to obtain the red-blue coloring of depicted here.

Is there an easier way to check?

This is, up to isomorphism (relabeling or repositioning the vertices) the only solution to the game. We can think of each of the red subgraph and blue subgraph of the complete graph as graphs on their own. In this case, each of the subgraphs has the same structure, that of a cycle of length 5. We say they are each a five-cycle, denoted C_5.

This gif shows that the unique solution to Game 1 has the red subgraph and blue subgraph each being a five-cycle, denoted C_5.

Game 2

Suppose you are so successful that you acquire another vassal (say Russia) so that you now have six Kingdom tier vassals beneath you.

Following the same rules as in Game 1, choose each of the, now, 15 relationships between your six vassals and try to avoid three vassals that are mutual allies and three vassals that are mutual enemies. Remember, if either of those two substructures occur, then you lose your realm and it’s game over.

Does there exist a solution?

If so, give a coloring of K_6 that avoids monochromatic triangle.

If not, why not?

Solution and Analysis of Game 2

There is no solution. The following gif and argument help to demonstrate this fact.

The gif above depicts the steps in the argument below.

To read the proof below, understand why each fact is true and why the next fact follows.

1. Fact: Each vertex is adjacent to five other vertices.

2. Fact: Given any vertex, say Denmark, each of its five incident edges must be colored one of two colors.

3. Follows: It follows that there must be at least three edges incident with Denmark that are the same color[1]. Without loss of generality, we may assume they are red. (If they are blue, then swap the words red and blue for the remainder of the proof.)

4. Fact: The three other vertices (not Denmark) that are incident with these three red edges form a complete graph on three vertices. All possible colorings of this subgraph can be split into two cases:

a. At least one of these three edges is red.

b. Each of the three edges is colored blue.

5. Follows: In each either a red triangle or a blue triangle must be formed. So, there are no possible ways to avoid a monochromatic triangle, i.e., no solution exists.

a. If one of the three edges is red, then that edge together with the two red edges incident with Denmark form a red triangle.

b. If none of the edges is red, then they are all blue. In this case, a blue triangle is formed.

[1] This is an application of the pigeonhole principle. You can learn more about this combinatorial principle in the activity [Basic Counting Principles].

The above argument demonstrates the following theorem:

In any red-blue coloring of the edges of , there must exist a monochromatic triangle.

The solution to Game 1 demonstrates a related theorem:

There exists a red-blue coloring of the edges of which avoids a monochromatic triangle.

Combining these results, we can state an extremal result concerning red-blue colorings of complete graphs that avoid monochromatic triangles:

The smallest complete graph for which every red-blue coloring of its edges is guaranteed to admit a monochromatic triangle is the complete graph on six vertices, .

Taking three vassals, all whose relationships are the same, as our definition of an instable realm, the result answers the question:

What is the least number of vassals that must be contained in Ramsey’s Realm to guarantee instability?

The answer, then, is 6. There are two steps to a proof of an extremal result like this. We must

1. Present the coloring of that demonstrates it is possible to color the edges of while avoiding a monochromatic triangle.

2. Present an argument for why every red-blue coloring of contains either a red triangle or a blue triangle.

We have now built up enough language to be comfortable with the next Ramsey’s Realm puzzle.

Game 3

Suppose you are an experienced leader, clever diplomat, and a powerful military commander. Your prowess and acumen allow you to maintain order of your realm in more situations than the other two games. Let’s say that you can now manage three mutual allies and three mutual enemies, but you are still not powerful enough to manage either four mutual allies or four mutual enemies.

That is, you now lose control of your realm only when there are either four mutual allies or four mutual enemies.

As a powerful realm, you now have 10 vassals.

There are 45 relationships to choose in your attempt to avoid four vertices whose edges are all the same color.

Several solutions exist, can you find one?

A drawing of with uncolored edges is given below for your use.

A solution (red-blue coloring of with no monochromatic ) is given on the page that follows.

Several solutions exist, can you find one?

Solution and Analysis of Game 3

Depicted below is a red-blue coloring of K_10 which avoids a monochromatic K_4.

Do you have a different solution?

With this many vertices and edges, the task becomes more difficult. It is even difficult to verify a solution. If we were to exhaustively check that there are no monochromatic s in the drawing, then we would have to check every set of four vertices. So, we would have to scan subsets of vertices and verify that there is at least one edge of each color present. It helps if there is some explanation of the coloring given above:

1. Separate the 10 vertices into two groups of 5. Group A will be the first five vertices including the vertex at the 9 o’clock position and proceeding clockwise. Group B are the remaining five vertices.

2. This naturally separates the edges into the following groups:

a. Those edges within group A, call these edge group A,

b. Those edges within group B, call these edge group B,

c. Those edges between vertices in group A and vertices in group B.

3. Color the edges in each of group A and group B using as many red edges as possible. The most red edges possible is 8, leaving two disjoint blue edges in each group.

4. Color the edges between group A and group B using mostly blue edges. We insert red edges carefully according to avoid a blue between a blue edge in group A and a blue edge in group B.

5. Since there are no blue triangles in either group A or group B, the only way for a blue to exist would be two vertices in group A, connected by a blue edge, and two vertices in group B, also connected by an edge. With the right selection of edges in step 4, you can achieve this goal while avoiding a red as well.

Game 4 (Extremely Challenging)

What is the greatest number of vassals you can maintain while avoiding four mutual allies and four mutual enemies?

Once you think you have discovered the magic number , there should be two parts to your justification: (1) a solution on vertices and (2) an argument for why there is no solution on vertices.

Game 4 Solution and Analysis

The steps below formalize the coloring process depicted above:

1. Separate the edges of into 8 groups based on the chord length of the edge. That is, the number of vertices the edge “skips over” as it connects to its other incident vertex. (See above.)

2. Color the edges with chord lengths or red and color the other edges (chord lengths 3,5,6,7) blue.

3. Check that with this coloring there can be no red and no blue . (Proof left to the reader.)

a. Hint: First try to categorize the possibility of a red triangle or a blue triangle.

So, there exists a red-blue coloring of which avoids a monochromatic . It turns out this is the largest complete graph that has such a coloring. Our final argument then, needs to be that every red-blue coloring of contains a monochromatic .

1. Pick any vertex, call it . It has neighbors in . So, at least of these must be the same color. We may assume that is adjacent to other vertices with red edges, call this group B.

2. Now, it can be shown that every red-blue coloring of results in either a red or a blue .

3. In either case, we have a red or a blue . Indeed,

a. If the edges of group B contain a red , then together with the red edges from vertex , we have a red .

b. If the edges of group B contain a blue , then we have a blue .

This gif shows that the red and blue subgraphs are isomorphic to each other. This same was true of the red-blue coloring of K_5 that avoids a monochromatic triangle.

Game 5 (Do Not Attempt)

What is the greatest number of vassals you can maintain while avoiding five mutual allies and five mutual enemies?

Hint: It’s between 43 and 49, and these are the best-known bounds to humanity. There is no solution or analysis given because no one knows the solution.

Ramsey Numbers

The smallest positive integer, n, for which every red-blue coloring of K_n contains a red K_s or a blue is known as the Ramsey number .

We used games 1 and 2 to understand the proof that since we were concerned with colors of that avoided monochromatic triangles (red and blue ).

In game 4, we used the fact that every red-blue coloring of K_n contains either a red K_s or a blue K_t. So, the Ramsey number used here (without proof) is R(3,4) . Using this fact, we were able to show R(4,4)=18.

In game 5, I warned you that no one yet knows the answer. The best-known information on is that . The prolific mathematician and graph theorist Paul Erdös had this to say about the difficulty of the problem:

Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.

The following table is a complete list of these types of Ramsey numbers when s and t are at least 3.

There is a terrible amount that is not known about Ramsey numbers. You have witnessed the difficulty of these problems firsthand. The sheer number of computations needed to simply verify that we have a coloring that works gives you some clue as to why even computers have not solved the problem.

You may be wondering “why?” That is, do Ramsey numbers help us solve any real-world problem? For this, Noga Alon and Michael Krivelevich told the story of a Hungarian sociologist in their Princeton Companion to Mathematics:

In the course of an examination of friendship between children some fifty years ago, the Hungarian sociologist Sandor Szalai observed that among any group of about twenty children he checked he could always find four children any two of whom were friends, or else four children no two of whom were friends. Despite the temptation to try to draw sociological conclusions, Szalai realized that this might well be a mathematical phenomenon rather than sociological one. Indeed, a brief discussion with the mathematicians Erdös, Turán, and Sós convinced him this was the case.

Like the setting of the games in this activity. Ramsey theory gives us information about unavoidable structure in the relationships between people. Depending on the types of relationship and the people under consideration, Ramsey number results can be interpreted in that context to give us information about social structures.

Social structures are not the only place Ramsey numbers show up. There are applications to radio frequency allocation, computer science, network engineering as well as other mathematical fields like geometry, number theory, and algebra. In any case, Ramsey numbers tell us about unavoidable substructures.

To summarize the flavor of Ramsey theory, the late mathematician Theodore Motzkin remarked:

Complete disorder is impossible. In any sufficiently large structure there exists a prescribed substructure.

So, perhaps the theme of Ramsey’s Realm is a philosophical one. When we seek to avoid a prescribed substructure (like 3 mutual allies or 3 mutual enemies), we know that at some point we will fail. It is impossible to avoid the existence of substructure within a large structure.

One can let your imagination run wild with this philosophical interpretation. For example, one may consider life as a prescribed substructure existing within the larger structure of organic chemistry. The formation of stars, galaxies, and planets could be taken as the inevitable creation of order within the physical universe. While I have not seen any of these ideas formalized mathematically, it is fun to dream. But it is not just for fun. Dreaming can often steer us toward provocative questions in any scientific field. Indeed, every invention, work of art, and scientific breakthrough begins in this way – with a dream. So, take any topic that you are interested in, and dream about unavoidable order within a chaotic system. You just might find Ramsey’s realm hidden in the shadows.

Discussion Prompts

Respond to the following prompts according to the guidelines for in-person or online discussion.

How realistic do you find the Ramsey Realm set-up? Can you think of any modifications that make it more realistic but still allow Ramsey numbers to be used in some way?

Can you think of another application of Ramsey numbers? How is similar/different to the applications you’ve seen in this activity? If you can, try and apply Ramsey numbers to your own domain specific knowledge.

Can you think of any variations, generalizations, or modifications to the classical Ramsey numbers? (Do we have to avoid complete graphs? Do we have to color complete graphs? Do we have to use only two colors?)

Prove that R(3,4)=9. That is, find a red-blue coloring of K_8 that avoids a red triangle and a blue K_4 and explain why every red-blue coloring of K_9 contains either a red triangle or a blue K_4 . Present your proof as a discussion board post if you’re comfortable.

Page updated

Google Sites

Report abuse