# Fluctuations of the connectivity threshold and largest nearest-neighbour
link

Mathew D. Penrose and Xiaochuan Yang
University of Bath and Brunel University

(August 31, 2024)

###### Abstract

Consider a random uniform sample of $n$ points in a compact region $A$ of
Euclidean $d$-space, $d\geq 2$, with a smooth or (when $d=2$) polygonal
boundary. Fix $k\in\mathbb{N}$. Let $T_{n,k}$ be the threshold $r$ at which
the geometric graph on these $n$ vertices with distance parameter $r$ becomes
$k$-connected. We show that if $d=2$ then $n(\pi/|A|)T_{n,1}^{2}-\log n$ is
asymptotically standard Gumbel. For $(d,k)\neq(2,1)$, it is
$n(\theta_{d}/|A|)T_{n,k}^{d}-(2-2/d)\log n-(4-2k-2/d)\log\log n$ that
converges in distribution to a nondegenerate limit, where $\theta_{d}$ is the
volume of the unit ball. The limit is Gumbel with scale parameter 2 except
when $(d,k)=(2,2)$ where the limit is two component extreme value distributed.
The different cases reflect the fact that boundary effects are more more
important in some cases than others. We also give similar results for the
largest $k$-nearest neighbour link $U_{n,k}$ in the sample, and show
$T_{n,k}=U_{n,k}$ with high probability. We provide estimates on rates of
convergence and give similar results for Poisson samples in $A$. Finally, we
give similar results even for non-uniform samples, with a less explicit
sequence of centring constants.
Keywords: Connectivity threshold; weak limit; Poisson process; Gumbel
distribution.

###### Contents

  1. 1 Introduction
    1. 1.1 Overview and motivation
    2. 1.2 The largest $k$-nearest-neighbour link
    3. 1.3 Literature review
    4. 1.4 Main results
  2. 2 Geometrical preliminaries
  3. 3 Poisson approximation for the $k$-isolated vertices
  4. 4 Relating the $L_{n,k}$ to $M_{n,k}$
    1. 4.1 Small separating sets
    2. 4.2 Medium sized separating sets
    3. 4.3 Large separating pairs
  5. 5 Proof of Theorem 1.3
    1. 5.1 Proof of Parts (i) and (ii)
    2. 5.2 Proof of Theorem 1.3: Conclusion
  6. 6 Proof of Theorem 1.1

##  1 Introduction

###  1.1 Overview and motivation

This paper is concerned with the threshold at which the random geometric graph
becomes connected. This graph is defined as follows. Let $d\in\mathbb{N}$.
Given a finite set $\mathcal{X}\subset\mathbb{R}^{d}$, and $r>0$, the
geometric graph $G(\mathcal{X},r)$ has vertex set $\mathcal{X}$, with an edge
drawn between any two vertices at Euclidean distance at most $r$ from each
other. We say $G(\mathcal{X},r)$ is $k$-connected if it is not possible to
disconnect the graph by removing $k-1$ or fewer vertices. (in particular,
1-connectivity is the same as connectivity). The $k$-connectivity threshold of
$\mathcal{X}$ is the number

$\displaystyle M_{k}(\mathcal{X}):=\inf\\{r>0:G(\mathcal{X},r)\mbox{ is
$k$-connected}\\}.$

An alternative characterization of $M_{1}(\mathcal{X})$ is in terms of minimal
spanning tree (MST). A MST on $\mathcal{X}$ is a tree spanning $\mathcal{X}$
that minimizes the total (Euclidean) length of the edges. It is not hard to
see that $M_{1}(\mathcal{X})$ equals the longest edge length of a MST on
$\mathcal{X}$.

For the random geometric graph, the vertex set $\mathcal{X}$ is given by the
set of points of a Poisson point process $\mathcal{P}_{n}$ in $\mathbb{R}^{d}$
with intensity measure $n\nu$, where $\nu$ is a probability measure on
$\mathbb{R}^{d}$ with probability density function
$f:\mathbb{R}^{d}\to[0,\infty)$, and $n\in(0,\infty)$ is the mean number of
vertices. Alternatively, for $n\in\mathbb{N}$ we can take
$\mathcal{X}=\mathcal{X}_{n}$, where $\mathcal{X}_{n}$ denotes a binomial
point process whose points are $n$ independent random $d$-vectors with common
density $f$. Since the vertices are placed randomly in $\mathbb{R}^{d}$, the
thresholds $M_{k}(\mathcal{X}_{n})$ and

$\displaystyle
M_{n,k}:=M_{k}(\mathcal{P}_{n})=\inf\\{r>0:G(\mathcal{P}_{n},r)\mbox{ is
$k$-connected}\\}$ (1.1)

are random variables.

In this paper we investigate the limiting behaviour of the connectivity
threshold $M_{n,k}$ and $M_{k}(\mathcal{X}_{n})$ for large $n$ and fixed
$k\in\mathbb{N}$. We assume throughout that $d\geq 2$. We consider a broad
class of measures $\nu$, subject to the working assumption that $\nu$ has
compact support $A\subset\mathbb{R}^{d}$, and its density $f$ is continuous
and bounded away from zero on $A$. As $n$ grows, the spacing between vertices
becomes smaller, so one expects to have $M_{n,k}\to 0$ as $n\to\infty$. A
simple consideration by computing typical spacing of vertices leads to the
belief that $M_{n,k}$ should decay more slowly than $n^{-1/d}$, in the sense
that $nM_{n,k}^{d}$ should tend to infinity in probability. In the special
case where $\nu$ is the uniform distribution on $[0,1]^{d}$, it is known [9,
11, 8], that there is an explicit sequence of centring constants
$(a_{n})_{n\geq 1}$ satisfying $a_{n}\to\infty$ as $n\to\infty$ such that

$\displaystyle
nM_{n,k}^{d}-a_{n}\overset{d}{\longrightarrow}X;\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
nM_{k}(\mathcal{X}_{n})^{d}-a_{n}\overset{d}{\longrightarrow}X,$ (1.2)

where $X$ is an explicit non-degenerate random variable. Clearly (1.2) is what
is needed to determine $\lim_{n\to\infty}\mathbb{P}[M_{n,k}\leq r_{n}]$ for
any sequence $(r_{n})_{n\geq 1}$ such that the limit exists.

In the present paper, we show that (1.2) holds for suitable $a_{n}$ and $X$,
for a broad class of measures $\nu$. While one might perhaps anticipate that
the limiting behaviour of the form (1.2) would carry over from the uniform
distribution on $[0,1]^{d}$ to more general $\nu$ satisfying our working
assumption, proving this seems to be considerably harder that one might
naively expect, and in the last 20 years or so there has been limited progress
in proving such results. It turns out that even in the uniform case where $f$
is constant on $A$, boundary effects are important because the ‘most isolated’
vertex is likely to lie near the boundary when $d\geq 3$. Thus the formula for
$a_{n}$, even when $\nu$ is uniform on $[0,1]^{d}$, is quite complicated (see
(1.9) below) due to having to consider all of the different kinds of faces
making up the boundary, and does not necessarily provide much insight into the
appropriate choice of centring constants for other $A$. In the non-uniform
case, determining appropriate constants $a_{n}$ is even harder because they
depend in a delicate way on how $f$ approaches its minimum, both in the
interior and on the boundary of $A$.

In this work we chiefly consider the case where $\partial A$ is smooth. In the
uniform case we determine an explicit sequence of centring constants $a_{n}$
such that (1.2) holds for suitable $X$. In the non-uniform case we are still
(in most cases) able to derive (1.2) on taking $a_{n}$ to be the median of the
distribution of $nM_{n,k}^{d}$. Part of our proof involves approximating $A$
with a polyhedral set $A_{n}$ with the spacing between vertices of $A_{n}$
decreasing slowly as $n$ becomes large. This technique was developed recently
for a random coverage problem in [15], and its availability is one reason why
this problem is more tractable now than it was before.

We also address the case where $d=2$ and $A$ is polygonal; this case could be
of importance for some applications, and it turns out that boundary effects
are less complicated for $d=2$ than for $d\geq 3$. We hope to deal with the
case of polytopal $A$ in dimension $d\geq 3$ in future work.

Understanding the connectivity threshold is important for a variety of
applications. In telecommunications, the vertices could represent mobile
transceivers and one might be interested in whether the network of
transceivers is connected; see e.g. [3]. In topological data analysis (TDA),
detecting connectivity is a fundamental step for inspecting all other higher
dimensional topological features (here the dimension of the ambient space may
be very high). See also applications in machine learning (clustering),
statistical tests (e.g. for outliers), spatial epidemics or forest fires (see
the description in [9])

Note that (1.2) implies the weaker statement that the sequence
$(nM_{n,k}^{d}-a_{n})_{n\geq 1}$ is tight as $n\to\infty$, and even in the
(rather exceptional) cases where we cannot prove (1.2), we shall prove this
weaker statement. Tightness in turn implies $nM_{n,k}^{d}/a^{\prime}_{n}\to 1$
in probability as $n\to\infty$, for any sequence $(a^{\prime}_{n})_{n\geq 1}$
satisfying $a^{\prime}_{n}/a_{n}\to 1$ as $n\to\infty$. Another direction of
research (not followed in the present paper) is to improve this to almost sure
convergence, i.e. a strong law of large numbers (SLLN), under the natural
coupling of $(\mathcal{X}_{n},n\geq 1)$:

$\displaystyle\frac{nM_{k}(\mathcal{X}_{n})^{d}}{a^{\prime}_{n}}\overset{a.s.}{\longrightarrow}1,$
(1.3)

or to establish (1.3) even in cases where (1.2) is not known. In previous
work, [13, 17] provide a SLLN in the case of $A$ having a smooth boundary, or
$A$ polytopal, with $\nu$ not necessarily uniform on $A$, but no result along
the lines of (1.2).

###  1.2 The largest $k$-nearest-neighbour link

Given $x\in\mathbb{R}^{d}$ and $r>0$, we denote the closed Euclidean ball of
radius $r$, centred at $x$, by either $B_{r}(x)$ or $B(x,r)$. Given finite
$\mathcal{X}\subset\mathbb{R}^{d}$ we define the largest $k$-nearest-neighbour
link $L_{k}(\mathcal{X})$ of $\mathcal{X}$, by

$\displaystyle
L_{k}(\mathcal{X}):=\begin{cases}\max_{x\in\mathcal{X}}\left(\inf\\{r>0:\mathcal{X}(B_{r}(x))>k\\}\right)&{\rm
if}\leavevmode\nobreak\ |\mathcal{X}|\geq k+1,\\\ 0&{\rm
otherwise,}\end{cases}$ (1.4)

where $|\mathcal{X}|$ denotes the number of elements of $\mathcal{X}$ and
$\mathcal{X}(\cdot):=|\mathcal{X}\cap\cdot|$ denotes the counting measure
associated with $\mathcal{X}$. Note that if $|\mathcal{X}|\geq k+1$ and
$x\in\mathcal{X}$, then $\inf\\{r>0:\mathcal{X}(B_{r}(x))>k\\}$ is the
distance from $x$ to its $k$-nearest neighbour in $\mathcal{X}$. Note also
that $L_{k}(\mathcal{X})\leq M_{k}(\mathcal{X})$ since if
$r<L_{k}(\mathcal{X})$ and $|\mathcal{X}|\geq k+1$, then $G(\mathcal{X},r)$
has at least one vertex with degree less than $k$ and therefore is not
$k$-connected, so $r\leq M_{k}(\mathcal{X})$.

Our analysis of $M_{n,k}$ and $M_{k}(\mathcal{X}_{n})$ will involve first
investigating $L_{n,k}:=L_{k}(\mathcal{P}_{n})$ and $L_{k}(\mathcal{X}_{n})$.
A priori, it is not obvious that $L_{k}(\mathcal{X}_{n})$ is a sharp lower
bound for $M_{k}(\mathcal{X}_{n})$; nevertheless, it is known in some cases
(see Section 1.3) that $M_{k}(\mathcal{X}_{n})$ enjoys the same limiting
behaviour as $L_{k}(\mathcal{X}_{n})$, and even sometimes that

$\displaystyle\lim_{n\to\infty}\mathbb{P}[L_{k}(\mathcal{X}_{n})=M_{k}(\mathcal{X}_{n})]=1.$
(1.5)

Equation (1.5), when true, says that with probability tending to 1 as
$n\to\infty$ the point set $\mathcal{X}_{n}$ has the following property: If we
start with no edges between the vertices of $\mathcal{X}_{n}$, and then add
edges one by one in order of increasing Euclidean length until we arrive at a
$k$-connected graph, then just before the addition of the last edge we still
have a vertex of degree less than $k$; if $k=1$ then just before the addition
of the last edge we have exactly two components, one of which is a singleton.

The largest $k$-nearest neighbour link $L_{k}(\mathcal{X}_{n})$ (or
$L_{k}(\mathcal{P}_{n})$) is of interest in its own right. To quote [1], it
‘comes up in almost all discussions of computational complexity involving
nearest neighbours’. See e.g. [9] for further motivation. As with $M_{n,k}$,
its limiting behaviour has previously been studied on the torus, and the unit
cube, and only at the level of a SLLN for regions with smooth or polytopal
boundary. By providing a limiting distribution for $L_{k}(\mathcal{X}_{n})$
for regions with smooth or polygonal boundary, we here add significantly to
this body of work, too.

###  1.3 Literature review

Before stating our main results, let us give a literature review on this
topic. Under our working assumption (WA), we use throughout the notation

$\displaystyle f_{0}:=\inf_{x\in A}f(x);\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ f_{1}:=\inf_{x\in\partial A}f(x);\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ f_{\rm max}:=\sup_{x\in A}f(x).$ (1.6)

Note that $0<f_{0}\leq f_{1}\leq f_{\rm max}<\infty$ under our WA. Let
$\theta_{d}$ denote the volume of a $d$-dimensional unit ball. i.e.
$\theta_{d}:=\pi^{d/2}/\Gamma(1+d/2)$,

In the case where $A$ is the flat torus $\mathbb{T}^{d}$ of any dimension, it
is known [8, Theorem 13.6] that under the natural coupling of
$(\mathcal{X}_{n},n\geq 1)$ we have

$\displaystyle\lim_{n\to\infty}\left(\frac{\theta_{d}n(M_{k}(\mathcal{X}_{n}))^{d}}{\log
n}\right)=\frac{1}{f_{0}}\quad a.s.$

The dimensionality and the density play a crucial role when one considers
compact sets with boundaries. More precisely, if $A$ has a smooth boundary, it
is proved for $k=1$ in [12, 13], and for general $k$ in [8], that

$\displaystyle\lim_{n\to\infty}\left(\frac{\theta_{d}n(M_{k}(\mathcal{X}_{n}))^{d}}{\log
n}\right)=\lim_{n\to\infty}\left(\frac{\theta_{d}n(L_{k}(\mathcal{X}_{n}))^{d}}{\log
n}\right)=\max\Big{(}\frac{1}{f_{0}},\frac{2-2/d}{f_{1}}\Big{)}\quad a.s.$
(1.7)

When $A$ is a convex polytope, it is proved in [17] that

$\displaystyle\lim_{n\to\infty}\left(\frac{n(M_{k}(\mathcal{X}_{n}))^{d}}{\log
n}\right)=\lim_{n\to\infty}\left(\frac{n(L_{k}(\mathcal{X}_{n}))^{d}}{\log
n}\right)=\max_{\varphi\in\Phi^{*}(A)}\Big{(}\frac{D(\varphi)}{f_{\varphi}\rho_{\varphi}d}\Big{)}\quad
a.s.$ (1.8)

where $\Phi^{*}$ denotes the collection of all faces of $\varphi$ of all
dimensions (including $A$ itself, considered as a face of dimension $d$), and
where $D(\varphi)$ is the dimension of face $\varphi$, and where $f_{\varphi}$
denotes the infimum of $f$ over face $\varphi$ and $\rho_{\varphi}$ is the
angular volume of face $\varphi$.

Less is known about the fluctuations of $nM_{k}(\mathcal{X}_{n})^{d}-a_{n}$.
Weak limit results of the type (1.2) are proved for two cases in [9, 11]. The
first case is when $f$ is uniform on $\mathbb{T}^{d}$ for any $d\geq 2$. In
this case, by [8, Corollary 13.20], one has

$\displaystyle\theta_{d}n(M_{k}(\mathcal{X}_{n}))^{d}-\log n-(k-1)\log\log
n+\log((k-1)!)\overset{d}{\longrightarrow}{\mathsf{Gu}},$

where ${\mathsf{Gu}}$ denotes a standard Gumbel random variable, i.e. one with
cumulative distribution function $F(x)=\exp(-e^{-x}),x\in\mathbb{R}$. (For
$a\in\mathbb{R},b>0$ the random variable $b{\mathsf{Gu}}+a$ is said to be
Gumbel distributed with scale parameter $b$ and location parameter $a$.)

The second case is when $f$ is uniform on $[0,1]^{d}$. For this case, we
describe only the results for $k=1$ from [8] but the case of general $k$ is
also treated there. When $f$ is uniform on $[0,1]^{d}$, one has by [8,
Corollary 13.21] that

$\displaystyle 2^{2-d}\theta_{d}n(M_{1}(\mathcal{X}_{n}))^{d}-(2/d)\log
n+(d-3+2/d)\log\log n$
$\displaystyle+\log\left(\Big{(}\frac{2^{2-2/d}}{d(d-1)}\Big{)}(\theta_{d}d)^{3-d-2/d}\theta_{d-1}^{d-2}\right)\overset{d}{\longrightarrow}{\mathsf{Gu}}.$
(1.9)

Similar results hold for $L_{k}(\mathcal{X}_{n})$; see [8, Theorems 8.3 and
8.4]. Moreover it is known that (1.5) holds. Also these results hold for
$\mathcal{P}_{n}$ instead of $\mathcal{X}_{n}$.

So far as we know, there is no weak limit result for other shaped boundaries
or for non-uniform distributions (until now). In the special case where $d=2$
and $f$ is uniformly distributed in a disk, [3] gives a partial result in the
direction of a weak limit.

The main results of this paper considerably generalize previous findings and
deepen the understanding of the connectivity threshold in terms of the
geometry of $A$. In the uniform case, we also provide a bound on the rate of
convergence that is new for all shapes under the WA.

We end this section by mentioning some related results. It is natural to ask
what happens if we drop the working assumption and take the support of $f$ to
be unbounded. Penrose [10] found that the scaling is completely different in
the case of standard Gaussian density in $\mathbb{R}^{d}$; see also Hsing and
Rootzén [5] for a significant extension in dimension two, where a class of
elliptically contoured distributions are included, e.g. Gaussian densities
with correlated coordinates. Gupta and Iyer [2] give a limting distribution
and SLLN for $L_{n,1}$ for a class of radially symmetric densities with
unbounded support, including cases where $L_{n,1}$ (and hence also $M_{n,1}$)
does not even tend to zero.

###  1.4 Main results

Throughout this paper, $c$ and $c^{\prime}$ denote positive finite constants
whose values may vary from line to line and do not depend on $n$. Also if
$n_{0}\in(0,\infty)$ and $f(n),g(n)$ are two functions, defined for all $n\geq
n_{0}$ with $g(n)>0$ for all $n\geq n_{0}$, the notation $f(n)=O(g(n))$ as
$n\to\infty$ means that $\limsup_{n\to\infty}(|f(n)|/g(n))<\infty$. If also
$f(n)>0$ for all $n\geq n_{0}$, we use notation $f(n)=\Theta(g(n))$ to mean
that both $f(n)=O(g(n))$ and $g(n)=O(f(n))$.

Given $d,k\in\mathbb{N}$, define the constant

$\displaystyle
c_{d,k}:=\theta_{d-1}^{-1}\theta_{d}^{1-1/d}(2-2/d)^{k-2+1/d}2^{1-k}/(k-1)!$
(1.10)

In this paper, given $A\subset\mathbb{R}^{d}$, we say that $A$ has $C^{2}$
boundary (or for short: $\partial A\in C^{2}$) if for each $x\in\partial A$,
the topological boundary of $A$, there exists a rigid motion $\rho_{x}$ of
$\mathbb{R}^{d}$, an open set $U_{x}\subset\mathbb{R}^{d-1}$ and a $C^{2}$
function $f_{x}:\mathbb{R}^{d-1}\to\mathbb{R}$ such that $\rho(A\cap
U)=\rho(U)\cap\mathrm{epi}(f_{x})$, where
$\mathrm{epi}(f_{x}):=\\{(u,z)\in\mathbb{R}^{d-1}\times\mathbb{R}:z\geq
f_{x}(u)\\}$, the closed epigraph of $f_{x}$.

For compact $A\subset\mathbb{R}^{d}$ with $C^{2}$ or polytopal boundary, let
$|A|$ denote the volume (Lebesgue measure) of $A$, and $|\partial A|$ the
perimeter of $A$, i.e. the $(d-1)$-dimensional Hausdorff measure of $\partial
A$. Also define

$\displaystyle\sigma_{A}:=\frac{|\partial A|}{|A|^{1-1/d}}.$ (1.11)

Note that $\sigma_{A}^{d}$ is sometimes called the isoperimetric ratio of $A$,
and is at least $d^{d}\theta_{d}$ by the isoperimetric inequality.

######  Theorem 1.1 (Weak limits in the uniform case).

Suppose either that $d\geq 2$ and $A$ a compact subset of $\mathbb{R}^{d}$
with $C^{2}$ boundary, or that $d=2$ and $A$ is a convex polygon. Let $f\equiv
f_{0}1_{A}$ with $f_{0}=|A|^{-1}$. Let $\beta\in\mathbb{R}$. Then, if $d=2$,
we have as $n\to\infty$ that

