We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A randomized version of Ramsey's theorem.
- Authors
Gugelmann, Luca; Person, Yury; Steger, Angelika; Thomas, Henning
- Abstract
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
- Publication
Random Structures & Algorithms, 2012, Vol 41, Issue 4, p488
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20449