Ramsey’s theorem is a fundamental theorem in combinatorial mathematics, and initiated the combinatorial theory called * Ramsey Theory*. This theory aims to seek regularity in disorder: “

*general conditions for the existence of substructures with regular properties*“.

Ramsey’s theorem states that:

“for each pair of positive integers k and l there exists an integer R(k,l) such that any graph with R(k,l) nodes contains a clique with at least k nodes or an independent set with at least l nodes.

**Clique:**

A clique of agraph **G** is a complete subgraph of **G**.

**Independent Set:**

An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of the graph. Below are some examples:

Another formulation of the theorem states that “there exists a least positive integer *R*(*r*, *s*) for which every blue-red edge colouring of the complete graph on *R*(*r*, *s*) vertices contains a blue clique on *r *vertices or a red clique on *s* vertices”. Extending this theorem, we can apply this to *n* colours rather than just 2.

For a proof of this theorem, click here.

### Ramsey Numbers

The numbers *R(r,s) *in Ramsey’s theorem are called Ramsey numbers. Ramsey numbers give the solution to the *party problem *that asks:

“the minimum number of guests,

R(m,n), that must be invited so that at leastmwill know each other or at leastnwill not know each other”

Connecting Ramsey numbers to graph theory, the Ramsey number is the minimum number of vertices, *v = R(m,n)*, needed in order for all undirected graphs of order *v* to contain a clique of order *m* or an independent set of order *n*. Ramsey’s theorem tells us that this exists for all *m* and *n*.

Click here for an article on how to calculate R(4,3).

M x