Clairvoyant embedding in one dimension. Issue 3 (13th June 2014) - Gács, Peter
Abstract Let v, w be infinite 0‐1 sequences, and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqtx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m˜</alternatives> a positive integer. We say that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqsc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />w</alternatives> is <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqw1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m˜</alternatives>‐embeddable in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqvg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />v</alternatives>, if there exists an increasing sequence <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqn5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(ni:i≥0)</alternatives> of integers with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqpq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n0=0</alternatives>, such that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqq8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />1≤ni−ni−1≤m˜</alternatives>, <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqrt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />w(i)=v(ni)</alternatives> for all <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsqmm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />i≥1</alternatives>. Let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr72" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />X</alternatives> and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr6h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Y</alternatives> be coin‐tossing sequences. We will show that there is an <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr5z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m˜</alternatives> with the property that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr4d" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Y</alternatives> is <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr3v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />m˜</alternatives>‐embeddable into <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tsr29" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />X</alternatives> 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