Asymmetric Ramsey properties of random graphs involving cliques

Author(s)

Marciniszyn‚ M. ; Skokan‚ J. ; Spöhel‚ R. ; Steger‚ A.

• Document type: Journal article
• Source: RANDOM STRUCTURES & ALGORITHMS; v. 34, n. 4, p. 419-453, 2009.

Abstract

Consider the following problem: Forgiven 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; in color i. Rodl and Rucinski studied this problem for the random graph G,,, 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(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn-beta, where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F-1, ..., F-k. In this article 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(-beta) for some constant b = b(F-1,..., F-k), where beta = beta(F-1,..., F-k) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn-beta the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009 (AU)

• FAPESP's process: 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures
• Grantee: Yoshiharu Kohayakawa
• Support Opportunities: PRONEX Research - Thematic Grants