## The stretch-length tradeoff in spatial networks

Here is the abstract of Aldous-Lando (2015).
Consider a network linking the points of a rate-1 Poisson point process on the plane. Write $$\Psi^{ave}(s)$$ for the minimum possible mean length per unit area of such a network, subject to the constraint that the route-length between every pair of points is at most $$s$$ times the Euclidean distance. We give upper and lower bounds on the function $$\Psi^{ave}(s)$$, and on the analogous "worst-case" function $$\Psi^{worst}(s)$$ where the point configuration is arbitrary subject to average density one per unit area. Our bounds are numerically crude, but raise the question of whether there is an exponent $$\alpha$$ such that each function has $$\Psi(s) \asymp (s-1)^{- \alpha} \mbox{ as } s \downarrow 1$$.
One problem is to improve the explicit bounds: upper bounds require a construction, and lower bounds require some kind of "stochastic geometry" argument. Here is one improvement by Haoyu Wang. A more familiar kind of "theory" problem is to prove existence of the exponent $$\alpha$$ in that dense network limit.

Back to Open Problem list