Ramsey numbers

Perhaps made famous by the work of Erdős, the Ramsey numbers are one very nice example of graph theory and combinatorics.

Notation here is somewhat nasty (well, it could be worse), so say that a complete graph of size {n} is denoted as {K_n}, a totally disconnected graph as {D_n} (i.e. a graph with {n} vertices and {0} edges), and given a graph {G} the expression {K_n \leq G } means {G} has a subgraph with {n} vertices which is isomorphic to a complete graph (same for {D_n}).

Definition 1 Given {k,l\in\mathbb{N}}, the Ramsey number {R(k,l)} is the minimum number such that a graph with at least {R(k,l)} vertices either contains a subgraph isomorphic to {K_k} or to {D_l}.

In order to generalize this notion readily, it’s better to reformulate it in terms of {2}-colorings:

Definition 2 Given {k,l\in\mathbb{N}}, the Ramsey number {R(k,l)} is the minimum number such that any {2}-coloring of {K_{R(k,l)}} has a red subgraph isomorphic to {K_k} or a blue subgraph isomorphic to {K_l}.

In this way the definition only requires notation for complete subgraphs. Notice that the definition makes the Ramsey number naturally symmetric, {R(k,l)=R(l,k)}, that trivially {R(1,k)=1} for every {k} and {R(2,k)=k}. Finally, notice that the number is increasing in the arguments, i.e. {R(k,l)\leq R(k+1,l)}.
Continue reading