9.2. Bounds on Ramsey Numbers

As we already have seen the bound given in Theorem 12.3. for is exact if one of s and t is 1 or 2.

It is also true that the bound is exact for .

On the other hand (Theorem 12.3) we get the following upper bound:

The following theorem shows that the bound is improvable:

 

Theorem 9.4. For every integer ,

Proof.

We prove by induction on t.

For the assertion is true.

Assume , for some , and we consider .

Because of the Theorem 12.2. we have

To complete the proof it is enough to show that the above inequality is strict.

  • Suppose that t is odd. Then is also odd, and so

  • Suppose that t is even.

If   then the statement is true.

If , then   is even since t is also even.

Therefore we can use the second part of the Theorem 12.2. and we get again a strict nequality.

How can we give lower bounds for the Ramsey number?

There are three ways in which lower bounds for   have been obtained:

  • Constructive Method,
  • Counting Method,
  • Probabilistic Method.

In case of Constructive Method a lower bound for is established by explicitly constructing a complete graph of an appropriate order such that it does not contain neither a red  nor a blue .

FIGURE Graph-Theory-2007/10  17.  oldal . Nem kell animáció. (Ha nagyon bonyolult, hagyd el.)

Counting Method: Suppose that we wish to establish the existence of a graph G of order n having some property P.

  • We estimate the number of graphs of order n that do not have property P.
  • We show that this number is strictly less than the total number of graphs of order n.

Therefore there must exist a graph G of order n having property P.

The first application of a Counting Method was establish by Erdős:

Theorem 9.5. (Erdős, 1947): For every integer ,

.

Proof.

Let . We will two-colour the edges of and prove that there exists neither a red nor a blue  subgraph. 

There are distinct labeled graphs of order n with the same vertex set V.

For each subset with , the number of these graphs in which S induces a complete

graph is .

Thus if M denotes the number of "red" graphs with vertex set V that contain a subgraph isomorphic to  then

By hypothesis, . Thus . Since we have

and so

Combining (1) and (2) we conclude that

.

Similarly, we can get the same upper bound for the number of „blue" subgraphs. So, the total number of those graphs which contain either a red or a blue subgraph is 2M and

Since there are distinct labelled graphs, we conclude that there is a such that contains neither a red nor a blue subgraph.

Example: Using the Theorem 9.3 and Theorem 9.5 we have that

.

Actually, .

Theorem 9.6. (Erdős, 1947): For every integer ,

The Ramsey's „two-colour" problem can be easily extendable to colouring with arbitrary (but finitely) many colours.