WIAS Preprint No. 2774, (2020)

Absence of percolation in graphs based on stationary point processes with degrees bounded by two


  • Jahnel, Benedikt
    ORCID: 0000-0002-4212-0065
  • Tóbiás, András

2010 Mathematics Subject Classification

  • 82B43 60G55 60K35


  • Continuum percolation, stationary point processes, degree bounds, bidirectional k-nearest neighbor graph, edge-preserving property, signal-to-interference ratio




We consider undirected graphs that arise as deterministic functions of stationary point processes such that each point has degree bounded by two. For a large class of point processes and edge-drawing rules, we show that the arising graph has no infinite connected component, almost surely. In particular, this extends our previous result for SINR graphs based on stabilizing Cox point processes and verifies the conjecture of Balister and Bollobás that the bidirectional $k$-nearest neighbor graph of a two-dimensional homogeneous Poisson point process does not percolate for k=2.

Appeared in

  • Random Structures Algorithms, published online on 30.03.2022 (2022), DOI 10.1002/rsa.21084 .

Download Documents