Ramsey number

From Graph
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).

Facts

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