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