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.
A clique of agraph G is a complete subgraph of G.
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.
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 least m will know each other or at least n will 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).