A randomized version of Ramsey's theorem

The standard randomization of Ramsey's theorem asks for a fixed graph F and a fixed number r of colors: for what densities p = p ( n ) can we asymptotically almost surely color the edges of the random graph G ( n , p ) with r colors without creating a monochromatic copy of F . This question was solved in full generality by Rödl and Ruciński [Combinatorics, Paul Erdős is eighty, vol. 1, 1993, 317–346; J Am Math Soc 8(1995), 917–942]. In this paper we consider a different randomization that was recently suggested by Allen et al. [Random Struct Algorithms, in press]. Let \documentclass{article} \usepackage{amsmath,amsfonts} \pagestyle{empty} \begin{document}${{\mathcal R}_F(n,q)}$\end{document} be a random subset of all copies of F on a vertex set V n of size n , in which every copy is present independently with probability q . For which functions q = q ( n ) can we color the edges of the complete graph on V n with r colors such that no monochromatic copy of F is contained in \documentclass{article} \usepackage{amsmath,amsfonts} \pagestyle{empty} \begin{document}${{\mathcal R}_F(n,q)}$\end{document} ? We answer this question for strictly 2‐balanced graphs F . Moreover, we combine bsts an r ‐edge‐coloring of G ( n , p )oth randomizations and prove a threshold result for the property that there exi such that no monochromatic copy of F is contained in \documentclass{article} \usepackage{amsmath,amsfonts} \pagestyle{empty} \begin{document}${{\mathcal R}_F(n,q)}$\end{document} . © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012