$\displaystyle\mathbb{P}[nf_{0}\pi M_{1}(\mathcal{X}_{n})^{2}-\log
n\leq\beta]=\exp\Big{(}-\frac{\sigma_{A}\pi^{1/2}e^{-\beta/2}}{2(\log
n)^{1/2}}\Big{)}e^{-e^{-\beta}}+O((\log n)^{-1});$ (1.12)
$\displaystyle\mathbb{P}[nf_{0}\pi M_{n,1}^{2}-\log
n\leq\beta]=\exp\Big{(}-\frac{\sigma_{A}\pi^{1/2}e^{-\beta/2}}{2(\log
n)^{1/2}}\Big{)}e^{-e^{-\beta}}+O((\log n)^{-1}).$ (1.13)

Also, given $k\in\mathbb{N}$, set

$\displaystyle u_{n,k}$
$\displaystyle:=\mathbb{P}[n\theta_{d}f_{0}M_{n,k}^{d}-(2-2/d)\log
n+(4-2k-2/d)\log\log n\leq\beta];$ $\displaystyle u^{\prime}_{n,k}$
$\displaystyle:=\mathbb{P}[n\theta_{d}f_{0}M_{k}(\mathcal{X}_{n})^{d}-(2-2/d)\log
n+(4-2k-2/d)\log\log n\leq\beta].$

If $d=2$ then as $n\to\infty$

$\displaystyle
u_{n,2}=\exp\Big{(}-\frac{\pi^{1/2}\sigma_{A}e^{-\beta/2}\log\log n}{8\log
n}-\frac{e^{-\beta}\log\log n}{\log
n}\Big{)}\exp\Big{(}-e^{-\beta}-\frac{\pi^{1/2}\sigma_{A}e^{-\beta/2}}{4}\Big{)}$
$\displaystyle+O\big{(}\frac{1}{\log n}\big{)},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ $ (1.14)

and likewise for $u^{\prime}_{n,2}$. If $d\geq 3$, or if $d=2,k\geq 3$ we have
as $n\to\infty$ that

$\displaystyle
u_{n,k}=\exp\Big{(}-\frac{c_{d,k}\sigma_{A}e^{-\beta/2}(k-2+1/d)^{2}\log\log
n}{(1-1/d)\log
n}\Big{)}\exp(-c_{d,k}\sigma_{A}e^{-\beta/2})+O\big{(}\frac{1}{\log
n}\big{)},$ (1.15)

and likewise for $u^{\prime}_{n,k}$. Also (1.5) holds, and all of the above
results hold with $L_{n,k}$ (resp. $L_{n}(\mathcal{X}_{n})$) instead of
$M_{n,k}$ (resp. $M_{k}(\mathcal{X}_{n})$).

######  Remark 1.2.

  1. i)

The statements abouts $L_{n,k}$ and $L_{k}(\mathcal{X}_{n})$ in this theorem
are spelt out in Corollaries 6.3 and 6.4.

  2. ii)

These results imply certain convergence in distribution results. Namely,
$n\theta_{d}f_{0}M_{n,k}^{d}$, suitably centred, is asymptotically Gumbel
distributed with scale parameter $1$ when $d=2,k=1$ but with scale parameter
$2$ when $d\geq 3$ or $d=2,k\geq 3$. When $d=2,k=2$ the limiting distribution
is a so-called two-component extreme value distribution (TCEV), that is, a
probability distribution with cumulative distribution function (cdf) given by
the product of two Gumbel cdfs with different scale parameters, in this case 1
and 2. The terminology TCEV was introduced in the hydrology literature [18].

  3. iii)

We have included a multiplicative correction factor in each of (1.12)–(1.15),
namely the first factor in the right hand side in each case, because this
factor tends to 1 very slowly, especially in (1.12) and (1.13) where the
correction factor is $1+O((\log n)^{-1/2})$ so for moderately large values of
$n$ the limiting Gumbel distribution with cdf $e^{-e^{-\beta}}$ is not very
close to the centred distribution of $nf_{0}\theta_{d}M_{n,1}^{d}$. If $d\geq
3$ it is possible to give some extra terms in the correction and improve the
error bound to $O((\log n)^{\varepsilon-2})$.

  4. iv)

The error bounds above are for fixed $\beta$ but we would need uniform in
$\beta$ for an error bound in the Kolmogorov distance between probability
distributions. We do not address this in this paper.

  5. v)

It seems likely that our results carry over to the case where $d=2$ and $A$ is
a non-convex polygon. Our main reason for restricting attention to polygons
that are convex its that some of our arguments in Section 4 are based on
results from [17] that are stated there only for convex polytopes.

We now give a result for the general non-uniform case; that is, we still use
our WA on $f$, but drop the stronger assumption that $f$ is constant on $A$.
Recall $f_{0},f_{1}$ defined at (1.6). In this more general case, subject to
the condition $f_{1}\neq f_{0}(2-2/d)$, we still provide a result along the
lines of (1.2), but now, instead of using the explicit centring constants
$a_{n}=(2-2/d)\log n-(4-2k-2/d){\bf 1}\\{d\geq 3\leavevmode\nobreak\ {\rm
or}\leavevmode\nobreak\ k\geq 2\\}\log\log n$ as in Theorem 1.1, we take
$a_{n}$ to be the median of the distribution $nM_{n}^{d}$. In the case
$f_{1}=f_{0}(2-2/d)$ we prove only the weaker result that our sequence of
centred random variables is tight.

Given a random variable $X$, let
$\mu(X):=\inf\\{x\in\mathbb{R}:\mathbb{P}[X\leq x]\geq 1/2\\}$, the median of
the distribution of $X$. Note that $\mu({\mathsf{Gu}})=-\log(\log 2)$, so for
$\alpha>0$, the random variable $\alpha({\mathsf{Gu}}+\log(\log 2))$ has a
Gumbel distribution with median 0 and with scale parameter $\alpha$.

######  Theorem 1.3 (Weak limit in the non-uniform case).

Suppose our working assumption applies, either with $d\geq 2$ and $A$ a
compact subset of $\mathbb{R}^{d}$ with $C^{2}$ boundary, or with $d=2$ and
$A$ a convex polygon. Let $k\in\mathbb{N}$.

(i) If $f_{1}>f_{0}(2-2/d)$, then as $n\to\infty$,

$\displaystyle
nM_{k}(\mathcal{X}_{n})^{d}-n\mu(M_{k}(\mathcal{X}_{n}))^{d}\overset{d}{\longrightarrow}(\theta_{d}f_{0})^{-1}({\mathsf{Gu}}+\log\log
2);$ (1.16) $\displaystyle
nL_{k}(\mathcal{X}_{n})^{d}-n\mu(L_{k}(\mathcal{X}_{n}))^{d}\overset{d}{\longrightarrow}(\theta_{d}f_{0})^{-1}({\mathsf{Gu}}+\log\log
2);$ (1.17) $\displaystyle
nM_{n,k}^{d}-n\mu(M_{n,k})^{d}\overset{d}{\longrightarrow}(\theta_{d}f_{0})^{-1}({\mathsf{Gu}}+\log\log
2);$ (1.18) $\displaystyle
nL_{n,k}^{d}-n\mu(L_{n,k})^{d}\overset{d}{\longrightarrow}(\theta_{d}f_{0})^{-1}({\mathsf{Gu}}+\log\log
2).$ (1.19)

(ii) If $f_{1}<f_{0}(2-2/d)$, then as $n\to\infty$,

$\displaystyle
nM_{k}(\mathcal{X}_{n})^{d}-n\mu(M_{k}(\mathcal{X}_{n}))^{d}\overset{d}{\longrightarrow}(2/(\theta_{d}f_{1}))({\mathsf{Gu}}+\log\log
2);$ (1.20) $\displaystyle
nL_{k}(\mathcal{X}_{n})^{d}-n\mu(L_{k}(\mathcal{X}_{n}))^{d}\overset{d}{\longrightarrow}(2/(\theta_{d}f_{1}))({\mathsf{Gu}}+\log\log
2).$ (1.21) $\displaystyle
nM_{n,k}^{d}-n\mu(M_{n,k}^{d})\overset{d}{\longrightarrow}(2/(\theta_{d}f_{1}))({\mathsf{Gu}}+\log\log
2);$ (1.22) $\displaystyle
nL_{n,k}^{d}-n\mu(L_{n,k})^{d}\overset{d}{\longrightarrow}(2/(\theta_{d}f_{1}))({\mathsf{Gu}}+\log\log
2);$ (1.23)

(iii) In all cases, including when $f_{1}=f_{0}(2-2/d)$, (1.5) holds, and also
the family of random variables $(n(M_{n,k}^{d}-\mu(M_{n,k})^{d}))_{n\geq 1}$
is tight. Likewise the collection of random variables
$(n(L_{n,k}^{d}-\mu(L_{n,k})^{d}))_{n\geq 1}$ is tight, as are the sequences
$(n(M_{k}(\mathcal{X}_{n})^{d}-\mu(M_{k}(\mathcal{X}_{n}))^{d}))_{n\geq 1}$
and $(n(L_{k}(\mathcal{X}_{n})^{d}-\mu(L_{k}(\mathcal{X}_{n}))^{d}))_{n\geq
1}$.

Before proceeding to proofs, we give a rough calculation indicating why, in
the uniform case with $f\equiv f_{0}{\bf 1}_{A}$, we might expect to see
qualitative differences between the cases with $d=2$ and $k=1$ or $k=2$, and
other cases, as seen in Theorem 1.1. Suppose we take a sequence of distance
parameters $r_{n}$ with $nf_{0}\theta_{d}r_{n}^{d}=\log n+(k-1)\log\log n+c$
for some constant $c$. Given $r_{n}$, let $F^{o}_{n}$, $F_{n}^{\partial}$ be
the number of vertices of degree less than $k$ in the interior of $A$,
respectively near the boundary of $A$. We give a rough calculation suggesting
that for $d\geq 3$ we have
$\mathbb{E}[F_{n}^{\partial}]\gg\mathbb{E}[F_{n}^{o}]$ so the boundary region
dominates, while for $d=2$, it depends on the value of $k$ whether the
interior or boundary region dominates. Firstly,

$\mathbb{E}[F_{n}^{o}]\approx
n((nf_{0}\theta_{d}r_{n}^{d})^{k-1}/(k-1)!)e^{-nf_{0}\theta_{d}r_{n}^{d}}\sim(e^{-c})/(k-1)!.$

For $F_{n}^{\partial}$, note that for small positive $s$ the volume of the
intersection of $A$ with a ball of radius $r_{n}$ centred at distance $sr_{n}$
from $\partial A$ is about $(\theta_{d}/2)r_{n}^{d}+\theta_{d-1}sr_{n}^{d}$,
suggesting

$\displaystyle\mathbb{E}[F_{n}^{\partial}]$ $\displaystyle\approx
nr_{n}(f_{0}\theta_{d}nr_{n}^{d}/2)^{k-1}(|\partial
A|/(k-1)!)e^{-nf_{0}\theta_{d}r_{n}^{d}/2}\int_{0}^{\infty}e^{-nf_{0}\theta_{d-1}sr_{n}^{d}}ds$
$\displaystyle\approx{\rm const.}\times
n^{(1/2)-(1/d)}(nr_{n}^{d})^{(1/d)+k-2}(\log n)^{(1-k)/2}$
$\displaystyle\approx{\rm const.}\times n^{(1/2)-(1/d)}(\log
n)^{(1/d)+((k-3)/2)}.$

If $d\geq 3$ this tends to infnity (regardless of $k$). Thus the boundary
effects dominate in this case; we should choose a slightly bigger $r_{n}$ to
make $\mathbb{E}[F_{n}^{\partial}]$ tend to a constant, and then
$\mathbb{E}[F_{n}^{o}]$ will tend to zero.

If $d=2$, the last expression for $\mathbb{E}[F_{n}^{\partial}]$ tends to zero
if $k=1$ and to infinity if $k\geq 3$, so the interior contribution dominates
when $k=1$ but the boundary contribution dominates when $k\geq 3$. When $k=2$
the interior and boundary effects are of comparable size.

Having chosen $r_{n}$ so that $\mathbb{E}[F_{n}^{o}+F_{n}^{\partial}]$ tends
to a constant, we shall use Poisson approximation to show that
$\mathbb{P}[L_{n}^{o}\leq r_{n}]$ tends to a non-trivial constant, and then
some percolation arguments to show the same limit holds for
$\mathbb{P}[M_{n,1}\leq r_{n}]$.

The rest of the paper is organised as follows. After the preparation of
geometrical ingredients in Section 2, we prove Poisson approximation for the
number of $k$-isolated vertices in Section 3, asymptotic equivalence of
$L_{n,k}$ and $M_{n,k}$ in Section 4, the weak law in the nonuniform case
(Theorem 1.3) in Section 5 and finally the weak law in the uniform case
(Theorem 1.1) in Section 6.

##  2 Geometrical preliminaries

In this section, we prepare some geometrical ingredients for later use. Let
$A$ be a compact subset of $\mathbb{R}^{d}$ with $d\geq 2$.

Given $B,C\subset\mathbb{R}^{d}$, set $B\oplus C:=\\{x+y:x\in B,y\in C\\}$.
Let $o$ denote the origin in $\mathbb{R}^{d}$. Given $x\in\mathbb{R}^{d}$, we
write $B+x$ for $B\oplus\\{x\\}$.

Given $s>0$, and $\Gamma\subset A$, we write $\Gamma^{(s)}$ for $(\Gamma\oplus
B_{s}(o))\cap A$, the set of points in $A$ distant at most $s$ from $\Gamma$.
Also we set $\operatorname{diam}(\Gamma):=\sup_{x,y\in\Gamma}\|y-x\|$, or zero
if $\Gamma=\varnothing$.

We write $A^{(-s)}$ for $A\setminus(\partial A)^{(s)}$, the set of points in
$A$ distant more than $s$ from the boundary $\partial A$ of $A$.

When $A$ is polygonal, we denote by $\mathsf{Cor}$ the set of corners of $A$.

######  Lemma 2.1.

Suppose $A$ has a $C^{2}$ boundary. Let $\varepsilon\in(0,1]$. Then:

(i) For all small enough $r>0$ we have

$\displaystyle|B_{r}(x)\cap
A|\geq((\theta_{d}/2)+(\theta_{d}\varepsilon/4))r^{d},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall\leavevmode\nobreak\ x\in A^{(-\varepsilon r)}.$
(2.1)

(ii) There exists $\delta>0$ and $r_{0}>0$ such that if $0<r<s<2r<r_{0}$, then

$\displaystyle|A\cap B_{s}(x)\setminus
B_{r}(x)|\leq((\theta_{d}/2)+\varepsilon)(s^{d}-r^{d}),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall x\in(\partial A)^{(\delta s)}.$ (2.2)

###### Proof.

Clearly (2.1) holds for $x\in A^{(-r)}$.

Let $x\in(\partial A)^{(r)}\cap A^{(-K_{0}r^{2})}$ with $K_{0}$ to be chosen
later. Without loss of generality (after a translation and rotation), we can
assume that the closest point of $\partial A$ to $x$ lies at the origin, and
$x=he_{d}$ for some $h>0$ (where $e_{d}$ is the $d$th coordinate vector), and
for some convex open $V\subset\mathbb{R}^{d}$ with $o\in V$ and some open
convex neighbourhood $U$ of the origin in $\mathbb{R}^{d-1}$, and some $C^{2}$
function $\phi:\mathbb{R}^{d-1}\to\mathbb{R}$ we have that $A\cap
V=V\cap\mathrm{epi}(\phi)$.

Since $z=o$ is the closest point in $\partial A$ to $x$, we must have
$\nabla\phi(o)=o$. By a compactness argument, we can also assume
$\sum_{i=1}^{d}\sum_{j=1}^{d}|\partial^{2}_{ij}\phi|\leq K/(9d^{2})$ on $U$
for some constant $K$ (depending on $A$).

Now suppose $u\in\mathbb{R}^{d-1}$ with $\|u\|\leq 3r$ (assume $r$ is small
enough that all such $u$ lie in $U$). By the Mean Value theorem
$\phi(u)=u\cdot\nabla\phi(w)$ for some $w\in[o,u]$, and for $1\leq i\leq d$,
$\partial_{i}\phi(w)=w\cdot\nabla\partial_{i}\phi(v)$ for some $v\in[o,w]$.
Hence

$\displaystyle|\phi(u)|\leq(K/9)\|u\|^{2}\leq Kr^{2},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
u\in\mathbb{R}^{d-1}\leavevmode\nobreak\ {\rm with}\leavevmode\nobreak\
\|u\|\leq 3r.$ (2.3)

For $a>0$ set $g(a):=|B_{1}(o)\cap(\mathbb{R}^{d-1}\times[0,a])|$. Then
$g(a)/a$ is decreasing in $a$, so for $0\leq a\leq 1$ we have $g(a)/a\geq
g(1)=\theta_{d}/2$.

Let $\pi:\mathbb{R}^{d}\to\mathbb{R}^{d-1}$ denote projection onto the first
$d-1$ coordinates and let $h:\mathbb{R}^{d}\to\mathbb{R}$ denote projection
onto the last coordinate ($h$ stands for ‘height’). Take $K_{0}=2K$. Then
$h(x)=d(x,\partial A)\geq K_{0}r^{2}$. Also $h(x)\leq r$. For $z\in
B_{r}(x)\cap(\mathbb{R}^{d-1}\times[Kr^{2},\infty))$ we have $\|\pi(z)\|\leq
r$ so that by (2.3) we have $|\phi(\pi(z))|\leq Kr^{2}\leq h(z)$, and hence
$z\in A$. Therefore

$\displaystyle|B_{r}(x)\cap A|$
$\displaystyle\geq|B_{r}(x)\cap(\mathbb{R}^{d-1}\times[Kr^{2},\infty))|$
$\displaystyle\geq(\theta_{d}/2)r^{d}+r^{d}g((h(x)-Kr^{2})/r)$
$\displaystyle\geq(\theta_{d}/2)r^{d}+(\theta_{d}/2)r^{d-1}(h(x)-Kr^{2})$
$\displaystyle\geq(\theta_{d}/2)r^{d}+(\theta_{d}h(x)/4)r^{d-1},$ (2.4)

where the last line is because $Kr^{2}=K_{0}r^{2}/2\leq h(x)/2$.

Let $\varepsilon>0$. Provided $r$ is small enough we have $\varepsilon r\geq
K_{0}r^{2}$, so that $A^{(-\varepsilon r)}\subset A^{(-K_{0}r^{2})}$. Hence
for $x\in(\partial A)^{(r)}\cap A^{(-\varepsilon r)}$ we have (2.4), and
therefore since $h(x)\geq\varepsilon r$,

$|B_{r}(x)\cap A|\geq((\theta_{d}/2)+(\theta_{d}\varepsilon/4))r^{d}.$

Thus we have (i).

Figure 1:  The horizontal lines are at height $0$, $-2\delta s$ and $-4\delta
s$. The circles are of radius $r,s$ centred on the origin.

For Part (ii), let $\delta>0$, to be chosen later. Suppose that $s>0$ and
$x\in(\partial A)^{(\delta s)}$. Let $r\in(s/2,s)$. Provided $s$ is small
enough, by (2.3) we have $\phi(u)\geq-\delta s$ for all $u\in\mathbb{R}^{d-1}$
with $\|u\|\leq 3s$. Therefore

$A\cap B_{s}(x)\setminus B_{r}(x)\subset(B_{s}(x)\setminus
B_{r}(x))\cap(\mathbb{R}^{d-1}\times[h(x)-2\delta s,\infty)).$

Define the set $S_{\delta}:=\\{x\in
B_{1}(o):\pi_{d}(\|x\|^{-1}x)\geq-4\delta\\}.$ Then since $s\leq 2r$, as shown
in Figure 1,

$\displaystyle|A\cap B_{r}(x)\setminus
B_{s}(x)|\leq(s^{d}-r^{d})|S_{\delta}|.$

On taking $\delta$ small enough so that
$|S_{\delta}|\leq\theta_{d}((1/2)+\varepsilon)$, we obtain (2.2), completing
the proof of Part (ii). ∎

Given $x\in A$, set ${\rm dist}(x,\partial A):=\inf_{z\in\partial
A}\\{\|z-x\|\\}$.

######  Lemma 2.2.

Suppose $A\subset\mathbb{R}^{d}$ is compact with $C^{2}$ boundary.

(i) Given $\varepsilon>0$, there exists $r_{0}=r_{0}(d,A,\varepsilon)>0$ such
that

$\displaystyle|B_{r}(x)\cap
A|\geq((\theta_{d}/2)-\varepsilon)r^{d},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall x\in
A,r\in(0,r_{0}).$ (2.5)

(ii) There is a constant $r_{1}=r_{1}(d,A)$, such that if $r\in(0,r_{1})$ and
$x,y\in A$ with $\|y-x\|\leq 2r$ and ${\rm dist}(x,\partial A)\leq{\rm
dist}(y,\partial A)$, then

$\displaystyle|A\cap B_{r}(y)\setminus B_{r}(x)|\geq
8^{-d}\theta_{d-1}r^{d-1}\|y-x\|.$ (2.6)

(iii) Given $\varepsilon>0$, there exists $r_{0}=r_{0}(d,A,\varepsilon)>0$
such that

$\displaystyle|A\cap B_{r}(x)\setminus
B_{s}(x)|\geq((\theta_{d}/2)-\varepsilon)(s^{d}-r^{d}),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall x\in
A,s\in(0,r_{0}),r\in(0,s).$

###### Proof.

For (i) and (ii), see [4, Lemma 3.2]. For (iii), as in the proof of the proof
of Lemma 2.1, it suffices to consider $x\in A$ such that the closest point of
$\partial A$ to $x$ is at $o$ with $x=he_{d}$ for some $h\in(0,s]$, and
moreover $\partial A$ near $o$ is the graph of a $C^{2}$ function
$\phi:U\to\mathbb{R}$ with $U$ an open neighbourhood of the origin in
$\mathbb{R}^{d-1}$ and with
$\sum_{i=1}^{d}\sum_{j=1}^{d}|\partial^{2}_{ij}\phi|\leq K/(9d^{2})$ on $U$
for some constant $K$ depending only on $A$.

