Clairvoyant embedding in one dimension. Issue 3 (13th June 2014)

• Record Type: Journal Article
• Authors: Gács, Peter
• Is Part Of: Random structures & algorithms. Volume 47:Issue 3(2015)
• Page Start: 520
• Page End: 560
• Publication Date: 2014-06-13
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20551
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let <italic>v, w</italic> be infinite 0‐1 sequences, and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqtx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mover accent="true"><mml:mi>m</mml:mi><mml:mo>˜</mml:mo></mml:mover></mml:math></alternatives></inline-formula> a positive integer. We say that <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqsc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>w</mml:mi></mml:math></alternatives></inline-formula> is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqw1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mover accent="true"><mml:mi>m</mml:mi><mml:mo>˜</mml:mo></mml:mover></mml:math></alternatives></inline-formula>‐<italic>embeddable</italic> in <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqvg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>v</mml:mi></mml:math></alternatives></inline-formula>, if there exists an increasing sequence <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqn5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>n</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>:</mml:mo><mml:mi>i</mml:mi><mml:mo>≥</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> of integers with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqpq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>n</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>, such that <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqq8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>1</mml:mn><mml:mo>≤</mml:mo><mml:msub><mml:mi>n</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>−</mml:mo><mml:msub><mml:mi>n</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>≤</mml:mo><mml:mover accent="true"><mml:mi>m</mml:mi><mml:mo>˜</mml:mo></mml:mover></mml:mrow></mml:math></alternatives></inline-formula>, <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqrt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>w</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>i</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>v</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>n</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> for all <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqmm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>i</mml:mi><mml:mo>≥</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. Let <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr72" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>X</mml:mi></mml:math></alternatives></inline-formula> and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr6h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Y</mml:mi></mml:math></alternatives></inline-formula> be coin‐tossing sequences. We will show that there is an <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr5z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mover accent="true"><mml:mi>m</mml:mi><mml:mo>˜</mml:mo></mml:mover></mml:math></alternatives></inline-formula> with the property that <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr4d" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Y</mml:mi></mml:math></alternatives></inline-formula> is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr3v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0014" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mover accent="true"><mml:mi>m</mml:mi><mml:mo>˜</mml:mo></mml:mover></mml:math></alternatives></inline-formula>‐embeddable into <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr29" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20551:rsa20551-math-0015" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>X</mml:mi></mml:math></alternatives></inline-formula> with positive probability. This answers a question that was open for a while. The proof generalizes somewhat the hierarchical method of an earlier paper of the author on dependent percolation. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 520–560, 2015</p> </abstract>