Uniqueness and full coverage in k-neighbor graphs
Abstract
We study the number of infinite clusters in the 2dp-neighbor graph on ℤd, d≥2, in which every vertex independently selects ⌊ 2dp⌋ of its nearest neighbors uniformly at random, and one more with probability 2dp−⌊ 2dp⌋. The model has negatively correlated edges and, for 1≤2dp≤2d−1, neither finite energy nor insertion or deletion tolerance. We prove that the undirected graph has at most one infinite cluster for every p∈ [0,1], and that in the planar case the same holds for forward and strong forward clusters of the directed graph when p∈[1/2,1]. We further exhibit a second phase transition: for p≥(d+1)/(2d) the open cluster of the origin is almost surely the whole lattice, and for p>(d+1)/(2d) any two vertices of a box are connected inside the box of twice the size with probability exponentially close to one. In particular, the percolation function is continuous but not analytic on the supercritical interval (pc,1]. Finally, we prove that the full-coverage phase transition at pf = (d+1)/2d is of order 2d.
Related
- 2-Neighbor Bootstrap Percolation on Odd Graphs
- Rich-neighbor 5-edge-colorings of subcubic graphs whose 3-vertices induce a matching
- Conditional Mean Independence, Global Sensitivity Analysis, and Variable Screening Using nearest neighbor Graphs
- A proof of Lehmer's permutation conjecture for neighbor-swap graphs
- Weak uniqueness for the stochastic heat equation with nondegenerate diffusion: the full Hölder regime
BibTeX
@misc{coupier2026uniqueness,
title = {{Uniqueness and full coverage in $k$-neighbor graphs}},
author = {David Coupier and Benoît Henry and Benedikt Jahnel and Jonas Köppl},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06800},
eprint = {2611.06800},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06800},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Uniqueness and full coverage in k-neighbor graphs
AU - David Coupier
AU - Benoît Henry
AU - Benedikt Jahnel
AU - Jonas Köppl
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06800
UR - https://arxiv.org/abs/2611.06800
AB - We study the number of infinite clusters in the 2dp-neighbor graph on ℤ^d, d≥2, in which every vertex independently selects ⌊ 2dp⌋ of its nearest neighbors uniformly at random, and one more with probability 2dp−⌊ 2dp⌋. The model has negatively correlated edges and, for 1≤2dp≤2d−1, neither finite energy nor insertion or deletion tolerance. We prove that the undirected graph has at most one infinite cluster for every p∈ [0,1], and that in the planar case the same holds for forward and strong forward clusters of the directed graph when p∈[1/2,1]. We further exhibit a second phase transition: for p≥(d+1)/(2d) the open cluster of the origin is almost surely the whole lattice, and for p>(d+1)/(2d) any two vertices of a box are connected inside the box of twice the size with probability exponentially close to one. In particular, the percolation function is continuous but not analytic on the supercritical interval (p_c,1]. Finally, we prove that the full-coverage phase transition at p_f = (d+1)/2d is of order 2^d.
ER -