Then, as at (2.3), provided $r_{1}$ is small enough we have
$|\phi(u)|\leq(K/9)\|u\|^{2}$ for $\|u\|<r_{1}$. Therefore given $\delta>0$,
if also $\|u\|<\delta/K$ we have $|\phi(u)|\leq\delta\|u\|$.

Choose $\delta$ as follows. Given $a>0$, define the set
$\Lambda_{a}\subset\mathbb{R}^{d}$ by

$\Lambda_{a}:=\\{(u,z):u\in\mathbb{R}^{d-1},z\in\mathbb{R},z\geq
a\|u\|,\|u\|^{2}+z^{2}\leq 1\\}.$

Then $|\Lambda_{a}|\uparrow\theta_{d}/2$ as $a\downarrow 0$ so we can and do
choose $\delta>0$ such that
$|\Lambda_{\delta}|\geq(\theta_{d}/2)-\varepsilon$.

For $0\leq r<s$, given $x$ as above define the set
$S:=((s\Lambda_{\delta})\setminus(r\Lambda_{\delta}))+x.$ Then

$|S|=|(s\Lambda_{\delta})\setminus(r\Lambda_{\delta})|=(s^{d}-r^{d})|\Lambda_{\delta}|\geq((\theta_{d}/2)-\varepsilon)(s^{d}-r^{d}).$

Now suppose also that $s<\delta/K$. For $y=(v,h^{\prime})\in S$, we have
$\|v\|\leq s$ and

$h^{\prime}\geq(h^{\prime}-h)\geq\delta\|v\|\geq\phi(v),$

so $y\in A$ and $S\subset A$. Also $S\subset B_{s}(x)\setminus B_{r}(x)$. This
gives the result, with $r_{0}=\delta/K$. ∎

Recall that $\mathsf{Cor}$ denotes the set of corners of $A$ when $A$ is
polygonal.

######  Lemma 2.3.

Assume $d=2$ and $A$ is polygonal, then there exist $K>0$ and $r_{1}>0$
depending on $A$ such that for all $r\in(0,r_{1})$, $x,y\in
A\setminus\mathsf{Cor}^{(Kr)}$ with ${\rm dist}(x,\partial A)\leq{\rm
dist}(y,\partial A)$ and $\|x-y\|\leq 3r$, the lower bound (2.6) holds.

###### Proof.

Let $r_{1}$ be small enough such that non-overlapping edges of $A$ are distant
at least $8r_{1}$ from each other. Consider $x\in
A\setminus\mathsf{Cor}^{(Kr)}$ with $r<r_{1}$ where $K$ is made explicit
later. We can assume that the corner of $A$ closest to $x$ is formed by edges
$e,e^{\prime}$ meeting at the origin with angle
$\alpha\in(0,2\pi)\setminus\\{\pi\\}$. We claim that, provided
$K>4+8/|\sin\alpha|$, the disk $B(x,4r)$ intersects at most one of the two
edges. Indeed, if it intersects both edges, then taking $w\in B(x,4r)\cap
e,w^{\prime}\in B(x,4r)\cap e^{\prime}$ we have $\|w-w^{\prime}\|\leq 8r$;
hence ${\rm dist}(w,e^{\prime})\leq 8r$. Then, $\|w\|\leq{\rm
dist}(w,e^{\prime})/|\sin\alpha|\leq 8r/|\sin\alpha|$. However,
$\|w\|\geq(K-4)r$ by the triangle inequality, so we arrive at a contradiction.
We have thus shown that any ball of radius $4r$ with centre distant at least
$Kr$ from the corners of $A$ cannot intersect two edges at the same time,
where $K=5+(8/\min_{i}|\sin\alpha_{i}|)$ and $\\{\alpha_{i}\\}$ are the angles
of the corners of $A$.

We have $B(x,r_{n})\cup B(y,r_{n})\subset B(x,4r_{n})$; hence, the argument
leading to Lemma 2.2-(ii), namely [4, Lemma 3.2], gives the estimate (2.6) in
this case too. ∎

######  Lemma 2.4.

Let $\varepsilon\in(0,1]$. Then for all $r>0$ and all compact
$B\subset\mathbb{R}^{d}$ with $\operatorname{diam}B\geq\varepsilon r$ we have
$|B\oplus B_{r}(o)|\geq|B|+\theta_{d}(1+2^{-1}(2d)^{-d}\varepsilon^{d})r^{d}$.

###### Proof.

By scaling, it suffices to show that for all compact $B\subset\mathbb{R}^{d}$
with $\operatorname{diam}B\geq\varepsilon$, we have $|B\oplus
B_{1}(o)|\geq|B|+\theta_{d}(1+2^{-1}(2d)^{-d}\varepsilon^{d})$.

Let $B\subset\mathbb{R}^{d}$ with
$\varepsilon\leq\operatorname{diam}B<\infty$. Without loss of generality we
can assume $\operatorname{diam}(\pi_{1}(B))\geq\varepsilon/d$, where $\pi_{1}$
denotes projection onto the first coordinate.

Let $x$ be a left-most point of $B$, $y$ a right-most point of $B$ and $u$ a
top-most point of $B$. Here ‘left’ and ‘right’ refer to ordering using the
first coordinate and ‘top’ refers to ordering using the last coordinate. Let
$H^{+}$ be the right half of $B_{1}(y)$ and $H^{-}$ the left-half of
$B_{1}(x)$. Let $D:=B_{\varepsilon/(2d)}(u+(0,\ldots,0,\varepsilon/(2d)))$,
and let $D^{+}$ and $D^{-}$ be the left half and right half of $D$,
respectively. Then the interiors of $H^{+}$ and of $H^{-}$ are disjoint from
$B$ and from each other, and the interior of either $D^{+}$ or $D^{-}$ (or
both) is disjoint from all of $B,H^{+}$ and $H^{-}$. Therefore since $H^{+}$,
$H^{-}$ and $D$ are all contained in $B\oplus B_{1}(o)$, we obtain that

$|B\oplus
B_{1}(o)|\geq|B|+\theta_{d}+(\theta_{d}2^{-1}(2d)^{-d})\varepsilon^{d},$

as required. ∎

######  Lemma 2.5.

Suppose $A$ has a $C^{2}$ boundary. Let $\rho,\varepsilon\in\mathbb{R}$ with
$0<\varepsilon<\rho$. Then there exist $\delta=\delta(d,\rho,\varepsilon)>0$,
and $\delta^{\prime}=\delta^{\prime}(d,\rho,\varepsilon)>0$, and
$r_{0}=r_{0}(d,\rho,\varepsilon,A)$, such that for all $r\in(0,r_{0})$ and all
compact $B\subset A$ with $\varepsilon r\leq\operatorname{diam}B\leq\rho r$ we
have

$\displaystyle|(B\oplus B_{r}(o))\cap A|\geq|B|+((\theta_{d}/2)+\delta)r^{d},$
(2.7)

and also, letting $x_{0}$ denote a closest point of $B$ to $\partial A$, we
have

$\displaystyle|(B\oplus B_{r}(o))\cap A|\geq|B|+|B_{r}(x_{0})\cap
A|+\delta^{\prime}r^{d}.$ (2.8)

###### Proof.

It suffices to prove (2.8). Indeed, if (2.8) holds for some $\delta^{\prime}$
and $r_{0}$, then taking $\delta=\delta^{\prime}/2$, using (2.8) and Lemma 2.2
(i) readily yields (2.7) for some new, possibly smaller, choice of $r_{0}$.

Without loss of generality we may assume $\varepsilon\leq 1\leq\rho$. Let
$r>0$, and let $B\subset A$ be compact with $\varepsilon
r\leq\operatorname{diam}(B)\leq\rho r$. If $B\subset A^{(-r)}$ we can use the
preceding lemma, so it suffices to consider the case where $B\cap(\partial
A)^{(r)}\neq\varnothing$.

Let $x_{0}$ be a closest point of $B$ to $\partial A$. Without loss of
generality (after a rotation and translation), we can assume that the closest
point of $\partial A$ to $x_{0}$ lies at the origin, and $x_{0}=he_{d}$ for
some $h\in[0,r]$, and that within some neighbourhood of the origin, $A$
coincides with the closed epigraph of a function $\phi:U\to\mathbb{R}$ with
$U$ an open convex neighbourhood of the origin in $\mathbb{R}^{d-1}$. As in
the proof of Lemma 2.1, we can find $K=K(d,A)\in(1,\infty)$ such that

$\displaystyle|\phi(u)|\leq(K/9)\|u\|^{2}\leq
K\rho^{2}r^{2},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\forall u\in\mathbb{R}^{d-1}\leavevmode\nobreak\ {\rm
with}\leavevmode\nobreak\ \|u\|\leq 2\rho r.$ (2.9)

Assume $r\leq\varepsilon/(144dK\rho^{2})$. Let
$\pi:\mathbb{R}^{d}\to\mathbb{R}^{d-1}$ denote projection onto the first $d-1$
coordinates, and for $1\leq i\leq d$, let
$\pi_{i}:\mathbb{R}^{d}\to\mathbb{R}$ denote projection onto the $i$th
coordinate. Define the set $H^{-}$ (slightly less than half a ball of radius
$r$: see Figure 2) by

$\displaystyle H^{-}:=\\{z\in
B_{r}(x_{0}):\pi_{d}(z)<\pi_{d}(x_{0})-K\rho^{2}r^{2}\\}.$ (2.10)

For all $w\in B$ we have $\|\pi(w)\|\leq\|w-x_{0}\|\leq\rho r$, so by (2.9),

$\displaystyle\pi_{d}(x_{0})={\rm dist}(x_{0},\partial A)\leq{\rm
dist}(w,\partial
A)\leq\pi_{d}(w)+|\phi(\pi(w))|\leq\pi_{d}(w)+K\rho^{2}r^{2}.$ (2.11)

Therefore any $z\in H^{-}$, $w\in B$ satisfy $\pi_{d}(z)<\pi_{d}(w)$, so that
$H^{-}\subset(B\oplus B_{r}(o))\setminus B$.

We can bound above the volume difference of a half-ball and $H^{-}$ by the
volume of a cylinder of thickness $K\rho^{2}r^{2}$ with base of radius $r$.
Using this and the union bound, we obtain that

$\displaystyle|B_{r}(x_{0})\cap A|\leq(\theta_{d}/2)+|H^{-}\cap
A|+\theta_{d-1}r^{d-1}K\rho^{2}r^{2}.$ (2.12)

For at least one $i\in\\{1,\ldots,d\\}$, we must have
$\operatorname{diam}(\pi_{i}(B))\geq\varepsilon r/d$. We distinguish the cases
where this holds for $i=d$, and where it holds for some $i\leq d-1$.

Figure 2:  Illustration of the proof of Lemma 2.5.
Left: when $\operatorname{diam}(\pi_{d}(B))\geq\varepsilon r/d$, the sets
$B,H^{+},H^{-},S$ are disjoint. The point $x^{-}$ (not indicated) could be the
same as $x_{0}$; if not, it is only slightly lower than $x_{0}$.
Right: when $\operatorname{diam}(\pi_{1}(B))\geq\varepsilon r/d$, the sets
$B,H^{-},Q^{+},Q^{-},S$ are disjoint.

First suppose $\operatorname{diam}(\pi_{d}(B))\geq\varepsilon r/d$. Choose
$x^{+}\in B$ of maximal height (i.e., maximal $d$-coordinate), $x^{-}\in B$ of
minimal height, and $y\in B$ of maximal $1$-coordinate (see Figure 2 (Left)).

For all $z\in B\oplus B_{r}(o)$ we have $\|\pi(z)\|\leq\|z-x_{0}\|\leq 2\rho
r$ so by (2.9) we have $|\phi(\pi(z))|\leq K\rho^{2}r^{2}$. Applying this in
the case $z=x^{-}$, we deduce that

$\displaystyle\pi_{d}(x^{+})\geq\pi_{d}(x^{-})+\varepsilon r/d\geq(\varepsilon
r/d)-K\rho^{2}r^{2}\geq(8/9)\varepsilon r/d,$

and thus

$\displaystyle\pi_{d}(x^{+})-\phi(\pi(z))\geq(8/9)\varepsilon
r/d-K\rho^{2}r^{2}\geq(7/9)\varepsilon r/d,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall z\in
B\oplus B_{r}(o).$

Let $H^{+}:=\\{z\in B_{r}(x^{+}):\pi_{d}(z)>\pi_{d}(x^{+})\\}$ (see Figure 2).
Then $H^{+}\cap B=\varnothing$, since $x^{+}$ is a point of maximal height in
$B$. Also $H^{+}\subset B\oplus B_{r}(o)$, so for all $z\in H^{+}$ we have

$\phi(\pi(z))\leq
K\rho^{2}r^{2}\leq(\varepsilon/(9d))r\leq\pi_{d}(x^{+})<\pi_{d}(z),$

so $z\in A$. Also, since $\pi_{d}(z)>\pi_{d}(x^{+})\geq\pi_{d}(x_{0})$ we have
from (2.10) that $z\notin H^{-}$. Hence $H^{+}\subset A\setminus H^{-}$.

Now consider $y$. For $1\leq i\leq d$ let $e_{i}$ denote the $i$th unit
coordinate vector. Define a point $\tilde{y}$ slightly to the right of $y$ by

$\displaystyle\tilde{y}:=\begin{cases}y+(\varepsilon r/(8d))e_{1}-(\varepsilon
r/(8d))e_{d}&{\rm if}\leavevmode\nobreak\
\pi_{d}(y)\geq(\pi_{d}(x^{+})+\pi_{d}(x^{-}))/2\\\ y+(\varepsilon
r/(8d))e_{1}+(\varepsilon r/(8d))e_{d}&{\rm if}\leavevmode\nobreak\
\pi_{d}(y)<(\pi_{d}(x^{+})+\pi_{d}(x^{-}))/2,\end{cases}$

and define the small ball $S:=B_{\varepsilon r/(9d)}(\tilde{y}).$ Then
$|S|=\delta_{1}r^{d}$, where we set
$\delta_{1}:=\theta_{d}(\varepsilon/(9d))^{d}$.

Suppose $\pi_{d}(y)\geq(\pi_{d}(x^{+})+\pi_{d}(x^{-}))/2$ (as well as
$\operatorname{diam}(\pi_{d}(B))\geq\varepsilon r/d$).

Then for all $z\in S$ we have $\pi_{d}(z)\leq\pi_{d}(y)\leq\pi_{d}(x^{+})$ so
$z\notin H^{+}$. Moreover

$\pi_{d}(z)\geq\pi_{d}(y)-\varepsilon r/(4d)\geq\pi_{d}(x^{-})+\varepsilon
r/(4d)\geq\pi_{d}(x_{0})+\varepsilon r/(8d)$

by (2.11), applied to $w=x^{-}$. Therefore $z\notin H^{-}$ by (2.10), and also
(by (2.9)) $\pi_{d}(z)\geq\phi(z)$ so $z\in A$. Thus $S\subset
A\setminus(H^{+}\cup H^{-})$ in this case.

Now suppose $\pi_{d}(y)<(\pi_{d}(x^{+})+\pi_{d}(x^{-}))/2$ (as well as
$\operatorname{diam}(\pi_{d}(B))\geq\varepsilon r/d$).

Then for all $z\in S$ we have $\pi_{d}(z)\leq\pi_{d}(y)+\varepsilon
r/(4d)\leq\pi_{d}(x^{+})$, so $z\notin H^{+}$. Also, since
$\pi_{d}(y)\geq\phi(\pi(y))\geq-K\rho^{2}r^{2}$, we have

$\pi_{d}(z)\geq\pi_{d}(y)+\varepsilon r/(72d)\geq
K\rho^{2}r^{2}\geq\phi(\pi(z)),$

so $z\in A$, and also by (2.11) applied to $w=y$, we have
$\pi_{d}(z)\geq\pi_{d}(x_{0})$, so $z\notin H^{-}$. Therefore $S\subset
A\setminus(H^{+}\cup H^{-})$ in this case too. Thus, whenever
$\operatorname{diam}(\pi_{d}(B))\geq\varepsilon r/d$, we have

$\displaystyle|(B\oplus B_{r}(o))\cap A|\geq|B|+|H^{+}|+|S|+|H^{-}\cap A|.$
(2.13)

Combining (2.13) and (2.12), provided
$r\leq\delta_{1}/(2K\rho^{2}\theta_{d-1})$ we have

$\displaystyle|(B\oplus B_{r}(o))\cap A|\geq|B|$
$\displaystyle+|B_{r}(x_{0})\cap A|+(\delta_{1}/2)r^{d},$ $\displaystyle{\rm
if}\leavevmode\nobreak\ \operatorname{diam}(\pi_{d}(B))\geq\varepsilon r/d.$
(2.14)

Now suppose $\operatorname{diam}\pi_{i}(B)\geq\varepsilon r/d$ for some
$i\in\\{1,\ldots,d-1\\}$. We shall consider here the case where this holds for
$i=1$; the other cases may be treated similarly.

In this case, let $x^{-},x^{+},y$ be points in $B$ of minimal $1$-coordinate,
maximal $1$-coordinate, and maximum height respectively. Let
$\delta_{2}:=\delta_{1}/(2\theta_{d-1})$. Define the sets $Q^{-}$ and $Q^{+}$
(slightly less than quarter-balls of radius $r$: see Figure 2 (Right)) by

$\displaystyle Q^{-}:=\\{z\in
B_{r}(x^{-}):\pi_{d}(z)\geq\pi_{d}(x^{-})+\delta_{2}r,\pi_{1}(z)<\pi_{1}(x^{-})\\};$
$\displaystyle Q^{+}:=\\{z\in
B_{r}(x^{+}):\pi_{d}(z)\geq\pi_{d}(x^{+})+\delta_{2}r,\pi_{1}(z)>\pi_{1}(x^{+})\\}.$

By (2.9), for $z\in Q^{-}$ we have $\phi(\pi(z))\leq K\rho^{2}r^{2}$, so
provided $r<\delta_{2}/(2K\rho^{2})$, for all $z\in Q^{-}$ we have

$\pi_{d}(z)\geq\pi_{d}(x^{-})+\delta_{2}r\geq\delta_{2}r-K\rho^{2}r^{2}\geq
K\rho^{2}r^{2}\geq\phi(\pi(z)),$

so that $z\in A$. Also by (2.11) applied to $w=x^{-}$ we have
$\pi_{d}(z)\geq\pi_{d}(x^{-})\geq\pi_{d}(x_{0})-K\rho^{2}r^{2}$, so $z\notin
H^{-}$ by (2.10). Thus $Q^{-}\subset A\setminus H^{-}$, and similarly
$Q^{+}\subset A\setminus H^{-}$. Also $(Q^{-}\cup Q^{+})\cap B=\varnothing$,
and $|Q^{-}\cup
Q^{+}|\geq(\theta_{d}-2\delta_{2}\theta_{d-1})r^{d}/2=(\theta_{d}-\delta_{1})r^{d}/2$.

In this case we define a point $\tilde{y}$ slightly above $y$ by

$\displaystyle\tilde{y}:=\begin{cases}y+(\varepsilon r/(8d))e_{d}+(\varepsilon
r/(8d))e_{1}&{\rm if\leavevmode\nobreak\
}\pi_{1}(y)\leq(\pi_{1}(x^{-})+\pi_{1}(x^{+}))/2\\\ y+(\varepsilon
r/(8d))e_{d}-(\varepsilon r/(8d))e_{1}&{\rm if\leavevmode\nobreak\
}\pi_{1}(y)>(\pi_{1}(x^{-})+\pi_{1}(x^{+}))/2,\end{cases}$

and set $S:=B_{\varepsilon r/(9d)}(\tilde{y})$: see Figure 2 (Right). Then
$|S|=\delta_{1}r^{d}$ as before.

Then for all $z\in S$ we have $\pi_{d}(z)>\pi_{d}(y)\geq\pi_{d}(x_{0})$, so
that $z\notin B$ and $z\notin H^{-}$. Also $\phi(\pi(z))\leq
K\rho^{2}r^{2}<\varepsilon r/(72d)\leq\pi_{d}(z)$, so $z\in A$. Moreover, if
$\pi_{1}(y)>(\pi_{1}(x^{-})+\pi_{1}(x^{+}))/2$ then

$\pi_{1}(z)-\pi_{1}(x^{-})=\pi_{1}(y)-\pi_{1}(x^{-})+(\pi_{1}(z)-\pi_{1}(y))\geq(\varepsilon
r/(2d))-(\varepsilon r/(4d))>0,$

while if $\pi_{1}(y)\leq(\pi_{1}(x^{-})+\pi_{1}(x^{+}))/2$ then
$\pi_{1}(z)-\pi_{1}(x^{-})>\pi_{1}(y)-\pi_{1}(x^{-})\geq 0$ so in both cases
$z\notin Q^{-}$. Similarly $z\notin Q^{+}$. Thus $S\subset
A\setminus(Q^{+}\cup Q^{-}\cup B\cup H^{-})$. Combining all of this and using
(2.12) in the third line below yields

$\displaystyle|(B\oplus B_{r}(o))\cap A|$ $\displaystyle\geq|B|+|Q^{-}\cup
Q^{+}|+|S|+|H^{-}\cap A|$
$\displaystyle\geq|B|+((\theta_{d}+\delta_{1})/2)r^{d}+|H^{-}\cap A|$
$\displaystyle\geq|B|+|B_{r}(x_{0})\cap
A|-\theta_{d-1}r^{d-1}K\rho^{2}r^{2}+(\delta_{1}/2)r^{d}$
$\displaystyle\geq|B|+|B_{r}(x_{0})\cap
A|+(\delta_{1}/4)r^{d}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ {\rm if}\leavevmode\nobreak\
\operatorname{diam}(\pi_{1}(B))\geq\varepsilon r/d,$

provided $r\leq\delta_{1}/(4K\rho^{2}\theta_{d-1})$. Combined with (2.14),
this shows that (2.8) holds for $r$ small if we take
$\delta^{\prime}=\delta_{1}/4$. ∎

