The Party Problem (Ramsey's Theorem)

(Difference between revisions)
 Revision as of 15:48, 27 June 2012 (edit)m ← Previous diff Revision as of 15:50, 27 June 2012 (edit) (undo)m Next diff → Line 64: Line 64: {{{!}} {{{!}} {{!}} [[Image:Six1.png|left]] {{!}} [[Image:Six1.png|left]] - {{!}} rowspan=2 {{!}} Just because there are many configurations that suggest 6 is the answer, however, doesn't prove that it is. We have to apply a more general proof to show that, no matter what, in any set of 6 people, 3 people will be mutual friends or mutual strangers. To do this, we will try to find a configuration that does ''not'' produce any monochromatic triangles, and then realize it is impossible to do so. First, let's reconfigure the vertices so that the problem is easier to model — we will only draw the edges that originate at vertex A (Fig. 5a). To begin with, let's assume that all of these edges are blue. Later on, we'll see that it doesn't matter what color these edges are. + {{!}} rowspan=2 {{!}} Just because there are many configurations that suggest 6 is the answer, however, doesn't prove that it is. We have to apply a more general proof to show that, no matter what, in any set of 6 people, 3 people will be mutual friends or mutual strangers. To do this, we will try to find a configuration that does ''not'' produce any monochromatic triangles, and then realize it is impossible to do so. First, let's reconfigure the vertices so that the problem is easier to model — we will only draw the edges that originate at vertex A (see left). To begin with, let's assume that all of these edges are blue. Later on, we'll see that it doesn't matter what color these edges are. - {{!}}- + - {{!}} align="center" {{!}} ''Fig. 5a'' + {{!}}- {{!}}- {{!}} colspan=2 {{!}}
{{!}} colspan=2 {{!}}
Line 72: Line 70: {{!}} [[Image:Six2a.png|left]] {{!}} [[Image:Six2a.png|left]] {{!}} rowspan=2 {{!}} Remember that we are trying to find a configuration that does not produce any monochromatic triangles. In Fig. 5b, look at the triangle that would be formed by vertices A, B, and C. Since edges AB and AC are blue, we would have to make BC red to prevent triangle ABC from becoming monochromatic. Likewise, in triangle ACD, since edges AC and AD are blue, edge CD must be red. {{!}} rowspan=2 {{!}} Remember that we are trying to find a configuration that does not produce any monochromatic triangles. In Fig. 5b, look at the triangle that would be formed by vertices A, B, and C. Since edges AB and AC are blue, we would have to make BC red to prevent triangle ABC from becoming monochromatic. Likewise, in triangle ACD, since edges AC and AD are blue, edge CD must be red. - {{!}}- - {{!}} align="center" {{!}} ''Fig. 5b'' {{!}}- {{!}}- {{!}} colspan=2 {{!}}
{{!}} colspan=2 {{!}}
{{!}}- {{!}}- {{!}} [[Image:Six3a.png|left]] {{!}} [[Image:Six3a.png|left]] - {{!}} rowspan=2 {{!}} Now, in Fig. 5c, look at the triangle that would be formed by vertices A, B, and D. Since edges AB and AD are blue, edge BD must be red to avoid a monochromatic triangle. Even though we avoided creating a blue monochromatic triangle, we are eventually forced to form a red monochromatic triangle that has the vertices B, C, and D. + {{!}} rowspan=2 {{!}} Now, look at the triangle that would be formed by vertices A, B, and D. Since edges AB and AD are blue, edge BD must be red to avoid a monochromatic triangle. Even though we avoided creating a blue monochromatic triangle, we are eventually forced to form a red monochromatic triangle that has the vertices B, C, and D. - {{!}}- + - {{!}} align="center" {{!}} ''Fig. 5c'' + {{!}}- {{!}}- {{!}} colspan=2 {{!}}
{{!}} colspan=2 {{!}}
{{!}}- {{!}}- {{!}} [[Image:VertexAni1a.gif|left]] {{!}} [[Image:VertexAni1a.gif|left]] - {{!}} rowspan=2 {{!}} This holds true even if we change our initial assumption that all the edges emanating from A are blue. If edge AE were red, edge AF were red, or both edges AE and AF were red, our end results would not change (Fig. 5d). This is because these are trivial changes to the configuration. We didn't use or consider edges AE and AF when we formed the monochromatic triangle BCD, so changing their colors has no effect on triangle BCD. + {{!}} rowspan=2 {{!}} This holds true even if we change our initial assumption that all the edges emanating from A are blue. If edge AE were red, edge AF were red, or both edges AE and AF were red, our end results would not change. This is because these are trivial changes to the configuration. We didn't use or consider edges AE and AF when we formed the monochromatic triangle BCD, so changing their colors has no effect on triangle BCD. - {{!}}- + - {{!}} align="center" {{!}} ''Fig. 5d'' + {{!}}- {{!}}- {{!}} colspan=2 {{!}}
{{!}} colspan=2 {{!}}
{{!}}- {{!}}- {{!}} [[Image:VertexAni2a.gif|left]] {{!}} [[Image:VertexAni2a.gif|left]] - {{!}} rowspan=2 {{!}} Now what about nontrivial changes to the configuration? Say we change edge AD from blue to red (Fig. 5e). If AD isn't blue, we can no longer put a constraint on edge CD—it can be either red ''or'' blue. Therefore it is no longer guaranteed that triangle BCD is monochromatic. + {{!}} rowspan=2 {{!}} Now what about nontrivial changes to the configuration? Say we change edge AD from blue to red. If AD isn't blue, we can no longer put a constraint on edge CD—it can be either red ''or'' blue. Therefore it is no longer guaranteed that triangle BCD is monochromatic. - {{!}}- + - {{!}} align="center" {{!}} ''Fig. 5e'' + {{!}}- {{!}}- {{!}} colspan=2 {{!}}
{{!}} colspan=2 {{!}}
{{!}}- {{!}}- {{!}} [[Image:Six5a.png|left]] {{!}} [[Image:Six5a.png|left]] - {{!}} rowspan=2 {{!}} Let's look at this new configuration again (Fig. 5f). Edges AC and AF are blue, so edge CF must be red to prevent triangle ACF from becoming a blue monochromatic triangle. Edges AB and AF are blue, so edge BF must be red to prevent triangle ABF from becoming blue and monochromatic. Sound familiar? We are, once again, forced to form a red monochromatic triangle (triangle BCF). + {{!}} rowspan=2 {{!}} Let's look at this new configuration again. Edges AC and AF are blue, so edge CF must be red to prevent triangle ACF from becoming a blue monochromatic triangle. Edges AB and AF are blue, so edge BF must be red to prevent triangle ABF from becoming blue and monochromatic. Sound familiar? We are, once again, forced to form a red monochromatic triangle (triangle BCF). - {{!}}- + - {{!}} align="center" {{!}} ''Fig. 5f'' + {{!}}- {{!}}- {{!}} colspan=2 {{!}}
{{!}} colspan=2 {{!}}
{{!}}- {{!}}- {{!}} [[Image:Six6.png|left]] {{!}} [[Image:Six6.png|left]] - {{!}} rowspan=2 {{!}} Even if we make a nontrivial change to the configuration and change edge AC from blue to red (Fig. 5g), we are still forced to form the red monochromatic triangle BEF. + {{!}} rowspan=2 {{!}} Even if we make a nontrivial change to the configuration and change edge AC from blue to red, we are still forced to form the red monochromatic triangle BEF. {{!}}- {{!}}- {{!}} align="center" {{!}} ''Fig. 5g'' {{!}} align="center" {{!}} ''Fig. 5g''

Revision as of 15:50, 27 June 2012

The Party Problem
Field: Graph Theory
Image Created By: Awjin Ahn
Website: Author's user page

The Party Problem

You're going to throw a party, but haven't yet decided whom to invite. How many people do you need to invite to guarantee that at least m people will all know each other, or at least n people will all not know each other?

Basic Description

Imagine that the next party you throw is, in secret, a mathematical experiment to find a solution to the party problem. Exhausted after planning, cooking, and setting up, you fall onto the couch and have some downtime to analyze the situation. Here is the question that we want to answer:

How many people do you need to invite to make sure that at least 3 people will be mutual friends, or at least 3 people will be mutual strangers? Because you have limited food, you want to find the fewest number of people you can invite while still satisfying these conditions.

Trivial Case

Note: From here on out,

• blue edges will connect two vertices to represent that the people are mutual acquaintances
• red, dashed edges will connect two vertices to represent that the people are mutual strangers

 Fig. 1a In the case of 2 people, Adam and Ben, they can either know each other or not. Therefore, there is only one edge between them, indicating that they are either friends or strangers (Fig. 1a and 1b). Furthermore, since there are only 2 people, we cannot fulfill the minimum requirement of at least 3 people that are mutual friends or strangers. Fig. 1b

Nontrivial Cases

 Fig. 2a When you invite a third person, Cam, you can finally form a set of 3 people. Let's say, for the sake of argument, that they all know each other (Fig. 2a), thereby satisfying the conditions of the party problem. Note that in Fig. 2a, the edges that connect the 3 vertices form a triangle with edges of the same color. This kind of triangle, called a monochromatic triangle, indicates that the 3 people represented by the vertices are either all mutual friends or mutual strangers. It appears that 3 people is the answer to the party problem; inviting 3 people allows you to form a set of 3 people that all know each other. However, you could also think of a case in which Adam and Ben know each other, but don't know Cam (Fig. 2b). If that is the case, you can't form a set of 3 people that are either friends or strangers. This is a good illustration of a counterexample to our claim that 3 people were enough to solve the party problem. We need to invite more than 3 people. In the next two cases, we will again use counterexample to show that inviting 4 or 5 people is still not enough. Fig. 2b

 Fig. 3 Your fourth guest is Dina. Let's use the same counterexample strategy we used for 3 people. Assume that 4 is a solution to the party problem. In order to find a counterexample to our assumption, we have to find a configuration such that there exist no red or blue monochromatic triangles. Such a configuration is shown in Fig. 3. The outer edges are colored blue, and the inner edges (the diagonals of the square) are colored red. There is no way that you could make a monochromatic triangle from the blue outer edges, or from the red inner edges. In other words, you can't form a set of 3 people that are all mutual friends or mutual strangers. We have found a counterexample, and therefore 4 is not an answer to the party problem. When you invite Elsa, the fifth guest, again assume that 5 people is an answer to the party problem. Let's use the same coloring strategy that we used for 4 people. As shown in Fig. 4, color the outer edges blue and the inner edges red. You still can't form a monochromatic triangle from either the blue outer edges or the red inner edges. Fig. 4 is a counterexample to our assumption, and therefore 5 people is not an answer. Fig. 4

A More Complicated Case

Until now, it has been relatively easy to come up with counterexamples to prove that 3, 4, or 5 people are not enough to guarantee that at least 3 people will be mutual friends or strangers. When you invite a sixth person, Fiona, it becomes a little more complicated. We can think of various cases in which 6 seems to be an answer. In the following cases, there is always a monochromatic triangle:

 To find a configuration that will not form a monochromatic triangle, try using the coloring strategy that we used for 4 and 5 people. In other words, color the outer edges blue and the inner edges red. Does this work? Nope. This configuration still contains red, monochromatic triangles.
 Just because there are many configurations that suggest 6 is the answer, however, doesn't prove that it is. We have to apply a more general proof to show that, no matter what, in any set of 6 people, 3 people will be mutual friends or mutual strangers. To do this, we will try to find a configuration that does not produce any monochromatic triangles, and then realize it is impossible to do so. First, let's reconfigure the vertices so that the problem is easier to model — we will only draw the edges that originate at vertex A (see left). To begin with, let's assume that all of these edges are blue. Later on, we'll see that it doesn't matter what color these edges are. Remember that we are trying to find a configuration that does not produce any monochromatic triangles. In Fig. 5b, look at the triangle that would be formed by vertices A, B, and C. Since edges AB and AC are blue, we would have to make BC red to prevent triangle ABC from becoming monochromatic. Likewise, in triangle ACD, since edges AC and AD are blue, edge CD must be red. Now, look at the triangle that would be formed by vertices A, B, and D. Since edges AB and AD are blue, edge BD must be red to avoid a monochromatic triangle. Even though we avoided creating a blue monochromatic triangle, we are eventually forced to form a red monochromatic triangle that has the vertices B, C, and D. This holds true even if we change our initial assumption that all the edges emanating from A are blue. If edge AE were red, edge AF were red, or both edges AE and AF were red, our end results would not change. This is because these are trivial changes to the configuration. We didn't use or consider edges AE and AF when we formed the monochromatic triangle BCD, so changing their colors has no effect on triangle BCD. Now what about nontrivial changes to the configuration? Say we change edge AD from blue to red. If AD isn't blue, we can no longer put a constraint on edge CD—it can be either red or blue. Therefore it is no longer guaranteed that triangle BCD is monochromatic. Let's look at this new configuration again. Edges AC and AF are blue, so edge CF must be red to prevent triangle ACF from becoming a blue monochromatic triangle. Edges AB and AF are blue, so edge BF must be red to prevent triangle ABF from becoming blue and monochromatic. Sound familiar? We are, once again, forced to form a red monochromatic triangle (triangle BCF). Even if we make a nontrivial change to the configuration and change edge AC from blue to red, we are still forced to form the red monochromatic triangle BEF. Fig. 5g

 Because we failed to find any case in which there exists no monochromatic triangle, we have proven that 6 vertices is a solution to the party problem for the following configurations: 5 blue and 0 red edgers (Fig. 5c) , 4 blue and 1 red edge (Fig. 5f), and 3 blue and 2 red edges (Fig. 5g). What about the other configurations? The remaining configurations are (2 blue, 3 red), (1 blue, 4 red), and (0 blue, 5 red). We can obtain the diagrams for these configurations by simply flipping the colors in the previous 3 diagrams. For example, when the blue is replaced with red and vice-versa, the diagram for (5 blue, 0 red) becomes the diagram for and (0 blue, 5 red). (5 blue, 0 red) & (0 blue, 5 red) (4 blue, 1 red) & (1 blue, 4 red) (3 blue, 2 red) & (2 blue, 3 red) Since we have demonstrated that any configuration will always contain a monochromatic triangle, our results can be generalized to all cases.

Finally, we've arrived at an answer to the party problem: To guarantee that at least 3 people will be mutual friends or mutual strangers, you must invite a minimum of 6 people to the party.

A More Mathematical Explanation

Note: understanding of this explanation requires: *Graph Theory

The answer we just found is called a Ramsey number. In the simplistic terms of the party proble [...]

The answer we just found is called a Ramsey number. In the simplistic terms of the party problem, a Ramsey number R(m,n) is the minimum number of people you must invite so that at least m people will be mutual friends or at least n people will be mutual strangers. In the previous case, we proved that 6 is a Ramsey number when you want at least 3 people to be either mutual friends or mutual strangers. In other words, R(3,3) = 6.

 A graph with 6 vertices (v = 6). Monochromatic subgraphs with 3 vertices will always exist in this graph. So how does the party problem connect to graph theory? The transition from parties to graphs is simple—in fact, we've been modeling the invited people as the vertices of a graph already. We figured out earlier that the graph must have at least 6 vertices to guarantee that either a blue monochromatic subgraph with 3 vertices or a red monochromatic subgraph with 3 vertices exists. The constraint on the number of vertices v is denoted as follows: $v \ge R(3,3)$. Since R(3,3) = 6, we can be specific and say that v ≥ 6. A graph with 7 vertices (v = 7). Since 7 ≥ R(3,3), monochromatic subgraphs with 3 vertices will always exist in this graph as well. This can be taken even further and applied to any complete graph. Say you pick 2 colors, c1 and c2, and paint a graph with those colors (we previously picked blue and red). The Ramsey number is the minimum number of vertices that that graph must have to ensure that there exists either a c1-colored monochromatic subgraph with at least m vertices or a c2-colored monochromatic subgraph with at least n vertices: $v \ge R(m,n)$. As we will see later on, there is a Ramsey number for all complete graphs—there exists an R(3,4), R(4,4), etc. Subgraph H of graph G6 To put it in more formal terms, take a complete graph G with v vertices that has its edges painted in k colors. We call this a k-painting of Gv. A subgraph H of G is monochromatic if all its edges are painted with the same color. Furthermore, a complete graph with v vertices is denoted as Kv. Therefore, our previous results can be expanded as follows: A 2-painting of K6 must contain monochromatic subgraphs that are isomorphic to K3. Monochromatic K3

Ramsey's Theorem

Ramsey's Theorem generalizes the notion of Ramsey numbers. It states that in any k-painting of a sufficiently large complete graph, there must always exist monochromatic complete subgraphs. In other words, for every complete graph, there exists a corresponding Ramsey number.

Graphical Proof

Lemma: An integer R(p,q) exists such that any painting of KR(p,q) in 2 colors c1 and c2 contains either a Kp with all its edges in c1 or a Kq with all its edges in c2.

Proof: We will perform induction on p + q = 1. Because the graph must be painted in either of 2 colors, p ≠ 0 and q ≠ 0.

1. The Lemma holds when p + q = 1. This is because p = q = 1, and R(1,1) = 1.
2. Assume that the Lemma is true when p + q < N. Now take two positive integers P and Q that add up to N. If P + Q = N, then P + Q - 1 < N. Therefore, both R(P - 1, Q) and R(P, Q - 1) exist.
3. Consider Kv painted in c1 and c2, where vR(P - 1,Q) + R(P,Q - 1).
If you select any vertex x, it is guaranteed that x will either lie on R(P - 1, Q) edges of c1 or R(P, Q - 1) edges of c2. In the former case, the vertices that are connected to x by edges colored in c1 form a subgraph KR(P - 1, Q). This subgraph either 1) contains a Kp - 1 whose edges are all colored in c1 and form a Kp with x, or 2) the graph contains a Kq whose edges are all colored in c2. Either way, we have demonstrated that KR(P - 1, Q), and by extension Kv, contain a monochromatic subgraph in either c1 or c2.
4. Therefore, by induction, we have proved that R(P, Q) exists.

By proving the Lemma, we have confirmed a case in which monochromatic subgraphs always exist in a 2-painting of Kv. In the following proof, we will generalize our results to show that monochromatic subgraphs exist in any k-painting of Kv. In other words, a Ramsey Number exists for every complete graph, regardless of the number of colors in which the graph is painted.

Theorem: G1, G2, …, Gk, are any k graphs. There exists an integer R(G1, G2, …, Gk) such that, when vR(G1, G2, …, Gk), a k-painting of Kv must contain a subgraph that is isomorphic to Gi and monochromatic in color i, where 1 ≤ ik.

A word on notation:

• R(G1, G2, ..., Gk) are Ramsey Numbers.
• If all the graphs are complete graphs, i.e. G1 = Kp1, G2 = Kp2, ..., Gk = Kpk , then R(Kp1, Kp2, ..., Kpk) is rewritten as R(p1, p2, ..., pk).
• The number of vertices in Gi is denoted as v(Gi).

Proof: It is sufficient to prove this theorem for the case in which all Gi are complete graphs. To see this, say that v is large enough that a k-painted Kv contains a monochromatic Kv(Gi) in color ci. Since the number of edges in Kv(Gi) is greater or equal to the number of edges in Gi, it necessarily follows that Kv also contains a monochromatic Gi in color ci. In other words:

$R(v(G_1), v(G_2), ..., v(G_k)) \ge R(G_1, G_2, ..., G_k)$

In order to prove that R(p1, p2, ..., pk) always exists, we will perform an induction on k.

1. We previously saw the proof for the basic case, k = 2, in the Lemma.
2. Assume that for k < K, R(p1, p2, ..., pk) exists. Then if the integers p1, p2, ..., pK are given, R(p1, p2, ..., pK - 1) exists.
3. Now suppose that vR(R(p1, p2, ..., pK-1), pK). Take any k-painting of Kv. For all edges painted in a color other than ck, assign a new color cl to form a 2-painting of Kv in cl and ck. The repainted graph must now contain either a KR(p1, p2, ..., pK-1) monochromatic in color cl or a KpK monochromatic in color cK.
4. Take the former subgraph, KR(p1, p2, ..., pK-1), and look at its corresponding subgraph in the original painting (before its edges were recolored to cl). It has edges in colors c1, c2, ..., cK - 1 only. Therefore, by induction, it contains a Kpi monochromatic in color ci for some i.

Ramsey Numbers

It is extremely difficult to compute Ramsey numbers for increasingly larger graphs. Many of the Ramsey numbers have been determined by using exhaustive computer algorithms that compute a range of numbers, given values for m and n.

Why It's Interesting

Impossibility of Disorder

The party problem is a simple example of Ramsey's Theorem, which states that total disorder in a graph is impossible. To extend the party metaphor, imagine that you invite more than 6 people. Regardless of how many people you invite, there will always be at least 3 people who are mutual friends or acquaintances.

More formally: Regardless of the size of a system, if it is partitioned arbitrarily into subsystems, at least one subsystem will have a particular property that is shared by its constituents (monochromaticism, for example). This ensures that total disorder is impossible.

References

Ryser, Hervert John. The Carus Mathematical Monographs: Combinatorial Mathematics. Vol. Fourteen. Rahway: Quinn & Boden Company, Inc., 1963.

Wallis, W. D. A Beginner's Guide to Graph Theory. Boston: Birkhäuser, 2000.

Caldwell, Chris. "Graph Theory Glossary." Graph Theory Glossary. 19 June 2012 <http://primes.utm.edu/cgi-bin/caldwell/tutor/graph/glossary.html>.

"Ramsey's theorem." Wikipedia. 18 June 2012. 19 June 2012 <http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Extensions_of_the_theorem>.

Weisstein, Eric W. "Ramsey Number." MathWorld--A Wolfram Web Resource. 19 June 2012 <http://mathworld.wolfram.com/RamseyNumber.html>.