论文部分内容阅读
Ⅰ.Introduction
Ramsey’s theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. And the Ramsey theorem is a branch of is a branch of mathematics that studies the unavoidable regularity in large structures （the definition above came from Gould， Martin. “Ramsey Theory.” Ramsey Theory， 2010）. Or in other words， complete disorder is impossible. A famous problem could be in any class of six or more people， there are at least three mutual friends or three mutual strangers if every pair of them are either friends or not friends . Which is provable by the Ramsey Theorem. And through the last century， Ramsey theorem developed significantly with more and more excellent Mathematician work input. Although the Ramsey theorem is keep developing， the Ramsey theorem’s abstract applications became more and more widely used during the past century.
Ⅱ.Preliminaries
Definition： A graph is a collection of vertices V and edges E， which are pairs of vertices.
Definition： A simple graph is a graph that each edge connect two vertices and no loops occurs.
Definition： A complete graph is a simple graph that each E has two vertices and we named it by the number of vertices kn.
Definition： A proper c-colouring graph emphasis that each edge has its own color and no adjacent edges has same coloring.
Definition： A clique of size n is a set of n vertices such that all pairs among them are edges. And a independent set means there are no edges between them.
Definition： The Ramsey number R（s，t） is the minimum number n such
that any graph on n vertices contains either an independent set of size s or a clique of size n（）.
Definition： In mathematics， the pigeonhole principle states that if n items are put into m containers， then at least one container must contain more than one item. Then if an infinite number of items are put into finite containers， then one of the containers must fit infinite items.
Ⅲ.Ramsey Theorem
1.party problem. Proposition：There are six people at a party. We assume that for every pair of them， they are either friends or not friends （i.e. strangers）. Prove that either there are three people all of whom are friends， or there are three people of whom no two are friends.
Proof ： As the graph shows， we have 6 people Julie， Alison， Edna， Barack， Camryn and David. We pick David as the person we are considering. Among the other 5 people，we suppose that David are friends with 3 people. Then we can divide into 2 situation. Situation 1： if two of David friends knows each other then they will be a group of 3 mutually friends. Situation 2： if David’s friends do not know each other， then this 3 people will be a group of 3 mutually strangers. If David do not know 3 people in the 6 people group， then there must be at least three that are strangers to David. Then we can divide into 2 situation. Situation 1： If any two of these are strangers， then together with Joe， they are a group of three mutually strangers. Situation 2： If none of them are strangers to each other， then they are a group of at least three mutual friends. So， through this proof above we can conclude that either there are three people all of whom are friends， or there are three people of whom no two are friends. As the graph shows below we use red line to represent strangers and use blue to represent friends.
And through this section we can proof that for any monochromatic K3 no matter how you want to 2-color Kn， n=6 will be sufficient.
2.Ramsey Theorem and Ramsey Number. From the last section we gained the information that n=6 will be sufficient for any monochromatic K3 no matter how you want to 2-color Kn. Then the question comes， what if we apply it to an monochromatic K6 graph， what’s the number of n will make the graph sufficient and for how many coloring it might be working？
Ramsey Theorem can be defined by following： For all c， m ≥2， there exists n
m such that every c-coloring of Kn has a monochromatic Km.
One of the division under Ramsey Theorem is Ramsey numbers. A Ramsey Number， R（m，n） = r， is the smallest size of a graph r such that every graph of that size has either a clique of size m or an independent set of size n. Like above we proof that R（3，3）=6 through the party example. And also R（a，b）=R（b，a）. R（2，b）=b still applies and the proof was showned in the previous.
Notation： Let a， b ≥ 2.Let R（a， b） denote the least number， if it exists， such
that every 2-coloring of KR（a，b） has a RED Ka or a BLUE Kb. We abbreviate
R（a， a） by R（a）.
Facts： 1. For all a，b， R（a，b） = R（b，a）.
2. For b 2， R（2， b） = b： First， we show that R（2， b） ≤ b. Given any 2-
coloring of Kb ， we want a RED K2 or a BLUE Kb. Note that a RED K2 is just a RED edge. Hence EITHER there exists one RED edge （so you get a RED K2） OR all the edges are BLUE （so you get a BLUE Kb）. Now we prove that R（2，b） = b. If b = 2， this is obvious. If b
Ramsey’s theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. And the Ramsey theorem is a branch of is a branch of mathematics that studies the unavoidable regularity in large structures （the definition above came from Gould， Martin. “Ramsey Theory.” Ramsey Theory， 2010）. Or in other words， complete disorder is impossible. A famous problem could be in any class of six or more people， there are at least three mutual friends or three mutual strangers if every pair of them are either friends or not friends . Which is provable by the Ramsey Theorem. And through the last century， Ramsey theorem developed significantly with more and more excellent Mathematician work input. Although the Ramsey theorem is keep developing， the Ramsey theorem’s abstract applications became more and more widely used during the past century.
Ⅱ.Preliminaries
Definition： A graph is a collection of vertices V and edges E， which are pairs of vertices.
Definition： A simple graph is a graph that each edge connect two vertices and no loops occurs.
Definition： A complete graph is a simple graph that each E has two vertices and we named it by the number of vertices kn.
Definition： A proper c-colouring graph emphasis that each edge has its own color and no adjacent edges has same coloring.
Definition： A clique of size n is a set of n vertices such that all pairs among them are edges. And a independent set means there are no edges between them.
Definition： The Ramsey number R（s，t） is the minimum number n such
that any graph on n vertices contains either an independent set of size s or a clique of size n（）.
Definition： In mathematics， the pigeonhole principle states that if n items are put into m containers， then at least one container must contain more than one item. Then if an infinite number of items are put into finite containers， then one of the containers must fit infinite items.
Ⅲ.Ramsey Theorem
1.party problem. Proposition：There are six people at a party. We assume that for every pair of them， they are either friends or not friends （i.e. strangers）. Prove that either there are three people all of whom are friends， or there are three people of whom no two are friends.
Proof ： As the graph shows， we have 6 people Julie， Alison， Edna， Barack， Camryn and David. We pick David as the person we are considering. Among the other 5 people，we suppose that David are friends with 3 people. Then we can divide into 2 situation. Situation 1： if two of David friends knows each other then they will be a group of 3 mutually friends. Situation 2： if David’s friends do not know each other， then this 3 people will be a group of 3 mutually strangers. If David do not know 3 people in the 6 people group， then there must be at least three that are strangers to David. Then we can divide into 2 situation. Situation 1： If any two of these are strangers， then together with Joe， they are a group of three mutually strangers. Situation 2： If none of them are strangers to each other， then they are a group of at least three mutual friends. So， through this proof above we can conclude that either there are three people all of whom are friends， or there are three people of whom no two are friends. As the graph shows below we use red line to represent strangers and use blue to represent friends.
And through this section we can proof that for any monochromatic K3 no matter how you want to 2-color Kn， n=6 will be sufficient.
2.Ramsey Theorem and Ramsey Number. From the last section we gained the information that n=6 will be sufficient for any monochromatic K3 no matter how you want to 2-color Kn. Then the question comes， what if we apply it to an monochromatic K6 graph， what’s the number of n will make the graph sufficient and for how many coloring it might be working？
Ramsey Theorem can be defined by following： For all c， m ≥2， there exists n
m such that every c-coloring of Kn has a monochromatic Km.
One of the division under Ramsey Theorem is Ramsey numbers. A Ramsey Number， R（m，n） = r， is the smallest size of a graph r such that every graph of that size has either a clique of size m or an independent set of size n. Like above we proof that R（3，3）=6 through the party example. And also R（a，b）=R（b，a）. R（2，b）=b still applies and the proof was showned in the previous.
Notation： Let a， b ≥ 2.Let R（a， b） denote the least number， if it exists， such
that every 2-coloring of KR（a，b） has a RED Ka or a BLUE Kb. We abbreviate
R（a， a） by R（a）.
Facts： 1. For all a，b， R（a，b） = R（b，a）.
2. For b 2， R（2， b） = b： First， we show that R（2， b） ≤ b. Given any 2-
coloring of Kb ， we want a RED K2 or a BLUE Kb. Note that a RED K2 is just a RED edge. Hence EITHER there exists one RED edge （so you get a RED K2） OR all the edges are BLUE （so you get a BLUE Kb）. Now we prove that R（2，b） = b. If b = 2， this is obvious. If b