Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2007-02

January 2007

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

M. Marciniszyn, J. Skokan, R. Spöhel, A. Steger

Consider the following problem: For given graphs G and F1,..., Fk, find a coloring of the edges of G with k colors such that G does not contain Fi in color i. Rödl and Rucinski studied this problem for the random graph Gn, p in the symmetric case when k is fixed and F1=...=Fk=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). 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. Kohayakawa and Kreuter conjectured a threshold function n-β(F1,..., Fk) for arbitrary F1,..., Fk.

In this paper we address the case when F1,..., Fk are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of Gn, p with

p < bn-β
for some constant b = b(F1,..., Fk). This algorithm also extends to the symmetric case. We also show that there exists a constant B = B(F1,..., Fk) such that for
p > Bn-β,
the random graph Gn, p a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds.

A PDF file (424 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2007-02, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk 

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2007