The Party Problem (Ramsey's Theorem)
From Math Images
m 
m 

(15 intermediate revisions not shown.)  
Line 3:  Line 3:  
Image=PartyProbB.gif  Image=PartyProbB.gif  
ImageIntro=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?  ImageIntro=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?  
  ImageDescElem=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  +  ImageDescElem=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 you want to answer: 
  ''How many people do you need to invite to make sure that at least 3 people will be mutual  +  ''How many people do you need to invite to make sure that at least 3 people will be mutual acquaintances, or at least 3 people will be mutual strangers? Because you have limited food, you want to find the lowest number of people you can invite while still satisfying these conditions.'' 
Line 18:  Line 18:  
{{{!}}  {{{!}}  
{{!}} align="center" {{!}} [[Image:Dinner2a.pngleft]] ''Fig. 1a''  {{!}} align="center" {{!}} [[Image:Dinner2a.pngleft]] ''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  +  {{!}} 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 acquaintances 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 acquaintances or strangers. 
{{!}} align="center" {{!}} [[Image:Dinner2b.png]] ''Fig. 1b''  {{!}} align="center" {{!}} [[Image:Dinner2b.png]] ''Fig. 1b''  
{{!}}}  {{!}}}  
Line 27:  Line 27:  
{{{!}}  {{{!}}  
{{!}} align="center" {{!}} [[Image:Dinner3a.pngleft]] ''Fig. 2a''  {{!}} align="center" {{!}} [[Image:Dinner3a.pngleft]] ''Fig. 2a''  
  {{!}} When you invite a third person, Cam, you can 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  +  {{!}} When you invite a third person, Cam, you can 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 acquaintances 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  +  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 acquaintances or strangers. 
  This is a good illustration of a <balloon title="In proving a claim, if you can find a single example that refutes that claim, the claim is incorrect.">counterexample</balloon> 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  +  This is a good illustration of a <balloon title="In proving a claim, if you can find a single example that refutes that claim, the claim is incorrect.">counterexample</balloon> 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 counterexamples to show that inviting 4 or 5 people is still not enough. 
{{!}} align="center" {{!}} [[Image:Dinner3b.png]] ''Fig. 2b''  {{!}} align="center" {{!}} [[Image:Dinner3b.png]] ''Fig. 2b''  
{{!}}}  {{!}}}  
Line 38:  Line 38:  
{{{!}}  {{{!}}  
{{!}} align="center" {{!}} [[Image:Dinner4.pngleft]] ''Fig. 3''  {{!}} align="center" {{!}} [[Image:Dinner4.pngleft]] ''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  +  {{!}} 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 acquaintances 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.  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.  
Line 47:  Line 47:  
===A More Complicated Case===  ===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  +  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 acquaintances 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: 
{{{!}}  {{{!}}  
{{!}} [[Image:Pos1.png]]  {{!}} [[Image:Pos1.png]]  
Line 58:  Line 58:  
{{!}}  {{!}}  
{{!}}  {{!}}  
  {{!}} colspan=4 {{!}} 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?  +  {{!}} colspan=4 {{!}} 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? {{HideThis1=answer2= 
  {{  +  
[[Image:Pos2.png]] Nope. This configuration still contains red, monochromatic triangles.  [[Image:Pos2.png]] Nope. This configuration still contains red, monochromatic triangles.  
}}  }}  
{{!}}}  {{!}}}  
+  
+  
{{{!}}  {{{!}}  
{{!}} [[Image:Six1.pngleft]]  {{!}} [[Image:Six1.pngleft]]  
Line 85:  Line 86:  
{{!}}  {{!}}  
{{!}} [[Image:VertexAni2a.gifleft]]  {{!}} [[Image:VertexAni2a.gifleft]]  
  {{!}} 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  +  {{!}} 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. It is no longer guaranteed that triangle BCD is monochromatic. 
{{!}}  {{!}}  
{{!}} colspan=2 {{!}} <br />  {{!}} colspan=2 {{!}} <br />  
Line 112:  Line 113:  
{{!}}}  {{!}}}  
  Finally, we've arrived at an answer to [[#Basic Descriptionthe party problem]]: ''To guarantee that at least 3 people will be mutual  +  Finally, we've arrived at an answer to [[#Basic Descriptionthe party problem]]: ''To guarantee that at least 3 people will be mutual acquaintances or mutual strangers, you must invite a minimum of 6 people to the party.'' 
  ImageDesc=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  +  ImageDesc=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 the Ramsey number when you want at least 3 people to be either mutual acquaintances or mutual strangers. In other words, ''R''(3,3) = 6. 
{{{!}}  {{{!}}  
{{!}} rowspan=2 {{!}} [[image:Proof1.pngleftthumbA complete graph with 6 vertices (''v'' = 6). Monochromatic subgraphs with 3 vertices will always exist in this graph.]]  {{!}} rowspan=2 {{!}} [[image:Proof1.pngleftthumbA complete 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  +  {{!}} ''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, complete subgraph with 3 vertices or a red, monochromatic, complete subgraph with 3 vertices exists. The constraint on the number of vertices ''v'' is denoted as follows: 
:<math>v \ge R(3,3)</math>.  :<math>v \ge R(3,3)</math>.  
  Since R(3,3) = 6, we can be specific and say that ''v''  +  Since R(3,3) = 6, we can be specific and say that ''v'' ≥ 6. 
  {{!}} rowspan=2 {{!}} [[image:Proof2.pngthumbA complete graph with 7 vertices (''v'' = 7). Since 7  +  {{!}} rowspan=2 {{!}} [[image:Proof2.pngthumbA complete 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, ''c''<sub>1</sub> and ''c''<sub>2</sub>, 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 ''c''<sub>1</sub>colored monochromatic, complete subgraph with at least ''m'' vertices or a ''c''<sub>2</sub>colored monochromatic, complete subgraph with at least ''n'' vertices:  {{!}} This can be taken even further and applied to any complete graph. Say you pick 2 colors, ''c''<sub>1</sub> and ''c''<sub>2</sub>, 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 ''c''<sub>1</sub>colored monochromatic, complete subgraph with at least ''m'' vertices or a ''c''<sub>2</sub>colored monochromatic, complete subgraph with at least ''n'' vertices:  
Line 128:  Line 129:  
:<math>v \ge R(m,n)</math>.  :<math>v \ge R(m,n)</math>.  
  As we will see later on, there is a Ramsey number for all complete  +  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. 
{{!}}  {{!}}  
{{!}}[[image:Proof4.pngleftthumbSubgraph ''H'' of graph ''K''<sub>6</sub>]]  {{!}}[[image:Proof4.pngleftthumbSubgraph ''H'' of graph ''K''<sub>6</sub>]]  
Line 145:  Line 146:  
First, let's look at the case for painting with 2 colors. We previously demonstrated that ''R''(3,3) exists. We will now prove that any ''R''(''m'',''n'') always exists.  First, let's look at the case for painting with 2 colors. We previously demonstrated that ''R''(3,3) exists. We will now prove that any ''R''(''m'',''n'') always exists.  
  
  '''Lemma for Painting a Graph with 2 Colors:''' An integer ''R''(''m,n'') exists such that any painting of ''K''<sub>''R''(''m,n'')</sub> in 2 colors ''c''<sub>1</sub> and ''c''<sub>2</sub> contains either a ''K''<sub>''m''</sub> with all its edges in ''c''<sub>1</sub> or a ''K''<sub>''n''</sub> with all its edges in ''c''<sub>2</sub>.  +  '''Lemma for Painting a Graph with 2 Colors:''' An integer ''R''(''m,n'') exists such that any painting of ''K''<sub>''R''(''m,n'')</sub> in 2 colors ''c''<sub>1</sub> and ''c''<sub>2</sub> contains either a ''K''<sub>''m''</sub> with all its edges in ''c''<sub>1</sub> or a ''K''<sub>''n''</sub> with all its edges in ''c''<sub>2</sub>.<ref name=ProofSource>Wallis, W. D. A Beginner's Guide to Graph Theory. Boston: Birkhäuser, 2000.</ref> 
  '''Proof:''' We need to find the base case  +  {{SwitchPreviewShowMessage=1  Proof of Lemma that will help us prove Ramsey's TheoremHideMessage=Click to hidePreviewText= FullText= 
+  
+  You might have noticed a new term, ''K''<sub>''R''(''m,n'')</sub>, in the lemma statement. This is simply notation for a complete graph ''K''<sub>''v''</sub> that is large enough so that it has ''v'' = ''R''(''m,n'') vertices. Since ''K''<sub>''R''(''m,n'')</sub> has a number of vertices equal to the Ramsey number ''R''(''m,n''), it is guaranteed to have a complete subgraph with ''m'' vertices painted in ''c''<sub>1</sub> or ''n'' vertices painted in ''c''<sub>2</sub>.  
+  
+  So for example, as we saw before, ''R''(3,3) ≥ 6. That means that <math>K_{R(m,n)} = K_{R(3,3)} = K_6</math>. (Or ''K''<sub>7</sub>. Or any ''K''<sub>''v''</sub> where ''v'' ≥ 6, really.)  
+  
+  Now, we have to prove that this ''R''(''m,n'') exists for every ''m'' and ''n'', not just ''m'' = ''n'' = 3.  
+  
+  
+  '''Proof:''' We need to find the base case so that we can perform [[induction]] on it. Remember the [[#Trivial Casefirst, trivial case]] that we covered in the basic description? All we need to do this start from this case, because it is the most basic.  
{{{!}}  {{{!}}  
Line 156:  Line 165:  
{{!}}}  {{!}}}  
  ''R''(2,2) is our base case  +  ''R''(2,2) is our base case, where ''m'' = ''n'' = 2. We will perform induction on ''m'' + ''n'' = 4. 
+  
+  As we just demonstrated, the Lemma holds for the base case, when ''m'' + ''n'' = 4.  
+  Assume that the Lemma is true when ''m'' + ''n'' < ''Q''. Now take two positive integers ''M'' and ''N'' that add up to ''Q''. If ''M'' + ''N'' = ''Q'', then ''M'' + ''N''  1 < ''Q''. Therefore, both ''R''(''M''  1, ''N'') and ''R''(''M'', ''N''  1) exist.  
+  
+  Say we have a graph ''K''<sub>v</sub> painted in ''c''<sub>1</sub> and ''c''<sub>2</sub> colors, where ''v'' ≥ ''R''(''M''  1, ''N'') + ''R''(''M'', ''N''  1). To visualize this, think of a simple example: ''K''<sub>6</sub>. Since it has 6 vertices, let's "split it up" into two graphs with 3 vertices each so that we can model ''v'' ≥ ''R''(''M''  1, ''N'') + ''R''(''M'', ''N''  1) as ''v'' ≥ 3 + 3:  
+  
+  
+  [[Image:Proof6.png175px]] [[Image:Rarrow.png75px]] [[Image:Proof7.png175px]]  
+  
+  
+  There is a give and take between the two colors; if you have less than 3 edges of blue, you will have more than 3 edges of red, and vice versa. This means that you will ''always'' have at least 3 edges of blue or 3 edges of red.  
+  
+  To generalize this, if you select any vertex ''x'', it is guaranteed that ''x'' will either lie on ''R''(''M''  1, ''N'') edges of ''c''<sub>1</sub> or ''R''(''M'', ''N''  1) edges of ''c''<sub>2</sub>, because we required that ''v'' ≥ ''R''(''M''  1, ''N'') + ''R''(''M'', ''N''  1). In the former case, the vertices that are connected to ''x'' by edges colored in ''c''<sub>1</sub> form a subgraph ''K''<sub>''R''(''M''  1, ''N'')</sub>. Now let's look at this subgraph in isolation and repaint it in colors ''c''<sub>1</sub> and ''c''<sub>2</sub>. Because we are assuming that the Ramsey number ''R''(''M''  1, ''N'') exists, the subgraph contains either:  
+  
+  
+   a ''K''<sub>''M''  1</sub> with edges colored in ''c''<sub>1</sub> that, together with the additional vertex ''x'', form a ''K''<sub>''M''</sub>, or  
+  
+   a ''K''<sub>''N''</sub> whose edges are all colored in ''c''<sub>2</sub>.  
+  
  +  Either way, we have demonstrated that ''K''<sub>''R''(''M''  1, ''N'')</sub> contains a monochromatic subgraph in either ''c''<sub>1</sub> or ''c''<sub>2</sub>. Since ''K''<sub>''v''</sub> contains ''K''<sub>''R''(''M''  1, ''N'')</sub> as a subgraph, we can extend our result and see that ''K''<sub>''v''</sub> also contains a monochromatic subgraph. By induction, we have proved that ''R''(''M'',''N'') exists.  
  +  
  +  
  +  
}}By proving the lemma, we have shown that monochromatic, complete subgraphs always exist in a 2painting of ''K''<sub>''v''</sub>. In the following proof, we will generalize our results to show that monochromatic subgraphs of any shape exist in any ''k''painting of ''K''<sub>''v''</sub>. In other words, a Ramsey Number exists for every complete graph, regardless of the number of colors in which the graph is painted.  }}By proving the lemma, we have shown that monochromatic, complete subgraphs always exist in a 2painting of ''K''<sub>''v''</sub>. In the following proof, we will generalize our results to show that monochromatic subgraphs of any shape exist in any ''k''painting of ''K''<sub>''v''</sub>. In other words, a Ramsey Number exists for every complete graph, regardless of the number of colors in which the graph is painted.  
+  '''Ramsey's Theorem:''' ''G''<sub>1</sub>, ''G''<sub>2</sub>, …, ''G''<sub>''k''</sub>, are any ''k'' graphs. There exists an integer ''R''(''G''<sub>1</sub>, ''G''<sub>2</sub>, …, ''G''<sub>''k''</sub>) such that, when ''v'' ≥ ''R''(''G''<sub>1</sub>, ''G''<sub>2</sub>, …, ''G''<sub>''k''</sub>), a ''k''painting of ''K''<sub>''v''</sub> must contain a subgraph that is isomorphic to ''G''<sub>''i''</sub> and monochromatic in color ''i'', for some ''i'' where 1 ≤ ''i'' ≤ ''k''.<ref name=ProofSource>Wallis, W. D. A Beginner's Guide to Graph Theory. Boston: Birkhäuser, 2000.</ref>  
{{SwitchPreviewShowMessage=2  Proof of Ramsey's TheoremHideMessage=Click to hidePreviewText= FullText=  {{SwitchPreviewShowMessage=2  Proof of Ramsey's TheoremHideMessage=Click to hidePreviewText= FullText=  
  '  +  
+  Let's break this theorem down into an identical but simpler statement. Say you have an arbitrary number of graphs (''G''<sub>1</sub>, ''G''<sub>2</sub>, …, ''G''<sub>''k''</sub> ). If you have a complete graph (''K''<sub>''v''</sub> ) that meets certain specifications, and you paint it with ''k'' colors, you are guaranteed to have monochromatic subgraphs within ''K''<sub>''v''</sub> that are identical to the arbitrary graphs you started with. The specifications for the complete graph are that it must have a number of vertices greater than or equal to the Ramsey number (''R''(''G''<sub>1</sub>, ''G''<sub>2</sub>, …, ''G''<sub>''k''</sub>) ). The theorem states that such a Ramsey number always exists, no matter what arbitrary graphs and colors you pick.  
+  
+  
:This builds upon the lemma we just proved, which had limited results:  :This builds upon the lemma we just proved, which had limited results:  
::'''Point 1:''' We showed that a Ramsey number ''R''(''G''<sub>1</sub>, ''G''<sub>2</sub>) always exists. We only proved this for when the ''G''<sub>1</sub> and ''G''<sub>2</sub> are complete graphs.  ::'''Point 1:''' We showed that a Ramsey number ''R''(''G''<sub>1</sub>, ''G''<sub>2</sub>) always exists. We only proved this for when the ''G''<sub>1</sub> and ''G''<sub>2</sub> are complete graphs.  
Line 175:  Line 204:  
A word on notation before we start:  A word on notation before we start:  
  * The notation ''G''<sub>''k''</sub> does not necessarily mean that the graph ''G'' has ''k'' vertices. It can be any graph. ''G''<sub>''k''</sub>  +  :* The number of vertices in ''G''<sub>''i''</sub> is denoted as ''v''(''G''<sub>''i''</sub>). 
  +  :* The notation ''G''<sub>''k''</sub> does not necessarily mean that the graph ''G'' has ''k'' vertices. It can be any graph. Instead, we use ''v''(''G''<sub>''k''</sub>) to indicate the size of the monochromatic subgraph we are looking for, just as ''R''(3,3) meant that we were looking for a monochromatic, complete subgraph with 3 vertices.  
  * If all the graphs are complete graphs, i.e. ''G''<sub>''1''</sub> = ''K''<sub>''p''<sub>1</sub></sub>, ''G''<sub>''2''</sub> = ''K''<sub>''p''<sub>2</sub></sub>, ..., ''G''<sub>''k''</sub> = ''K''<sub>''p''<sub>''k''</sub></sub> , then ''R''(''K''<sub>''p''<sub>1</sub></sub>, ''K''<sub>''p''<sub>2</sub></sub>, ..., ''K''<sub>''p''<sub>''k''</sub></sub>) is rewritten as ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''k  +  :* If all the graphs are complete graphs, i.e. ''G''<sub>''1''</sub> = ''K''<sub>''p''<sub>1</sub></sub>, ''G''<sub>''2''</sub> = ''K''<sub>''p''<sub>2</sub></sub>, ..., ''G''<sub>''k''</sub> = ''K''<sub>''p''<sub>''k''</sub></sub> , then ''R''(''K''<sub>''p''<sub>1</sub></sub>, ''K''<sub>''p''<sub>2</sub></sub>, ..., ''K''<sub>''p''<sub>''k''</sub></sub>) is rewritten as ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''k''</sub>). 
  +  
Line 185:  Line 213:  
''Expanding Point 1''  ''Expanding Point 1''  
  ''K''<sub>''v''(''G''<sub>''i''</sub>)</sub> is the complete graph that has the same  +  ''K''<sub>''v''(''G''<sub>''i''</sub>)</sub> is the complete graph that has the same number of vertices as ''G''<sub>''i''</sub>. Proving the theorem for ''K''<sub>''v''(''G''<sub>''i''</sub>)</sub> implies the proof for ''G''<sub>''i''</sub>. To see why, say that ''v'' is large enough that a ''k''painted ''K''<sub>''v''</sub> contains a monochromatic ''K''<sub>''v''(''G''<sub>''i''</sub>)</sub> in color ''c''<sub>''i''</sub> : 
{{{!}}  {{{!}}  
Line 201:  Line 229:  
{{!}}}  {{!}}}  
  The number of edges in ''K''<sub>''v''(''G''<sub>''i''</sub>)</sub> is greater or equal to the number of edges in ''G''<sub>''i''</sub>  +  The number of edges in ''K''<sub>''v''(''G''<sub>''i''</sub>)</sub> is greater or equal to the number of edges in ''G''<sub>''i''</sub> : 
{{{!}}  {{{!}}  
Line 222:  Line 250:  
''Expanding Point 2''  ''Expanding Point 2''  
  In order to prove that ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''k''</sub>) always exists, we will perform an induction on ''k''.  +  In order to prove that ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''k''</sub>) always exists, we will perform an induction on ''k''. 
  +  
  +  We previously saw the proof for the basic case, ''k'' = 2, in the Lemma. Now assume that for ''k'' < ''Q'', ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''k''</sub>) exists. Then if the integers ''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''</sub> are given, ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''  1</sub>) exists.  
  +  
  +  Let's take the graph ''K''<sub>''v''</sub>, where ''v'' ≥ ''R'' ( ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''  1</sub>), ''p''<sub>''Q''</sub> ). We know that the Ramsey number ''R'' ( ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''  1</sub>), ''p''<sub>''Q''</sub> ) exists, due to the lemma we proved before, and we already assumed that ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''  1</sub>) exists in the previous step. Remember that ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''  1</sub>) is the minimum number of vertices a complete graph (let's call it ''K''<sub>''P''</sub>) must have to contain the monochromatic subgraphs ''K''<sub>''p''<sub>1</sub></sub>, ''K''<sub>''p''<sub>2</sub></sub>, ..., ''K''<sub>''p''<sub>''Q''  1</sub></sub>. This means that ''R'' ( ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''  1</sub>), ''p''<sub>''Q''</sub> ) is the minimum number of vertices a complete graph must have to contain either a monochromatic ''K''<sub>''P''</sub> or a monochromatic ''K''<sub>''Q''</sub>.  
+  
+  Now take this ''K''<sub>''v''</sub> and paint it in any ''k'' colors. Here's the induction step: let's say that ''k'' = ''Q''.  
+  
+  For all edges painted in a color other than ''c''<sub>''k''</sub>, temporarily assign a new color ''c''<sub>''m''</sub>. This creates a 2painting, which we already know how to analyze! The repainted graph must contain either a ''K''<sub>''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''  1</sub>)</sub> monochromatic subgraph in color ''c''<sub>''m''</sub> or a ''K''<sub>''p''<sub>''Q''</sub></sub> monochromatic subgraph in color ''c''<sub>''Q''</sub>.  
+  
+  Take the former subgraph, ''K''<sub>''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''Q''  1</sub>)</sub>, and look at it in the original painting (before its edges were recolored to ''c''<sub>''m''</sub>). It has edges in colors ''c''<sub>1</sub>, ''c''<sub>2</sub>, ..., ''c''<sub>''Q''  1</sub> only. Therefore, by induction, it contains a monochromatic ''K''<sub>''p''<sub>''i''</sub></sub> painted in color ''c''<sub>''i''</sub> for some ''i''.  
+  
+  This shows that a Ramsey number ''R''(''p''<sub>1</sub>, ''p''<sub>2</sub>, …, ''p''<sub>''k''</sub>) always exists. When a ''k''painting of ''K''<sub>''v''</sub> has a number of vertices greater or equal to this Ramsey number, it must contain a monochromatic ''K''<sub>''p''<sub>''i''</sub></sub> subgraph in color ''i'', for some ''i'' where 1 ≤ ''i'' ≤ ''k''.  
}}  }}  
===Ramsey Numbers===  ===Ramsey Numbers===  
Line 242:  Line 278:  
===Impossibility of Disorder===  ===Impossibility of Disorder===  
  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  +  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 acquaintances or acquaintances. 
Take any infinite graph you'd like. If you color it with an arbitrary, finite number of colors, there will always exist monochromatic subgraphs. So no matter how you color the graph, there will always be pockets of order.  Take any infinite graph you'd like. If you color it with an arbitrary, finite number of colors, there will always exist monochromatic subgraphs. So no matter how you color the graph, there will always be pockets of order.  
Line 249:  Line 285:  
More generally: Regardless of the size of a system, if it's partitioned arbitrarily into subsystems, at least one subsystem will have a property that is shared by its constituents (monochromaticism, for example).  More generally: Regardless of the size of a system, if it's partitioned arbitrarily into subsystems, at least one subsystem will have a property that is shared by its constituents (monochromaticism, for example).  
  References=  +  References=<references /> 
  +  Ryser, Hervert John. The Carus Mathematical Monographs: Combinatorial Mathematics. Vol. Fourteen. Rahway: Quinn & Boden Company, Inc., 1963.  
Caldwell, Chris. "Graph Theory Glossary." Graph Theory Glossary. 19 June 2012 <http://primes.utm.edu/cgibin/caldwell/tutor/graph/glossary.html>.  Caldwell, Chris. "Graph Theory Glossary." Graph Theory Glossary. 19 June 2012 <http://primes.utm.edu/cgibin/caldwell/tutor/graph/glossary.html>. 
Current revision
The Party Problem 

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?
Contents 
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 you want to answer:How many people do you need to invite to make sure that at least 3 people will be mutual acquaintances, or at least 3 people will be mutual strangers? Because you have limited food, you want to find the lowest 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
Nontrivial Cases
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 acquaintances 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:
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. 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. 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. 
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 edges, 4 blue and 1 red edge, and 3 blue and 2 red edges. What about the other configurations? The remaining configurations are (0 blue, 5 red), (1 blue, 4 red), and (2 blue, 3 red). We can obtain the diagrams for these configurations by simply flipping the colors in the three proven configurations. For example, when the blue is replaced with red and viceversa, the diagram for (5 blue, 0 red) becomes the diagram for (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 of 6 people 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 acquaintances 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 the Ramsey number when you want at least 3 people to be either mutual acquaintances or mutual strangers. In other words, R(3,3) = 6.
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, complete subgraph with 3 vertices or a red, monochromatic, complete subgraph with 3 vertices exists. The constraint on the number of vertices v is denoted as follows:
Since R(3,3) = 6, we can be specific and say that v ≥ 6.  
This can be taken even further and applied to any complete graph. Say you pick 2 colors, c_{1} and c_{2}, 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 c_{1}colored monochromatic, complete subgraph with at least m vertices or a c_{2}colored monochromatic, complete subgraph with at least n vertices:
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.  
To put it in more formal terms, take a complete graph K with v vertices that has its edges painted in k colors. We call this a kpainting of K_{v}. A subgraph H of K is monochromatic if all its edges are painted with the same color. Therefore, our previous results can be expanded as follows:

Ramsey's Theorem
Until now, we have only considered painting graphs with 2 colors. What if we paint a graph with more than 2 colors? Can we still guarantee that monochromatic, complete subgraphs will exist in a 3painting of a graph? In a 4painting? The short answer is yes. Ramsey's Theorem, which generalizes the notion of Ramsey numbers, states that if you take a sufficiently large graph and paint it in any k colors, there must always exist monochromatic, complete subgraphs.
Graphical Proof
First, let's look at the case for painting with 2 colors. We previously demonstrated that R(3,3) exists. We will now prove that any R(m,n) always exists.
Lemma for Painting a Graph with 2 Colors: An integer R(m,n) exists such that any painting of K_{R(m,n)} in 2 colors c_{1} and c_{2} contains either a K_{m} with all its edges in c_{1} or a K_{n} with all its edges in c_{2}.^{[1]}
You might have noticed a new term, K_{R(m,n)}, in the lemma statement. This is simply notation for a complete graph K_{v} that is large enough so that it has v = R(m,n) vertices. Since K_{R(m,n)} has a number of vertices equal to the Ramsey number R(m,n), it is guaranteed to have a complete subgraph with m vertices painted in c_{1} or n vertices painted in c_{2}.
So for example, as we saw before, R(3,3) ≥ 6. That means that . (Or K_{7}. Or any K_{v} where v ≥ 6, really.)
Now, we have to prove that this R(m,n) exists for every m and n, not just m = n = 3.
Proof: We need to find the base case so that we can perform induction on it. Remember the first, trivial case that we covered in the basic description? All we need to do this start from this case, because it is the most basic.
In K_{2} (Fig. 5), there are 2 possible configurations. The two vertices are connected by either a c_{1}colored edge or a c_{2}colored edge. Notice that there will always be either a monochromatic c_{1}colored subgraph with 2 vertices, or a monochromatic c_{2}colored subgraph with 2 vertices. Therefore, the Ramsey number for the base case exists, and is R(2,2) = 2. 
R(2,2) is our base case, where m = n = 2. We will perform induction on m + n = 4.
As we just demonstrated, the Lemma holds for the base case, when m + n = 4. Assume that the Lemma is true when m + n < Q. Now take two positive integers M and N that add up to Q. If M + N = Q, then M + N  1 < Q. Therefore, both R(M  1, N) and R(M, N  1) exist.
Say we have a graph K_{v} painted in c_{1} and c_{2} colors, where v ≥ R(M  1, N) + R(M, N  1). To visualize this, think of a simple example: K_{6}. Since it has 6 vertices, let's "split it up" into two graphs with 3 vertices each so that we can model v ≥ R(M  1, N) + R(M, N  1) as v ≥ 3 + 3:
There is a give and take between the two colors; if you have less than 3 edges of blue, you will have more than 3 edges of red, and vice versa. This means that you will always have at least 3 edges of blue or 3 edges of red.
To generalize this, if you select any vertex x, it is guaranteed that x will either lie on R(M  1, N) edges of c_{1} or R(M, N  1) edges of c_{2}, because we required that v ≥ R(M  1, N) + R(M, N  1). In the former case, the vertices that are connected to x by edges colored in c_{1} form a subgraph K_{R(M  1, N)}. Now let's look at this subgraph in isolation and repaint it in colors c_{1} and c_{2}. Because we are assuming that the Ramsey number R(M  1, N) exists, the subgraph contains either:
 a K_{M  1} with edges colored in c_{1} that, together with the additional vertex x, form a K_{M}, or
 a K_{N} whose edges are all colored in c_{2}.
Either way, we have demonstrated that K_{R(M  1, N)} contains a monochromatic subgraph in either c_{1} or c_{2}. Since K_{v} contains K_{R(M  1, N)} as a subgraph, we can extend our result and see that K_{v} also contains a monochromatic subgraph. By induction, we have proved that R(M,N) exists.
By proving the lemma, we have shown that monochromatic, complete subgraphs always exist in a 2painting of K_{v}. In the following proof, we will generalize our results to show that monochromatic subgraphs of any shape exist in any kpainting of K_{v}. In other words, a Ramsey Number exists for every complete graph, regardless of the number of colors in which the graph is painted.
Ramsey's Theorem: G_{1}, G_{2}, …, G_{k}, are any k graphs. There exists an integer R(G_{1}, G_{2}, …, G_{k}) such that, when v ≥ R(G_{1}, G_{2}, …, G_{k}), a kpainting of K_{v} must contain a subgraph that is isomorphic to G_{i} and monochromatic in color i, for some i where 1 ≤ i ≤ k.^{[1]}
Let's break this theorem down into an identical but simpler statement. Say you have an arbitrary number of graphs (G_{1}, G_{2}, …, G_{k} ). If you have a complete graph (K_{v} ) that meets certain specifications, and you paint it with k colors, you are guaranteed to have monochromatic subgraphs within K_{v} that are identical to the arbitrary graphs you started with. The specifications for the complete graph are that it must have a number of vertices greater than or equal to the Ramsey number (R(G_{1}, G_{2}, …, G_{k}) ). The theorem states that such a Ramsey number always exists, no matter what arbitrary graphs and colors you pick.
 This builds upon the lemma we just proved, which had limited results:
 Point 1: We showed that a Ramsey number R(G_{1}, G_{2}) always exists. We only proved this for when the G_{1} and G_{2} are complete graphs.
 Point 2: We tested for only 2 colors, c_{i}, for some i where i = 1 or 2.
 As you saw in the theorem's statement, we will now expand on both of these points. We will see that the graphs G_{k} do not have to be complete, and that we can color a sufficiently large K_{v} with more than 2 colors and still find monochromatic subgraphs.
A word on notation before we start:
 The number of vertices in G_{i} is denoted as v(G_{i}).
 The notation G_{k} does not necessarily mean that the graph G has k vertices. It can be any graph. Instead, we use v(G_{k}) to indicate the size of the monochromatic subgraph we are looking for, just as R(3,3) meant that we were looking for a monochromatic, complete subgraph with 3 vertices.
 If all the graphs are complete graphs, i.e. G_{1} = K_{p1}, G_{2} = K_{p2}, ..., G_{k} = K_{pk} , then R(K_{p1}, K_{p2}, ..., K_{pk}) is rewritten as R(p_{1}, p_{2}, ..., p_{k}).
Proof:
Expanding Point 1
K_{v(Gi)} is the complete graph that has the same number of vertices as G_{i}. Proving the theorem for K_{v(Gi)} implies the proof for G_{i}. To see why, say that v is large enough that a kpainted K_{v} contains a monochromatic K_{v(Gi)} in color c_{i} :
3painted K_{7}....  ...contains blue monochromatic K_{v(Gi)}.  K_{v(Gi)} (isomorphic to K_{5}) 
The number of edges in K_{v(Gi)} is greater or equal to the number of edges in G_{i} :
K_{v(Gi)}...  ...contains G_{i} 
It necessarily follows that if K_{v} contains a monochromatic K_{v(Gi)} in color c_{i}, it will also contain a monochromatic G_{i} in the same color. In other words:
This is why it is sufficient to prove this theorem for the case in which all G_{i} are complete graphs.
Expanding Point 2
In order to prove that R(p_{1}, p_{2}, ..., p_{k}) always exists, we will perform an induction on k.
We previously saw the proof for the basic case, k = 2, in the Lemma. Now assume that for k < Q, R(p_{1}, p_{2}, ..., p_{k}) exists. Then if the integers p_{1}, p_{2}, ..., p_{Q} are given, R(p_{1}, p_{2}, ..., p_{Q  1}) exists.
Let's take the graph K_{v}, where v ≥ R ( R(p_{1}, p_{2}, ..., p_{Q  1}), p_{Q} ). We know that the Ramsey number R ( R(p_{1}, p_{2}, ..., p_{Q  1}), p_{Q} ) exists, due to the lemma we proved before, and we already assumed that R(p_{1}, p_{2}, ..., p_{Q  1}) exists in the previous step. Remember that R(p_{1}, p_{2}, ..., p_{Q  1}) is the minimum number of vertices a complete graph (let's call it K_{P}) must have to contain the monochromatic subgraphs K_{p1}, K_{p2}, ..., K_{pQ  1}. This means that R ( R(p_{1}, p_{2}, ..., p_{Q  1}), p_{Q} ) is the minimum number of vertices a complete graph must have to contain either a monochromatic K_{P} or a monochromatic K_{Q}.
Now take this K_{v} and paint it in any k colors. Here's the induction step: let's say that k = Q.
For all edges painted in a color other than c_{k}, temporarily assign a new color c_{m}. This creates a 2painting, which we already know how to analyze! The repainted graph must contain either a K_{R(p1, p2, ..., pQ  1)} monochromatic subgraph in color c_{m} or a K_{pQ} monochromatic subgraph in color c_{Q}.
Take the former subgraph, K_{R(p1, p2, ..., pQ  1)}, and look at it in the original painting (before its edges were recolored to c_{m}). It has edges in colors c_{1}, c_{2}, ..., c_{Q  1} only. Therefore, by induction, it contains a monochromatic K_{pi} painted in color c_{i} for some i.
This shows that a Ramsey number R(p_{1}, p_{2}, …, p_{k}) always exists. When a kpainting of K_{v} has a number of vertices greater or equal to this Ramsey number, it must contain a monochromatic K_{pi} subgraph in color i, for some i where 1 ≤ i ≤ k.
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
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 acquaintances or acquaintances.
Take any infinite graph you'd like. If you color it with an arbitrary, finite number of colors, there will always exist monochromatic subgraphs. So no matter how you color the graph, there will always be pockets of order.
There will always be an island of order in random, infinite chaos. Sounds quite poetic, right?
More generally: Regardless of the size of a system, if it's partitioned arbitrarily into subsystems, at least one subsystem will have a property that is shared by its constituents (monochromaticism, for example).
Teaching Materials
 There are currently no teaching materials for this page. Add teaching materials.
References
 ↑ ^{1.0} ^{1.1} Wallis, W. D. A Beginner's Guide to Graph Theory. Boston: Birkhäuser, 2000.
Ryser, Hervert John. The Carus Mathematical Monographs: Combinatorial Mathematics. Vol. Fourteen. Rahway: Quinn & Boden Company, Inc., 1963.
Caldwell, Chris. "Graph Theory Glossary." Graph Theory Glossary. 19 June 2012 <http://primes.utm.edu/cgibin/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." MathWorldA Wolfram Web Resource. 19 June 2012 <http://mathworld.wolfram.com/RamseyNumber.html>.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.