2. OUTLINE OF THE PROOF

7

• At the end of the paper we include a glossary of symbols and definitions

as well as a flowchart of constants exhibiting their mutual dependencies.

We strongly encourage the reader to make use of both when struggling

through our proof.

Notation: In Sections 4-6 we use the following notation. For 0 e 1, and

positive reals x, y,

x ~ y denotes that (1 — e)y x (1 + e)y.

We will often abbreviate it further as follows: if e' is any function of e that tends

to zero with e, and x ~ ?/, then we will simply write x « y.

Let G = (V,E) be a graph, v, u G V and W C V. We write eG(W) = \E{G[W})\

for the number of edges in the subgraph of G induced by W, degG(v,W) =

deg(v,W) for the number of neighbors of v in W, degG(f) = deg(i) = deg(f, V),

for the degree of v in G, and codeg(t, u) for the number of common neighbors of

u and v in G, called the co-degree of i and u. The set of neighbors of v in G is

denoted by NG{V) = AT(w), while A^c(W) stands for the set of vertices outside W,

each having at least one neighbor in W (so called open neighborhood of W).

For a family of sets (Ai)iei, we call a set T a hitting set if Tfl Ai ^ 0 for all i E L

We will often use set partitions V = Vi U ... U T4, where |Vi| ... \Vt\ \Vi\ + 1.

Such partitions will be called here equipartitions. Finally, all logarithms are natural

and will be denoted by log.

2. Outline of the Proof

2.1. Main steps. Recall that 1Z is the graph property that for every blue-red

coloring of the edges of a graph there exists a monochromatic triangle. Graphs that

have this property will be called Ramsey graphs. For a non-Ramsey graph, we call

a coloring that does not have a monochromatic triangle a triangle-free coloring.

We wish to prove that 1Z has a sharp threshold. By Theorem 1.2, there exist

constants C2 and C2 such that any threshold p for 1Z satisfies

C2/y/n p C2/Vn.

This means that when applying Theorem 1.3 to Property 7Z we may restrict our-

selves to sequences p = p(n) falling into this range, and consequently to balanced

graphs M with p(M) — 2 (i.e. average degree 4.) Thus it suffices to prove the fol-

lowing result, which is a mere adaptation of Theorem 1.3 to our case. (In fact, it is

slightly stronger, since the inequality in (iv) is replaced in (4) below by convergence

to 1.)

THEOREM

2.1. For all a,£ 0, all sequences

C2/Vn p = p(n) C2/Vn

and all balanced graphs M with p(M) — 2, there exists a graph property Q with

limn_,oo Pr[G(n,p) € G] = 1, and an integer n\, such that for all G £ Q \1Z with

\V(G)\=nnlfif

(3) Pr[G UM* eK}2a

then

(4)

Pr[(G U G(n, &)) eTZ] = l - o(l).