9.1. Classical Ramsey numbers.
The problem: Is it true that in a party of six people there is always a group of three who either all know each other or are all strangers to each other?
The problem was raised and proved first by F.P. Ramsey in 1928.
Solution 1.:
The number of edges 15. So, the number of different cases is
.
These are too many different cases.
Solution 2.:
Let us denote the people
by . We
denote by
if A and B know each other.
- Suppose A know at least 3 people. Let them B, C, D.
o
, so we have the desired result.
o If it is not true then B, C and D are strangers, so we are ready.
-
Suppose A know at most 2 people:
o If D⍭E ∨ D⍭F ∨ E⍭F then A and the two "not-related" person gives the result.
o If it is not true then
, so we are ready.
We shall consider partitions of the edges of graphs. A partition will be called a colouring.
Here the adjacent edges may have the same colour and, indeed, our aim is to show that there are large subgraphs all of whose edges have the same colour. We say that such subgraphs are monochromatic.
In a 2-colouring we shall always choose red and blue as colours.
More generally, the
problem can be reformulate as follows: Given a natural number s, is
there an such that
if
then every
colouring of the edges of
with red
and blue contains either a red
or a blue
?
Let be the
minimum of n for which every red-blue colouring of
yields
either a red
or a blue
.
We assume that , and we adopt the convention that
is both red
and blue since it has no edges.
At the first sight it is
not clear that is finite
for every s and t. However the following statements are obvious:
-
.
-
for any
.
-
.
Proof.
The first two assertions are trivial.
In the third equality follows
immediately from the definition of R. On the other hand, it is also
trivial that
.
Let us consider a
colouring of . There are two possibilities:
Every edge is red. Then
it has a red too. Not
every edge is red. Then it has a blue
. So
.
and therefore
.
Theorem 9.1. The Ramsey number .
Proof.
From the Problem we
have seen that . On the other side neither
nor contains
as a subgraph. So
.
The following result
shows that is finite
for every s and t, and the same time it gives a bound on
.
Theorem 9.2. If then
.
Moreover, if and
are both
even, then strict inequality holds.
Proof.
We may assume that and
are finite.
Let and
consider a „two-colouring" of the graph
.
We need to show that
this colouring contains either a red or a blue
. Let
. Then
.
Let us suppose that we
have red and
blue edges
are adjacent to x in
. Suppose that
.
Then , which is a contradiction.
Firstly, we assume that . Consider a subgraph
of
spanned by
vertices
joined to x by a red edge.
-
If
has a blue
then we are ready.
-
If
contains a red
then it forms with x together a
subgraph
Now we assume that . Consider a subgraph
of
spanned by
vertices
joined to x by a blue edge.
-
If
has a red
then we are ready.
-
If
contains a blue
then it forms with x together a
subgraph
To prove the strict
inequality we consider a „two-colouring" of the graph . Now
and it is
even.
Let us suppose that we
have red and
blue edges which are adjacent to x in
.
-
If
then we can use the first part of our „original" proof.
-
If
then
since both
and
are even. From that it follows that
, since otherwise we would get
which is a contradiction. So, since
, we can use the second part of the „original" proof.
So we have got that if we two-colour then we get
either a
red or a
blue
subgraph, which completes the proof.
Theorem 9.3. (P. Erdős, G. Szekeres, 1935): For
every two positive integers and
the Ramsey
number exists and
Proof.
We will prove by
induction on .
If or
then the
statement is (with equality) true.
Suppose that and
and (2) is
true for all
pairs for
which
.
Because of the Theorem 12.2. we know that
The known Ramsey numbers
Tálázat Graph-Theory-2007/10 12. oldal .
It is very difficult to decide the Ramsey numbers.
Erdős story: Suppose
that extra territorial beings attack our Planet. They want to blowing up the
Earth unless we can not count the Ramsey number within one
year.
Erdős told that if the
most clever mathematicians develop the best know algorithms for the best
computers then we would able to decide the number .
If the condition would
be the number then the
only solution would be a good organized attack against the ET-s.