1. INTRODUCTION

3

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.

DEFINITION

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

,

n~1//2

and

n~2//5.

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.

DEFINITION

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.