WIAS Preprint No. 3028, (2023)

Percolation in lattice k-neighbor graphs


  • 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


  • 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




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