Index:
A mathematical game - SIM
Example - 6 points game
Proof - 6 points game
Pigeonhole Principle
Ramsey's Theorem
Reference
- 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.
Please click the picture or example.ps
to download the postscript file
Proof - 6
points game
Click proof.ps
download this example in postscript file.
1. Use 6 points game as an example for the proof.
4. Look at the lower left 3 points of the graph, connect the first line in
blue color will form a blue triangle.
7. Mark the second line with the red color instead and try next line.
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.
Therefore, we can also say that:
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.
How about the case with many colors? here we will prove the other case with c
colors.
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.
5. Mark the first line with the red color instead and try next line.
6. Connect the second line will form another blue triangle.
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.
If and only if there is a pigeonhole with more than one pigeon, then there must be
an empty pigeonhole left.
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
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.
we already prove the case with c=1 and 2, so let c>2 for the following
statement:
R(n1,...,nc;c)≤R(n1,...,nc-2,R(nc-1,nc;2);c-1)
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: