We consider the problem of embedding one i.i.d. collection of Bernoulli random variables indexed by @math into an independent copy in an injective @math -Lipschitz manner. For the case @math , it was shown by Basu and Sly (PTRF, 2014) to be possible almost surely for sufficiently large @math . In this paper we provide a multi-scale argument extending this result to higher dimensions.
We prove several facts concerning Lipschitz percolation, including the following. The critical probability p_L for the existence of an open Lipschitz surface in site percolation on Z^d with d 2 satisfies the improved bound p_L 1-1 [8(d-1)]. Whenever p > p_L, the height of the lowest Lipschitz surface above the origin has an exponentially decaying tail. The lowest surface is dominated stochastically by the boundary of a union of certain independent, identically distributed random subsets of Z^d. As a consequence, for p sufficiently close to 1, the connected regions of Z^ d-1 above which the surface has height 2 or more exhibit stretched-exponential tail behaviour.    We consider critical site percolation on the triangular lattice, that is, we choose @math or 1 with probability 1 2 each, independently for all vertices @math of the triangular lattice. We say that a word @math is seen in the percolation configuration if there exists a selfavoiding path @math on the triangular lattice with @math . We prove that with probability 1 "almost all" words, as well as all periodic words, except the two words @math and @math , are seen. "Almost all" words here means almost all with respect to the measure @math under which the @math are i.i.d. with @math (for an arbitrary @math ).  There exists a Lipschitz embedding of a d-dimensional comb graph (consisting of infinitely many parallel copies of Z^ d-1 joined by a perpendicular copy) into the open set of site percolation on Z^d, whenever the parameter p is close enough to 1 or the Lipschitz constant is sufficiently large. This is proved using several new results and techniques involving stochastic domination, in contexts that include a process of independent overlapping intervals on Z, and first-passage percolation on general graphs. Does there exist a Lipschitz injection of ℤd into the open set of a site percolation process on ℤD, if the percolation parameter p is sufficiently close to 1? We prove a negative answer when d = D and also when d ≥ 2 if the Lipschitz constant M is required to be 1. Earlier work of Dirr, Dondl, Grimmett, Holroyd and Scheutzow yields a positive answer for d < D and M = 2. As a result, the above question is answered for all d, D and M. Our proof in the case d = D uses Tucker’s lemma from topological combinatorics, together with the aforementioned result for d < D. One application is an affirmative answer to a question of Peled concerning embeddings of random patterns in two and more dimensions.  A number of tricky problems in probability are discussed, having in common one or more infinite sequences of coin tosses, and a representation as a problem in dependent percolation. Three of these problems are of Winkler' type, that is, they ask about what can be achieved by a clairvoyant demon.