Upper bounds on probability thresholds for asymmetric Ramsey properties. Issue 1 (18th July 2012) - Kohayakawa, Yoshiharu; Schacht, Mathias; Spöhel, Reto
Abstract Given two graphs G and H, we investigate for which functions <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3z37hb10" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=p(n)</alternatives> the random graph <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3z37hb2j" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Gn, p</alternatives> (the binomial random graph on n vertices with edge probability p) satisfies with probability <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3z37hb33" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />1−o(1)</alternatives> that every red‐blue‐coloring of its edges contains a red copy of G or a blue copy of H. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which G and H are complete graphs of arbitrary size. In our proof we present an alternative to the so‐called deletion method, which was introduced by Rödl and Ruciński in their study of symmetric Ramsey properties of random graphs (i.e. the case G = H), and has been used in many proofs of similar results since then.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 1–28, 2014