##  3 Poisson approximation for the $k$-isolated vertices

Fix $k\in\mathbb{N}$. We say a vertex is $k$-isolated if its degree is at most
$k-1$. Given $n,r>0$ let $F_{n,r}$ denote the number of $k$-isolated vertices
in $G(\mathcal{P}_{n},r)$:

$\displaystyle
F_{n,r}:=\sum_{x\in\mathcal{P}_{n}}\mathbbm{1}\\{\mathcal{P}_{n}(B(x,r))\leq
k\\}.$ (3.1)

The goal of this section is to prove (in Proposition 3.1 below) Poisson
approximation for $F_{n,r}$ when $n$ is large and $r$ is small.

Throughout this section we adopt our working assumption on $\nu$. Moreover we
assume either that $d\geq 2$ and the support $A$ of $\nu$ is compact with
$C^{2}$ boundary, or that $d=2$ and $A$ is a polygon. We do not assume in this
section that $\nu$ is necessarily uniform on $A$. Recall that
$\mathcal{P}_{n}$ is the Poisson process in $\mathbb{R}^{d}$ with intensity
measure $n\nu$.

A fundamental identity used throughout this paper is the Mecke equation which
basically says that the law of a Poisson process $\mathcal{P}$ conditioned on
having a point mass at $x$ is that of $\mathcal{P}\cup\\{x\\}$. More
precisely, let $\mathcal{P}$ be a Poisson process on $\mathbb{R}^{d}$ with
diffuse intensity measure $\lambda$ (that is, $\lambda$ does not charge
atoms). The Mecke equation says that

$\displaystyle\mathbb{E}\Big{[}\sum_{x\in\mathcal{P}}f(x,\mathcal{P})\Big{]}=\int\mathbb{E}\left[f(x,\mathcal{P}\cup\\{x\\})\right]\lambda(dx),$
(3.2)

for all $f:\mathbb{R}^{d}\times\mathbf{N}(\mathbb{R}^{d})\to\mathbb{R}$ such
that both sides of the identity are finite, where $\mathbf{N}(\mathbb{R}^{d})$
denotes the space of all locally finite subsets of $\mathbb{R}^{d}$ \- see [7,
Chapter 4] for a more general statement.

By the Mecke equation, given $n,r>0$ we have

$\displaystyle\mathbb{E}[F_{n,r}]=n\int_{A}p_{n,r}(x)\nu(dx),$ (3.3)

where for each $x\in A$ we set

$\displaystyle p_{n,r}(x):=\mathbb{P}[\mathcal{P}_{n}(B(x,r))\leq
k-1]=\sum_{j=0}^{k-1}(n(\nu(B_{r}(x)))^{j}/j!)\exp(-n\nu(B_{r}(x))).$ (3.4)

Given random variables $X,Z$ taking values in
$\mathbb{N}_{0}:=\mathbb{N}\cup\\{0\\}$, define the total variation distance

$\displaystyle
d_{\mathrm{TV}}(X,Z):=\sup_{B\subset\mathbb{N}_{0}}|\mathbb{P}[X\in
B]-\mathbb{P}[Z\in B]|.$

Given $\alpha>0$, let ${\mathsf{Po}}_{\alpha}$ be Poisson distributed with
mean $\alpha$.

######  Proposition 3.1 (Poisson approximation).

Let $\beta^{\prime}>0$. Let $(r_{n})_{n\geq 1}$ be chosen so that $r_{n}\geq
0$ for all $n$ and

$\displaystyle\lim_{n\to\infty}\mathbb{E}[F_{n,r_{n}}]=\beta^{\prime}.$ (3.5)

Then we have

$\displaystyle
d_{\mathrm{TV}}(F_{n,r_{n}},{\mathsf{Po}}_{\mathbb{E}F_{n,r_{n}}})=O((\log
n)^{1-d})\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ {\rm
as}\leavevmode\nobreak\ n\to\infty.$ (3.6)

In particular, with $L_{n,k}=L_{k}(\mathcal{P}_{n})$ defined at (1.4),

$\displaystyle\mathbb{P}[L_{n,k}\leq
r_{n}]-\exp(-\mathbb{E}[F_{n,r_{n}}])=O((\log n)^{1-d})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ {\rm as}\leavevmode\nobreak\
n\to\infty.$ (3.7)

We prepare for proving this with three lemmas, the first of which is used
repeatedly later on.

######  Lemma 3.2.

Under the WA, assuming either that $A$ has a $C^{2}$ boundary or $d=2$ and $A$
is polygonal, there exists a constant $\delta_{0}>0$ (depending on $A$ and
$f$) such that

$\displaystyle 2\delta_{0}r^{d}\leq\nu(B_{r}(x))\leq\theta_{d}r^{d}f_{\rm
max},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\ x\in
A,r\in(0,1].$ (3.8)

###### Proof.

The second inequality is clear. The first inequality follows from Lemma
2.2-(i) in the case where $A$ has a $C^{2}$ boundary, and can be seen directly
when $A$ is polygonal. ∎

######  Lemma 3.3.

Let $\beta^{\prime}\in(0,\infty)$ and suppose that $(r_{n})_{n\geq 1}$
satisfies (3.5). Then we have that $\liminf_{n\to\infty}(nr_{n}^{d}/\log
n)\geq 1/(f_{\rm max}\theta_{d})$, and $\limsup_{n\to\infty}(nr_{n}^{d}/\log
n)<\infty$.

###### Proof.

Let $\alpha\in(0,1/(f_{\rm max}\theta_{d}))$. If $nr_{n}^{d}<\alpha\log n$,
then for all $x\in A$ we have $n\nu(B_{r_{n}}(x))\leq n\theta_{d}f_{\rm
max}r_{n}^{d}\leq\alpha\theta_{d}f_{\rm max}\log n$. Therefore $n\int
e^{-n\nu(B_{r_{n}}(x))}\nu(dx)\geq n^{1-\alpha\theta_{d}f_{\rm max}}$, so the
condition (3.5) implies that $nr_{n}^{d}\geq\alpha\log n$ for all large enough
$n$. The first claim follows.

For the second claim, let $\delta_{0}>0$ be as in (3.8). Take $s_{n}>0$ so
that $ns_{n}^{d}=\delta_{0}^{-1}\log n$. Using (3.8), for some constant $c$ we
have

$\displaystyle n\int_{A}p_{n,s_{n}}(x)\nu(dx)\leq cn(\log
n)^{k-1}\exp(-2n\delta_{0}s_{n}^{d})=c(\log n)^{k-1}n^{-1},$

which tends to zero. Hence by (3.5) we have $r_{n}\leq s_{n}$ for $n$ large,
and hence the second claim. ∎

Given $x,y\in\mathbb{R}^{d}$ and $n>0$, setting
$\mathcal{P}_{n}^{x}=\mathcal{P}_{n}\cup\\{x\\}$, we define the quantity

$\displaystyle q_{n,r}(x,y):=\mathbb{P}[\mathcal{P}^{y}_{n}(B(x,r))\leq
k-1,\mathcal{P}^{x}_{n}(B(y,r))\leq k-1].$

Our proof of Proposition 3.1 is based on the following estimate which was
proved by the local dependence approach of Stein’s method.

######  Lemma 3.4 ([8, Theorem 6.7]).

Let $n,r>0$. Then

$\displaystyle
d_{\mathrm{TV}}(F_{n,r},{\mathsf{Po}}_{\mathbb{E}[F_{n,r}]})\leq
3(I_{1}(n,r)+I_{2}(n,r))$

where

$\displaystyle I_{1}(n,r)$ $\displaystyle=n^{2}\int\mathbbm{1}\\{\|x-y\|\leq
3r\\}p_{n,r}(x)p_{n,r}(y)\nu^{2}(d(x,y))$ $\displaystyle I_{2}(n,r)$
$\displaystyle=n^{2}\int\mathbbm{1}\\{\|x-y\|\leq
3r\\}q_{n,r}(x,y)\nu^{2}(d(x,y)).$

###### Proof of Proposition 3.1.

Observe first that whenever $|\mathcal{P}_{n}|\geq k+1$, the statement
$L_{n,k}\leq r_{n}$ is equivalent to $F_{n,r_{n}}=0$, so that
$|\mathbb{P}[L_{n,k}\leq
r_{n}]-\mathbb{P}[F_{n,r_{n}}=0]|\leq\mathbb{P}[|\mathcal{P}_{n}|\leq
k]=O(n^{k}e^{-n}).$ Therefore (3.6) will imply (3.7), so it suffices to prove
(3.6).

By (3.8), provided $n$ is large enough, we have

$\displaystyle p_{n,r_{n}}(y)\leq
k(nf_{\mathrm{max}}\theta_{d}r_{n}^{d})^{k-1}\exp(-n\nu(B(y,r_{n})))\leq\exp(-\delta_{0}nr_{n}^{d}).$

Therefore,

$\displaystyle I_{1}(n,r_{n})$ $\displaystyle\leq n(3^{d}f_{\rm
max}\theta_{d}r_{n}^{d})\exp(-\delta_{0}nr_{n}^{d})n\int
p_{n,r_{n}}(x)\nu(dx)$
$\displaystyle\leq\exp(-(\delta_{0}/2)nr_{n}^{d})\mathbb{E}[F_{n,r}].$ (3.9)

Now we estimate $I_{2}:=I_{2}(n,r_{n})$. Since the integrand of $I_{2}$ is
symmetric in $x$ and $y$; thus,

$\displaystyle I_{2}=2n^{2}\int\mathbbm{1}\\{\|x-y\|\leq 3r_{n},{\rm
dist}(x,\partial A)\leq{\rm dist}(y,\partial
A)\\}q_{n,r_{n}}(x,y)\nu^{2}(d(x,y)).$

To further simplify the integral, writing $B_{x}=B(x,r_{n})$ and likewise for
$B(y,r_{n})$, we have

$\displaystyle q_{n,r_{n}}(x,y)$
$\displaystyle\leq\mathbb{P}[\mathcal{P}_{n}(B_{x})\leq
k-1,\mathcal{P}_{n}(B_{y}\setminus B_{x})\leq k-1]$
$\displaystyle=p_{n,r_{n}}(x)\mathbb{P}[\mathcal{P}_{n}(B_{y}\setminus
B_{x})\leq k-1].$

Consider first the case where $A$ has a $C^{2}$ boundary. If ${\rm
dist}(x,\partial A)\leq{\rm dist}(y,\partial A)$, setting
$\kappa_{d}:=2^{-3d-1}\theta_{d-1}$ and using Lemma 2.2-(ii) for the lower
bound and Fubini’s theorem for the upper bound below, we have

$\displaystyle f_{0}\kappa_{d}\|y-x\|r_{n}^{d-1}\leq\nu(B_{y}\setminus
B_{x})\leq f_{\rm max}\theta_{d-1}r_{n}^{d-1}\|y-x\|,$

and hence

$\displaystyle q_{n,r_{n}}(x,y)$ $\displaystyle\leq
p_{n,r_{n}}(x)\sum_{j=0}^{k-1}(nf_{\rm
max}\theta_{d-1}r_{n}^{d-1}\|y-x\|)^{j}\exp(-\kappa_{d}f_{0}\|y-x\|nr_{n}^{d-1}).$

Therefore, we have

$\displaystyle I_{2}$ $\displaystyle\leq 2\max(f_{\rm
max}\theta_{d-1},1)^{k-1}n^{2}$
$\displaystyle\times\int_{A}\left(\int_{B(x,3r_{n})}\sum_{j=0}^{k-1}(nr_{n}^{d-1}\|y-x\|)^{j}\exp(-\kappa_{d}f_{0}\|y-x\|nr_{n}^{d-1})\nu(dy)\right)p_{n,r_{n}}(x)\nu(dx).$

A change of variables $z=nr_{n}^{d-1}(y-x)$ shows that the inner integral is
bounded by $c^{\prime}r_{n}^{d}(nr_{n}^{d})^{-d}$ for some finite constant
$c^{\prime}$. Together with (3.3), this yields for some further constant
$c^{\prime\prime}$ that

$\displaystyle I_{2}\leq
2c^{\prime\prime}(nr_{n}^{d})^{1-d}\mathbb{E}[F_{n,r_{n}}].$ (3.10)

This, together with (3) and (3.5), shows that
$I_{1}+I_{2}=O((nr_{n}^{d})^{1-d})$; applying Lemma 3.4 proves (3.6) as
required for this case.

Now consider the other case, where $d=2$ and $A$ is polygonal. Let $x,y\in A$
with $\|y-x\|\leq 3r_{n}$ and ${\rm dist}(x,\partial A)\leq{\rm
dist}(y,\partial A)$. By Lemma 2.3, there exists $\delta_{1}>0$ such that
$\nu(B(y,r_{n})\setminus B(x,r_{n}))\geq\delta_{1}\|x-y\|r_{n}$. Using this,
we can estimate the contribution to $I_{2}$ from $x,y$ not too close to the
corners similarly to how we estimated $I_{2}$ at (3.10) in the previous case.

Suppose instead that $x$ is close to a corner of $A$ and $\|x-y\|\leq 3r_{n}$.
By (3.8) the contribution to $I_{2}$ from such pairs $(x,y)$ is at most
$c^{\prime\prime}n^{2}r_{n}^{4}\exp(-\delta_{2}nr_{n}^{2})$ for suitable
constants $c^{\prime\prime}<\infty,\delta_{2}>0$. Hence using Lemma 3.3, we
see that this contribution is $O(n^{-\delta_{3}})$ for some $\delta_{3}>0$.
The proof is now complete. ∎

##  4 Relating the $L_{n,k}$ to $M_{n,k}$

Throughout this section we assume that $\partial A\in C^{2}$ or that $A$ is a
convex polygon. We adopt our WA but do not assume $f$ is necessarily constant
on $A$.

Fix $k\in\mathbb{N}$. Recall that $L_{n,k}$ and $M_{n,k}$ were defined at
(1.4) and (1.1). While Proposition 3.1 provides an understanding of
$\mathbb{P}[L_{n,k}\leq r_{n}]$ for suitable $r_{n}$, for Theorems 1.1 and 1.3
we also need to understand the limiting behaviour of $\mathbb{P}[M_{n,k}\leq
r_{n}]$ and $\mathbb{P}[M_{k}(\mathcal{X}_{n})\leq r_{n}]$. In this section,
we work towards this by showing (in Proposition 4.5) that
$\mathbb{P}[L_{n,k}\leq r<M_{n,k}]$ and $\mathbb{P}[L_{k}(\mathcal{X}_{n})\leq
r<M_{k}(\mathcal{X}_{n})]$ are small for $n$ large and $r$ small.

Suppose $\mathcal{X}\subset\mathbb{R}^{d}$ with $|\mathcal{X}|\geq k+2$. By
[8, Lemma 13.1], a geometric graph $G(\mathcal{X},r)$ is either $k$-connected
or has a $(k-1)$-separating pair, but not both. Here, for
$j\in\mathbb{N}\cup\\{0\\}$ a $j$-separating pair means a pair of disjoint
non-empty subsets $\mathcal{Y},\mathcal{Y}^{\prime}$ of $\mathcal{X}$ such
that $G(\mathcal{Y},r)$ and $G(\mathcal{Y}^{\prime},r)$ are both connected,
$G(\mathcal{Y}\cup\mathcal{Y}^{\prime},r)$ is not, and
$\mathcal{X}\setminus(\mathcal{Y}\cup\mathcal{Y}^{\prime})$ contains at most
$j$ points within distance $r$ of $\mathcal{Y}\cup\mathcal{Y}^{\prime}$.

When we need to refer to an individual set in a separating pair, we use the
terminology separating set. That is, for $j\in\mathbb{N}_{0}$ a $j$-separating
set is a set $\mathcal{Y}\subset\mathcal{X}$ such that $G(\mathcal{Y},r)$ is
connected, and with $\Delta\mathcal{Y}$ denoting the set of sites in
$\mathcal{X}\setminus\mathcal{Y}$ adjacent to $\mathcal{Y}$, we have
$|\Delta\mathcal{Y}|\leq j$ and
$\mathcal{X}\setminus(\mathcal{Y}\cup\Delta\mathcal{Y})\neq\varnothing$.

Let $r>0$. When $M_{n,k}>r$, there exists a $(k-1)$-separating pair
$\mathcal{Y},\mathcal{Y}^{\prime}\subset\mathcal{P}_{n}$. When also
$L_{n,k}\leq r$, every vertex $x\in\mathcal{P}_{n}$ has degree at least $k\geq
1$, which implies that neither $\mathcal{Y}$ nor $\mathcal{Y}^{\prime}$ can be
a singleton. Our strategy in this section is to estimate the probability that
there exists a pair of non-singleton separating sets for $G({\cal P}_{n},r)$
or $G(\mathcal{X}_{n},r)$. We do this in stages, according to the size of the
separating sets.

For $x,y\in A$, we write $x<y$ if $x$ precedes $y$ in the lexicographic
ordering. We define the following ordering $\prec$ on $A$, that we shall use
repeatedly:

$\displaystyle x\prec y\Leftrightarrow({\rm dist}(x,\partial A)<{\rm
dist}(y,\partial A)){\rm\leavevmode\nobreak\ or\leavevmode\nobreak\ }({\rm
dist}(x,\partial A)={\rm dist}(y,\partial A){\rm\leavevmode\nobreak\
and\leavevmode\nobreak\ }x<y).$ (4.1)

###  4.1 Small separating sets

The goal of this section is to prove that for any fixed vertex $x\in A$, the
probability that $x$ belongs to a non-singleton $(k-1)$-separating set of
‘small’ diameter in $G(\mathcal{P}_{n}\cup\\{x\\},r)$ is negligible compared
to the probability that it has degree at most $k-1$, provided that $x\prec y$
for all other $y$ in the separating set containing $x$ (the ordering $\prec$
was defined at (4.1)).

We introduce further notation. With $k$ fixed, for $r>0$ and finite
$\mathcal{X}\subset\mathbb{R}^{d}$, $x\in\mathbb{R}^{d}$, let
$\mathcal{C}_{r}(x,\mathcal{X})$ denote the collection of $(k-1)$-separating
sets $\mathcal{Y}$ for $G(\mathcal{X}\cup\\{x\\},r)$ containing $x$ such that
moreover $x\prec y$ for all $y\in\mathcal{Y}\setminus\\{x\\}$. Given also
$\rho>0$, we are interested in the event

$\displaystyle
E_{x,\rho,r}(\mathcal{X}):=\\{\exists\mathcal{Y}\in\mathcal{C}_{r}(x,\mathcal{X}),0<\operatorname{diam}(\mathcal{Y})\leq\rho
r\\}.$ (4.2)

######  Lemma 4.1.

(i) Suppose $d\geq 2$ and $A$ has $C^{2}$ boundary. Then there exist
$\delta,r_{0}\in(0,1)$ and $c<\infty$ such that for all $n\geq k+2$, any $x\in
A$ and any $r\in(0,r_{0})$ we have

$\displaystyle\mathbb{P}[E_{x,\delta,r}(\mathcal{P}_{n})]\leq
cp_{n,r}(x)(nr^{d})^{1-d};$ (4.3)
$\displaystyle\mathbb{P}[E_{x,\delta,r}(\mathcal{X}_{n-1})]\leq
cp_{n,r}(x)(nr^{d})^{1-d},$ (4.4)

where $p_{n,r}(x)$ was defined at (3.4)

(ii) Suppose $d=2$ and $A$ is polygonal. Then there exist $K\in(0,\infty)$,
and $\delta,r_{0}\in(0,1)$ and $c<\infty$ such that for all $n\geq 3$, $x\in
A\setminus\mathsf{Cor}^{(Kr)}$, and $r\in(0,r_{0})$, (4.3) and (4.4) hold.

###### Proof.

(i) Let $\delta\in(0,1)$. Suppose that $E_{x,\delta,r}(\mathcal{P}_{n})$
occurs with some $\mathcal{Y}$. Then by considering the vertex furthest from
$x$ in $\mathcal{Y}$, we see that there exists $y\in\mathcal{P}_{n}$ such that
$\mathcal{Y}\subset B_{\|y-x\|}(x)$ and $\|y-x\|\leq\delta r$. Moreover,
setting $D_{x,y}:=(B_{r}(x)\cup B_{r}(y))\setminus B_{\|y-x\|}(x)$ we have
that $\mathcal{P}_{n}(D_{x,y})\leq k-1$. By Markov’s inequality,
$\mathbb{P}[E_{x,\delta,r}(\mathcal{P}_{n})]$ is bounded above by the expected
number of $y\in\mathcal{P}_{n}$ satisfying the aforementioned properties, and
hence by the Mecke formula

$\displaystyle\mathbb{P}[E_{x,\delta,r}({\cal P}_{n})]\leq
n\int_{B(x,\delta)}\mathbb{P}[{\cal P}_{n}(D_{x,y})\leq k-1]\nu(dy).$ (4.5)

To proceed, we need to bound the volume of $D_{x,y}$ from below. By Lemma 2.2,
there exists $r_{0}>0$ such that for all $0<r<r_{0}$ and $x,y\in A$ with
$\|x-y\|\leq r$ and $x\prec y$, setting $\kappa_{d}:=2^{-3d-1}\theta_{d-1}$ we
have

$\nu(B_{r}(x)\cup B_{r}(y))\geq\nu(B_{r}(x))+2\kappa_{d}f_{0}r^{d-1}\|y-x\|.$

Hence, for $r<r_{0}$, for $x,y\in A$ with $\|y-x\|\leq\delta r$ and $x\prec
y$,

$\displaystyle\nu(D_{x,y})\geq\nu(B_{r}(x))+2\kappa_{d}f_{0}r^{d-1}\|y-x\|-f_{\rm
max}\theta_{d}\|y-x\|^{d}.$

Now provided $\delta\leq(\kappa_{d}f_{0}/(f_{\rm max}\theta_{d}))^{1/(d-1)}$,
we have $f_{\rm max}\theta_{d}\|y-x\|^{d}\leq\kappa_{d}f_{0}r^{d-1}\|y-x\|$,
yielding

