4 E. FRIEDGUT , V. RODL, A. RUCINSKI, AND P. TETALI
Otherwise we say that Q has a coarse threshold.
Thus, the property of being connected has a sharp threshold at p log n/n.
Our main theorem in this paper, Theorem 1.1, states that the Ramsey property 1Z
has a sharp threshold.
In [8] the first author gives a necessary and sufficient condition for an increasing
property to have a sharp threshold. This condition will be the central tool used in
this paper. Roughly stated, it says that a property with a sharp threshold is not
statistically determined by a simple local reason, that is, by the presence or absence
of finitely many edges. For example, the property of having a triangle as a subgraph
is obviously local, and indeed has a coarse threshold (both the critical probability
and the length of the threshold interval equal 6(l/n)), whereas it seems obvious
that connectivity is a non-local property, even though it is statistically equivalent
to the absence of isolated vertices.
For the Ramsey property 7£, the condition in [8] asserts that in order to estab-
lish the sharpness of its threshold, one has to show that 1Z is not influenced by the
appearance of any fixed subgraph, which is likely to be contained in G(n,p), with
the range of p = p(n) limited by Theorem 1.2 to p = Q(l/y/n). Of course, 1Z is
extremely influenced by the appearance of KQ, which, however, is very unlikely to
be present in such a G(n,p).
In this paper we will use a version of the sharpness criterion from [8], which
follows readily from the original statement but is more suitable for applications.
Given a graph M and a disjoint set of n vertices, let M* be an ordered copy of M
placed uniformly at random on one of the n\/(n |F(M)|)! possible locations.
THEOREM
1.3. Let Q be an increasing graph property, with a coarse threshold.
Then there exist real constants 0cC,(30, a rational p, and a sequence
p = p(n) satisfying cn~1/p p(n) Cn~1/p, such that (5 Pr[G(n,p) G Q] 1-/3
for all n. Furthermore, there exist a,£ 0 and a balanced graph M with density p
for which the following holds:
For every graph property Q such that G(n,p) G Q a.a.s. there are infinitely many
values of n for which there exists a graph G on n vertices for which the following
holds:
(i) G e g ,
(ii) G £ Q ,
(hi) Pr[(GUM*) G2] 2a,
(iv) Pr[(GuG(n^p))eQ] a .
What the theorem says, intuitively, is that in the case of a coarse threshold one
can find two graphs, G and M as follows: G is a fixed graph on n vertices that is
not a random graph but rather a pseudorandom graph, typical of G(n,p) (actually
a random choice of G G G(n,p) \ Q will work with probability close to 1); M is
a "magical" balanced graph such that it is often the case that adding a random
copy of M to G induces the property in question, whereas increasing the number
of edges in G randomly by a constant proportion £ does not induce the property.
The addition of a copy of M corresponds roughly to inducing a local property, in
contrast to increasing the number of edges which corresponds roughly to increasing
the global density of a random graph. Therefore the conclusion of the hypotheses
of the theorem is that the property Q is "statistically local".
Previous Page Next Page