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

• Recurrence relation bound for Ramsey numbers: This states that $R(m,n)\leq R(m-1,n)+R(m,n-1)$
• Binomial coefficient bound for Ramsey numbers: This states that $R(m,n)\leq {\binom {m+n-2}{m-1}}$