$\nu(D_{x,y})\geq\nu(B_{r}(x))+\kappa_{d}f_{0}r^{d-1}\|y-x\|.$ (4.6)

By (3.8), there is also a bound the other way, namely
$\nu(D_{x,y})\leq\nu(B_{r}(x)\cup B_{r}(y))\leq c_{0}\nu(B_{r}(x))$ for some
constant $c_{0}\in[1,\infty)$. Using (4.5) and the preceding upper and lower
bounds on $\nu(D_{x,y})$, we have

$\displaystyle\mathbb{P}[E_{x,\delta,r}(\mathcal{P}_{n})]\leq
c_{0}^{k-1}n\int_{B(x,\delta
r)}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))-nr^{d-1}f_{0}\kappa_{d}\|y-x\|}\nu(dy).$
(4.7)

Recall that
$p_{n,r}(x)=\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))}$.
Changing variable to $y^{\prime}=y-x$, and then to $z=nr^{d-1}y^{\prime}$
leads to

$\displaystyle\mathbb{P}[E_{x,\delta,r}(\mathcal{P}_{n})]$ $\displaystyle\leq
c_{0}^{k-1}f_{\max}np_{n,r}(x)\int_{\|y^{\prime}\|\leq\delta
r}e^{-nf_{0}\kappa_{d}r^{d-1}\|y^{\prime}\|}dy^{\prime}$ $\displaystyle\leq
nc^{\prime}p_{n,r}(x)n(nr^{d-1})^{-d}\int_{\mathbb{R}^{d}}e^{-f_{0}\kappa_{d}\|z\|}dz,$

for a suitable positive constant $c^{\prime}$, not depending on $r$ or $n$.
This proves (4.3).

To prove (4.4), we use similar reasoning to before, now using the union bound
(instead of the Mecke formula) and the binomial distribution, to obtain that

$\displaystyle\mathbb{P}[E_{x,\delta,r}(\mathcal{X}_{n-1})]\leq(n-1)\int_{B(x,\delta
r)}\sum_{j=0}^{k-1}\binom{n-2}{j}\nu(D_{x,y})^{j}(1-\nu(D_{x,y}))^{n-2-j}\nu(dy)$

As before we bound $\nu(D_{x,y})^{j}$ from above by
$c_{0}^{k-1}\nu(B_{r}(x))^{j-1}$. Provided $r$ is sufficiently small, we have
for all $x,y$ and all $j\leq k-1$ that $(1-\nu(D_{x,y}))^{-2-j}\leq 2$. Also
we can bound the binomial coefficient from above by $n^{j}/j!$. Combining all
of these and also using the bound $(1-t)\leq e^{-t}$ we obtain that

$\displaystyle\mathbb{P}[E_{x,\delta,r}(\mathcal{X}_{n-1})]\leq
2c_{0}^{k-1}n\int_{B(x,\delta
r)}\sum_{j=0}^{k-1}\frac{(n\nu(B_{r}(x)))^{j}}{j!}\exp(-n\nu(D_{x,y}))\nu(dy);$

then using (4.6) and arguing similarly to the Poisson case, we obtain (4.4).

(ii) Suppose $d=2$ and $A$ is polygonal. We use Lemma 2.3 in place of Lemma
2.2 to get lower bound (4.6). This together with the simple upper bound
$\nu(D_{x,y})\leq c_{0}\nu(B_{r}(x))$ and the same reasoning as in part (i)
lead to (4.3) and (4.4) in this case too. ∎

###  4.2 Medium sized separating sets

Recall the definition of $\mathcal{C}_{r}(x,\mathcal{X})$ before the previous
lemma, and $p_{n,r}(x)$ at (3.4). Given $\varepsilon,\rho$ with
$0<\varepsilon<\rho<\infty$, define the event

$\displaystyle F_{x,\varepsilon,\rho,r}({\cal
P}_{n}):=\\{\exists\mathcal{Y}\in\mathcal{C}_{r}(x,\mathcal{P}_{n}),\leavevmode\nobreak\
\varepsilon r<\operatorname{diam}(\mathcal{Y})<\rho r\\}.$ (4.8)

The next lemma helps us bound the probability of having a medium-sized
separating set.

######  Lemma 4.2.

(i) Suppose $A$ has $C^{2}$ boundary. Given $\rho,\varepsilon\in\mathbb{R}$
with $0<\varepsilon<\rho$, there exist $\delta,r_{0},c>0$ such that for all
$n\geq 2+k$, $r\in(0,r_{0})$ and all $x\in A$, we have

$\displaystyle\mathbb{P}[F_{x,\varepsilon,\rho,r}({\cal P}_{n})]\leq
cp_{n,r}(x)e^{-\delta nr^{d}};$ (4.9)
$\displaystyle\mathbb{P}[F_{x,\varepsilon,\rho,r}(\mathcal{X}_{n-1})]\leq
cp_{n,r}(x)e^{-\delta nr^{d}}.$ (4.10)

(ii) Suppose $d=2$ and $A$ is polygonal. Given $0<\varepsilon<\rho<\infty$,
there exists $K\in(0,\infty)$ and $\delta,r_{0}>0$ such that for all $n\geq
3$, $r\in(0,r_{0})$ and all $x\in A\setminus\mathsf{Cor}^{(Kr)}$, we have
(4.9) and (4.10).

###### Proof.

Later in the proof we shall use the fact that since we assume $A$ is compact
and $f$ is continuous on $A$ with $f_{0}>0$,

$\displaystyle\lim_{s\downarrow 0}\big{(}\sup\\{f(y)/f(x):x,y\in A,\|y-x\|\leq
s\\}\big{)}=1.$ (4.11)

(i) Suppose $\partial A\in C^{2}$. Without loss of generality, we can and do
assume $\varepsilon<1$. Let $\delta_{1}:=\delta^{\prime}(d,\rho,\varepsilon)$
be as in Lemma 2.5. With $e_{1}$ denoting an arbitrary unit vector in
$\mathbb{R}^{d}$, choose $\delta_{2}\in(0,1/(99\sqrt{d}))$ such that

$\displaystyle|B_{1}(o)\setminus
B_{1-\sqrt{d}\delta_{2}}(o)|\leq\delta_{1}/8;\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ |B_{1}(o)\setminus
B_{1}(2\sqrt{d}\delta_{2}e_{1})|\leq\delta_{1}/16.$ (4.12)

Partition $\mathbb{R}^{d}$ into cubes of side length $\delta_{2}r$. Given
$\mathcal{Y}\in\mathcal{C}_{r}(x,{\cal P}_{n})$, denote by
$\mathsf{A}_{\delta_{2}}(\mathcal{Y})$ the closure of the union of all the
cubes in the partition that intersect $\mathcal{Y}$. Here $\mathsf{A}$ stands
for “animal” and has no connection to our underlying domain $A$. If
$\operatorname{diam}\mathcal{Y}\in(\varepsilon r,\rho r]$, then
$\mathsf{A}_{\delta_{2}}(\mathcal{Y})\subset B(x,\rho r+r)$ and
$\mathsf{A}_{\delta_{2}}(\mathcal{Y})$ can take at most
$c=2^{{(2\lceil\rho/{\delta_{2}}\rceil+2)^{d}}}$ different possible shapes.

If the event $F_{x,\varepsilon,\rho,r}({\cal P}_{n})$ occurs there is at least
one set $\mathcal{Y}\in\mathcal{C}_{r}(x,{\cal P}_{n})$ with $\varepsilon
r<\operatorname{diam}\mathcal{Y}\leq\rho r$. If there are several such sets
$\mathcal{Y}$, choose one of these according to some deterministic rule, and
denote it by $\mathcal{Y}^{*}({\cal P}_{n})$.

Fix a possible shape $\sigma$ that might arise as
$\mathsf{A}_{\delta_{2}}(\mathcal{Y})$ for some
$\mathcal{Y}\in\mathcal{C}_{r}(x,{\cal P}_{n})$ with
$\operatorname{diam}\mathcal{Y}\in(\varepsilon r,\rho r]$, and suppose the
event $F_{x,\varepsilon,\rho,r}({\cal
P}_{n})\cap\\{\mathsf{A}_{\delta_{2}}(\mathcal{Y}^{*}({\cal
P}_{n}))=\sigma\\}$ occurs. Let $\sigma^{*}:=\\{z\in\sigma:x\prec
z\\}\cup\\{x\\}$. Set $H:=H(\sigma)=(\sigma^{*}\oplus
B_{(1-\sqrt{d}{\delta_{2}})r}(o))\setminus\sigma^{*}$. By the triangle
inequality, $H\subset\mathcal{Y}^{*}({\cal P}_{n})\oplus B_{r}(o)$. We claim
that $\mathcal{P}_{n}(H)\leq k-1$. Indeed, if there are $k$ or more points in
$\mathcal{P}_{n}\cap H$, then since $\mathcal{Y}^{*}({\cal P}_{n})$ is
$(k-1)$-separating, necessarily one of these points, denoted by $y$, belongs
to $\mathcal{Y}^{*}({\cal P}_{n})$. Hence $y\in\mathcal{P}_{n}\cap
H\cap\mathcal{Y}^{*}({\cal P}_{n})$, implying $y\in\sigma$ and therefore
$y\in\sigma\setminus\sigma^{*}$ (since $y\in H$), but this would contradict
the assumption that $x\prec y$ for all $y\in\mathcal{Y}^{*}({\cal
P}_{n})\setminus\\{x\\}$.

Now we estimate from below the volume of $H\cap A$. Recall that
$\delta_{1}=\delta^{\prime}(d,\rho,\varepsilon)$ is as in Lemma 2.5. Applying
(2.8) from there leads to

$\displaystyle|H\cap A|\geq|B_{r(1-\sqrt{d}{\delta_{2}})}(x)\cap
A|+\delta_{1}r^{d}.$

By (4.12), $|(B_{r}(x)\setminus B_{r(1-\sqrt{d}\delta_{2})}(x))\cap
A|\leq(\delta_{1}/8)r^{d}$ and hence

$|B_{r(1-\sqrt{d}{\delta_{2}})}(x)\cap A|\geq|B_{r}(x)\cap
A|-(\delta_{1}/8)r^{d}.$

Let $\delta_{3}\in(0,1/2)$ be such that
$\delta_{4}:=(1-2\delta_{3})(1+7\delta_{1}/(8f_{\rm max}\theta_{d}))-1>0$. By
the preceding estimates, and (4.11), provided $r$ is small we have that

$\displaystyle\nu(H)$ $\displaystyle\geq(1-\delta_{3})f(x)\left(|B_{r}(x)\cap
A|+(7/8)\delta_{1}r^{d}\right)$
$\displaystyle\geq(1-2\delta_{3})\nu(B_{r}(x))\left(1+\frac{7\delta_{1}r^{d}}{8f_{\rm
max}\theta_{d}r^{d}}\right)=(1+\delta_{4})\nu(B_{r}(x)).$

Let $\delta_{5}=\delta_{0}\delta_{4}$, with $\delta_{0}$ given at (3.8). Then

$\displaystyle\nu(H)\geq\nu(B_{r}(x))+\delta_{5}r^{d}.$ (4.13)

Also, because of the upper bound on diameters and (3.8), there is a constant
$c_{1}$ such that $\nu(H)\leq c_{1}\nu(B_{r}(x))$ uniformly over all possible
$x$, all small $r$, and all possible $\sigma$.

Using these upper and lower bounds on $\nu(H)$, we can deduce that

$\displaystyle\mathbb{P}[F_{x,\varepsilon,\rho,r}({\cal
P}_{n})\cap\\{\mathsf{A}_{\delta_{2}}(\mathcal{Y}^{*}({\cal
P}_{n}))=\sigma\\}]$ $\displaystyle\leq\mathbb{P}[{\cal P}_{n}(H)\leq k-1]$
$\displaystyle\leq
c_{1}^{k-1}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))-n\delta_{5}r^{d}}$
$\displaystyle=c_{1}^{k-1}p_{n,r}(x)e^{-n\delta_{5}r^{d}}.$

This, together with the union bound over the choice of possible shapes
$\sigma$, gives us (4.9).

To prove the result (4.10) for the binomial case we use the volume estimates
(4.13) and $\nu(H)\leq c_{1}\nu(B_{r}(x))$ once more. We have

$\displaystyle\mathbb{P}[F_{x,\varepsilon,\rho,r}(\mathcal{X}_{n-1})\cap\\{\mathsf{A}_{\delta_{2}}(\mathcal{Y}^{*}(\mathcal{X}_{n-1}))=\sigma\\}]$
$\displaystyle\leq\mathbb{P}[\mathcal{X}_{n-1}(H)\leq k-1]$
$\displaystyle=\sum_{j=0}^{k-1}\binom{n-1}{j}\nu(H)^{j}(1-\nu(H))^{n-1-j}$
$\displaystyle\leq
2c_{1}^{k-1}\sum_{j=0}^{k-1}(n^{j}/j!)\nu(B_{r}(x))^{j}\exp(-n\nu(H))$
$\displaystyle\leq 2c_{1}^{k-1}p_{n,r}(x)e^{-n\delta_{5}r^{d}},$

and hence (4.10).

(ii) Suppose $d=2$ and $A$ is polygonal. Let $0<\varepsilon<\rho<\infty$.
Choose $K$ such that for all $r$ and all $x\in A\setminus\mathsf{Cor}^{(Kr)}$,
the ball $B_{(\rho+9)r}(x)$ intersects at most one edge of $A$. We can choose
such a $K$ by a similar argument to the proof of Lemma 2.3. Then for $x\in
A\setminus\mathsf{Cor}^{(Kr)}$ we can deduce (4.9) and (4.10) in the same way
as in the proof of part (i). ∎

Next we consider the probability of having a small or medium-sized separating
set near the corner of a polygon in dimension 2. We do not attempt to compare
this probability with $p_{n,k-1}(x)$ because the corners have negligible area
and we can get by with a less precise estimate.

######  Lemma 4.3.

Suppose that $d=2$ and $A$ is polygonal. Then there exists constants
$c,\delta,r_{0}\in(0,\infty)$ depending only on $A$ and $f_{0}$, such that for
any $\rho,K\in(0,\infty)$, if $n\geq k+2$ then

$\displaystyle\sup_{x\in\mathsf{Cor}^{(Kr)},r\in(0,r_{0})}\mathbb{P}[\exists\mathcal{Y}\in\mathcal{C}_{r}(x,\mathcal{P}_{n}),\operatorname{diam}(\mathcal{Y})\leq\rho
r]\leq c\exp(-\delta nr^{2});$ (4.14)
$\displaystyle\sup_{x\in\mathsf{Cor}^{(Kr)},r\in(0,r_{0})}\mathbb{P}[\exists\mathcal{Y}\in\mathcal{C}_{r}(x,\mathcal{X}_{n-1}),\operatorname{diam}(\mathcal{Y})\leq\rho
r]\leq c\exp(-\delta nr^{2}).$ (4.15)

###### Proof.

Fix $\rho,K\in(0,\infty)$. Let $\alpha_{\rm min}$ be the smallest angle of the
corners of $A$. Assume without loss of generality that one of the corners of
$A$ lies at the origin, and moreover one of the edges of $A$ incident to the
origin is in the direction of the positive $x$-axis, while the other edge is
the in the anti-clockwise direction from the positive $x$-axis which can be
either in the upper (convex polygon) or lower (non-convex polygon) half-plane.

Let $\delta_{2}:=1/4$. Define $\mathsf{A}_{\delta_{2}}(\mathcal{Y}^{*}({\cal
P}_{n}))$ as in the proof of Lemma 4.2. As argued there, if there exists
$\mathcal{Y}\in\mathcal{C}_{r}(x,{\cal P}_{n})$ with
$\operatorname{diam}(\mathcal{Y})\leq\rho r$, then
$\mathsf{A}_{\delta_{2}}(\mathcal{Y}^{*}({\cal P}_{n}))$ can take at most $c$
different possible shapes for some finite $c$ not depending on $r$.

Suppose $x\in B_{Kr}(o)$. Fix a possible shape $\sigma$ that might arise when
there exists $\mathcal{Y}\in\mathcal{C}_{r}(x,{\cal P}_{n})$ with
$\operatorname{diam}(\mathcal{Y})\leq\rho r$, and suppose the event
$\\{\mathsf{A}_{\delta_{2}}(\mathcal{Y}^{*}({\cal P}_{n}))=\sigma\\}$ occurs.
Let $y_{\rm max}$ be the largest point of $\sigma$ in the lexicographic
ordering (i.e., the highest rightmost point). Let $S$ be a sector centred on
$y$ of radius $r/2$ and with one straight edge from $y$ in the direction of
the positive $x$-axis, while the other edge is in the anti-clockwise direction
with angle $\min(\alpha_{\rm min},\pi/2)$ from the first edge.

Then provided $r$ is small enough, $S\subset A$ and the interior of $S$ is
disjoint from $\sigma$. Also ${\cal P}_{n}(S)\leq k-1$, since the squares
making up $\sigma$ have diameter less than $r/2$, so $S$ is contained in
${\cal P}_{n}\oplus B_{r}(o)$. Also
$f_{0}\min(\alpha_{\min},\pi/2)r^{2}/2\leq\nu(S)\leq(\pi/4)f_{\rm max}r^{2}.$
Therefore

$\displaystyle\mathbb{P}[\\{\exists\mathcal{Y}\in\mathcal{C}_{r}(x,\mathcal{P}_{n}),\operatorname{diam}(\mathcal{Y})\leq\rho
r\\}\cap\\{\mathsf{A}_{\delta_{2}}(\mathcal{Y}^{*}({\cal
P}_{n}))=\sigma\\}]\leq k(nf_{\rm max}(\pi/4)r^{2})^{k-1}$
$\displaystyle\times\exp(-nf_{0}\min(\alpha_{\min},\pi/2)r^{2}/2).$

Summing over all possible $\sigma$ and treating other corners similarly, we
obtain (4.14). Also

$\displaystyle\mathbb{P}[\\{\exists\mathcal{Y}\in\mathcal{C}_{r}(x,\mathcal{X}_{n-1}),\operatorname{diam}(\mathcal{Y})\leq\rho
r\\}\cap\\{\mathsf{A}_{\delta}(\mathcal{Y}^{*}(\mathcal{X}_{n-1}))=\sigma\\}]$
$\displaystyle\leq\sum_{j=0}^{k-1}\binom{n-1}{j}\nu(S)^{j}(1-\nu(S))^{n-1-j}$
$\displaystyle\leq\sum_{j=0}^{n}2((n\nu(S))^{j}/j!)\exp(-n\nu(S))$

and using the same upper and lower bounds on $\nu(S)$ as before gives us
(4.15). ∎

###  4.3 Large separating pairs

Given $r>0$, $\rho>0$, recall that if $L_{n,k}\leq r<M_{n,k}$ then there is a
$(k-1)$-separating pair for $G({\cal P}_{n},r)$, and each individual set in
the pair is non-singleton. Then, either there exists a non-singleton
$(k-1)$-separating set with diameter at most $\rho r$, or both sets in the
pair have diameter greater than $\rho r$. Our next lemma deals with the latter
possibility. Given $\rho>0,r\geq 0$, define the event

$H_{r,\rho}(\mathcal{X})=\\{\exists\text{ a }(k-1)\text{-separating pair
}\mathcal{Y},\mathcal{Y}^{\prime}\text{ for
}G(\mathcal{X},r),\min(\operatorname{diam}(\mathcal{Y}),\operatorname{diam}(\mathcal{Y}^{\prime}))>\rho
r\\}.$

######  Lemma 4.4.

Suppose $(r_{n})_{n>0}$ satisfies (3.5) for some
$\beta^{\prime}\in(0,\infty)$. Then there exists $\rho\in(0,\infty)$ such that
$\mathbb{P}[H_{r_{n},\rho}(\mathcal{P}_{n})]=O(n^{-2})$ and
$\mathbb{P}[H_{r_{n},\rho}(\mathcal{X}_{n})]=O(n^{-2})$ as $n\to\infty$.

###### Proof.

Case 1: $\partial A\in C^{2}$. See [13, Equation (3.14)]. That result is
formulated only for $\mathcal{X}_{n}$, not for ${\cal P}_{n}$, and also only
for the case $k=0$. However, it uses only the probability bound that if $X$ is
binomial with mean $\mu$ then $\mathbb{P}[X=0]\leq e^{-\mu}$. Using a standard
Chernoff bound, e.g. [8, Lemmas 1.1 and 1.2], we have that if $X$ is either
binomal or Poisson distributed with mean $\mu$ for $\mu$ sufficiently large,
we have $\mathbb{P}[X<k]\leq e^{-\mu/2}$, and using this we can readily adapt
the argument in [13] to the generality required here.

Case 2: $d=2$ and $A$ is polygonal. In this case we use the proof of [17,
Lemma 3.12]. Our $r_{n}$ is not quite the same as there, but the argument
works for our $r_{n}$ too; the properties of $r_{n}$ given in Lemma 3.3 are
sufficient. Again, the proof in [17] is only for $\mathcal{X}_{n}$, but it
relies only on Chernoff probability bounds for a binomial random variable,
which also apply for a Poisson random variable with the same mean and
therefore the result holds for ${\cal P}_{n}$ as well as for
$\mathcal{X}_{n}$. ∎

We can now bound $\mathbb{P}[L_{n,k}\leq r_{n}<M_{n,k}]$, which is the result
we have been leading up to in this whole section.

######  Proposition 4.5.

Let $\beta^{\prime}\in(0,\infty)$ and suppose $(r_{n})_{n\geq 1}$ satisfies
(3.5). Then as $n\to\infty$,

$\displaystyle\mathbb{P}[L_{n,k}\leq r_{n}<M_{n,k}]=O((\log n)^{1-d});$ (4.16)
$\displaystyle\mathbb{P}[L_{k}(\mathcal{X}_{n})\leq
r_{n}<M_{k}(\mathcal{X}_{n})]=O((\log n)^{1-d}).$ (4.17)

