Percolating paths through random points :

David Aldous, Maxim Krikun

Published 2005-09-21Version 1

We prove consistency of four different approaches to formalizing the idea of minimum average edge-length in a path linking some infinite subset of points of a Poisson process. The approaches are (i) shortest path from origin through some $m$ distinct points; (ii) shortest average edge-length in paths across the diagonal of a large cube; (iii) shortest path through some specified proportion $\delta$ of points in a large cube; (iv) translation-invariant measures on paths in $\Reals^d$ which contain a proportion $\delta$ of the Poisson points. We develop basic properties of a normalized average length function $c(\delta)$ and pose challenging open problem