treated in [10] cover vertex-coloring when # , the graph defining the Ramsey prop-
erty, belongs to a wide family of graphs including, for example, all complete graphs.
Also the case of edge-coloring when H is a tree is dealt with. In all these in-
stances it is shown that there exists a function p(ri) such that for every e 0,
limn_ocPr[G(n,p) (H)] = 1, if p (1 + e)p(n) and 0, if p (1 - s)p(n).
It is worthwhile pointing out here a difference between this kind of a "sharp
threshold" statement and the previous Ramsey threshold results. Although the
results from [10] show that the transition from the non-Ramsey region of the values
of p to the Ramsey region is swift and sharper than what was previously proven,
these are only an existence results. They give no further information on the critical
value of p which was calculated in previous works.
The most basic case not treated in [10] is the case of graphs with a monochro-
matic triangle in every edge coloring, for which a (weak) threshold is given by
Theorem 1.2. In the present paper we prove a sharp threshold theorem for this
Ramsey property, with two colors. This is our Theorem 1.1 stated above.
1.3. Sharp Thresholds of Increasing Graph Properties. In this subsec-
tion we introduce the notion of a sharp threshold for a graph property, as well as
a technique for proving sharpness of thresholds. Consider a property Q of graphs
on n vertices. We identify Q with the set of graphs having this property, and use
the notation G G Q to denote the fact that G has property Q. We will restrict
ourselves to properties which are invariant under a graph automorphism and also
distinguish an important class of increasing graph properties, i.e. those that are
preserved under edge addition.
1.1. We say that p = p(n) is a threshold function for an increasing
graph property Q if
lim Pr [G(n,p) G Q]
if p = o(p)
if p = o(p).
Bollobas and Thomason proved in [4] the existence of threshold functions for
all increasing set properties, and in particular for all graph properties.
Some properties do not have sharper thresholds in the sense that for all p = p(n)
which are of the same order as p, we have 0 limn_*oo Pr[G(n,p) G Q] 1.
E.g., this is the case of the (increasing) property of containing a copy of a given,
balanced graph H, the threshold for which has been established by Erdos and
Renyi [7] at n~l/p(H\ Here p(H) is the edge to vertex ratio in H. For example,
p(Kk) = {k— l)/2, so the thresholds for the appearance in G(n,p) of a copy of K3,
if5, and KQ, respectively, are n
_ 1
But there are other properties, like connectivity, which enjoy much sharper
thresholds. Indeed, it has been proved by Erdos and Renyi in [6] that
lim Pr [G(n,p) is connected] =
n-+oc 10 if np logn —• 00.
1.2. We say that an increasing property Q has a sharp threshold
if there exists a function p = p(n), such that for every e 0:
iimpr[G(n,P)eQ]={; ! ^ ; ;
+ e
i ?
n-oc 10 it p (1 6)p.
Previous Page Next Page