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 DE DF EF 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.