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).
Previous Page Next Page