# Ramsey number

Jump to: navigation, search

## Definition

### For two parameters

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

## Particular cases

   (precise value if known) Proof that this is an upper bound Example graph with  vertices that does not have a -clique and does not have a -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  cycle graph:C5
4 1 1
4 2 4
4 3 9 We use the recurrence relation bound for Ramsey numbers, to get . 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  Paley graph:P17