Upper bounds on probability thresholds for asymmetric Ramsey properties. Issue 1 (18th July 2012)

• Record Type: Journal Article
• Authors: Kohayakawa, Yoshiharu; Schacht, Mathias; Spöhel, Reto
• Is Part Of: Random structures & algorithms. Volume 44:Issue 1(2014)
• Page Start: 1
• Page End: 28
• Publication Date: 2012-07-18
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20446
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Given two graphs <italic>G</italic> and <italic>H</italic>, 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" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20446:rsa20446-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mi>p</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></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" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20446:rsa20446-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>G</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>, </mml:mo><mml:mi>p</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives> (the binomial random graph on <italic>n</italic> vertices with edge probability <italic>p</italic>) satisfies with probability <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3z37hb33" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20446:rsa20446-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives> that every red‐blue‐coloring of its edges contains a red copy of <italic>G</italic> or a blue copy of <italic>H</italic>. 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 <italic>G</italic> and <italic>H</italic> 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 <italic>G</italic> = <italic>H</italic>), and has been used in many proofs of similar results since then.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 1–28, 2014</p> </abstract>