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. Roedl and Rucinski studied this problem for the random graph G_(n,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~(-β(F_1,...,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.