Threshold Functions for Asymmetric Ramsey Properties Involving Cliques

Consider the following problem: For given graphs

G

and

F

1

,...,

F

k

, find a coloring of the edges of

G

with

k

colors such that

G

does not contain

F

i

in color

i

. For example, if every

F

i

is the path

P

3

on 3 vertices, then we are looking for a proper

k

-edge-coloring of

G

, i.e., a coloring of the edges of

G

with no pair of edges of the same color incident to the same vertex.

Rödl and Ruciński studied this problem for the random graph

G

$_{n,{\it p}}$

in the symmetric case when

k

is fixed and

F

1

=...=

F

k

=

F

. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that

p

≤

bn

 − β

for some constants

b

=

b

(

F

,

k

) and

β

=

β

(

F

). Their proof was, however, non-constructive. This result is essentially best possible because for

p

≥

Bn

 − β

, where

B

=

B

(

F

,

k

) is a large constant, such an edge-coloring does not exist. For this reason we refer to

n

 − β

as a

threshold function

.

In this paper we address the case when

F

1

,...,

F

k

are cliques of different sizes and propose an algorithm that a.a.s. finds a valid

k

-edge-coloring of

G

n

,

p

with

p

≤

bn

 − β

for some constants

b

=

b

(

F

1

,...,

F

k

,

k

) and

β

 = 

β

(

F

1

,...,

F

k

). Kohayakawa and Kreuter conjectured that

$n^{-\beta(F_1,\dots, F_k)}$

is a threshold function in this case. This algorithm can be also adjusted to produce a valid

k

-coloring in the symmetric case.