Percolation in lattice k-neighbor graphs

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.