187 – On Ramsey theory

Given a natural number {n}, write {K_n} for the complete graph on {n} vertices, and {E_n} for the edgeless graph on {n} vertices.

As explained in problem 47.10 from the textbook, given natural numbers {a,b,n}, the notation

\displaystyle  n\rightarrow(a,b)

means that {n} is so large that whenever {G} is a graph on {n} vertices, either {G} contains a copy of {K_a} as a subgraph, or a copy of {E_b} as an induced subgraph.

We denote the negation of this statement by {n\not\rightarrow(a,b)}. In detail, this means that there is a graph {G=(V,E)} on {n} vertices such that for any collection of {a} vertices of {G}, at least one of the edges between them is not in {E}, and also for any collection of {b} vertices of {G}, at least of the edges between them is in {E}.

Note that if {n\rightarrow(a,b)} then also:

  • {n\rightarrow(b,a)},
  • {m\rightarrow(a,b)} for any {m\ge n}, and
  • {n\rightarrow(a,c)} for any {c\le b}.

Clearly, {0\rightarrow(m,0)} and {1\rightarrow(m,1)} for any {m}. It is also clear that {m\rightarrow(m,2)} for any {m}. When {a,b\ge3}, however, the determination of the smallest {n} such that {n\rightarrow(a,b)} is a subtle and difficult problem. This {n} is called the Ramsey number of {a,b}. We will denote it {R(a,b)}, so

\displaystyle  R(a,b)\rightarrow(a,b)

and, if {m<R(a,b)}, then {m\not\rightarrow(a,b)}.

Theorem 1 If {n\rightarrow(a-1,b)} and {m\rightarrow(a,b-1)}, then {n+m\rightarrow(a,b)}.

Proof: Consider a graph {G=(V,E)} with {|V|=n+m}. We need to show that either there is a copy of {K_a} or of {E_b} as an induced subgraph of {G}.

Let {v\in V}. Divide the remaining {n+m-1} vertices of {G} into two sets {A} and {B} by setting

\displaystyle  A=\{w\in V\mid v\sim w\}

and

\displaystyle  B=\{w\in V\mid w\ne v\mbox{ and }v\not\sim w\},

where {v\sim w} means that there is an edge between {v} and {w}. We have {|A|+|B|=n+m-1} and therefore either {|A|\ge n} or {|B|\ge m}. Otherwise, {|A|\le n-1} and {|B|\le m-1}, from which it follows that {|A|+|B|\le n+m-2}.

Suppose first that {|A|\ge n}. Since {n\rightarrow(a-1,b)}, then the subgraph of {G} induced by {A} either contains a copy of {K_{a-1}} or an induced copy of {E_b}. In the latter case, {E_b} is also an induced subgraph of {G}, and we are done. In the former case, let {C} be a subset of {A} of size {a-1} such that the subgraph of {G} induced by {C} is (isomorphic to) {K_{a-1}}. Then, by definition of {A}, the subgraph of {G} induced by {C\cup\{v\}} is isomorphic to {K_a}, and we are done as well.

If, on the other hand, {|B|\ge m}, the symmetric argument holds: Either there is a subset of {B} of size {a} whose induced subgraph is {K_a}, and we are done, or else {B} contains a copy {C} of {E_{b-1}}. But then (by definition of {B}) we have that {C\cup\{v\}} is a copy of {E_b}.

We have shown that in all cases {G} either contains a copy of {K_a} or of {E_b}, as we needed to prove. \Box

For example:

  • Since {3\rightarrow(2,3)} and {3\rightarrow(3,2)}, it follows that {6\rightarrow(3,3)}. A pentagon is an example of a graph witnessing {5\not\rightarrow(3,3)}, and therefore {R(3,3)=6}.
  • Since {4\rightarrow(2,4)} and {6\rightarrow(3,3)}, then {10\rightarrow(3,4)}. On the other hand, an octagon with two of its main diagonals is an example of a graph witnessing {8\not\rightarrow(3,4).} This means that {R(3,4)} is either 9 or 10. That it is actually 9 is a consequence of the following general result:

Theorem 2 Suppose that {n} and {m} are even, and that {n\rightarrow(a-1,b)} and {m\rightarrow(a,b-1)}. Then {n+m-1\rightarrow(a,b)}.

Proof: We argue as before: Let {G=(V,E)} be a graph with {n+m-1} vertices. Given {v\in V}, define {A} and {B} as before, and note that {|A|+|B|=n+m-2}. There are three cases:

  1. {|A|\ge n}. The result then follows by arguing as in the previous proof.
  2. {|B|\ge m}. Again, the result follows as in the previous proof.
  3. {|A|\le n-1} and {|B|\le m-1}. Since {|A|+|B|=n+m-2}, we must have that in fact {|A|=n-1} and {|B|=m-1}. Note that (by definition) {d(v)=|A|=n-1}, where {d(v)} is the degree (or valence) of {v}.

If there is at least one {v\in V} for which we have either case 1 or 2, we are done. But this must actually happen. Otherwise,

\displaystyle  \sum_{v\in V}d(v)=(n-1)|V|=(n-1)(n+m-1)

is an odd number, since both {n} and {m} are even by assumption. However, as shown in Theorem 46.5 from the textbook, for any graph {G=(V,E)}, we have that

\displaystyle  \sum_{v\in V}d(v)=2|E|,

which is obviously an even number. This contradiction completes the proof. \Box

Theorems 1 and 2 provide us with an obvious algorithm to obtain upper bounds for the values of the Ramsey numbers {R(a,b)}, but these bounds are usually not optimal. For example,

\displaystyle  R(4,4)\le R(3,4)+R(4,3)=18

and

\displaystyle  R(5,3)\le R(4,3)+R(5,2)=9+5=14,

so {R(5,4)\le R(4,4)+R(5,3)-1=31}. However, the exact value of {R(5,4)} is 25.

For up-to-date bounds on the Ramsey numbers and references, the online survey Small Ramsey numbers by Stanislaw Radziszowski (The Electronic Journal of Combinatorics) is highly recommended. Typeset using LaTeX2WP. Here is a printable version of this post.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: