Math 308 2003 Term Project

Topic: A mathematical game - SIM

Student: Derek Kao
Student #: 85537991
Date: Dec 18, 2003

A mathematical game - SIM
Example - 6 points game
Proof - 6 points game
Pigeonhole Principle
Ramsey's Theorem

A mathematical game - SIM

It is a game designed for two players, and each player draw a line by using one color between two points. The player who gets a triangle with his color first loses the game. The game can be played with any point which is lager or equal than six and the result never be a draw.

Example - 6 points game

Please click the picture or to download the postscript file
in order to see the full process of the example. 

Proof - 6 points game

Click download this example in postscript file.

1. Use 6 points game as an example for the proof.
2. Choose a point, then there are 5 separate lines connect to it.
3. Since we only have two players for this game (red and blue), so by applying the Pigeonhole Principle
---we know that there must be 3 line in the same color, here we assume those 3 lines are in blue color.

4. Look at the lower left 3 points of the graph, connect the first line in blue color will form a blue triangle.
5. Mark the first line with the red color instead and try next line.
6. Connect the second line will form another blue triangle.

7. Mark the second line with the red color instead and try next line.
8. Connect the third line will form another blue triangle.
9. Mark the third line with the red color instead but form a red triangle now.

Therefore, there must be at least one monochromatic triangle formed.

However, for 5 points game, it is possible to have no monochromatic triangle. We can simply draw:

Click the picture to download the postscript file 

Pigeonhole Principle

If there are X pigeons that live in X pigeonholes, then every pigeonhole should have one pigeon.
If and only if there is a pigeonhole with more than one pigeon, then there must be an empty pigeonhole left.

Therefore, we can also say that:
If there are X pigeons that live in Y pigeonholes and X is greater than Y, then there must be a hole with more than one pigeon.

Ramsey's theorem

Ramsey's theorem states that every positive integers m and n, there exists r=R(m,n) which are any complete graph's vertices. Those edges between every vertices are marked in blue and red color, and there must be a monochromatic complete subgraph on r vertices with blue color or on s vertices with the red color.

By applying the pigeonhole principle, we know R(m,1) = R(1,m)=m. Here, we can use the induction method for the proof. By finding a bound of R(m,n), so we know R(m,n) exists and R(m-1,n) and R(m,n-1) also exist by mathematical induction.

Now we have to prove the statement: R(m,n)≤R(m-1,n)+R(m,n-1)
First of all, assume that there are R(m-1,n)+R(m,n-1) vertices on a complete graph. Choose a vertex p from the complete graph and consider there are two complete subgraphs X and Y. If and only if (p,q) is in blue color, and q is a vertex in X. Otherwise q is a vertex in Y instead. At this point, using the pigeonhole principle again, we can say either |M|≥R(m-1,n) or |N|≥R(m,n-1). In the first case, if X has a red Kn, then we prove the statement, otherwise X has a blue Km-1, and we can know X a blue Km too by the definition. We can use the similar technique to prove the second case.
Therefore, we proved the case for 2 colors. 

How about the case with many colors? here we will prove the other case with c colors.
we already prove the case with c=1 and 2, so let c>2 for the following statement:

First, we can know the inequality on the right hand side of statement exists by the mathematical induction. Now consider a complete graph with many vertices and with c colors to draw. Second, assume that we accidentally mix up c and c-1 color are the same color, so the total colors will become c-1 now. Thus, by applying the induction method again, the graph will have a Kn1 monochromatically subgraph with color i (1≤i≤2) or a KR(nc-1,nc;2) colored in "mixed-up color". In the first case, we proved the statement. In the other case, we found out c and c-1 color are not the same anymore and from the definition of R(nc-1,nc;2), there must be either a monochromatic Knc-1 or a monochromatic Knc.
Therefore, we proved the case for c colors.

but there exist a special case which has c=2 and n1=n2=3

This is a table of all of the known Ramsey numbers of the form r=R(Km, Kn) and some of the known lower/upper bounds for others:

m n R(Km, Kn)   m n R(Km, Kn)
3 3 6   3 4 9
3 5 14   3 6 18
3 7 23   3 8 28
3 9 36   3 10 [40,43]
3 11 [46,51]   3 12 [51,60]
3 13 [60,69]   3 14 [66,78]
3 15 [73,89]   4 4 18
4 5 25   4 6 [35,41]
4 7 [49,62]   4 8 [53,85]
4 9 [69,116]   4 10 [80,151]
5 5 [43,49]   5 6 [58,87]
5 7 [80,143]   5 8 [95,216]
5 9 [114,371]   6 6 [102,165]