Percolation in lattice k-neighbor graphs
Authors
- Jahnel, Benedikt
ORCID: 0000-0002-4212-0065 - Köppl, Jonas
ORCID: 0000-0001-9188-1883 - Lodewijks, Bas
ORCID: 0000-0002-8231-0736 - Tóbiás, András
2020 Mathematics Subject Classification
- 60K35 82B4
Keywords
- Lattice k-neighbor graphs, directed k-neighbor graph, undirected k-neighbor graph, bidirectional k-neighbor graph, 1-dependent percolation, oriented percolation, negatively correlated percolation models, connective constant, planar duality, coexistence of phases
DOI
Abstract
We define a random graph obtained via connecting each point of ℤ d independently to a fixed number 1 ≤ k ≤ 2d of its nearest neighbors via a directed edge. We call this graph the emphdirected k-neighbor graph. Two natural associated undirected graphs are the emphundirected and the emphbidirectional 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≥ d+1, k≥ 3 and d ≥5, or k ≥4 and d=4. 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 k-nearest-neighbor graphs studied in continuum percolation, and our results support this interpretation.
Download Documents