UC Berkeley

More than twenty years ago Peter Winkler introduced a fascinating class of dependent or “co-ordinate” percolation models with his compatible sequences and clairvoyant demon scheduling problems. These, and other problems in this class, can be interpreted either as problems of embedding one sequence into another according to certain rules or as oriented percolation problems in two dimensions where the sites are open or closed according to random variables on the co-ordinate axes. In most situations, these problems are not tractable by the usual tools of independent Bernoulli percolation, and new methods are required. We study several problems in this class and their natural extensions.

We develop a new multi-scale framework flexible enough to solve a number of problems involving embedding random sequences into random sequences. A natural question in this class was considered by Grimmett, Liggett and Richthammer; they asked whether there exists an increasing $M$-Lipschitz embedding from one i.i.d. Bernoulli sequence into an independent copy with positive probability. We give a positive answer for large enough $M$. A closely related problem is to show that

two independent Poisson processes on the real line are almost surely roughly isometric (or quasi-isometric). Our approach also applies in this case answering a conjecture of Szegedy and of Peled. We also obtain a new proof for Winkler's compatible sequence problem. All these results are obtained as corollaries to an abstract embedding result that can potentially be applied to a number of one-dimensional embedding questions.

We build upon the central idea of the multi-scale construction in the above work to apply it to a different problem. On the complete graph with $M \geq 3$ vertices consider two independent discrete

time random walks $\mathbb{X}$ and $\mathbb{Y}$, choosing their steps uniformly at random. We say that it is possible to {\textbf{schedule}} a pair of trajectories $\mathbb{X}= \{X_1, X_2, \ldots\}$ and $\mathbb{Y}=\{Y_1, Y_2, \ldots \}$, if by delaying their jump times one can keep both walks at distinct vertices forever. It was conjectured by Winkler that for large enough $M$ the set of pairs of trajectories $\{\mathbb{X}, \mathbb{Y}\}$ that can be scheduled has positive measure. Noga Alon translated this problem to the language of coordinate percolation. In this representation Winkler's

conjecture is equivalent to the existence of an infinite open cluster for large enough $M$. With a multi-scale construction we provide a positive answer for $M$ sufficiently large.

The questions of Lipschitz embedding and rough isometry of random sequences have natural higher dimensional analogues. We consider the higher dimensional analogue of the Lipschitz embedding problem. We show that for $M$ sufficiently large and two independent collections of i.i.d.\ Bernoulli random variables $\mathbb{X}=\{X_v\}_{v\in \mathbb{Z}^2}$ and $\mathbb{Y}=\{Y_{v}\}_{v\in \mathbb{Z}^2}$, almost surely there exists an $M$-Lipschitz embedding of $\mathbb{X}$ into $\mathbb{Y}$. The argument is again multi-scale using similar ideas, but this is technically much more challenging because of the more complicated geometry in two dimensions.

This presents an added difficulty in extending the argument in one dimension to show that copies of two dimensional Poisson processes are almost surely rough isometric. A key ingredient is to show that one can map measurable sets to smaller measurable sets in a bi-Lipschitz manner. This motivates the final problem we consider. We show that for $0<\gamma, \gamma'<1 $ and for measurable subsets of the unit square with Lebesgue measure $\gamma$ there exist bi-Lipschitz maps with bounded Lipschitz constant(uniformly over all such sets) which are identity on the boundary and increases the Lebesgue measure of the set to at least $1-\gamma'$.