CS17: Dependent Percolation Models: Discrete and Continuum

Organizer: Bas Lodewijks (University of Augsburg)

Percolation in lattice k-neighbor graphs

András Tóbiás

We define a random graph obtained via connecting each point of \(\mathbb Z^d\) independently to a fixed number \(1 \leq k \leq 2d\) of its nearest neighbors via a directed edge. We call this graph the directed \(k\)-neighbor graph. Two natural associated undirected graphs are the undirected and the bidirectional \(k\)-neighbor graph, where we connect two vertices by an undirected edge whenever there is a directed edge in the directed \(k\)-neighbor graph between them in at least one, respectively precisely two, directions. In these graphs we study the question of percolation, i.e., the existence of an infinite self-avoiding path. Using different kinds of proof techniques for different classes of cases, we show that for \(k=1\) even the undirected \(k\)-neighbor graph never percolates, but the directed one percolates whenever \(k \geq d+1\). Our main result is the following.

Theorem. The directed \(k\)-neighbor graph percolates when \(k \geq 3\) and \(d \geq 5\), or \(k=d=4\).

The proof of this result is based on a technique developed by Cox and Durrett \([2]\) (1983) for verifying the existence of an infinite oriented path in higher-dimensional oriented percolation.

We also show that the undirected 2-neighbor graph percolates for \(d=2\), the undirected 3-neighbor graph percolates for \(d=3\), and we provide some positive and negative percolation results regarding the bidirectional graph as well. A heuristic argument for high dimensions indicates that this class of models is a natural discrete analogue of the -nearest-neighbor graphs studied in continuum percolation, and our results support this interpretation.

Percolation in the directed graph for \(k=d=2\) has recently been proven by Coupier, Henry, Jahnel and Köppl \([1]\), which will be explained in another talk of our contributed session by Jonas Köppl.

Bibliography

\([1]\) David Coupier, Benoît Henry, Benedikt Jahnel and Jonas Köppl (2024). “The planar lattice two-neighbor graph percolates.” arXiv:2412.20781, 45 pp.

\([2]\) Theodore Cox and Richard Durrett (1983). “Oriented percolation in dimensions \(d \geq 4\): bounds and asymptotic formulas.” Math. Proc. Camb. Phil. Soc., vol. 93, pp. 151–162.