Page 1 of 6
Vol. 2, No. 2, July 2013 | At Right Angles 5
feature
A theorem on Facebook
It’s very likely that you have a Facebook account, and of course, you
have many friends on Facebook. If X is your friend on Facebook,
then you are X’s friend on Facebook too. But it’s possible that Y is X’s
friend and not yours. Still, I am sure you and X have many common
friends, forming a trio of friends. Now, here is a question for you.
What is the smallest number n of people on Facebook such that there
is definitely a trio among them, either all of whom are friends with
each other, or none of whom are friends with each other?
With three people, say A, B and C, it is easy that we will not have this
property: let A and B be friends, neither of whom are friends with
C. What about four people, A, B, C and D? Again it is easy: make A
and B friends, C and D friends, and no more. In both these case the
desired trio is not to be found.
The Artist of
Problem-Posing
Notes from a small suitcase
Paul Erdős has been described as one of the most universally adored mathematicians
of all time. No mathematician prior to him or since has had quite the lifestyle he
adopted: the peripatetic traveller living out of a suitcase, moving from one friend’s
house to another for decades at a stretch, and all the while collaboratively generating
papers; no one has had quite the social impact he has had, within the community of
mathematicians. This article offers a glimpse of his life and work.
R. Ramanujam
Paul Erdős
Page 2 of 6
6 At Right Angles | Vol. 2, No. 2, July 2013
When we have five people, it is a little more
difficult, but a picture can help think about it.
Let us have points denoting the 5 persons; draw
a red line connecting them to denote that they
are friends on Facebook, and a blue line between
them to denote that they are not. Now a red
pentagon with the persons on vertices and blue
lines to ‘opposite’ vertices (as in Figure 1) should
convince you that we can indeed have a situation
without the desired property.
Now to six. Take some time off now to draw
pictures like the above. The hexagon with its
diagonals does not help; while we get many
interesting pictures, we get none that works like
the one with five vertices. At this point, we start
suspecting that six might indeed be the smallest
number we seek. But then we need a proof that
among any six persons on Facebook, we have a
trio, either all of whom are friends, or not-friends.
Call the newcomer F . We first observe that we
already know something about F !
Claim. Among the other five persons, there are at
least three among them such that F is a friend of
all three, or F is friends with none of the three.
Why? Suppose not. Let us argue with reference to
a picture like the one we drew earlier; see Figure
2. We focus on the ‘lines’ coming out from F . Each
line is red or blue. Since there are five such lines,
one colour occurs three times or more. Whichever
that colour is, we get the three persons we want.
(If this colour is red, then the three persons the
lines connect to are friends of F , else they are
non-friends.)
Nice. Suppose that the three persons identified
in the previous step are A, B, C. (It could be any
three; we have renamed them as A, B, C.) Their
relationship with F is the same: all friends or all
non-friends. Suppose they are all friends of F .
Now if any two of A, B, C are friends with each
other, these two together with F form a trio of
friends. And if no two among A, B, C are friends
with each other, then A, B, C form a trio of non- friends! Either way we get the trio we need.
Please check that all possible cases can be
disposed of in a similar way. So we have proved a
Facebook Theorem that is valid for any six of the
millions of members who use that site, knowing
nothing at all about them!
The picture that we drew was a graph, with edges
connecting pairs of vertices. We used two kinds
of edges, red and blue. We can call this an edge- colouring of the graph with two colours. When
every pair of vertices has an edge between them,
we call it a complete graph. A complete graph on n
vertices is denoted by Kn . (So K2 is just an edge, K3
is a triangle, and K4 is a quadrilateral with its two
diagonals.)
In this language, what we showed was the
following: if each edge of K5 is coloured red or
blue, then a monochromatic K3 may not get
created, but if each edge of K6 is coloured red or
blue, then a monochromatic K3 necessarily does
get created. (‘Monochromatic’ means that all
edges have the same colour.)
The critical number 6 is an example of a Ramsey
number (named after the mathematician and
logician Frank Plumpton Ramsey) of a graph,
the minimum number of vertices needed to
force a monochromatic subgraph inside it. More
rigorously, given any two numbers s and t, the
non-friends
friends
Figure 1: Pentagon with ‘red’ edges, ‘blue’ diagonals:
no trio of the desired kind
Figure 2: Whom is F friends with?
This figure shows one of many possibilities.
Page 3 of 6
Vol. 2, No. 2, July 2013 | At Right Angles 7
Ramsey number R2(s, t) is the smallest integer m
satisfying the property that if the edges of Km are
coloured red or blue, then no matter which way it
is done there is either a subgraph Ks with all red
edges, or a subgraph Kt with all blue edges. With k
colours, we can similarly speak of Rk(s, t). What we
showed above was: R2(3, 3) = 6.
Why should anyone care about Ramsey numbers?
For one reason, finding them is extremely hard!
Only a handful are known, and Table 1 lists all the
known Ramsey numbers of the form R2(s, t).
You will find it a nice challenge to show that
R2(3, 4) = 9.
In the absence of any practical algorithm for
computing exact values of Ramsey numbers,
a great deal of research effort has been
concentrated on obtaining bounds instead.
For diagonal Ramsey numbers, i.e., Ramsey
numbers of the form R2(s, s), some bounds are
known. For instance, it can be shown without too
much difficulty that R2(s, s) ≤ 4s
, an upper bound.
Getting lower bounds is much harder.
In 1947, the mathematician Paul Erdős
(pronounced Air-dsh) proved this remarkable
theorem
Theorem 1. Let k, n be positive integers such that
. Then R2(k, k) is greater than n.
In order to show that R2(k, k) > n, it suffices to
show that there exists at least one colouring of the
edges of Kn which results in no monochromatic Kk.
Erdős showed this probabilistically! The details
are given in Figure 4.
Table 1: All the known Ramsey numbers
Figure 3: Paul Erdős having a chuckle.
Source: http://24.media.tumblr.com/tumblr_
maobc7dXYQ1qipuzxo1_1280.jpg
Consider an edge blue/red colouring of Kn in
which the colour for each edge is assigned
randomly and independently, with probability
1
/2 for each.
How many copies are there of Kk in this
configuration? Clearly as many as there are
subsets of size k in the set {1, 2, 3, . . . , n}, i.e., n
k . What is the probability that any particular
copy is monochromatic? Each of the k
2 edges
in the chosen Kk gets a particular colour with
probability 1
/2, and there are two colours to
choose from, so the probability is equal to
Hence the probability that there exists a
monochromatic Kk is at most
(For, the probability of a union of several
events is at most the sum of the probabilities
of the individual events.)
This quantity is less than 1 by the
assumption of the theorem, hence the
probability that there exists a colouring
with no monochromatic Kk is greater than 0.
Therefore, there exists a colouring with no
monochromatic Kk , and we are done.
Figure 4: A random proof!
Erdős’s probabilistic proof of Theorem 1.
s 3 3 3 3 3 3 4 4
t 4 5 6 7 8 9 4 5
R2(s, t) 9 14 18 23 28 36 18 25
.
.