Percolation in lattice k-neighbor graphs

Jahnel, Benedikt and Köppl, Jonas and Lodewijks, Bas and Tóbiás, András József (2025) Percolation in lattice k-neighbor graphs. JOURNAL OF APPLIED PROBABILITY. ISSN 0021-9002 (In Press)

Text percolation-in-lattice-k-neighbor-graphs.pdf - Published Version Restricted to Repository staff only Download (695kB) | Request a copy

Abstract

We define a random graph obtained by connecting each point of independently and uniformly to a fixed number 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 the vertices in at least one, respectively precisely two, directions. For 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 even the undirected k -neighbor graph never percolates, while the directed k -neighbor graph percolates whenever , , and , or and . We also show that the undirected 2-neighbor graph percolates for , the undirected 3-neighbor graph percolates for , 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 k -nearest-neighbor graphs studied in continuum percolation, and our results support this interpretation.

Actions (login required)

Edit Item