Ramsey number

Definition

For two parameters

Suppose $m,n$ are positive integers. The Ramsey number $R(m,n)$ is defined as the smallest positive integer $r$ such that, for any graph whose vertex set has size $r$, either the clique number is at least $m$ or the independence number is at least $n$. More explicitly, for any graph whose vertex set has size $r$, the graph must either contain a $m$-clique (i.e., $m$ vertices all adjacent to each other) or an independent set of size $n$ ($n$ vertices no two of which are adjacent to each other).

Facts

• Ramsey numbers are symmetric: $R(m,n)=R(n,m)$
• $R(m,1)=R(1,m)=1$ for all positive integers $m$
• $R(m,2)=R(2,m)=m$ for all positive integers $m$
• Recurrence relation bound for Ramsey numbers: This states that $R(m,n)\leq R(m-1,n)+R(m,n-1)$. Moreover, if both the numbers $R(m-1,n)$ and $R(m,n-1)$ are even, then we get $R(m,n)\leq R(m-1,n)+R(m,n-1)-1$
• Binomial coefficient bound for Ramsey numbers: This states that $R(m,n)\leq {\binom {m+n-2}{m-1}}$

Particular cases

$m$	$n$	$R(m,n)=R(n,m)$ (precise value if known)	Proof that this is an upper bound	Example graph with $R(m,n)-1$ vertices that does not have a $m$-clique and does not have a $n$-independent set
1	1	1
2	1	1
2	2	2
3	1	1
3	2	3
3	3	6	We use the recurrence relation bound for Ramsey numbers, to get $R(3,3)\leq R(2,3)+R(3,2)=3+3=6$	cycle graph:C5
4	1	1
4	2	4
4	3	9	We use the recurrence relation bound for Ramsey numbers, to get $R(4,3)\leq R(3,3)+R(4,2)-1=6+4-1=10-1=9$. Note that we can subtract 1 because both numbers are even.	cube graph
4	4	18	We use the recurrence relation bound for Ramsey numbers, to get $R(4,4)\leq R(3,4)+R(4,3)=9+9=18$	Paley graph:P17