###### Proof.

Given $r,\rho\in(0,\infty)$, and finite $\mathcal{X}\subset\mathbb{R}^{d}$,
define the event

$\displaystyle J_{r,\rho}(\mathcal{X}):=\\{\exists
x\in\mathcal{X},\mathcal{Y}\in\mathcal{C}_{r}(x,\mathcal{X}),0<\operatorname{diam}(\mathcal{Y})\leq\rho
r\\}.$

As discussed at the start of this section, if $L_{k}(\mathcal{X})\leq
r_{n}<M_{k}(\mathcal{X})$, then either $J_{r,\rho}(\mathcal{X})$ or
$H_{r,\rho}(\mathcal{X})$ occurs. Hence by Lemma 4.4, it suffices to prove
that for any $\rho\in(0,\infty)$, the events $J_{r_{n},\rho}(\mathcal{P}_{n})$
and $J_{r_{n},\rho}(\mathcal{X}_{n})$ occur with probability $O((\log
n)^{1-d})$ as $n\to\infty$.

Case 1: $\partial A\in C^{2}$. Fix $\rho\in(0,\infty)$. Let $N_{n}$ denote the
(random) number of $x\in{\cal P}_{n}$ such that there exists a
$\mathcal{Y}\in\mathcal{C}_{r_{n}}(x,{\cal P}_{n})$ with
$0<\operatorname{diam}(\mathcal{Y})\leq\rho r_{n}$. By Markov’s inequality
$\mathbb{P}[J_{\rho,r_{n}}({\cal P}_{n})]=\mathbb{P}[N_{n}\geq
1]\leq\mathbb{E}[N_{n}]$.

Let $\delta$ be as in Lemma 4.1 (i) and assume without loss of generality that
$0<\delta<\rho$. Then by the Mecke equation and the definitions of
$E_{x,\rho,r}$ and $F_{x,\varepsilon,\rho,r}$ at (4.2) and (4.8), and the
union bound

$\displaystyle\mathbb{E}[N_{n}]$ $\displaystyle\leq
n\int_{A}\mathbb{P}[E_{x,\delta,r_{n}}(x,\mathcal{P}_{n})]\nu(dx)+n\int_{A}\mathbb{P}[F_{x,\delta,\rho,r_{n}}(x,\mathcal{P}_{n})]\nu(dx).$
(4.18)

Using Lemma 4.1 for the first integral and Lemma 4.2 for the second integral,
and (3.3), we can find $c,\delta_{2}\in(0,\infty)$ such that for large enough
$n$ we have that

$\displaystyle\mathbb{E}[N_{n}]\leq
c((nr_{n}^{d})^{1-d}+e^{-\delta_{2}nr_{n}^{d}})\mathbb{E}[F_{n,r_{n}}],$

where $F_{n,r}$ was defined at (3.1) (not related to $F_{x,\delta,\rho,r}$).
From this, we obtain the claimed estimate (4.16) by (3.5) and Lemma 3.3.

Case 2: $d=2$ and $A$ is polygonal. Fix $\rho\in(0,\infty)$. Let $\delta$ be
as in Lemma 4.1 (ii); assume without loss of generality that $0<\delta<\rho$.
By a similar argument to (4.18) we have

$\displaystyle\mathbb{P}[J_{\rho,r_{n}}({\cal P}_{n})]$
$\displaystyle\leq\int_{A\setminus\mathsf{Cor}^{(Kr_{n})}}\mathbb{P}[E_{x,\delta,r_{n}}(x,\mathcal{P}_{n})]n\nu(dx).$
$\displaystyle+\int_{A\setminus\mathsf{Cor}^{(Kr_{n})}}\mathbb{P}[F_{x,\delta,\rho,r_{n}}(x,\mathcal{P}_{n})]n\nu(dx).$
$\displaystyle+\int_{\mathsf{Cor}^{(Kr_{n})}}\mathbb{P}[\\{\exists\mathcal{Y}\in\mathcal{C}_{r_{n}}(x,\mathcal{P}_{n}),\operatorname{diam}(\mathcal{Y})\leq\rho
r_{n}\\}]n\nu(dx).$

We can deal with the first two integrals just as we did in Case 1. By Lemma
4.3, there is a constant $\delta^{\prime}$ such that the third integral is
$O(nr_{n}^{2}\exp(-\delta^{\prime}nr_{n}^{2}))$, which completes the proof of
(4.16) for this case.

The proof of (4.17) is identical, now relying on the binomial parts of Lemmas
4.1–4.4. We omit the details. ∎

##  5 Proof of Theorem 1.3

Throughout this section we assume that $\partial A\in C^{2}$ or that $A$ is a
convex polygon. We adopt our WA but do not assume $f$ is necessarily constant
on $A$.

###  5.1 Proof of Parts (i) and (ii)

Given $\beta\in\mathbb{R}$, choose $n_{0}(\beta)$ such that
$n_{0}(\beta)>e^{-\beta}$ and $e^{-n}\sum_{j=0}^{k-1}(n^{j+1})/j!<e^{-\beta}$
for all $n\in[n_{0}(\beta),\infty)$. For example we could take
$n_{0}(\beta):=\max(2e^{-\beta},2\beta,9)$. Recall the definition of
$p_{n,r}(x)$ at (3.4). Given $n>n_{0}(\beta)$, define
$r_{n}(\beta)\in(0,\infty)$ by

$\displaystyle r=r_{n}(\beta)\Longleftrightarrow
n\int_{A}p_{n,r}(x)\nu(dx)=e^{-\beta}.$ (5.1)

By the Intermediate Value theorem, such an $r_{n}(\beta)$ exists and is unique
(note that the integrand is nonincreasing in $r$ because the
Poisson$(\lambda)$ distribution is stochastically monotone in $\lambda$).
Moreover, for $-\infty<\beta<\gamma<\infty$ and
$n\geq\min(n_{0}(\beta),n_{0}(\gamma))$, we have $r_{n}(\beta)<r_{n}(\gamma)$.

We first determine the first-order limiting behaviour of $r_{n}(\beta)$.

######  Lemma 5.1.

Let $\beta\in\mathbb{R}$ and let $r_{n}(\beta)$ satisfy (5.1) for all
$n>n_{0}(\beta)$. Then

$\displaystyle\lim_{n\to\infty}(n\theta_{d}r_{n}(\beta)^{d}/\log
n)=\max(1/f_{0},(2-2/d)/f_{1}).$ (5.2)

If also $\gamma\in\mathbb{R}$ with $\beta<\gamma$, then

$\displaystyle\lim_{n\to\infty}\sup_{x\in
A}\big{(}\nu(B(x,r_{n}(\gamma)))/\nu(B(x,r_{n}(\beta)))\big{)}=1.$ (5.3)

###### Proof.

By Proposition 3.1, as $t\to\infty$ (through $\mathbb{R}$),

$\displaystyle\mathbb{P}[L_{t,k}\leq r_{t}(\beta)]\to\exp(-e^{-\beta}).$ (5.4)

On the other hand, we claim that $t\theta_{d}L_{t,k}^{d}/\log
t\overset{\mathbb{P}}{\longrightarrow}\max(1/f_{0},(2-2/d)/f_{1})$ as
$t\to\infty$. Indeed, writing $N_{t}$ for the number of points of the Poisson
process $\mathcal{P}_{t}$, we have

$\displaystyle t\theta_{d}L_{t,k}^{d}/\log t=(N_{t}\theta_{d}L_{t,k}^{d}/\log
N_{t})\times(t/N_{t})\times(\log N_{t}/\log t)$ (5.5)

Since the conditional distribution of $L_{t,k}$, given $N_{t}=n$, is that of
$L_{k}(\mathcal{X}_{n})$, we have from (1.7) when $A$ has a $C^{2}$ boundary,
and from (1.8) when $A$ is a convex polygon, that the first factor in the
right hand side of (5.5) tends to $\max(1/f_{0},(2-2/d)/f_{1})$ in
probability, and by Chebyshev’s inequality the second factor also tends to $1$
in probability, from which we can deduce the third factor aso tends to 1 in
probability. Combining these gives us the claim.

Let $\alpha<\max(1/f_{0},(2-2/d)/f_{1})$. By the preceding claim we have
$\mathbb{P}[t\theta_{d}L_{t,k}^{d}/\log t<\alpha]\to 0$, and hence
$t\theta_{d}r_{t}^{d}/\log t\geq\alpha$ for $t$ large. Similarly, if
$\alpha^{\prime}>\max(1/f_{0},(2-2/d)/f_{1})$ then $\mathbb{P}[t\theta
L_{t,k}^{d}/\log t\leq\alpha]\to 1$, so by (5.4), $t\theta_{d}r_{t}^{d}/\log
t\leq\alpha^{\prime}$ for $t$ large. Combining these assertions gives us
(5.2).

For (5.3), note that $\nu(B_{s}(x)\setminus B_{r}(x))\leq f_{\rm
max}\theta_{d}(s^{d}-r^{d})$ for $x\in A$ and $0<r<s$. Therefore using (3.8),
for all $x\in A$ and all large enough $n$ we have

$\displaystyle\frac{\nu(B_{r_{n}(\gamma)}(x)\setminus
B_{r_{n}(\beta)}(x))}{\nu(B_{r_{n}(\beta)}(x))}\leq\frac{f_{\rm
max}\theta_{d}(r_{n}(\gamma)^{d}-r_{n}(\beta)^{d})}{\delta_{0}r_{n}(\beta)^{d},}$

which tends to zero by (5.2), and (5.3) follows. ∎

Recall that $\mu(X)$ denotes the median of a random variable $X$. For non-
uniform $\nu$, it seems to be hard in general to find a formula for
$r_{n}(\beta)$ satisfying (5.1) (even if the equality is replaced by
convergence). However, if we can determine a limit for
$nr_{n}(\gamma)^{d}-nr_{n}(\beta)^{d}$ for all $\beta<\gamma$, then we can
still obtain a weak limiting distribution for $nM_{n,k}^{d}-n\mu(M_{n,k})^{d}$
without giving an explicit sequence for $\mu(M_{n,k})$. The next lemma spells
out this argument.

######  Lemma 5.2.

Suppose there exists $\alpha\in(0,\infty)$ such that for all
$\beta,\gamma\in\mathbb{R}$ with $\beta<\gamma$, we have as $n\to\infty$ that

$\displaystyle\lim_{n\to\infty}n(r_{n}(\gamma)^{d}-r_{n}(\beta)^{d})=\alpha(\gamma-\beta),$
(5.6)

where $r_{n}(\beta)$ is defined by (5.1). Suppose that $(X_{n})_{n>0}$ are
random variables satisfying

$\displaystyle\lim_{n\to\infty}\mathbb{P}[X_{n}\leq
r_{n}(\beta)]=\exp(-e^{-\beta}),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall\leavevmode\nobreak\ \beta\in\mathbb{R}.$ (5.7)

Then

$\displaystyle
nX_{n}^{d}-n\mu(X_{n})^{d}\overset{d}{\longrightarrow}\alpha({\mathsf{Gu}}+\log\log
2)\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ {\rm as}\leavevmode\nobreak\
n\to\infty.$ (5.8)

###### Proof.

Set $\beta_{0}=-\log\log 2$. Let $r_{n}=r_{n}(\beta_{0})$ and let
$0<y<x<y^{\prime}<\infty$. Set $s_{n}:=r_{n}(\beta_{0}+y/\alpha)$ and
$s^{\prime}_{n}:=r_{n}(\beta_{0}+y^{\prime}/\alpha)$. Then by (5.6),
$n(s_{n}^{d}-r_{n}^{d})\to y$ and $n((s^{\prime}_{n})^{d}-r_{n}^{d})\to
y^{\prime}$. Hence for $n$ large we have $ns_{n}^{d}<x+nr_{n}^{d}$ and
$n(s^{\prime}_{n})^{d}>x+nr_{n}^{d}$, so that by (5.7), setting
$F(x):=\exp(-e^{-x})$ we have

$\mathbb{P}[nX_{n}^{d}-nr_{n}^{d}\leq x]\geq\mathbb{P}[nX_{n}^{d}\leq
ns_{n}^{d}]\to F(\beta_{0}+y/\alpha),$

and similarly $\mathbb{P}[nX_{n}^{d}-nr_{n}^{d}\leq
x]\leq\mathbb{P}[nX_{n}^{d}\leq n(s^{\prime}_{n})^{d}]\to
F(\beta_{0}+y^{\prime}/\alpha).$ Since we can take $y$ and $y^{\prime}$
arbitrarily close to $x$ and $F(\cdot)$ is continuous, we can deduce that

$\mathbb{P}[nX_{n}^{d}-nr_{n}^{d}\leq x]\to
F(\beta_{0}+x/\alpha),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ x>0.$

Now let $u_{n}:=r_{n}(\beta_{0}-y/\alpha)$ and
$u^{\prime}_{n}:=r_{n}(\beta_{0}-y^{\prime}/\alpha)$. Then by (5.6),
$n(r_{n}^{d}-u_{n}^{d})\to y$ and $n(r_{n}^{d}-(u^{\prime}_{n})^{d})\to
y^{\prime}$. Hence for $n$ large $nu_{n}^{d}>nr_{n}^{d}-x$ and
$n(u^{\prime}_{n})^{d}<nr_{n}^{d}-x$, so that by (5.7),

$\mathbb{P}[nX_{n}^{d}-nr_{n}^{d}\leq-x]\leq\mathbb{P}[nX_{n}^{d}\leq
nu_{n}^{d}]\to F(\beta_{0}-y/\alpha),$

while $\mathbb{P}[nX_{n}^{d}-nr_{n}^{d}\leq-x]\geq\mathbb{P}[nM_{n}^{d}\leq
n(u^{\prime}_{n})^{d}]\to F(\beta_{0}-y^{\prime}/\alpha).$ Taking $y\uparrow
x$ and $y^{\prime}\downarrow x$ yields

$\mathbb{P}[nX_{n}^{d}-nr_{n}^{d}\leq-x]\to
F(\beta_{0}-x/\alpha),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ x>0.$

Since $F(\beta_{0}+z/\alpha)=\mathbb{P}[\alpha({\mathsf{Gu}}+\log\log 2)\leq
z]$, we thus have

$\displaystyle
nX_{n}^{d}-nr_{n}^{d}\overset{d}{\longrightarrow}\alpha({\mathsf{Gu}}+\log\log
2).$ (5.9)

Finally we need to check that $n\mu(X_{n})^{d}-nr_{n}^{d}\to 0$. Let
$\varepsilon>0$. By (5.9), as $n\to\infty$ we have

$\displaystyle\mathbb{P}[nX_{n}^{d}-nr_{n}^{d}\leq\varepsilon]$
$\displaystyle\to\mathbb{P}[\alpha({\mathsf{Gu}}+\log\log
2)\leq\varepsilon]>1/2;$
$\displaystyle\mathbb{P}[nX_{n}^{d}-nr_{n}^{d}\leq-\varepsilon]$
$\displaystyle\to\mathbb{P}[\alpha({\mathsf{Gu}}+\log\log
2)\leq-\varepsilon]<1/2,$

so for large $n$ we have

$\mu(X_{n}^{d})-nr_{n}^{d}=\mu(nX_{n}^{d}-nr_{n}^{d})\in[-\varepsilon,\varepsilon],$

so $\mu(X_{n}^{d})-nr_{n}^{d}\to 0$ as $n\to\infty$, and then (5.8) follows
from (5.9) and the continuity of the Gumbel cdf. ∎

To use Lemma 5.2, we need to show that (5.6) holds for some $\alpha$. We do
this first for the case where $f_{1}>f_{0}(2-2/d)$.

######  Lemma 5.3.

Let $\beta,\gamma\in\mathbb{R}$ with $\beta<\gamma$. Define $r_{n}(\beta)$ by
(5.1). If $f_{1}>f_{0}(2-2/d)$, then

$\displaystyle
n(r_{n}(\gamma)^{d}-r_{n}(\beta)^{d})\to(\gamma-\beta)/(\theta_{d}f_{0})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ {\rm as}\leavevmode\nobreak\ n\to\infty.$ (5.10)

###### Proof.

Given $n$, set $r=r_{n}(\beta),s=r_{n}(\gamma)$. For all $x\in A^{(-s)}$,
$\nu(B_{s}(x)\setminus B_{r}(x))\geq\theta_{d}f_{0}(s^{d}-r^{d}),$ and hence
using (5.1), we have

$\displaystyle e^{-\beta}$
$\displaystyle\geq\int_{A^{(-s)}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}e^{n\nu(B_{s}(x)\setminus
B_{r}(x))}n\nu(dx)$ $\displaystyle\geq
e^{n\theta_{d}f_{0}(s^{d}-r^{d})}\int_{A^{(-s)}}\sum_{j=1}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx).$
(5.11)

Suppose $\partial A\in C^{2}$. Using our assumption $f_{1}>f_{0}(2-2/d)$,
choose $\delta>0$ such that $(2-2/d)(f_{1}-2\delta)^{-1}<f_{0}^{-1}$. Using
Lemma 2.2-(i) and the continuity of $f|_{A}$ we find for all large enough $n$
and all $x\in(\partial A)^{(s)}$ that
$\nu(B_{r}(x))\geq\theta_{d}(f_{1}-\delta)r^{d}/2$. Then using Lemma 5.1 and
our assumption $f_{1}>f_{0}(2-2/d)$, we have that

$\displaystyle\lim_{n\to\infty}\big{(}n\theta_{d}r^{d}/\log
n\big{)}=f_{0}^{-1}>(2-2/d)(f_{1}-2\delta)^{-1}.$ (5.12)

Hence there are constants $c,c^{\prime}$ such that for $n$ large

$\displaystyle\int_{(\partial
A)^{(s)}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))}n\nu(dx)\leq
c(\log n)^{k-1}nse^{-n\theta_{d}(f_{1}-\delta)r^{d}/2}$ $\displaystyle\leq
c^{\prime}(\log
n)^{k-1+1/d}n^{1-1/d}\exp(-(f_{1}-\delta)(1-1/d)(f_{1}-2\delta)^{-1}\log n),$

which tends to zero.

Suppose instead that $d=2$ and $A$ is polygonal. The preceding estimate shows
$\int_{(\partial
A)^{(s)}\setminus\mathsf{Cor}^{(s)}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)\exp(-n\nu(B_{r}(x)))n\nu(dx)$
tends to zero. Moreover, by (3.8) there exist $c,\delta_{0}\in(0,\infty)$ such
that

$\int_{\mathsf{Cor}^{(s)}}\sum_{j=0}^{k-1}\left((n\nu(B_{r}(x)))^{j}/j!\right)e^{-n\nu(B_{r}(x))}n\nu(dx)\leq
c(nr^{2})^{k}e^{-\delta_{0}nr^{2}}$

which tends to zero since $nr^{2}\to\infty$ by (5.2). Thus in both cases we
have that

$\displaystyle\int_{(\partial
A)^{(s)}}\sum_{j=0}^{k-1}((n\nu(B_{s}(x)))^{j}/j!)\exp(-n\nu(B_{r}(x)))n\nu(dx)\to
0.$ (5.13)

Therefore using (5.1) and (5.3) we obtain that

$\displaystyle e^{-\gamma}$
$\displaystyle=\lim_{n\to\infty}\int_{A^{(-s)}}\sum_{j=0}^{k-1}((n\nu(B_{s}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx),$
$\displaystyle=\lim_{n\to\infty}\int_{A^{(-s)}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx),$

and then taking $n\to\infty$ in (5.11) we obtain that $e^{-\beta}\geq
e^{-\gamma}\limsup_{n\to\infty}\left(e^{n\theta_{d}f_{0}(s^{d}-r^{d})}\right),$
so that

$\displaystyle\limsup(n(s^{d}-r^{d}))\leq(\gamma-\beta)/(\theta_{d}f_{0}).$
(5.14)

For an inequality the other way, let $\varepsilon>0$ and let
$A_{\varepsilon}:=\\{x\in A:f(x)\leq f_{0}+4\varepsilon\\}$. By the assumed
continuity of $f$ on $A$, for $n$ large enough, and for all $x\in
A_{\varepsilon}$, we have $\nu(B_{s}\setminus
B_{r})\leq\theta_{d}(f_{0}+5\varepsilon)(s^{d}-r^{d}).$ Therefore by (5.1),

$\displaystyle e^{-\beta}$
$\displaystyle\leq\int_{A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{n\theta_{d}(f_{0}+5\varepsilon)(s^{d}-r^{d})}e^{-n\nu(B_{s}(x))}n\nu(dx)$
$\displaystyle+\int_{A^{(-r)}\setminus
A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))}n\nu(dx)$
$\displaystyle+\int_{(\partial A)^{(r)}\setminus
A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))}n\nu(dx).$
(5.15)

The third integral on the right tends to zero as at (5.13). For $n$ large
enough, and all $x\in A^{(-r)}\setminus A_{\varepsilon}$, using (5.12) we have
$n\nu(B_{r}(x))\geq
n(f_{0}+3\varepsilon)\theta_{d}r^{d}\geq(f_{0}+3\varepsilon)(\log
n)/(f_{0}+\varepsilon)$, and hence the second integral in (5.15) tends to
zero. Therefore

