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 is denoted as , a totally disconnected graph as (i.e. a graph with vertices and edges), and given a graph the expression means has a subgraph with vertices which is isomorphic to a complete graph (same for ).
Definition 1 Given , the Ramsey number is the minimum number such that a graph with at least vertices either contains a subgraph isomorphic to or to .
In order to generalize this notion readily, it’s better to reformulate it in terms of -colorings:
Definition 2 Given , the Ramsey number is the minimum number such that any -coloring of has a red subgraph isomorphic to or a blue subgraph isomorphic to .
In this way the definition only requires notation for complete subgraphs. Notice that the definition makes the Ramsey number naturally symmetric, , that trivially for every and . Finally, notice that the number is increasing in the arguments, i.e. .
Anyway, this is a combinatorial frame, and in order to make sure the definition isn’t talking about the empty set we need to prove such numbers always exist. Here is the proof. Proof: We actually prove the inequality
Pick and consider any -coloring of . Every vertex has connectivity , therefore either there is a vertex with at least outgoing red edges, or a vertex with outgoing blue edges (actually, every vertex falls in at least one of the two cases). The argument is of course completely symmetric, so suppose is a vertex with outgoing red edges, and call the set of vertices connected to by a red edge. Then, by definition of , the complete graph on either contains a red red subgraph or a blue subgraph. In the latter case we have nothing to add since we are already satisfied, in the former case consider : this is a complete subgraph of size with only red edges, thus isomorphic to .
The first possible generalization of Ramsey numbers is to higher colorings of graphs. One has naturally
Definition 3 Given colors, is the minimum number such that any -coloring of contains a color-1 subgraph isomorphic to , or a color-2 subgraph isomorphic to , , or a color- subgraph isomorphic to .
Again, we need to make sure these numbers exist. One actually sees how the previous proof generalizes to this case, and actually that there are a lot of different proofs of the same fact.
Notice: an edge of colour is called a -edge. A (sub)graph with all -edges is called a -monochromatic complete (sub)graph.
Proof: It’s again true that if one of the arguments is then the number is identically , and that the definition of is symmetric in the arguments. Pick and consider any -coloring of . Then there exists at least one vertex and a color such that has at least outgoing -edges. Call the set of vertices connected to by a -edge. This is a subgraph of size , therefore if it doesn’t contain any monochromatic subgraph isomorphic to some for – in which case we are done – it contains a subgraph isomorphic to a -monochromatic , thus is isomorphic to a -monochromatic . Notice we proved
Another proof can be the following, based on what we could call “a dog vision argument”: collapse all colours into a single grey colour. Then pick and consider a -coloring of . By the definition of Ramsey numbers, this graph either contains a -monochromatic subgraph isomorphic to or a grey-monochromatic subgraph isomorphic to . But then any -coloring of this subgraph induces any -coloring on , and contains a monochromatic subgraph isomorphic to one of the . Thus we have proven inequality
Another dog-vision proof in the same spirit could be, for even, to prove the inequality
If we look deeper into the recursions given by these inequalities we can find some upperbounds for the Ramsey numbers. In the case, any quantity whose terms are uniformly bounded is bounded by a constant times a binomial coefficient; in this case
and Stirling approximation for is , that gives us the upperbound
The following is instead an exponential LOWERbound on :
Proposition 4 .
Proof: This is an example of probabilistic proof (which is just a counting argument in disguise).
Let be an integer to be chosen later. Assume all the possible 2-colorings of are equally likely, that is the probability distribution on the 3-colorings is uniform. We can realize this distribution by assigning to an edge color Red or Blue with probability . The set of -colorings is denoted by and a single coloring by . We can think of these as functions on the edges. We want to prove
because that would imply we can avoid the situation which is realized in , that is .
Of course it is the same to prove that the probability of having a monochromatic subgraph is strictly less than 1. Fix a subset of the vertices of cardinality , , and denote by the edges of the (complete) subgraph with vertices . Then the probability that is monochromatic is
because each edge has independent probability of of being Red, and the number of edges is . Thus the probability of having a monochromatic subgraph of size is bounded by the sum of this probability over all possible subsets of size , that is
and this last term can be bounded by . If we choose then the bound becomes , which is and thus can be made smaller than one at most by limiting by a further constant .
The above argument is readily generalized to the case of colours, giving the (polynomial in the colours, exponential in the size of the subgraphs) lowerbound
For colours this is
and notice that the diagonal value majorizes the Ramsey numbers for lower entries.
Let’s now look at some bounds depending on the colours. For example, we can prove
because . Thus the claim is proven by induction on , since . We can also prove a better lowerbound than the one found by the probabilistic argument, namely that
i.e. the growth is at least exponential (the previous bound gave only ). To prove this, we argue by induction. If is then . Now, suppose it’s true for and take a bipartite graph with vertices. For each of the two partitions, colour the edges with colours avoiding any triangle, which you can do by inductive hypothesis since they have size . Then colour all the edges connecting the two partitions with the remaining colour: these edges form no triangles. The argument generalizes easily to prove
For example, for , take a tripartite graph of size , colour each partition (of size ) with colours avoiding every monochromatic subgraph, then colour the edges connecting the partitions with the remaining colour. These edges form no . So the claim is proven once we verify the basic case, which is . By the probabilistic lowerbound , and is true for big enough, so that our claim is certainly verified for at least big (well, actually , which is not so bad. Anyway, for the claim is verified as well, look at this page of wikipedia for a summary of mixed methods results.).
Now we move on to see some applications of the Ramsey theory.
Theorem 5 (Schur) For big enough, any -coloring of the numbers is such that there exist such that have the same colour.
Proof: A colouring of the numbers can induce a coloring of a graph as follows. For the complete graph and a coloring of the vertices, we induce a -coloring of the graph by painting edge in colour . Then choose : there exists a monochromatic triangle then, with vertices . This says that . Now, observe that if and , then , that is, .
Then every mechanism that induces colorings on the numbers actually induces colorings of graphs, and therefore one can find such triplets . This has an unexpected and pleasant consequence:
Theorem 6 (Fermat’s theorem ) For every and prime number big enough, Fermat’s modular equation
has at least one non trivial solution.
Proof: is a cyclic group, call a generator and parametrize the elements as , where . Then choose as -coloring the one given by . By Schur’s theorem, provided is big enough, there exist such that . That means the elements are of the form , and . Dividing by and taking we have .