5.3 Ramsey Theory and Probabilistic method

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.

Exercise 5.10.

In any graph G on 6 vertices, either K3G or K3G¯.

Given m,n we define the Ramsey numbers R(m,n) as follows :

R(m,n):=inf{t:For any GKtKmG or KnGc}.

Note that R(m,n)=R(n,m), R(m,2)=m. Our previous lemma gives that R(3,3)6. R(m,n) can also be interpreted as follows: Colour all the edges of Kt with red or blue. Consider the subgraph of red edges as G and subgraph of blue edges as Gc. Hence, KmG is equivalent to a red Km or a red m-clique in Kt and similarly KnGc is equivalent to a blue Kn or a blue n-clique in Kt. This interpretation will be very useful in what follows. Ramsey(1929) showed that R(m,n)< for all m,n.

Lemma 5.11.

R(m,n)R(m1,n)+R(m,n1).

Proof.

Let us look at the complete graph on R(m1,n)+R(m,n1). Choose a vertex v from this graph. Now let us define P to be the set of all vertices which is connected by a red edge to v and Q to be the set of all vertices which is connected by a blue edge to v. Let us say |P|=p and |Q|=q. Then, p+q+1=R(m1,n)+R(m,n1). So by pigeonhole principle, either pR(m1,n) or qR(m,n1).
Case 1:(If pR(m1,n)) Either there is a red (m1)-clique in P and that red (m1)-clique along with v makes our required red m-clique. Otherwise there is a blue n-clique in P.
Case 1:(qR(m,n1)) Either there is a the blue (n1)-clique in Q and that blue (n1)-clique along with v makes our required blue n-clique. Otherwise there is a red m-clique in Q. ∎

It is now an exercise to now show that R(m,n)< for all m,n and R(n,n)4n. We will give a second proof of this using induced colorings.

Lemma 5.12.

R(n,n)4n.

Proof.

Take a colouring of Kt for t=4n. Order the vertices according to some order. Set S0=V. Let x1 be the smallest vertex in S0. By pigeonhole principle, there exists a set of vertices S1 with |S1|22n1, such that every edge from x1 to S1 has same colour. Let x2 be smallest vertex in S1 and S2 be of cardinality 22t2 such that edges from x2 to S2 have same colour. Repeating the procedure, we obtain S0S1S2S2n such that |Si|22ni and also we have a sequence x1,x2,x2n. By construction, for every i, xi+1,,x2nSi and so the edges joining xi with xi+1,,x2n are of same colour, say colour ci{red,blue}. Since there are only two colours, and 2n choices for i, again pigeonhole principle implies that there exists a subset T[2n] of cardinality at least n such that ci=cj for all i,jT. Thus the edges joining {xi:iT} are all of same colour and so we have a n-complete subgraph of Kt. ∎

We now give an exponential lower bound via the probabilistic method due to Erdös.

Lemma 5.13 (Erdös, 1947).

R(k,k)>2k/2.

Proof.

Let n=2k/2 and we wish to show that there is a coloring of edges of Kn with blue and red such that there is no monochromatic clique of size k. The set of all possible colorings on Kn is Ωn:=E(Kn){R,B} i.e., a set of cardinality 2(n2). The crucial idea in probabilistic method is to pick a random variable X with values in Ωn such that the probability X is a coloring with no monochromatic k-clique is positive and this trivially implies that the set of colorings with no monochromatic k-clique is non-empty as desired. As it is common, we can view fΩn as a function f:E(Kn){R,B}.

Let An:={fΩn:f has no monochromatic k-clique}. Instead of showing P(XAn)>0, we will show that P(XAnc)<1. We shall shortly see why the required upper bounding is easier. Firstly, note that if fAn, then there exists a subset S[n] and |S|=k such that fESR or fESB where we have used ES to abbreviate the edge set of <S>, the complete subgraph on S. Hence, we have that

AncS[n],|S|=k({f:fESR}{f:fESB}).

By the union bound for probability distribution, we have that

P(XAn)S[n],|S|=k(P(XESR)+P(XESB)).

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 XΩn as follows : X(e),eE(Kn) are i.i.d. random variables with probability such that P(X(e)=R)=1/2=P(X(e)B). Equivalently, P(X=f)=2(n2) for all fΩn i.e., X is uniformly distributed in Ωn. Now trivially, we have that

P(XESR)=P(XESB)=2(k2)

and thus

P(XAn)(nk)21(k2).

I will leave it as an exercise to verify that for the choice of n we have made (nk)21(k2)<1 as desired. This proves R(k,k)>n:=2k/2. ∎

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 k-clique in Kn.

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, R(5,5) 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 R(5,5) 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 R(6,6). 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].