$\displaystyle\liminf\left(\int_{A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{n\theta_{d}(f_{0}+5\varepsilon)(s^{d}-r^{d})}e^{-n\nu(B_{s}(x))}n\nu(dx)\right)\geq
e^{-\beta}.$

Also, by (5.3) the second and third integrals in (5.15) still tend to zero if
we change $B_{r}(x)$ to $B_{s}(x)$, so

$\displaystyle
e^{-\gamma}=\lim\int_{A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{s}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx).$

Hence, using (5.3) again we obtain that

$\displaystyle
e^{-\gamma}=\lim\int_{A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx).$

Hence $\liminf(e^{n\theta_{d}(f_{0}+5\varepsilon)(s^{d}-r^{d})})\times
e^{-\gamma}\geq e^{-\beta}$, so that

$\liminf(n(s^{d}-r^{d}))\geq(\gamma-\beta)/(\theta_{d}(f_{0}+5\varepsilon)).$

Since $\varepsilon>0$ is arbitrary, combining this with (5.14) yields (5.10).
∎

Next we show that (5.6) holds for a different $\alpha$ in the case where
$f_{1}<f_{0}(2-2/d)$.

######  Lemma 5.4.

Let $\beta,\gamma\in\mathbb{R}$ with $\beta<\gamma$. If $f_{1}<f_{0}(2-2/d)$,
then

$\displaystyle\lim_{n\to\infty}(n(r_{n}(\gamma)^{d}-r_{n}(\beta)^{d}))=2(\gamma-\beta)/(\theta_{d}f_{1}).$
(5.16)

Also, if $f_{1}=f_{0}(2-2/d)$, then

$\displaystyle\limsup_{n\to\infty}(n(r_{n}(\gamma)^{d}-r_{n}(\beta)^{d}))\leq
2(\gamma-\beta)/(\theta_{d}f_{1}).$ (5.17)

###### Proof.

Assume $f_{1}\leq f_{0}(2-2/d)$. For each $n$ set $r:=r_{n}(\beta)$,
$s:=r_{n}(\gamma)$. Suppose $\partial A\in C^{2}$. By Lemma 2.2-(iii), given
$\varepsilon>0$, for $n$ large enough and all $x\in(\partial A)^{(-s)}$, we
have $\nu(B_{s}(x)\setminus
B_{r}(x))\geq(f_{1}-\varepsilon)\theta_{d}(s^{d}-r^{d})/2$. Also
$\nu(B_{s}(x)\setminus B_{r}(x))\geq nf_{0}\theta_{d}(s^{d}-r^{d})$ for $x\in
A^{(-s)}$. Hence for $n$ large enough

$\displaystyle e^{-\beta}$ $\displaystyle\geq
e^{n(f_{1}-\varepsilon)\theta_{d}(s^{d}-r^{d})/2}\int_{(\partial
A)^{(s)}}\sum_{j=0}^{k-1}((\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+e^{nf_{0}\theta_{d}(s^{d}-r^{d})}\int_{A^{(-s)}}\sum_{j=0}^{k-1}((\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)$
$\displaystyle\geq
e^{n(f_{1}-\varepsilon)\theta_{d}(s^{d}-r^{d})/2}\Big{(}\int_{(\partial
A)^{(s)}}\sum_{j=0}^{k-1}((\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\int_{A^{(-s)}}\sum_{j=0}^{k-1}((\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)\Big{)},$
(5.18)

since the assumption $f_{1}\leq f_{0}(2-2/d)$ implies $f_{0}\geq f_{1}/2$.
Hence, for $n$ large enough, setting $\psi_{n}:=\inf_{x\in
A}\nu(B_{r}(x))/\nu(B_{s}(x))$ we have

$e^{-\beta}\geq
e^{n(f_{1}-\varepsilon)\theta_{d}(s^{d}-r^{d})/2}e^{-\gamma}\psi_{n}^{k-1}.$

By (5.3) we have $\psi_{n}\to 1$ as $n\to\infty$, and thus

$\displaystyle\limsup(n(s^{d}-r^{d}))\leq
2(\gamma-\beta)/(\theta_{d}(f_{1}-\varepsilon)).$ (5.19)

In the other case with $d=2$ and $A$ polygonal, on choosing a suitable large
$K$ (dependent on the smallest angle of $A$) we can obtain, similarly to
(5.18), that

$\displaystyle e^{-\beta}$ $\displaystyle\geq
e^{n(f_{1}-\varepsilon)\pi(s^{2}-r^{2})/2}\psi_{n}^{k-1}\int_{A\setminus\mathsf{Cor}^{(Kr)}}\sum_{j=0}^{k-1}((n\nu(B_{s}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)$
$\displaystyle=e^{n(f_{1}-\varepsilon)\pi(s^{2}-r^{2})/2}\psi_{n}^{k-1}\left(e^{-\gamma}-\int_{\mathsf{Cor}^{(Kr)}}\sum_{j=0}^{k-1}((n\nu(B_{s}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)\right).$
(5.20)

Since the integral over $\mathsf{Cor}^{(Kr)}$ tends to zero by (3.8), we
therefore obtain from (5.20) that (5.19) holds in this case too. Taking
$\varepsilon\downarrow 0$, we deduce in both cases that (5.17) holds whenever
$f_{1}\leq f_{0}(2-2/d)$.

Now assume the strict inequality $f_{1}<f_{0}(2-2/d)$. Again set
$r=r_{n}(\beta)$, $s=r_{n}(\gamma)$. Using (5.2) from Lemma 5.1, choose
$\delta_{2}>0$ such that

$\displaystyle\lim_{n\to\infty}\frac{n\theta_{d}r^{d}}{\log
n}=\frac{2-2/d}{f_{1}}>\frac{1+2\delta_{2}}{f_{0}}.$ (5.21)

Then there exists a constant $c$ such that for $n$ large,

$\displaystyle\int_{A^{(-r)}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))}n\nu(dx)\leq
cn(\log n)^{k-1}e^{-n\theta_{d}f_{0}r^{d}}$ $\displaystyle=nc(\log
n)^{k-1}e^{-(1+\delta_{2})\log n},$ (5.22)

which tends to zero.

Take a new $\varepsilon>0$. Let $A_{\varepsilon}:=\\{x\in A:f(x)\leq
f_{1}+3\varepsilon\\}$. Using Lemma 2.1 (ii), take $\delta>0$ such that for
all large enough $n$ and all $x\in(\partial A)^{(\delta r)}$. we have

$|A\cap B_{s}(x)\setminus
B_{r}(x)|\leq\theta_{d}(s^{d}-r^{d})(f_{1}+5\varepsilon)/(2(f_{1}+4\varepsilon)).$

Then for $n$ large and $x\in(\partial A)^{(\delta r)}\cap A_{\varepsilon}$ we
have $\sup_{B_{s}(x)\cap A}f\leq f_{1}+4\varepsilon$, and hence for $\partial
A\in C^{2}$ or for $A$ a convex polygon

$\displaystyle\nu(B_{s}(x)\setminus
B_{r}(x))\leq\theta_{d}(s^{d}-r^{d})(f_{1}+5\varepsilon)/2,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\
x\in(\partial A)^{(\delta r)}\cap A_{\varepsilon}.$ (5.23)

Using Lemma 2.2 (i), in the case where $\partial A\in C^{2}$ we have for large
$n$, and all $x\in A\setminus A_{\varepsilon}$, that
$\nu(B_{r}(x))\geq(f_{1}+2\varepsilon)\theta_{d}r^{d}/2$. Hence for $n$ large

$\displaystyle\int_{(\partial A)^{(r)}\setminus
A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))}n\nu(dx)\leq
c(\log n)^{k}nr\exp(-n(f_{1}+2\varepsilon)\theta_{d}r^{d}/2)$
$\displaystyle\leq cn^{1-1/d}(\log
n)^{k+1/d}\exp(-(f_{1}+\varepsilon)(1-1/d)(\log n)/f_{1})\to 0,$

where for the second inequality we have used the equality in (5.21).

By Lemma 2.1 (i), there is a constant $\delta_{1}>0$ such that for
$x\in(\partial A)^{(r)}\setminus(\partial A)^{(\delta r)}$ (in the case where
$\partial A\in C^{2}$) or for $x\in(\partial A)^{(r)}\setminus(\partial
A)^{(\delta r)}\setminus\mathsf{Cor}^{(Kr)}$ (in the case where $A$ is
polygonal) we have $\nu(B_{r}(x))\geq(f_{1}+2\delta_{1})\theta_{d}r^{d}/2$.
Thus if $\partial A\in C^{2}$ then

$\displaystyle\int_{(\partial A)^{(r)}\setminus(\partial A)^{(\delta
r)}}p_{n,r}(x)n\nu(dx)\leq c(\log
n)^{k}nr\exp(-n(f_{1}+2\delta_{1})\theta_{d}r^{d}/2),$

which tends to zero by (5.21). Combining the last two estimates with (5.22)
shows that

$\displaystyle\int_{A\setminus((\partial A)^{(\delta r)}\cap
A_{\varepsilon})}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))}n\nu(dx)\to
0,$ (5.24)

and therefore using (5.1) followed by (5.23) we have

$\displaystyle e^{-\beta}$ $\displaystyle=\lim_{n\to\infty}\int_{(\partial
A)^{(\delta r)}\cap
A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{r}(x))}n\nu(dx)$
$\displaystyle\leq\liminf_{n\to\infty}\left(e^{n\theta_{d}(s^{d}-r^{d})(f_{1}+5\varepsilon)/2}\int_{(\partial
A)^{(\delta r)}\cap
A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)\right).$
(5.25)

By (5.24) we have $\int_{A\setminus((\partial A)^{(\delta r)}\cap
A_{\varepsilon})}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)\to
0$, so using (5.2) from Lemma 5.1 we have

$\int_{(\partial A)^{(\delta r)}\cap
A_{\varepsilon}}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)e^{-n\nu(B_{s}(x))}n\nu(dx)\to
e^{-\gamma},$

and hence by (5.25),

$e^{-\beta}\leq\liminf_{n\to\infty}\left(e^{n\theta_{d}(s^{d}-r^{d})(f_{1}+5\varepsilon)/2}\right)\times
e^{-\gamma},$

so that

$\liminf_{n\to\infty}(n(s^{d}-r^{d}))\geq
2(\gamma-\beta)/(\theta_{d}(f_{1}+5\varepsilon)).$

Taking $\varepsilon\downarrow 0$ and combining with (5.17) shows that (5.16)
holds. ∎

######  Lemma 5.5 (De-Poissonization).

Let $\beta\in\mathbb{R}$ and suppose $r_{n}=r_{n}(\beta)$ is given by (5.1)
for $n$ sufficiently large. Then

$\displaystyle\lim_{n\to\infty}\mathbb{P}[L_{k}(\mathcal{X}_{n})\leq
r_{n}(\beta)]=\lim_{n\to\infty}\mathbb{P}[L_{n,k}\leq
r_{n}(\beta)]=\exp(-e^{-\beta}).$ (5.26)

###### Proof.

The statement about $L_{n,k}$ in (5.26) follows from Proposition 3.1. It
remains to prove the statement about $L_{k}(\mathcal{X}_{n})$.

Given $n>0,r>0$ define $I_{n,r}$ (nothing to do with $I_{i}(n,r)$ in Lemma 3.4
earlier) by

$\displaystyle
I_{n,r}:=\int_{A}p_{n,r}(x)n\nu(dx)=\int_{A}\sum_{j=0}^{k-1}((n\nu(B_{r}(x)))^{j}/j!)\exp(-n\nu(B_{r}(x)))n\nu(dx),$
(5.27)

which is decreasing in $r$. Set $n^{-}:=n-n^{3/4}$, $n^{+}:=n+n^{3/4}$, and
let $\beta\in\mathbb{R}$. Then

$\frac{I_{n^{-},r_{n}(\beta)}}{I_{n,r_{n}(\beta)}}\geq\big{(}\frac{n^{-}}{n}\big{)}^{k-1}=1+O(n^{-1/4}),$

and

$\frac{I_{n^{-},r_{n}(\beta)}}{I_{n,r_{n}(\beta)}}\leq\exp(n^{3/4}f_{\rm
max}\theta_{d}r_{n}(\beta)^{d})=1+O((\log n)n^{-1/4}),$

so that $I_{n^{-},r_{n}(\beta)}/I_{n,r_{n}(\beta)}\to 1$ as $n\to\infty$, and
thus $I_{n^{-},r_{n}(\beta)}\to e^{-\beta}$ as $n\to\infty$. Therefore using
Proposition 3.1, we have

$\displaystyle\mathbb{P}[L_{n^{-},k}\leq r_{n}(\beta)]\to\exp(-e^{-\beta}).$
(5.28)

Now, following the proof of [8, Theorem 8.1], we note that with
$\mathcal{P}_{n^{-}}$, $\mathcal{P}_{n^{+}}$ and $\mathcal{X}_{n}$ coupled in
the usual way (as described in [8]), we have

$\\{L_{n^{-},k}\leq r_{n}(\beta)\\}\triangle\\{L_{k}(\mathcal{X}_{n})\leq
r_{n}(\beta)\\}\subset E_{n}\cup F_{n}\cup G_{n}$

where, setting $N_{t}=\mathcal{P}_{t}(A)$ for all $t$, we set

$\displaystyle E_{n}$ $\displaystyle:=\\{\exists
x\in\mathcal{P}_{n^{+}}\setminus\mathcal{P}_{n^{-}}:\mathcal{P}_{n^{-}}(B_{r_{n}(\beta)}(x))\leq
k-1\\};$ $\displaystyle F_{n}$ $\displaystyle:=\\{\exists
x\in\mathcal{P}_{n^{-}},y\in\mathcal{P}_{n^{+}}\setminus\mathcal{P}_{n^{-}}:\mathcal{P}_{n^{-}}(B_{r_{n}(\beta)}(x))\leq
k,\|y-x\|\leq r_{n}(\beta)\\};$ $\displaystyle G_{n}$
$\displaystyle:=\\{N_{n^{-}}\leq n\leq N_{n^{+}}\\}^{c}.$

By Chebyshev’s inequality $\mathbb{P}[G_{n}]=O(n^{-1/2})$. By Markov’s
inequality,

$\displaystyle\mathbb{P}[E_{n}]$ $\displaystyle\leq
2n^{3/4}\int_{A}\mathbb{P}[{\cal P}_{n^{-}}(B_{r_{n}(\beta)}(x))\leq
k-1]\nu(dx)$ $\displaystyle=(2n^{3/4}/n^{-})I_{n^{-},r_{n}(\beta)},$

which tends to zero. Finally, by the Mecke formula,

$\displaystyle\mathbb{P}[F_{n}]$ $\displaystyle\leq 2n^{3/4}f_{\rm
max}\theta_{d}r_{n}(\beta)^{d}\int_{A}\mathbb{P}[{\cal
P}_{n^{-}}(B_{r_{n}(\beta)}(x))\leq k-1]n^{-}\nu(dx)$ $\displaystyle=2f_{\rm
max}\theta_{d}n^{3/4}r_{n}(\beta)^{d}I_{n^{-},r_{n}(\beta)}=O((\log
n)n^{-1/4}).$

Therefore using (5.28) we obtain (5.26). ∎

###### Proof of Theorem 1.3 Parts (i) and (ii).

For Part (i) we assume $f_{1}>f_{0}(2-2/d)$; in this case set
$\alpha=1/(\theta_{d}f_{0})$. For Part (ii) we assume $f_{1}<f_{0}(2-2/d)$; in
this case set $\alpha=2/(\theta_{d}f_{1})$.

By Lemma 5.3 in the first case, or by Lemma 5.4 in the second case, for all
$\beta,\gamma\in\mathbb{R}$ with $\beta<\gamma$ the condition (5.6) holds.

Let $\beta\in\mathbb{R}$ and suppose $r_{n}=r_{n}(\beta)$ is given by (5.1)
for $n$ sufficiently large. By Lemma 5.5, $\mathbb{P}[L_{n,k}\leq
r_{n}(\beta)]\to F(\beta)$ and $\mathbb{P}[L_{k}(\mathcal{X}_{n})\leq
r_{n}(\beta)]\to F(\beta)$, where we set $F(x):=\exp(-e^{-x})$. By Proposition
4.5, $\mathbb{P}[M_{n,k}\leq r_{n}(\beta)]\to F(\beta)$ as $n\to\infty$.

Then by Lemma 5.2 (taking $X_{n}=M_{n,k}$), we obtain that
$nM_{n,k}^{d}-n\mu(M_{n,k})^{d}\overset{d}{\longrightarrow}\alpha({\mathsf{Gu}}+\log\log
2),$ i.e. (1.18) holds if $f_{1}>f_{0}(2-2/d)$, and (1.22) holds if
$f_{1}<f_{0}(2-2/d)$. Also by taking $X_{n}=L_{n,k}$ in Lemma 5.2 we obtain
(1.19) if $f_{1}>f_{0}(2-2/d)$, and (1.23) if $f_{1}<f_{0}(2-2/d)$.

It remains to demonstrate the results for the binomial model, i.e. (1.16),
(1.17), (1.20) and (1.21). By Lemma 5.5, we can use Lemma 5.2 (now taking
$X_{n}=L_{k}(\mathcal{X}_{n})$) to deduce that (1.17) holds if
$f_{1}>f_{0}(2-2/d)$, and (1.21) holds if $f_{1}<f_{0}(2-2/d)$.

Using (5.26), and (4.17) from Proposition 4.5, we obtain that

$\mathbb{P}[M_{k}(\mathcal{X}_{n})\leq r_{n}(\beta)]\to\exp(-e^{-\beta}).$

Then using Lemma 5.2 (now taking $X_{n}=M_{k}(\mathcal{X}_{n})$) we can deduce
that (1.16) holds if $f_{1}>f_{0}(2-2/d)$, and (1.20) holds if
$f_{1}<f_{0}(2-2/d)$. ∎

###  5.2 Proof of Theorem 1.3: Conclusion

It remains to prove Part (iii) of Theorem 1.3. We deal first with the
assertions there concerning tightness.

######  Lemma 5.6.

The collection of random variables
$\\{nM_{n,k}^{d}-n\mu(M_{n,k})^{d}\\}_{n>0}$ is tight. So is the collection of
random variables $\\{nL_{n,k}^{d}-n\mu(L_{n,k})^{d}\\}_{n>0}$, and also the
sequence
$(nM_{k}(\mathcal{X}_{n})^{d}-n\mu(M_{k}(\mathcal{X}_{n}))^{d})_{n\in\mathbb{N}}$,
and the sequence
$(nL_{k}(\mathcal{X}_{n})^{d}-n\mu(L_{k}(\mathcal{X}_{n}))^{d})_{n\in\mathbb{N}}$.

###### Proof.

Let $\varepsilon\in(0,1/6)$. Choose $\beta<\beta^{\prime}$ with
$F(\beta)<\varepsilon/3$ and $F(\beta^{\prime})>1-\varepsilon/3$. Set
$r_{n}=r_{n}(\beta)$, $s_{n}=r_{n}(\beta^{\prime})$ as given by (5.1). By
Lemma 5.4 there exists a constant $K$ such that $n(s_{n}^{d}-r_{n}^{d})\leq K$
for all large enough $n$. By Proposition 3.1, $\mathbb{P}[L_{n,k}\leq
r_{n}(\beta)]\to F(\beta)$. By Proposition 4.5, $\mathbb{P}[M_{n,k}\leq
r_{n}]\to F(\beta)$ as $n\to\infty$. Similarly, $\mathbb{P}[L_{n,k}\leq
s_{n}]\to F(\beta^{\prime})$ and $\mathbb{P}[M_{n,k}\leq s_{n}]\to
F(\beta^{\prime})$ as $n\to\infty$. Therefore since
$F(\beta)<1/2<F(\beta^{\prime})$, we have $r_{n}\leq\mu(L_{n,k})<s_{n}$ and
$r_{n}\leq\mu(M_{n,k})<s_{n}$ for $n$ large. Then for $n$ large

$\displaystyle\mathbb{P}[nM_{n,k}^{d}\leq n\mu(M_{n,k})^{d}-(K+1)]$
$\displaystyle\leq\mathbb{P}[nM_{n,k}^{d}\leq ns_{n}^{d}-(K+1)]$
$\displaystyle\leq\mathbb{P}[M_{n,k}\leq r_{n}]<\varepsilon/2,$

and likewise for $L_{n,k}$. Similarly for $n$ large

$\displaystyle\mathbb{P}[nM_{n,k}^{d}>n\mu(M_{n,k})^{d}+(K+1)]$
$\displaystyle\leq\mathbb{P}[nM_{n,k}^{d}>nr_{n}^{d}+(K+1)]$
$\displaystyle\leq\mathbb{P}[M_{n,k}>s_{n}]<\varepsilon/2,$

and likewise for $L_{n,k}$. Thus
$\mathbb{P}[|n(M_{n,k}^{d}-\mu(M_{n,k})^{d})|>K+1]\leq\varepsilon$ and
$\mathbb{P}[|n(L_{n,k}^{d}-\mu(L_{n,k})^{d})|>K+1]\leq\varepsilon$ for all
large enough $n$, Also $\\{n(M_{n,k}^{d}-\mu(M_{n,k}^{d}))\\}_{0<n\leq n_{0}}$
and $\\{n(L_{n,k}^{d}-\mu(L_{n,k}^{d}))\\}_{0<n\leq n_{0}}$ are uniformly
bounded for any fixed $n_{0}\in(0,\infty)$. This yields the asserted tightness
of $(M_{n,k})_{n>0}$ and of $(L_{n,k})_{n>0}$.

The proof of tightness for $L_{k}(\mathcal{X}_{n})$ and of
$M_{k}(\mathcal{X}_{n})$ is similar, except that instead of Proposition 3.1 we
use (5.26). Proposition 4.5 still applies in the binomial setting. ∎

To prove (1.5) we shall adapt the ‘squeezing argument’ from [9]. For
$-\infty<\beta<\gamma<\infty$ we define the random variable

$\displaystyle
U_{n}(\beta,\gamma):=\sum_{x\in\mathcal{X}_{n}}\mathbbm{1}\\{\mathcal{X}_{n}(B_{r_{n}(\beta)}(x))\leq
k,\mathcal{X}_{n}(B_{r_{n}(\gamma)}(x)\setminus B_{r_{n}(\beta)}(x))\geq
2\\}.$ (5.29)

######  Lemma 5.7.

Let $K>0$. Then there is a constant $c\in(0,\infty)$ such that for all
$\beta,\gamma\in\mathbb{R}$ with $-K<\beta<\gamma<K$,

$\limsup_{n\to\infty}\mathbb{P}[U_{n}(\beta,\gamma)\geq 1]\leq
c(\gamma-\beta)^{2}.$

###### Proof.

Set $r_{n}:=r_{n}(\beta)$, and $s_{n}:=r_{n}(\gamma)$. By the union bound,

$\displaystyle\mathbb{P}[U_{n}(\beta,\gamma)\geq 1]\leq
n\int_{A}\mathbb{P}[\mathcal{X}_{n-1}(B_{r_{n}}(x))<k,\mathcal{X}_{n-1}(B_{s_{n}}(x)\setminus
B_{r_{n}}(x))\geq 2]\nu(dx).$ (5.30)

Let $x\in A$ and set $Y:=\mathcal{X}_{n-1}(B_{r_{n}}(x))$,
$Z:=\mathcal{X}_{n-1}(B_{s_{n}}(x)\setminus B_{r_{n}}(x))$. Also set
$v_{n}(x):=\nu(B_{r_{n}}(x))$ and $w_{n}(x):=\nu(B_{s_{n}}(x))$. Then

$\displaystyle\mathbb{P}[Y<k]$
$\displaystyle=\sum_{j=0}^{k-1}\binom{n-1}{j}v_{n}(x)^{j}(1-v_{n}(x))^{n-1-j}$
$\displaystyle\leq(1-v_{n}(x))^{-k}\sum_{j=0}^{k-1}((nv_{n}(x))^{j}/j!)(1-v_{n}(x))^{n}$
$\displaystyle\leq(1-f_{\rm
max}\theta_{d}r_{n}^{d})^{-k}\sum_{j=0}^{k-1}((nv_{n}(x))^{j}/j!)e^{-nv_{n}(x)}.$

Also using the fact that $\mathbb{P}[Z\geq 2|Y=j]$ is nonincreasing in $j$,
followed by Markov’s inequality, and then the fact that for any binomial
random variable $W$ with mean $\alpha$ we have
$\mathbb{E}[W(W-1)]\leq\alpha^{2}$, we have

$\displaystyle\mathbb{P}[Z\geq 2|Y<k]$ $\displaystyle\leq\mathbb{P}[|Z\geq
2|Y=0]$ $\displaystyle\leq(1/2)\mathbb{E}[Z(Z-1)|Y=0]$
$\displaystyle\leq(1/2)n^{2}((w_{n}(x)-v_{n}(x))/(1-v_{n}(x)))^{2}$
$\displaystyle\leq(1/2)n^{2}(1-f_{\rm
max}\theta_{d}r_{n}(\beta)^{d})^{-2}(w_{n}(x)-v_{n}(x))^{2}.$

If $n$ taken to be large enough we have $(1-f_{\rm
max}\theta_{d}r_{n}(\beta)^{d})^{-k-2}\leq 2$, and hence using (5.30) followed
by (5.1), we have

$\displaystyle\mathbb{P}[U_{n}(\beta,\gamma)\geq 1]$ $\displaystyle\leq
n^{3}\sup_{y\in
A}(w_{n}(y)-v_{n}(y))^{2}\int_{A}\sum_{j=0}^{k-1}((nv_{n}(x))^{j}/j!)e^{-nv_{n}(x)}\nu(dx)$
$\displaystyle=\big{(}n\sup_{y\in A}(w_{n}(y)-v_{n}(y))\big{)}^{2}e^{-\beta}.$
(5.31)

By Lemmas 5.3 and 5.4,

$\displaystyle\limsup_{n\to\infty}n\theta_{d}(s_{n}^{d}-r_{n}^{d})\leq\left(\frac{1}{f_{0}}\vee\frac{2}{f_{1}}\right)(\gamma-\beta),$
(5.32)

where $\vee$ denotes maximum, and hence

$\displaystyle\limsup_{n\to\infty}\sup_{x\in
A}n(w_{n}(x)-v_{n}(x))\leq\limsup_{n\to\infty}nf_{\rm
max}\theta_{d}(s_{n}^{d}-r_{n}^{d})\leq f_{\rm
max}\left(\frac{1}{f_{0}}\vee\frac{2}{f_{1}}\right)(\gamma-\beta),$

so by (5.31) we have $\limsup_{n\to\infty}\mathbb{P}[U_{n}(\beta,\gamma)\geq
1]\leq e^{K}(f_{\rm
max}(\frac{1}{f_{0}}\vee\frac{2}{f_{1}}))^{2}(\gamma-\beta)^{2}$. ∎

###### Proof of Theorem 1.3 (conclusion).

It remains to prove Part (iii), and by Lemma 5.6 it remains only to prove
(1.5). Let $\varepsilon>0$. Choose $K>0$ such that
$\exp(-e^{-K})>1-\varepsilon$, and also $\exp(-e^{K})<\varepsilon$. Then let
$c$ be as in Lemma 5.7. Choose $\beta_{0}<\ldots<\beta_{m}$ with
$\beta_{0}=-K$ and $\beta_{m}=K$ such that
$c\sum_{i=1}^{m}(\beta_{i}-\beta_{i-1})^{2}<\varepsilon$. Write
$L^{\prime}_{n,k}$ for $L_{k}(\mathcal{X}_{n})$ and $M^{\prime}_{n,k}$ for
$M_{k}(\mathcal{X}_{n})$. Since $L^{\prime}_{n,k}\leq M^{\prime}_{n,k}$, by
the union bound

$\displaystyle\mathbb{P}[L^{\prime}_{n,k}\neq M^{\prime}_{n,k}]$
$\displaystyle=\mathbb{P}[L^{\prime}_{n,k}<M^{\prime}_{n,k}]$
$\displaystyle\leq\mathbb{P}[L^{\prime}_{n,k}\leq\beta_{0}]+\mathbb{P}[L^{\prime}_{n,k}>\beta_{m}]+\sum_{i=1}^{m}\mathbb{P}[L^{\prime}_{n,k}\leq
r_{n}(\beta_{i})<M^{\prime}_{n,k}]$
$\displaystyle+\sum_{i=1}^{m}\mathbb{P}[r_{n}(\beta_{i-1})<L^{\prime}_{n,k}<M^{\prime}_{n,k}\leq
r_{n}(\beta_{i})].$

By Lemma 5.5, we have $\mathbb{P}[L^{\prime}_{n,k}\leq
r_{n}(\beta)]\to\exp(-e^{-\beta})$ as $n\to\infty$. Thus using also
Proposition 4.5, we obtain that

$\displaystyle\limsup_{n\to\infty}\mathbb{P}[L^{\prime}_{n,k}\neq
M^{\prime}_{n,k}]\leq
2\varepsilon+\sum_{i=1}^{m}\limsup_{n\to\infty}\mathbb{P}[r_{n}(\beta_{i-1})<L^{\prime}_{n,k}<M^{\prime}_{n,k}\leq
r_{n}(\beta_{i})].$

Suppose $\beta<\gamma$, and suppose
$r_{n}(\beta)<L^{\prime}_{n,k}<M^{\prime}_{n,k}\leq r_{n}(\gamma)$ and all
interpoint distances in $\mathcal{X}_{n}$ are distinct (the latter condition
holds almost surely).

Then there exist $x,y\in\mathcal{X}_{n}$ with $\|x-y\|=M^{\prime}_{n,k}$, and
it is possible to remove $k$ vertices from
$G(\mathcal{X}_{n},M^{\prime}_{n,k})$ leaving the resulting graph connected,
but disconnected if the edge $\\{x,y\\}$ is also removed. Removing the same
set of vertices from $G(\mathcal{X}_{n},r_{n}(\beta))$ leaves $x$ and $y$ in
distinct components, and if also for some fixed $\rho>0$, events
$H_{r_{n}(\beta),\rho}(\mathcal{X}_{n})$ (defined in Lemma 4.4) and
$J_{r_{n}(\beta),\rho}(\mathcal{X}_{n})$ (defined in the proof of Proposition
4.5), fail to occur, then $x$ or $y$ must have at most $k-1$ other points of
$\mathcal{X}_{n}$ within distance $r_{n}(\beta)$. But
$\mathcal{X}_{n}(B_{r_{n}(\gamma)}(x)\setminus\\{x\\})\geq k+1$ since
$L^{\prime}_{n,k}<\|y-x\|\leq r_{n}(\gamma)$, and similarly
$\mathcal{X}_{n}(B_{r_{n}(\beta)}(y)\setminus\\{y\\})\geq k+1$. Thus we have
the event inclusion

$\displaystyle\\{r_{n}(\beta)<L^{\prime}_{n,k}<M^{\prime}_{n,k}\leq
r_{n}(\gamma)\\}\subset H_{r_{n}(\beta),\rho}(\mathcal{X}_{n})\cup
J_{r_{n}(\beta),\rho}(\mathcal{X}_{n})\cup U_{n}(\beta,\gamma),$

where $U_{n}(\beta,\gamma)$ was defined at (5.29).

By Lemma 4.4, we can choose $\rho$ so that
$\mathbb{P}[H_{r_{n}(\beta),\rho}(\mathcal{X}_{n})]\to 0$, and by the proof of
Proposition 4.5 $\mathbb{P}[J_{r_{n}(\beta),\rho}(\mathcal{X}_{n})]\to 0$.
Therefore using Lemma 5.7 we obtain that

$\displaystyle\limsup_{n\to\infty}\mathbb{P}[r_{n}(\beta)<L^{\prime}_{n,k}<M^{\prime}_{n,k}\leq
r_{n}(\gamma)]\leq\limsup_{n\to\infty}\mathbb{P}[U_{n}(\beta,\gamma)\geq
1]\leq c(\gamma-\beta)^{2}.$

Thus

$\displaystyle\limsup_{n\to\infty}\mathbb{P}[L^{\prime}_{n,k}\neq
M^{\prime}_{n,k}]\leq
2\varepsilon+\sum_{i=1}^{m}c(\beta_{i}-\beta_{i-1})^{2}<3\varepsilon,$

and since $\varepsilon>0$ is arbitrary this gives us (1.5). ∎

##  6 Proof of Theorem 1.1

Now we specialise to the uniform case. We make the same assumptions on $A$ as
in the previous section, but now we take $f\equiv f_{0}{\bf 1}_{A}$ with
$f_{0}=|A|^{-1}$. Recall from (1.10) the definition

$\displaystyle
c_{d,k}:=\theta_{d-1}^{-1}\theta_{d}^{1-1/d}(2-2/d)^{k-2+1/d}2^{1-k}/(k-1)!$
(6.1)

Given $k\in\mathbb{N}$ and $\beta\in\mathbb{R}$, let $r_{n}=r_{n}(\beta)\geq
0$ be defined for all $n>0$ by

$f_{0}n\theta_{d}r_{n}^{d}=\max\big{(}(2-2/d)\log
n+(2k-4+2/d)\mathbbm{1}_{\\{d\geq 3\text{ or }k\geq 2\\}}\log\log
n+\beta,0\big{)}.$ (6.2)

We now show the convergence of $\mathbb{E}[F_{n,r_{n}}]$ (with $F_{n,r}$
defined at (3.1)). That is, we show that this choice of $r_{n}$ satisfies
(3.5) for appropriate $\beta^{\prime}$. Recall the definition of the
isoperimetric ratio $\sigma_{A}$ at (1.11).

######  Proposition 6.1 (convergence of the expectation in the uniform case
with $d=2$).

