## 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, 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.