2

E. FRIEDGUT, V. RODL, A. RUCINSKI, AND P. TETALI

THEOREM

1.1. There exists a function c = c(n) = 6(1) such that for every

a) .^pt(G(„,weK1={j z^-Mt

There is a slightly disappointing aspect of this result: although we prove that

d(n) is bounded, the natural conjecture is that c(n) converges to a positive limit,

and this does not follow from our theorem. Unfortunately, an inherent property

of the technique we use is that it can only supply such existence theorems but no

new information as to the exact threshold probability. We discuss various possible

extensions of Theorem 1.1 in Section 7.

1.2. Ramsey Properties of Random Graphs. Let us introduce the arrow

notation, commonly used in Ramsey theory. For two graphs, H and G, and an

integer r 2, we write G — (H)r if for every coloring of the edges of G by r

colors there exists a monochromatic copy of H. For example, it is well known that

KQ — (^3)2- Let 1Z be the set of all graphs G such that G — (#3)2.

A basic question studied in Ramsey theory is, given a graph H and an integer

r 2, when is G "rich" enough for G — (H)r? Here richness can be interpreted

either as the number of edges of G, or as the ratio of edges to vertices.

In modern graph theory, problems of this type are often studied via ran-

dom graphs. The theory of random graphs addresses questions concerning typi-

cal graphs, or graphs "on average". The standard model for a random graph is

G(n,p), a graph on n vertices, where every one of the (™) edges of the complete

graph belongs to G(n,p) independently, with probability p. When studying ran-

dom graphs a natural problem is: Given H, find a threshold function p{n) such that

G(n,p) — (H)r with probability tending to 1 when p(n) ^ p and G(n,p) — (H)r

with probability tending to 0 when p(n) C p. (The existence of such a threshold

function is guaranteed by a general result of Bollobas and Thomason [4].)

In a series of papers [11, 27, 29, 30, 31], a threshold function p(n) is deter-

mined for all graphs H. Its culmination, paper [31], establishes p = n

_ 1

/

m

^

as a threshold for G(n,p) — (i/)

r

, regardless of r, for all H which are not star

forests. Here m^(H) = maxFc#(\E(F)\ - 1)/(|V(F)| - 2). An analogous result

in the case when the vertices (and not the edges) are colored is given in [27]. In the

edge-coloring setting, the first case to be settled was that of triangles (not counting

star forests which are rather trivial).

THEOREM

1.2 ([30]). For every integer r 2 there exist constants cr and Cr

such that

(2) ^ P r [ G ( n ,

P

) ^ ( K

3

) , ] = { ; ^ £ ^

Remark: In the above theorem, and throughout the paper G(n,p) is usually

meant to denote G(n,p(n)), hence the limits, and asymptotic notations. As we can

see, for a range of p, namely for cr/y/n p Cr/y/n this statement is inconclu-

sive. Similarly, in all the papers mentioned above there is a multiplicative gap left

between the upper and lower bound on the threshold edge probability p(n).

In a recent paper [10] it was shown that in many cases this gap can be closed,

using a general technique from [8] for proving sharpness of thresholds. The cases