Ramsey Numbers

su ya xin

Ⅰ.Introduction

Ramseys 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 theorems 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 Davids 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， whats 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 > 2， then the all-BLUE coloring of Kb1 has neither a RED K2 nor a BLUE Kb， hence R（2， b） b. Combining the

two inequalities （R（2，b） ≥ bandR（2， b） ≥ b）， wef indthatR（2， b） = b.

3.R（3， 3） ≤ 6 （we proved in the section with 6 people in a party. ） We want to show that， for every n ≥2， R（n， n） exists. In this proof， we show something more： that for all a， b ≥ 2， R（a， b） exists. We do not really care about the case where a = b， but that case will help us get our result. This is a situation where

proving more than you need is easier.

The goal of this prove is to show that for every n ≥ 2， R（n， n） exists. In this proof， we show something more： that for all a， b ≥ 2， R（a， b） exists. We do not really care about the case where a= b， but that case will help us get our result.

In this section we tried to proof this three theorem below theorem 1.1：（2， b） = b （we proved this earlier）

theorem 1.2：For all a，b ≥ 3 If R（a ? 1， b） and R （a， b-1） existed， then

R（a，b） exist and

R（a， b） ≤ R（a ? 1， b） + R（a， b ? 1） （1）

theorem 1.3： For all a，b ≥ 2，R（a，b） exists and R（a，b） ≤ 2a+b

The proof of theorem 1.1， 1.2， 1.3 are included below， we closely follow the proof created by William Gasarch with slight modifications.

Proof for theorem 1.2

Assume R（a -1， b） and R（a， b -1） exist. Let n = R（a-1， b） + R（a， b-1） Let 2-co be a 2-coloring of Kn， and let x be a vertex. And the number of edges come out from x vertex can be represent by a function that R（a-1， b） + R（a， b-1）-1 Let Red be the number of red edges coming out of x， and let Be d be the number of blue edges coming out of x. So that

Red + Bed = R（a ? 1， b） + R（a， b ? 1） ? 1

hence， either

Red ≥ R（a ? 1， b）

or

Bed ≥ R（a， b ? 1）

To see this， suppose， by way of contradiction， that both inequalities are false.

Then

Red + Bed ≤ （a ? 1， b） ? 1 + R（a， b ? 1） ? 1

= R（a ? 1， b） + R（a， b ? 1） ? 2

< R（a ? 1， b） + R（a， b ? 1） ? 1.

There are two cases：

1. Case 1： Red ≥ R（a ? 1， b）.LetU = y | 2 ? col（x， y） = RED U is of size Red≥ R（a ? 1， b）.Consider the restriction of the coloring 2-col to the edges between vertices in U. Since | U |≥ R（a ? 1， b）， this coloring has a RED Ka-1 or a BLUE Kb. Within Case 1， there are two cases：

（a） There is a RED Ka-1. Recall that all of the edges in x， u | u ∈ U are

RED， hence all the edges between elements of the set U∪xare RED so they

form a RED Ka.

（b） There is a BLUE Kb.

2. Case

Bed ≥ R（a， b ? 1）. Similar to Case 1.

Proof for Theorem 1.3

To show that R（a， b） exists and R（a， b） ≤ 2a+b， we use induction on n=a+b. Since a，b≥ 2， the small value of a+b is 4. Thus n ≥4.

Base Case

n = 4. Since a + b = 4 and a， b ≥2， we must have a = b = 2. From part 1， we know that R（2， 2） exists and R（2， 2） = 2. Note that R（2，2）=2≤ 22+2 = 16

Induction Hypothesis： For all a， b ≥ 2 such that a + b = n， R（a， b）

exists and R（a， b） ≥2a+b.

Inductive Step： Let a， b be such that a， b≥ 2 and a + b = n + 1. There are three cases： Case 1： a=2. By part 1， R（2，b）exists and R（2，b）=b. Since b≥

2， we have b≥ 2b ≥ 4×2b = 22=2b = 22+b Hence R（2， b） ≥ 22+b .

2. Case 2： b = 2. Follows from Case 1 and R（a，b） = R（b，a）.

3. Case3： a，b≥3. Since a，b≥ 3，we have a1≥ 2and b1≥ 2. Also， a+b = n+1， so （a1） + b = n and a+（b1） = n. By the induction hypothesis， R（a 1， b） and R（a， b 1） exist; moreover，

R（a-1， b） ≤ 2（a?1）+b = 2a+b?1 R（a， b-1） ≤ 2a+（b?1） = 2a+b?1 From part 3， R（a， b） exists and

R（a， b）≤ R（a ? 1， b） + R（a， b ? 1）Hence

R（a，b） ≤ R（a ? 1， b） + R（a， b ? 1） ≤ 2a+b?1 + 2a+b?1 = 2 ? 2a+b?1 = 2a+b

3. Values of Ramsey Number. Through the last section， we understand the definition and the bounds of the Ramsey number. But there is a difference between understanding the definition and actually approach to the actual value. Throughout years， people have discover Ramsey number using various Ways. The table below gives a general review of the value and the “inventors”

Ⅲ. Application

Although the Ramsey theorem seems to be not practical for use， actually Ram- sey theorem have a lot abstract application.

· Density Ramsey Theory apply to Transversal Theory as a supplement theorem for the proof.

· A Topological Ramsey space R（Topological Ramsey spaces are spaces which support infinite dimensional Ramsey theory similarly to the El- lentuck space ）， by definition， is a space that satisfies an abstract version of the Ellentuck Theorem.

· Research into the Tukey theory of ultrafilters also has made use of results from set theory， topology and Ramsey theory.

· Design of packet switched networks—- Stephanie Boyles and Geoff Exoo （personal communication） have found an application of Ramsey theory in the design of a packet switched network， the Bell System signaling network.

· The dimension of partial orders： A decision-making application– which helps to prove that： “There are interval orders of arbitrarily high dimension， which can be implies by the Ramsey theorem.”

· Confusion graphs for noisy channels In communication theory， a noisy channel gives rise to a confusion graph， a graph whose vertices are elements of a transmission alphabet T and which has an edge between two letters of T if and only if， when sent over the channel， they can be received as the same letter. And the Ramsey theorem also can apply to this case.

References：

[1] Gasarch， William. “Ramseys Theorem on Graphs.” Cs.umd， www.cs.umd.edu/ gasarch/TOPICS/mathnotes/ramsey.pdf.

【作者簡(jiǎn)介】suyaxin，roland park country school.