In the previous video, I explained the notation R(m,n) to be the number of self-avoiding walks.
Turns out this is not the most famous use of this notation. It is much more commonly
used to denote Ramsey numbers, which we will explore in this video. Although it is a rhapsody,
I still want to structure it a bit. This journey will not be an easy one, particularly towards
the end, but it is a very rewarding one. Let’s start with the first chapter of the journey.
If we assume friendship is mutual, which means if A is friends with B, then B is also friends
with A, then it is a well-known fact that among any six people on the planet, you can
always find a group of 3 people who are friends with each other, or not friends with each
other. To analyse this and ultimately proving this fact, we first reduce each person here
to a vertex of a graph, and we connect people using a red edge if they are not friends with
each other, and a green edge, if they are friends with each other. Then the fact is
the same as saying that there is either a red triangle, meaning that these three people
are not friends with each other, or a green triangle, meaning that these three people
are friends with each other. Since any two people are either friends or not friends,
all the vertices are connected by edges, but we just don’t know the colour of the edges.
With this setup, we can now present the proof for the fact. We only focus on a particular
vertex, and all the 5 edges connected to that vertex. Among these 5 edges, since there are
only 2 colours, one colour must appear at least three times. Here, we choose the red
colour. The argument would be the same if the colours are reversed. Now consider the
connections between these three vertices. If any of the connections is red, then we
must form a red triangle. If not, then all the connections are green and we form a green
triangle. So a triangle is inevitable in all cases.
So this was the well-known fact and its classic proof. We move on to a less well-known proof
of the same fact. We start with these kinds of shapes, where the arms are edges of different
colours. Around a vertex, there can be no such V-shapes when all the edges connected
to it are of the same colour. Or precisely 4 V-shapes when there is an odd edge of different
colour to the others. Or precisely 6 V-shapes when the edges are in a 2-3 configuration
of colours. We can conclude that no matter which case you are in, the number of V-shapes
around any vertex is at most 6, and since there are 6 vertices, the total number of
V-shapes is at most 36.
Now, in a triangle, it can either have an odd edge of different colours, in which case
there are 2 V-shapes in a triangle, or all the edges in a triangle are of the same colour,
in which case there is no V-shape in a triangle. So the types of triangles are those with 2
V-shapes, or those with 0 V-shapes. Now we have proved that there are at most 36 V-shapes
in the whole graph. So there are at most 18 triangles with 2 V-shapes. However, the total
number of triangles in the 6-vertex graph is 6 choose 3 because we can freely choose
the 3 vertices to form a triangle, and this is equal to 20. So altogether we show that
there are actually at least 2 triangles with 0 V-shapes, or the red or green triangle that
we want. The fact only requires us to show at least 1 of the type with 0 V-shapes, but
now this proof tells us that we can say something stronger: there are at least 2 triangles of
this type. Since we have proved more than we want, it is natural to ask whether 5 vertices
still work, which brings us to the definition of the Ramsey numbers.
For the previous case, 5 does not work, because there is quite a nice counter-example. This
5-vertex graph does not contain any red or green triangle. We usually denote this fact
as R(3,3) equals 6, but what does the R thing mean? R(m,n) is the minimum number of vertices
of a graph that guarantees there are m vertices which are all joined by red edges, or n vertices
which are all joined by green edges. In mathematics, after you define anything, you should ask
yourself whether this is well-defined. The problematic bit is that we defined R(m,n)
to be the minimum no. of something, but it is possible that we can never guarantee any
of the two things below no matter how large the graph is. But it is indeed well-defined,
and this is a special case of Ramsey’s theorem. It takes a theorem to justify the well-definedness
of something. The proof of it is not difficult, and I will put it in a separate video. But
we will use this central idea of the proof for the next section of this video.
So now, after defining the Ramsey numbers, the most exciting bit is R(4,4), and the proof
is a very nice and sneaky argument.
First of all, let’s borrow this inequality for a second to have a grasp on the size of
R(4,4). By substituting m and n to be 4, we have an upper bound of this sum of R of something.
By applying the same inequality one more time, we get this. Now we know that R(3,3) is 6.
In fact we proved it right in the beginning of this video. From the separate video, I
detailed the reasons why both R(2,4) and R(4,2) equal to 4. so R(4,4) has an upper bound of
23. But that does not tell us what R(4,4) is exactly. We just know that it is smaller
than or equal to 23. If we really want to hunt for the exact value of R(4,4), what we
might do is to ask the computer to check all the 22-vertex graphs. There are altogether
231 edges in a 22-vertex graph, and each edge can be coloured red or green, so there are
altogether 2 to the power of 231 configurations. This is a huge number. Even if we assume that
a supercomputer can check one quintillion graphs, it needs 10^44 years to check all
the 22-vertex graphs. Although it turns out that R(4,4) is 18, please bear in mind that
it is nearly impossible to brute force this answer without clever proofs like the following.
To prove that, we first consider a graph with 18 vertices. And similarly, we consider a
particular vertex and its connections with other vertices. Now, there are 17 edges connected
to this vertex, and there are only 2 colours available. So one colour must appear at least
9 times. Assume that colour is red. Since we want to guarantee that there is either
4 vertices connected in red, or 4 vertices connected in green, this amounts to proving
that we can guarantee 3 vertices connected in red, or 4 vertices connected in green in
these 9 vertices.
So we reduced to a slightly simpler problem of 9 vertices, where we want to prove that
it guarantees that there are 3 vertices connected in red, or 4 vertices connected in green.
Again, we consider 8 edges around a single point. Among these 8 edges, there can be different
cases of red-green distribution. In the case where there are more than 6 green edges, then
among these 6 vertices, we have proved that there must be a red or green triangle here.
If the triangle is red, then we have 3 vertices connected in red, and if the triangle is green,
then together with the initial vertex, there are altogether 4 vertices all connected in
green. So in this case, we are done.
In another case where there are 4 more red edges and 4 or less green edges, then among
these 4 vertices, there is either a red edge or not. If there is a red edge, then there
is a red triangle, so there is a group of 3 vertices all connected in red. If not, then
all the connections are green, so there are 4 vertices all connected in green. So in this
case, we are done.
What remains is this annoying case where there are exactly 3 red edges, and 5 green edges.
You can do some brute force, but here is the most sneaky trick. Think about what happens
if all the vertices among the 9 we are considering are in this case. Is it even possible? Take
a look at the number of green edges if all vertices have 5 green edges coming from it.
The total number of green edges can be counted to be 9 times 5, as there are altogether 9
vertices, each have 5 green edges emanating from it. But every single edge connects two
vertices, so each edge should be counted exactly twice in this process, but this is not an
integer, and that does not make any sense! So it is indeed impossible to have all vertices
of this case. So when we unfortunately chose a particular vertex of this case, just pick
another vertex not of this case, and all the other cases have been taken care of, so we
are safe. This is a really sneaky trick, and it might take a moment to appreciate this.
But we are not done yet. Asserting that R(4,4) is equal to 18 also means that a 17-vertex
graph does not guarantee 4 vertices all connected in red or green. Again, it is nearly impossible
that it is done by brute force, because there are altogether more than 10 to the power 40
configurations to check, and even with a quintillion computations per second, we need more than
the age of the universe to check them all. So there must be a slick trick to construct
a counter-example, which we will discuss in another separate video.
It is a natural question to ask what about R(5,5) or even R(6,6). The answer is we don’t
know, and it is possibly best famously summarized by Paul Erdos. Here we slightly modify the
wordings. Suppose aliens invade the earth and threaten to obliterate it in a year's
time unless human beings can find R(5,5). We could marshal the world's best minds and
fastest computers, and within a year we could probably calculate the value. If the aliens
demanded R(6,6), however, we would have no choice but to launch a preemptive attack.
(pause) This just illustrates how difficult it is to calculate R(5,5) and R(6,6).
This problem is simple to state, but it is extremely difficult to solve, as you have
seen in the Erdos quote, where we should just give up on R(6,6). This kind of simple to
state but difficult to solve problems are prevalent in Mathematics, not just the Ramsey
numbers. Another famous example is Fermat’s last theorem. But I think that is kind of
the attraction of mathematics. A deceptively simple problem can often yield rich theories
in Mathematics.
I will release the videos for the proof of Ramsey’s theorem and R(4,4) not equal to
17 in a few weeks. Stay tuned by subscribing to the channel with notifications on. Don’t
forget to click the like button if you enjoyed it. See you next time. Bye!