This section is not part of syllabus but rather an introduction to one of the most powerful tools in modern day graph theory and combinatorics.
In any graph on vertices, either or .
Given we define the Ramsey numbers as follows :
Note that , . Our previous lemma gives that can also be interpreted as follows: Colour all the edges of with red or blue. Consider the subgraph of red edges as and subgraph of blue edges as . Hence, is equivalent to a red or a red -clique in and similarly is equivalent to a blue or a blue -clique in . This interpretation will be very useful in what follows. Ramsey(1929) showed that for all .
.
Let us look at the complete graph on . Choose a vertex from this graph. Now let us define to be the set of all vertices which is connected by a red edge to and to be the set of all vertices which is connected by a blue edge to . Let us say and . Then, . So by pigeonhole principle, either or .
Case 1:(If ) Either there is a red -clique in and that red -clique along with makes our required red -clique. Otherwise there is a blue -clique in .
Case 1:() Either there is a the blue -clique in and that blue -clique along with makes our required blue -clique. Otherwise there is a red -clique in .
∎
It is now an exercise to now show that for all and . We will give a second proof of this using induced colorings.
.
Take a colouring of for . Order the vertices according to some order. Set . Let be the smallest vertex in . By pigeonhole principle, there exists a set of vertices with , such that every edge from to has same colour. Let be smallest vertex in and be of cardinality such that edges from to have same colour. Repeating the procedure, we obtain such that and also we have a sequence . By construction, for every , and so the edges joining with are of same colour, say colour . Since there are only two colours, and choices for , again pigeonhole principle implies that there exists a subset of cardinality at least such that for all . Thus the edges joining are all of same colour and so we have a -complete subgraph of . ∎
We now give an exponential lower bound via the probabilistic method due to Erdös.
.
Let and we wish to show that there is a coloring of edges of with blue and red such that there is no monochromatic clique of size . The set of all possible colorings on is i.e., a set of cardinality . The crucial idea in probabilistic method is to pick a random variable with values in such that the probability is a coloring with no monochromatic -clique is positive and this trivially implies that the set of colorings with no monochromatic -clique is non-empty as desired. As it is common, we can view as a function .
Let . Instead of showing , we will show that . We shall shortly see why the required upper bounding is easier. Firstly, note that if , then there exists a subset and such that or where we have used to abbreviate the edge set of , the complete subgraph on . Hence, we have that
By the union bound for probability distribution, we have that
The union bound is what makes it easier to upper bound than lower bound. Also, so far we have not used any specific property of the random variable at all. We can now make a ‘clever’ choice of the random variable to obtain the desired upper bound. This flexibility in making ‘clever’ choices of random variables to obtain desired bounds is another hallmark of the probabilistic method and lends enormous power to the method.
Now choose as follows : are i.i.d. random variables with probability such that . Equivalently, for all i.e., is uniformly distributed in . Now trivially, we have that
and thus
I will leave it as an exercise to verify that for the choice of we have made as desired. This proves . ∎
The defect of probabilistic method as obvious in the above proof is that it is non-constructive i.e., it did not give explicitly a coloring that has a monochromatic -clique in .
Read [Alon and Spencer 2004, Chapter 1], [Aigner et al. 2010, Chapter 40] and [Jukna 2011, Part IV] for more illustrative examples on the probabilistic method and if interested, read more of [Alon and Spencer 2004].
Regardless of your liking of the proof via probabilistic method, Ramsey numbers raise many interesting questions themselves. For example, is still unknown. Here is a legendary statement from Erdös attesting to the complexity of Ramsey numbers (see [Spencer 1994, Page 4]) :
" Erdös asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for . In that case, he believes, we should attempt to destroy the aliens. "
For more on Ramsey numbers, read https://en.wikipedia.org/wiki/Ramsey’s_theorem and [Jukna 2011, Sections 4.9 and 4.10].