Suppose $f\equiv f_{0}{\bf 1}_{A}$, with $d=2$ and either $A$ compact with
$C^{2}$ boundary, or $A$ polygonal. Fix $k\in\mathbb{N}$,
$\beta\in\mathbb{R}$, and let $r_{n},F_{n,r}$ be as given in (6.2) and (3.1).
Then as $n\to\infty$,

$\displaystyle\mathbb{E}[F_{n,r_{n}}]=\begin{cases}e^{-\beta}+\sigma_{A}e^{-\beta/2}\frac{\sqrt{\pi}}{2}(\log
n)^{-1/2}+O((\log n)^{-3/2})&\mbox{ if }k=1\\\
e^{-\beta}+\sigma_{A}e^{-\beta/2}\frac{\sqrt{\pi}}{4}\Big{(}1+\frac{\log\log
n}{2\log n}\Big{)}+\frac{e^{-\beta}\log\log n}{\log n}+O((\log n)^{-1})&\mbox{
if }k=2\\\
\sigma_{A}e^{-\beta/2}\frac{\sqrt{\pi}}{(k-1)!2^{k}}\left(1+\frac{(2k-3)^{2}\log\log
n}{2\log n}\right)+O\big{(}(\log n)^{-1}\big{)}&\mbox{ if }k\geq 3\end{cases}$
(6.3)

###### Proof.

Define the ‘vacant region’ $V_{n,k}:=\\{x\in A:{\cal
P}_{n}(B_{r_{n}}(x))<k\\}$. Recall the definition of $p_{n,r}(x)$ at (3.4). By
(3.3), we have

$\displaystyle\mathbb{E}[F_{n,r_{n}}]=nf_{0}\int_{A}p_{n,r_{n}}(x)dx=nf_{0}\mathbb{E}[|V_{n,k}|].$
(6.4)

Therefore the result follows from [4, Proposition 5.1]. ∎

######  Proposition 6.2 (convergence of the expectation in the uniform case
with $d\geq 3$).

Suppose $f\equiv f_{0}{\bf 1}_{A}$, with $d\geq 3$ and $A$ compact with
$\partial A\in C^{2}$. Fix $\beta\in\mathbb{R}$ and let
$r_{n}(\beta),F_{n,r},c_{d,k},\sigma_{A}$ be as given in (6.2), (3.1) (6.1)
and (1.11). Let $\varepsilon>0$. Then as $n\to\infty$,

$\displaystyle\mathbb{E}[F_{n,r_{n}}]$
$\displaystyle=e^{-\beta/2}c_{d,k}\sigma_{A}\Big{(}1+\frac{(k-2+1/d)^{2}\log\log
n}{(1-1/d)\log n}$ $\displaystyle+\frac{(k-2+1/d)\beta+4k-4}{(2-2/d)\log
n}\Big{)}+O\big{(}(\log n)^{\varepsilon-2}\big{)}.$ (6.5)

###### Proof.

Again using (6.4), we obtain this result from [4, Proposition 5.2]. ∎

######  Corollary 6.3.

Let $d=2$, $\beta\in\mathbb{R}$. Then (1.13) holds, and also

$\displaystyle\mathbb{P}[nf_{0}\pi L_{n,1}^{2}-\log
n\leq\beta]=\exp\big{(}-\frac{\sigma_{A}\pi^{1/2}e^{-\beta/2}}{2(\log
n)^{1/2}}\big{)}\exp(-e^{-\beta})+O((\log n)^{-1}).$ (6.6)

Moreover (1.14) holds, and

$\displaystyle\mathbb{P}[nf_{0}\pi L_{n,2}^{2}-\log n-\log\log n\leq\beta]=$
$\displaystyle\exp\Big{(}-\frac{\sigma_{A}\pi^{1/2}e^{-\beta/2}\log\log
n}{8\log n}-\frac{e^{-\beta}\log\log n}{\log n}\Big{)}$
$\displaystyle\times\exp\Big{(}-e^{-\beta}-\frac{\pi^{1/2}\sigma_{A}e^{-\beta/2}}{4}\Big{)}+O\Big{(}\frac{1}{\log
n}\Big{)}.$ (6.7)

###### Proof.

Let $r_{n}=r_{n}(\beta)$ be given by (6.2) with $d=2,k=1$; then $nf_{0}\pi
r_{n}^{2}-\log n=\beta$ for all large enough $n$.

Let $F_{n,r}$ be the number of isolated vertices of $G({\cal P}_{n},r)$ as
defined at (3.1), taking $k=1$. By Proposition 6.1, (3.5) holds on taking
$\beta^{\prime}=e^{-\beta}$. Hence by Proposition 3.1,

$\displaystyle\mathbb{P}[nf_{0}\pi L_{n,1}^{2}-\log
n\leq\beta]=\mathbb{P}[L_{n,1}\leq
r_{n}]=\exp(-\mathbb{E}[F_{n,r_{n}}])+O(1/(\log n)).$

Then using Proposition 6.1, and the fact that
$|e^{-\lambda}-e^{-\lambda^{\prime}}|\leq|\lambda-\lambda^{\prime}|$ for any
$\lambda,\lambda^{\prime}>0$, we obtain (6.6). We can then deduce (1.13) using
Proposition 4.5.

Next, let $r_{n}=r_{n}(\beta)$ be given by (6.2) again, but now with
$d=2,k=2$. Then $nf_{0}\pi r_{n}^{2}-\log n-\log\log n=\beta$ for $n$ large.
Repeating the previous argument gives us (6.7) and then (1.14). ∎

######  Corollary 6.4.

Suppose either $d\geq 3$, or $d=2,k\geq 3$. Let $\beta\in\mathbb{R}$. Then
(1.15) holds, and

$\displaystyle\mathbb{P}[nf_{0}\theta_{d}L_{n,k}^{d}-(2-2/d)\log
n+(4-2k-2/d)\log\log n\leq\beta]$
$\displaystyle=\exp\Big{(}-\frac{c_{d,k}\sigma_{A}e^{-\beta/2}(k-2+1/d)^{2}\log\log
n}{(1-1/d)\log
n}\Big{)}\exp(-c_{d,k}\sigma_{A}e^{-\beta/2})+O\big{(}\frac{1}{\log
n}\big{)},$

###### Proof.

The proof is the same as for Corollary 6.3, using Proposition 6.2 in place of
Proposition 6.1. ∎

We are now ready to finish the proof of Theorem 1.1.

###### Proof of Theorem 1.1.

We already showed (1.13), (1.14), (1.15) and the corresponding results for
$L_{n,k}$, in Corollaries 6.3 and 6.4. We already proved (1.5) under weaker
assumptions in Theorem 1.3. Therefore it remains only to prove (1.12) and the
binomial versions of (1.14) and (1.15), along with the corresponding results
for $L_{k}(\mathcal{X}_{n})$.

Let $I_{n,r}$ be as defined at (5.27). Set $n^{-}:=n-n^{3/4}$. As shown in the
proof of Lemma 5.5 given $\beta\in\mathbb{R}$ we have that

$I_{n^{-},r_{n}(\beta)}=\Big{(}1+O\big{(}\frac{\log
n}{n^{1/4}}\big{)}\Big{)}I_{n,r_{n}(\beta)}.$

Then by Proposition 3.1,

$\displaystyle\mathbb{P}[L_{n^{-},k}\leq
r_{n}]=\exp(-I_{n^{-},r_{n}(\beta)})+O((\log n)^{-1})$
$\displaystyle=\exp(-I_{n,r_{n}(\beta)})+O((\log n)^{-1}).$

By the proof of Lemma 5.5,

$\displaystyle\mathbb{P}[L_{k}(\mathcal{X}_{n})\leq r_{n}(\beta)]$
$\displaystyle=\mathbb{P}[L_{n^{-},k}\leq r_{n}(\beta)]+O((\log n)/n^{1/4}).$
$\displaystyle=\exp(-I_{n,r_{n}(\beta)})+O((\log n)^{-1}).$

Plugging in the expressions for $I_{n,r_{n}(\beta)}$ in Lemmas 6.1 and 6.2
gives us the result (1.12) for $L_{k}(\mathcal{X}_{n})$ and the binomial
versions of (1.14) and (1.15) for for $L_{k}(\mathcal{X}_{n})$. Finally
applying Proposition 4.5 gives the same results for $M_{k}(\mathcal{X}_{n})$.
∎

## References

  * [1] Dette, H. and Henze, N. (1989) The limit distribution of the largest nearest-neighbour link in the unit $d$-cube. J. Appl. Probab. 26, 67–80.
  * [2] Gupta, B. and Iyer, S. (2010). Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs. Adv. in Appl. Probab. 42, 631–658.
  * [3] Gupta, P. and Kumar, P. R. (1999) Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis, Control, Optimization and Applications (eds. W.H. McEneany, G. Yin and Q. Zhang), 547–566. Birkhäuser, Boston.
  * [4] Higgs, F., Penrose, M.D. and Yang, X. (2024) Covering one point process with another. arXiv: 2401.03832v1
  * [5] Hsing, T. and Rootzén, H. (2005) Extremes on trees. Ann. Probab. 33, 413–444.
  * [6] Iyer, S. K. and Thacker, D. (2012) Nonuniform random geometric graphs with location-dependent radii. Ann. Appl. Probab. 22, 2048–2066.
  * [7] Last, G. and Penrose, M. (2018) Lectures on the Poisson process. Cambridge University Press, Cambridge.
  * [8] Penrose, M. (2003) Random Geometric Graphs. Oxford University Press, Oxford.
  * [9] Penrose, M. D. (1997) The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7, 340–361.
  * [10] Penrose, M. D. (1998) Extremes for the minimal spanning tree on normally distributed points. Adv. in Appl. Probab. 30, 628–639.
  * [11] Penrose, M. D. (1999) On $k$-connectivity for a geometric random graph. Random Structures Algorithms 15, 145–164.
  * [12] Penrose, M. D. (1999) A strong law for the largest nearest-neighbour link between random points. J. London Math. Soc. (2) 60, 951–960.
  * [13] Penrose, M. D. (1999) A strong law for the longest edge of the minimal spanning tree. Ann. Probab. 27, 246–260.
  * [14] Penrose, M. D. (2018) Inhomogeneous random graphs, isolated vertices, and Poisson approximation. J. Appl. Probab. 55, 112–136.
  * [15] Penrose, M. D. (2023) Random Euclidean coverage from within. Probab. Theory Related Fields 185, 747–814.
  * [16] Penrose, M. D. and Yang, X. (2023) On $k$-clusters of high-intensity random geometric graphs. arXiv:2209.14758v3
  * [17] Penrose, M. D., Yang, X., and Higgs, F. (2023). Largest nearest-neighbour link and connectivity threshold in a polytopal random sample. Journal of Applied and Computational Topology, 1-28.
  * [18] Rossi, F., Fiorentino, M. and Versace, P. (1984) Two-component extreme value distribution for flood frequency analysis. Water Resources Research 20, 847–856.