**Almost optimal sparsification of random geometric graphs.**N. Broutin, L. Devroye, and G. Lugosi. Submitted (26 pages), 2014. [arXiv:1403.1274] [±]

A random geometric irrigation graph $\Gamma_n(r_n,\xi)$ has $n$ vertices identified by $n$ independent uniformly distributed points $X_1,\ldots,X_n$ in the unit square $[0,1]^2$. Each point $X_i$ selects $\xi_i$ neighbors at random, without replacement, among those points $X_j$ ($j\neq i$) for which $\|X_i-X_j\| \le r_n$, and the selected vertices are connected to $X_i$ by an edge. The number $\xi_i$ of the neighbors is an integer-valued random variable, chosen independently with identical distribution for each $X_i$ such that $\xi_i$ satisfies $1\le \xi_i \le \kappa$ for a constant $\kappa>1$. We prove that when $r_n = \gamma_n \sqrt{\log n/n}$ for $\gamma_n \to \infty$ with $\gamma_n =o(n^{1/6}/\log^{5/6}n)$, then the random geometric irrigation graph experiences \emph{explosive percolation} in the sense that when $\mathbf E \xi_i=1$, then the largest connected component has size $o(n)$ but if $\mathbf E \xi_i >1$, then the size of the largest connected component is with high probability $n-o(n)$. This offers a natural non-centralized sparsification of a random geometric graph that is mostly connected.

**Connectivity of sparse Bluetooth networks.**N. Broutin, L. Devroye, and G. Lugosi. Submitted (12 pages), 2014. [arXiv:1402.3696] [±]

Consider a random geometric graph defined on $n$ vertices uniformly
distributed in the $d$-dimensional unit torus. Two vertices are connected
if their distance is less than a ``visibility radius'' $r_n$.
We consider *Bluetooth networks* that are locally sparsified random
geometric graphs. Each vertex selects $c$ of its neighbors in the random
geometric graph at random and connects only to the selected points.
We show that if the visibility radius is at least of the order of
$n^{-(1-\delta)/d}$ for some $\delta > 0$, then a constant value of $c$
is sufficient for the graph to be connected, with high probability.
It suffices to take $c \ge \sqrt{(1+\epsilon)/\delta} + K$ for any
positive $\epsilon$ where $K$ is a constant depending on $d$ only. On
the other hand, with $c\le \sqrt{(1-\epsilon)/\delta}$, the graph is
disconnected with high probability.

**Efficiently navigating a random Delaunay triangulation.**N. Broutin, O. Devillers, and R. Hemsley. Submitted (46 p), 2014. [hal-00940743] [±]

Planar graph navigation is an important problem with significant implications
to both point location in geometric data structures and routing in networks.
However, whilst a number of algorithms and existence proofs have been
proposed, very little analysis is available for the properties of the paths
generated and the computational resources required to generate them under a
random distribution hypothesis for the input. In this paper we analyse a
new deterministic planar navigation algorithm with constant competitiveness
which follows vertex adjacencies in the Delaunay triangulation. We call this
strategy *cone walk*. We prove that given $n$ uniform points in a smooth
convex domain of unit area, and for any start point $z$ and query point $q$;
cone walk applied to $z$ and $q$ will access at most $O(|zq|\sqrt{n} +\log^7
n)$ sites with complexity $O(|zq|\sqrt{n} \log \log n + \log^7 n)$ with
probability tending to 1 as $n$ goes to infinity. We additionally show that in
this model, cone walk is $(\log ^{3+\xi} n)$-memoryless with high probability
for any pair of start and query point in the domain, for any positive $\xi$.
We take special care throughout to ensure our bounds are valid even when the
query points are arbitrarily close to the border.

**The scaling limit of the minimum spanning tree of a complete graph.**L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont. Submitted (60 p), 2013. [aXv:1301.1664] [±]

Consider the minimum spanning tree of the complete graph with $n$ vertices, when edges are assigned independent random weights. We show that, when this tree is endowed with the graph distance renormalized by $n^{1/3}$ and with the uniform measure on its vertices, the resulting space converges in distribution as $n\to\infty$ to a random limiting metric space in the Gromov--Hausdorff--Prokhorov topology. We show that this space is a random binary $\mathbb R$-tree and has Minkowski dimension $3$ almost surely. In particular, its law is mutually singular with that of the Brownian continuum random tree or any rescaled version thereof. Our approach relies on a coupling between the minimum spanning tree problem and the Erdös--Rényi random graph, and the explicit description of its scaling limit in the so-called critical window.