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.