# Largest nearest-neighbour link and connectivity threshold in a polytopal
random sample ††thanks:  Supported by EPSRC grant EP/T028653/1

Mathew D. Penrose  Department of Mathematical Sciences, University of Bath,
Bath BA2 7AY, United Kingdom<EMAIL_ADDRESS>Xiaochuan Yang Department
of Mathematics, Brunel University London, Uxbridge, UB83PH, United Kingdom.
<EMAIL_ADDRESS>ORCID:0000-0003-2435-4615

###### Abstract

Let $X_{1},X_{2},\ldots$ be independent identically distributed random points
in a convex polytopal domain $A\subset\mathbb{R}^{d}$. Define the largest
nearest neighbour link $L_{n}$ to be the smallest $r$ such that every point of
$\mathcal{X}_{n}:=\\{X_{1},\ldots,X_{n}\\}$ has another such point within
distance $r$. We obtain a strong law of large numbers for $L_{n}$ in the
large-$n$ limit. A related threshold, the _connectivity threshold_ $M_{n}$, is
the smallest $r$ such that the random geometric graph $G(\mathcal{X}_{n},r)$
is connected. We show that as $n\to\infty$, almost surely $nL_{n}^{d}/\log n$
tends to a limit that depends on the geometry of $A$, and $nM_{n}^{d}/\log n$
tends to the same limit.

##  1 Introduction

This paper is primarily concerned with the connectivity threshold and largest
nearest-neighbour link for a random sample $\mathcal{X}_{n}$ of $n$ points
specified compact region $A$ in a $d$-dimensional Euclidean space.

The connectivity threshold, here denoted $M_{n}$, is defined to be the
smallest $r$ such that the random geometric graph $G(\mathcal{X}_{n},r)$ is
connected. For any finite $\mathcal{X}\subset\mathbb{R}^{d}$ the graph
$G(\mathcal{X},r)$ is defined to have vertex set $\mathcal{X}$ with edges
between those pairs of vertices $x,y$ such that $\|x-y\|\leq r$, where
$\|\cdot\|$ is the Euclidean norm. More generally, for $k\in\mathbb{N}$, the
$k$-connectivity threshold $M_{n,k}$ is the smallest $r$ such that
$G(\mathcal{X}_{n},r)$ is $k$-connected (see the definition in Section 2).

The largest nearest neighbour link, here denoted $L_{n}$, is defined to be the
the smallest $r$ such that every vertex in $G(\mathcal{X}_{n},r)$ has degree
at least 1. More generally, for $k\in\mathbb{N}$ with $k<n$, the largest
$k$-nearest neighbour link $L_{n,k}$ is the smallest $r$ such that every
vertex in $G(\mathcal{X}_{n},r)$ has degree at least $k$. These thresholds are
random variables, because the locations of the centres are random. We
investigate their probabilistic behaviour as $n$ becomes large.

We shall derive strong laws of large numbers showing that that
$nL_{n,k}^{d}/\log n$ converges almost surely (as $n\to\infty$) to a finite
positive limit, and establishing the value of the limit. Moreover we show that
$nM_{n,k}^{d}/\log n$ converges to the same limit. These strong laws carry
over to more general cases where $k$ may vary with $n$, and the distribution
of points may be non-uniform. We give results of this type for $A$ a convex
polytope.

Previous results of this type (both for $L_{n,k}$ and for $M_{n,k}$) were
obtained for $A$ having a smooth boundary, and for $A$ a $d$-dimensional
hypercube; see [5]. It is perhaps not obvious from the earlier results,
however, how the limiting constant depends on the geometry of $\partial A$,
the topological boundary of $A$, for general polytopal $A$, which is quite
subtle.

It turns out, for example, that when $d=3$ and the points are uniformly
distributed over a polyhedron, the limiting behaviour of $L_{n}$ is determined
by the angle of the sharpest edge if this angle is less than $\pi/2$. We
believe (but do not formally prove here) that if this angle exceeds $\pi/2$
then the point of $\mathcal{X}_{n}$ furthest from the rest of
$\mathcal{X}_{n}$ is asymptotically uniformly distributed over $\partial A$,
but if this angle is less than $\pi/2$ the location of this point in is
asymptotically uniformly distributed over the union of those edges which are
sharpest.

Our motivation for this study is twofold. First, understanding the
connectivity threshold in dimension two is vital in telecommunications, for
example, in 5G wireless network design, with the nodes of $\mathcal{X}_{n}$
representing mobile transceivers (see for example [1]). Second, detecting
connectivity is a fundamental step for detecting all other higher dimensional
topological features in modern topological data analysis (TDA), where the
dimension of the ambient space may be very high. See [2, 3] for discussion of
issues related to the one considered here, in relation to TDA. General
motivation for considering random geometric graphs is discussed in [5].

While our main results are presented (in Section 2) in the concrete setting of
a polytopal sample in $\mathbb{R}^{d}$, our proofs proceed via general lower
and upper bounds (Propositions 3.2 and 3.6) that are presented in the more
general setting of a random sample of points in a metric space satisfying
certain regularity conditions. This could be useful in possible future work
dealing with similar problems for random samples in, for example, a Riemannian
manifold with boundary, a setting of importance in TDA.

##  2 Statement of results

Throughout this paper, we work within the following mathematical framework.
Let $d\in\mathbb{N}$. Suppose we have the following ingredients:

  * •

A finite compact convex polytope $A\subset\mathbb{R}^{d}$ (i.e., one with
finitely many faces).

  * •

A Borel probability measure $\mu$ on $A$ with probability density function
$f$.

  * •

On a common probability space $(\mathbb{S},{\cal F},\mathbb{P})$, a sequence
$X_{1},X_{2},\ldots$ of independent identically distributed random $d$-vectors
with common probability distribution $\mu$, and also a unit rate Poisson
counting process $(Z_{t},t\geq 0)$, independent of $(X_{1},X_{2},\ldots)$ (so
$Z_{t}$ is Poisson distributed with mean $t$ for each $t>0$).

For $n\in\mathbb{N}$, $t>0$, let $\mathcal{X}_{n}:=\\{X_{1},\ldots,X_{n}\\}$,
and let ${\cal P}_{t}:=\\{X_{1},\ldots,X_{Z_{t}}\\}$. These are the point
processes that concern us here. Observe that ${\cal P}_{t}$ is a Poisson point
process in $\mathbb{R}^{d}$ with intensity measure $t\mu$ (see e.g. [4]).

For $x\in\mathbb{R}^{d}$ and $r>0$ set
$B(x,r):=\\{y\in\mathbb{R}^{d}:\|y-x\|\leq r\\}$. For $r>0$, let
$A^{(r)}:=\\{x\in A:B(x,r)\subset A^{o}\\}$, the ‘$r$-interior’ of $A$.

For any point set $\mathcal{X}\subset\mathbb{R}^{d}$ and any
$D\subset\mathbb{R}^{d}$ we write $\mathcal{X}(D)$ for the number of points of
$\mathcal{X}$ in $D$, and we use below the convention
$\inf(\varnothing):=+\infty$.

Given $n,k\in\mathbb{N}$, and $t\in(0,\infty)$, define the largest $k$-nearest
neighbour link $L_{n,k}$ by

$\displaystyle L_{n,k}:=\inf(\left\\{r>0:\mathcal{X}_{n}(B(x,r))\geq
k+1~{}~{}~{}~{}\forall x\in\mathcal{X}_{n}\right\\}).$ (2.1)

Set $L_{n}:=L_{n,1}$. Then $L_{n}$ is the largest nearest-neighbour link.

We are chiefly interested in the asymptotic behaviour of $L_{n}$ for large
$n$. More generally, we consider $L_{n,k}$ where $k$ may vary with $n$.

Let $\theta_{d}:=\pi^{d/2}/\Gamma(1+d/2)$, the volume of the unit ball in
$\mathbb{R}^{d}$. Given $x,y\in\mathbb{R}^{d}$, we denote by $[x,y]$ the line
segment from $x$ to $y$, that is, the convex hull of the set $\\{x,y\\}$.

Given $m\in\mathbb{N}$ and functions $f:\mathbb{N}\cap[m,\infty)\to\mathbb{R}$
and $g:\mathbb{N}\cap[m,\infty)\to(0,\infty)$, we write $f(n)=O(g(n))$ as
$n\to\infty$, if $\limsup_{n\to\infty}|f(n)|/g(n)<\infty$. We write
$f(n)=\Omega(g(n))$ as $n\to\infty$ if $\liminf_{n\to\infty}(f(n)/g(n))>0$.
Given $s>0$ and functions $f:(0,s)\to\mathbb{R}$ and $g:(0,s)\to(0,\infty)$,
we write $f(r)=O(g(r))$ as $r\downarrow 0$ if $\limsup_{r\downarrow
0}|f(r)|/g(r)<\infty$. We write $f(r)=\Omega(g(r))$ as $r\downarrow 0$, if
$\liminf_{r\downarrow 0}(f(r)/g(r))>0$.

Throughout this section, assume we are given a constant $\beta\in[0,\infty]$
and a sequence $k:\mathbb{N}\to\mathbb{N}$ with

$\displaystyle\lim_{n\to\infty}\left(k(n)/\log
n\right)=\beta;~{}~{}~{}~{}~{}\lim_{n\to\infty}\left(k(n)/n\right)=0.$ (2.2)

We make use of the following notation throughout:

$\displaystyle f_{0}:={\rm ess~{}inf}_{x\in
A}f(x);~{}~{}~{}~{}~{}~{}~{}f_{1}:=\inf_{x\in\partial A}f(x);$ (2.3)
$\displaystyle H(t):=\begin{cases}1-t+t\log t,~{}~{}~{}&{\rm if}~{}t>0\\\
1,&{\rm if}~{}t=0.\end{cases}$ (2.4)

Observe that $-H(\cdot)$ is unimodal with a maximum value of $0$ at $t=1$.
Given $a\in[0,\infty)$, we define the function
$\hat{H}_{a}:[0,\infty)\to[a,\infty)$ by

$\displaystyle y=\hat{H}_{a}(x)\Longleftrightarrow yH(a/y)=x,~{}y\geq a,$

with $\hat{H}_{0}(0):=0$. Note that $\hat{H}_{a}(x)$ is increasing in $x$, and
that $\hat{H}_{0}(x)=x$ and $\hat{H}_{a}(0)=a$.

Throughout this paper, the phrase ‘almost surely’ or ‘a.s.’ means ‘except on a
set of $\mathbb{P}$-measure zero’. For $n\in\mathbb{N}$, we use $[n]$ to
denote $\\{1,2,\ldots,n\\}$. We write $f|_{A}$ for the restriction of $f$ to
$A$.

Let $\Phi(A)$ denote the set of all faces of the polytope $A$ (of all
dimensions up to $d-1$). Also, let $\Phi^{*}(A):=\Phi(A)\cup\\{A\\}$; it is
sometimes useful for us to think of $A$ itself as a face, of dimension $d$.

Given a face $\varphi\in\Phi^{*}(A)$, denote the dimension of this face by
$D(\varphi)$. Then $0\leq D(\varphi)\leq d$, and $\varphi$ is a
$D(\varphi)$-dimensional polytope embedded in $\mathbb{R}^{d}$. Let
$\varphi^{o}$ denote the relative interior of $\varphi$, and set
$\partial\varphi:=\varphi\setminus\varphi^{o}$ (if $D(\varphi)=0$ we take
$\varphi^{o}:=\varphi$). If $D(\varphi)<d$ then set
$f_{\varphi}:=\inf_{x\in\varphi}f(x)$, and if $\varphi=A$ then set
$f_{\varphi}:=f_{0}$.

Then there is a cone ${\cal K}_{\varphi}$ in $\mathbb{R}^{d}$ such that every
$x\in\varphi^{o}$ has a neighbourhood $U_{x}$ such that $A\cap U_{x}=(x+{\cal
K}_{\varphi})\cap U_{x}$. Define the angular volume $\rho_{\varphi}$ of
$\varphi$ to be the $d$-dimensional Lebesgue measure of ${\cal
K}_{\varphi}\cap B(o,1)$.

For example, if $\varphi=A$ then $\rho_{\varphi}=\theta_{d}$. If
$D(\varphi)=d-1$ then $\rho_{\varphi}=\theta_{d}/2$. If $D(\varphi)=0$ then
$\varphi=\\{v\\}$ for some vertex $v\in\partial A$, and $\rho_{\varphi}$
equals the volume of $B(v,r)\cap A$, divided by $r^{d}$, for all sufficiently
small $r$. If $d=2$, $D(\varphi)=0$ and $\omega_{\varphi}$ denotes the angle
subtended by $A$ at the vertex $\varphi$, then
$\rho_{\varphi}=\omega_{\varphi}/2$. If $d=3$ and $D(\varphi)=1$, and
$\alpha_{\varphi}$ denotes the angle subtended by $A$ at the edge $\varphi$
(which is the angle between the two boundary planes of $A$ meeting at
$\varphi$), then $\rho_{\varphi}=2\alpha_{\varphi}/3$.

######  Theorem 2.1.

Suppose $A$ is a compact convex finite polytope in $\mathbb{R}^{d}$. Assume
that $f|_{A}$ is continuous at $x$ for all $x\in\partial A$, and that
$f_{0}>0$. Assume $k(\cdot)$ satisfies (2.2). Then, almost surely,

$\displaystyle\lim_{n\to\infty}nL_{n,k(n)}^{d}/k(n)$
$\displaystyle=\max_{\varphi\in\Phi^{*}(A)}\left(\frac{1}{f_{\varphi}\rho_{\varphi}}\right)$
$\displaystyle{\rm if}~{}\beta=\infty;$ (2.5)
$\displaystyle\lim_{n\to\infty}nL_{n,k(n)}^{d}/\log n$
$\displaystyle=\max_{\varphi\in\Phi^{*}(A)}\left(\frac{\hat{H}_{\beta}(D(\varphi)/d)}{f_{\varphi}\rho_{\varphi}}\right)$
$\displaystyle{\rm if}~{}\beta<\infty.$ (2.6)

In the next three results, we spell out some special cases of Theorem 2.1.

######  Corollary 2.2.

Suppose that $d=2$, $A$ is a convex polygon and $f|_{A}$ is continuous at $x$
for all $x\in\partial A$. Let $V$ denote the set of vertices of $A$, and for
$v\in V$ let $\omega_{v}$ denote the angle subtended by $A$ at vertex $v$.
Assume (2.2) holds with $\beta<\infty$. Then, almost surely,

$\displaystyle\lim_{n\to\infty}\left(\frac{nL_{n,k(n)}^{2}}{\log
n}\right)=\max\left(\frac{\hat{H}_{\beta}(1)}{\pi
f_{0}},\frac{2\hat{H}_{\beta}(1/2)}{\pi f_{1}},\max_{v\in
V}\left(\frac{2\beta}{\omega_{v}f(v)}\right)\right).$ (2.7)

In particular, for any constant $k\in\mathbb{N}$,
$\lim_{n\to\infty}\left(\frac{n\pi L_{n,k}^{2}}{\log
n}\right)=\frac{1}{f_{0}}.$

######  Corollary 2.3.

Suppose $d=3$ (so $\theta_{d}=4\pi/3$), $A$ is a convex polyhedron and
$f|_{A}$ is continuous at $x$ for all $x\in\partial A$. Let $V$ denote the set
of vertices of $A$, and $E$ the set of edges of $A$. For $e\in E$, let
$\alpha_{e}$ denote the angle subtended by $A$ at edge $e$, and $f_{e}$ the
infimum of $f$ over $e$. For $v\in V$ let $\rho_{v}$ denote the angular volume
of vertex $v$. Suppose (2.2) holds with $\beta<\infty$. Then, almost surely,

$\displaystyle\lim_{n\to\infty}\left(\frac{nL_{n,k(n)}^{3}}{\log
n}\right)=\max\left(\frac{\hat{H}_{\beta}(1)}{\theta_{3}f_{0}},\frac{2\hat{H}_{\beta}(2/3)}{\theta_{3}f_{1}},\frac{3\hat{H}_{\beta}(1/3)}{2\min_{e\in
E}(\alpha_{e}f_{e})},\max_{v\in
V}\left(\frac{\beta}{\rho_{v}f(v)}\right)\right).$

In particular, if $\beta=0$ the above limit comes to $\max\left(\frac{3}{4\pi
f_{0}},\frac{1}{\pi f_{1}},\max_{e\in
E}\left(\frac{1}{2\alpha_{e}f_{e}}\right)\right)$.

######  Corollary 2.4 ([5]).

Suppose $A=[0,1]^{d}$, and $f|_{A}$ is continuous at $x$ for all $x\in\partial
A$. For $1\leq j\leq d$ let $\partial_{j}$ denote the union of all
$(d-j)$-dimensional faces of $A$, and let $f_{j}$ denote the infimum of $f$
over $\partial_{j}$. Assume (2.2) with $\beta<\infty$. Then

$\displaystyle\lim_{n\to\infty}\left(\frac{nL_{n,k(n)}^{d}}{\log
n}\right)=\max_{0\leq j\leq
d}\left(\frac{2^{j}\hat{H}_{\beta}(1-j/d)}{\theta_{d}f_{j}}\right),~{}~{}~{}~{}~{}a.s.$
(2.8)

It is perhaps worth spelling out what the preceding results mean in the
special case where $\beta=0$ (for example, if $k(n)$ is a constant) and also
$\mu$ is the uniform distribution on $A$ (i.e. $f(x)\equiv f_{0}$ on $A$). In
this case, the right hand side of (2.6) comes to
$\max_{\varphi\in\Phi^{*}(A)}\frac{D(\varphi)}{(df_{0}\rho_{\varphi})}$. The
limit in (2.7) comes to $1/(\pi f_{0})$, while the limit in Corollary 2.3
comes to $f_{0}^{-1}\max[1/\pi,\max_{e}(1/(2\alpha_{e}))]$.

So far we have only presented results for the largest $k$-nearest neighbor
link. A closely related threshold is the _$k$ -connectivity threshold_ defined
by

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

where a graph $G$ of order $n$ is said to be $k$-connected ($k<n$) if $G$
cannot be disconnected by the removal of at most $k-1$ vertices. Set
$M_{n,1}=M_{n}$. Then $M_{n}$ is the connectivity threshold.

Notice that for all $k,n$ with $k<n$ we have

$\displaystyle L_{n,k}\leq M_{n,k}.$ (2.9)

Indeed, if $r<L_{n,k}$, then there exists $i\in[n]$ such that $\deg X_{i}<k$
in $G(\mathcal{X}_{n},r)$. Then the removal of all vertices adjacent to
$X_{i}$ disconnects $G(\mathcal{X}_{n},r)$, implying that $r<M_{n,k}$. This
proves the claim.

Our second main result shows that $(M_{n,k}/L_{n,k})\to 1$ almost surely as
$n\to\infty$. For this result we need $d\geq 2$.

######  Theorem 2.5.

Suppose $d\geq 2$. Suppose $A$ is a compact convex finite polytope in
$\mathbb{R}^{d}$. Assume that $f|_{A}$ is continuous at $x$ for all
$x\in\partial A$, and that $f_{0}>0$. Assume $k(\cdot)$ satisfies (2.2) Then,
almost surely,

$\displaystyle\lim_{n\to\infty}nM_{n,k(n)}^{d}/k(n)$
$\displaystyle=\max_{\varphi\in\Phi^{*}(A)}\left(\frac{1}{f_{\varphi}\rho_{\varphi}}\right)$
$\displaystyle{\rm if}~{}\beta=\infty;$ (2.10)
$\displaystyle\lim_{n\to\infty}nM_{n,k(n)}^{d}/\log n$
$\displaystyle=\max_{\varphi\in\Phi^{*}(A)}\left(\frac{\hat{H}_{\beta}(D(\varphi)/d)}{f_{\varphi}\rho_{\varphi}}\right)$
$\displaystyle{\rm if}~{}\beta<\infty.$ (2.11)

######  Remark 2.6.

One can spell out consequences of Theorem 2.5 in dimensions $d=2,3$ and the
case of $[0,1]^{d}$ with exactly the same statement as in Corollaries 2.2-2.4.

######  Remark 2.7.

Theorems 2.1 and 2.5 extend earlier work found in [5] on the case where $A$ is
the unit cube, to more general polytopal regions. The case where $A$ has a
smooth boundary is also considered in [5] (in this case with also $k(n)=$
const., the result was first given in [6] for $L_{n,k}$ and in [7] for
$M_{n,k}$).

######  Remark 2.8.

In [8], similar results are given for the $k$-coverage threshold $R_{n,k}$,
which is given by

$\displaystyle R_{n,k}:=\inf\left\\{r>0:\mathcal{X}_{n}(B(x,r))\geq
k~{}~{}~{}~{}\forall x\in A\right\\};~{}~{}~{}n,k\in\mathbb{N}.$ (2.12)

Our results here, together with [8, Theorem 4.2], show that both $L_{n,k(n)}$
and $M_{n,k(n)}$ are asymptotic to $R_{n,k(n)}$ almost surely, as
$n\to\infty$.

##  3 Proofs

In this section we prove the results stated in Section 2. Throughout this
section we are assuming we are given a constant $\beta\in[0,\infty]$ and a
sequence $(k(n))_{n\in\mathbb{N}}$ satisfying (2.2). Recall that $\mu$ denotes
the distribution of $X_{1}$, and this has a density $f$ with support $A$, and
that $L_{n,k}$ is defined at (2.1). Recall that $\hat{H}_{\beta}(x)$ is
defined to be the $y\geq\beta$ such that $yH(\beta/y)=x$, where $H(\cdot)$ was
defined at (2.4).

For $n\in\mathbb{N}$ and $p\in[0,1]$ let ${\rm Bin}(n,p)$ denote a binomial
random variable with parameters $n,p$. Recall that $H(\cdot)$ was defined at
(2.4), and $Z_{t}$ is a Poisson$(t)$ variable for $t>0$. The proofs in this
section rely heavily on the following lemma.

######  Lemma 3.1 (Chernoff bounds).

Suppose $n\in\mathbb{N}$, $p\in(0,1)$, $t>0$ and $0\leq k<n$.

(a) If $k\geq np$ then $\mathbb{P}[{\rm Bin}(n,p)\geq
k]\leq\exp\left(-npH(k/(np))\right)$.

(b) If $k\leq np$ then $\mathbb{P}[{\rm Bin}(n,p)\leq
k]\leq\exp\left(-npH(k/(np))\right)$.

(c) If $k\geq e^{2}np$ then $\mathbb{P}[{\rm Bin}(n,p)\geq
k]\leq\exp\left(-(k/2)\log(k/(np))\right)\leq e^{-k}$.

(d) If $k<t$ then $\mathbb{P}[Z_{t}\leq k]\leq\exp(-tH(k/t))$.

(e) If $k\in\mathbb{N}$ then $\mathbb{P}[Z_{t}=k]\geq(2\pi
k)^{-1/2}e^{-1/(12k)}\exp(-tH(k/t))$.

###### Proof.

See e.g. [5, Lemmas 1.1, 1.2 and 1.3]. ∎

###  3.1 A general lower bound

In this subsection we present an asymptotic lower bound on $L_{n,k(n)}$, not
requiring any extra assumptions on $A$. In fact, $A$ here can be any metric
space endowed with a Borel probability measure $\mu$ which satisfies the
following for some $\varepsilon^{\prime}>0$ and some $d>0$:

$\displaystyle\mu(B(x,r))\geq\varepsilon^{\prime}r^{d},\quad\forall~{}r\in(0,1),x\in
A.$ (3.1)

The definition of $L_{n,k}$ at (2.1) carries over in an obvious way to this
general setting.

Later, we shall derive the results stated in Section 2 by applying the results
of this subsection to the different regions within $A$ (namely interior,
boundary, and lower-dimensional faces).

Given $r>0,a>0$, define the ‘packing number’ $\nu(r,a)$ be the largest number
$m$ such that there exists a collection of $m$ disjoint closed balls of radius
$r$ centred on points of $A$, each with $\mu$-measure at most $a$.

######  Proposition 3.2 (General lower bound).

Assume (3.1) with $d,\varepsilon^{\prime}>0$. Let $a>0,b\geq 0$. Suppose
$\nu(r,ar^{d})=\Omega(r^{-b})$ as $r\downarrow 0$. Assume (2.2). Then almost
surely, if $\beta=\infty$ then
$\liminf_{n\to\infty}\left(nL_{n,k(n)}^{d}/k(n)\right)\geq 1/a$. If
$\beta<\infty$ then $\liminf_{n\to\infty}\left(nL_{n,k(n)}^{d}/\log
n\right)\geq a^{-1}\hat{H}_{\beta}(b/d)$, almost surely.

###### Proof.

First suppose $\beta=\infty$. Let $u\in(0,1/a)$. Set
$r_{n}:=\left(uk(n)/n\right)^{1/d}$, $n\in\mathbb{N}$. By (2.2), $r_{n}\to 0$
as $n\to\infty$. Then, given $n$ sufficiently large, we have
$\nu(r_{n},ar_{n}^{d})>0$ so we can find $y_{n}\in A$ such that
$\mu(B(y_{n},r_{n}))\leq ar_{n}^{d}$, and hence $n\mu(B(y_{n},r_{n}))\leq
auk(n)$. If $k(n)\leq e^{2}n\mu(B(y_{n},r_{n}))$ (and hence
$n\mu(B(y_{n},r_{n}))\geq e^{-2}k(n)$), then since
$\mathcal{X}_{n}(B(y_{n},r_{n}))$ is binomial with parameters $n$ and
$\mu(B(y_{n},r_{n}))$, by Lemma 3.1(a) we have that

$\displaystyle\mathbb{P}[\mathcal{X}_{n}(B(y_{n},r_{n}))\geq k(n)]$
$\displaystyle\leq$
$\displaystyle\exp\left(-n\mu(B(y_{n},r_{n}))H\left(\frac{k(n)}{n\mu(B(y_{n},r_{n}))}\right)\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-e^{-2}k(n)H\left((au)^{-1}\right)\right),$

while if $k(n)>e^{2}n\mu(B(y_{n},r_{n}))$ then by Lemma 3.1(c),
$\mathbb{P}[\mathcal{X}_{n}(B(y_{n},r_{n}))\geq k(n)]\leq e^{-k(n)}$.
Therefore $\mathbb{P}[\mathcal{X}_{n}(B(y_{n},r_{n}))\geq k(n)]$ is summable
in $n$ because $k(n)/\log n\to\infty$ as $n\to\infty$ by (2.2).

Let $\delta_{0}\in(0,1)$. By (3.1)
$\mu(B(y_{n},\delta_{0}r_{n})\geq\varepsilon^{\prime}\delta_{0}^{d}uk(n)/n$.
Therefore by Lemma 3.1(b),
$\mathbb{P}[\mathcal{X}_{n}(B(y_{n},\delta_{0}r_{n}))=0]\leq\exp(-\varepsilon^{\prime}\delta_{0}^{d}uk(n))$,
which is summable in $n$.

Thus by the Borel-Cantelli lemma, almost surely event
$F_{n}:=\\{\mathcal{X}_{n}(B(y_{n},r_{n}))<k(n)\\}\cap\\{\mathcal{X}_{n}(B(y_{n},\delta_{0}r_{n}))>0\\}$
occurs for all but finitely many $n$. But if $F_{n}$ occurs then
$L_{n,k(n)}\geq(1-\delta_{0})r_{n}$ so that
$nL_{n,k(n)}^{d}/k(n)\geq(1-\delta_{0})^{d}u$. This gives the result for
$\beta=\infty$.

Now suppose instead that $\beta<\infty$. Suppose first that $b=0$, so that
$\hat{H}_{\beta}(b/d)=\beta$. Assume that $\beta>0$ (otherwise the result is
trivial). Choose $\beta^{\prime}\in(0,\beta)$. Let $\delta>0$ with
$\beta^{\prime}<\beta-2\delta$ and with
$\beta^{\prime}H\left(\frac{\beta-2\delta}{\beta^{\prime}}\right)>\delta.$
This is possible because $H(\beta/\beta^{\prime})>0$ and $H(\cdot)$ is
continuous. For $n\in\mathbb{N}$, set $r_{n}:=((\beta^{\prime}\log
n)/(an))^{1/d}$. Also set $k^{\prime}(n)=\lceil(\beta-\delta)\log n\rceil$,
and $k^{\prime\prime}(n)=\lceil(\beta-2\delta)\log n\rceil$. By assumption
$\nu(r_{n},ar_{n}^{d})=\Omega(1)$, so for all $n$ large enough, we can (and
do) choose $x_{n}\in A$ such that $n\mu(B(x_{n},r_{n}))\leq
nar_{n}^{d}=\beta^{\prime}\log n.$ Then by a simple coupling, and Lemma
3.1(a),

$\displaystyle\mathbb{P}[\mathcal{X}_{n}(B(x_{n},r_{n}))\geq
k^{\prime\prime}(n)]$ $\displaystyle\leq$ $\displaystyle\mathbb{P}\left[{\rm
Bin}\left(n,(\beta^{\prime}\log n)/n)\right)\geq k^{\prime\prime}(n)\right]$
$\displaystyle\leq$ $\displaystyle\exp\left(-\left(\beta^{\prime}\log
n\right)H\left(\frac{\beta-2\delta}{\beta^{\prime}}\right)\right)\leq
n^{-\delta}.$

Let $\delta^{\prime}\in(0,1)$. By (3.1), for $n$ large enough and all $x\in
A$,

$\displaystyle n\mu(B(x,\delta^{\prime}r_{n}))\geq
n\varepsilon^{\prime}(\delta^{\prime}r_{n})^{d}=\varepsilon^{\prime}(\delta^{\prime})^{d}(\beta^{\prime}/a)\log
n$

so that by Lemma 3.1(b),
$\mathbb{P}[\mathcal{X}_{n}(B(x,\delta^{\prime}r_{n}))=0]\leq
n^{-\varepsilon^{\prime}(\delta^{\prime})^{d}\beta^{\prime}/a}$.

Now choose $K\in\mathbb{N}$ such that $\delta K>1$ and
$K\varepsilon^{\prime}(\delta^{\prime})^{d}\beta^{\prime}/a>1$. For
$n\in\mathbb{N}$ set $z(n):=n^{K}$. For all large enough $n$ we have
$k^{\prime}(z(n))\geq k^{\prime\prime}(z(n+1))$, so by the preceding
estimates,

$\displaystyle\mathbb{P}[\mathcal{X}_{z(n+1)}(B(x_{z(n+1)},r_{z(n+1)}))\geq
k^{\prime}(z(n))]~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\leq\mathbb{P}[\mathcal{X}_{z(n+1)}(B(x_{z(n+1)},r_{z(n+1)}))\geq
k^{\prime\prime}(z(n+1))]\leq(n+1)^{-\delta K},$

and since $x_{z(n+1)}\in A$, also
$\mathbb{P}[\mathcal{X}_{z(n)}(B(x_{z(n+1)},\delta^{\prime}r_{z(n)}))=0]\leq
n^{-\varepsilon^{\prime}(\delta^{\prime})^{d}\beta^{\prime}K/a}$. Both of
these upper bounds are summable in $n$, so by the Borel-Cantelli lemma, almost
surely for all large enough $n$ we have the event

$\\{\mathcal{X}_{z(n+1)}(B(x_{z(n+1)},r_{z(n+1)}))<k^{\prime}(z(n))\\}\cap\\{\mathcal{X}_{z(n)}(B(x_{z(n+1)},\delta^{\prime}r_{z(n)}))>0\\}.$

Suppose the above event occurs and suppose $m\in\mathbb{N}$ with $z(n)\leq
m\leq z(n+1)$. Note that $r_{z(n+1)}/r_{z(n)}\to 1$ as $n\to\infty$. Then,
provided $n$ is large enough,

$L_{m,k^{\prime}(z(n))}\geq
r_{z(n+1)}-\delta^{\prime}r_{z(n)}\geq(1-\delta^{\prime})^{2}r_{m},$

and moreover $k^{\prime}(z(n))\leq k(m)$ so that
$L_{m,k(m)}\geq(1-\delta^{\prime})^{2}r_{m}$. Hence it is almost surely the
case that

$\liminf_{m\to\infty}(mL_{m,k(m)}^{d}/\log
m)\geq(1-\delta^{\prime})^{2d}\liminf_{m\to\infty}(mr_{m}^{d}/\log
m)=(1-\delta^{\prime})^{2d}a^{-1}\beta^{\prime},$

and this yields the result for this case.

Now suppose instead that $\beta<\infty$ and $b>0$. Let
$u\in(a^{-1}\beta,a^{-1}\hat{H}_{\beta}(b/d))$; note that this implies
$uaH(\beta/(ua))<b/d$. Choose $\varepsilon>0$ such that
$(1+\varepsilon)uaH(\beta/(ua))<(b/d)-9\varepsilon$. Also let
$\delta^{\prime}\in(0,1)$.

For each $n\in\mathbb{N}$ set $r_{n}=(u(\log n)/n)^{1/d}$. Let
$m_{n}:=\nu(r_{n},ar_{n}^{d})$, and choose $x_{n,1},\ldots,$ $x_{n,m_{n}}\in
A$ such that the balls $B(x_{n,1},r_{n}),\ldots,B(x_{n,m_{n}},r_{n})$ are
pairwise disjoint and each have $\mu$-measure at most $ar_{n}^{d}$.

Set $\lambda(n):=n+n^{3/4}$ and $\lambda^{-}(n):=n-n^{3/4}$. For $1\leq i\leq
m_{n}$, if $k(n)\geq 1$ then by a simple coupling, and Lemma 3.1(e),

$\displaystyle\mathbb{P}[{\cal P}_{\lambda(n)}(B(x_{n,i},r_{n}))\leq
k(n)]\geq\mathbb{P}[Z_{\lambda(n)ar_{n}^{d}}\leq k(n)]$
$\displaystyle\geq\left(\frac{e^{-1/(12k(n))}}{\sqrt{2\pi
k(n)}}\right)\exp\left(-\lambda(n)ar_{n}^{d}H\left(\frac{k(n)}{\lambda(n)ar_{n}^{d}}\right)\right).$

Now $\lambda(n)r_{n}^{d}/\log n\to u$ so by (2.2),
$k(n)/(\lambda(n)ar_{n}^{d})\to\beta/(ua)$ as $n\to\infty$. Thus by the
continuity of $H(\cdot)$, provided $n$ is large enough, for $1\leq i\leq
m_{n}$,

$\displaystyle\mathbb{P}[{\cal P}_{\lambda(n)}(B(x_{n,i},r_{n}))\leq
k(n)]~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\geq\left(\frac{e^{-1/12}}{\sqrt{2\pi(\beta+1)\log
n}}\right)\exp\left(-(1+\varepsilon)auH\left(\frac{\beta}{au}\right)\log
n\right).$

Hence, by our choice of $\varepsilon$, there is a constant $c>0$ such that for
all large enough $n$ and all $i\in[m_{n}]$ we have

$\displaystyle\mathbb{P}[{\cal P}_{\lambda(n)}(B(x_{n,i},r_{n}))\leq k(n)]\geq
c(\log n)^{-1/2}n^{9\varepsilon-b/d}\geq n^{8\varepsilon-b/d}.$ (3.2)

Since $x_{n,i}\in A$, by (3.1), for $n$ large enough and $1\leq i\leq m_{n}$
we have
$\mu(B(x_{n,i},\delta^{\prime}r_{n}))\geq\varepsilon^{\prime}(\delta^{\prime}r_{n})^{d}$
(as well as $\mu(B(x_{n,i},r_{n}))\leq ar_{n}^{d}$). Thus, given the value of
${\cal P}_{\lambda(n)}(B(x_{n,i},r_{n}))$, the value of ${\cal
P}_{\lambda^{-}(n)}(B(x_{n,i},\delta^{\prime}r_{n}))$ is binomially
distributed with probability parameter bounded away from zero. Also
$\max_{1\leq i\leq m_{n}}\mathbb{E}\,[{\cal
P}_{\lambda(n)}(B(x_{n,i},r_{n}))]$ tends to infinity as $n\to\infty$.
Therefore there exists $\eta>0$ such that for all large enough $n$, defining
the event

$E_{n,i}:=\\{{\cal P}_{\lambda(n)}(B(x_{n,i},r_{n}))\leq k(n)\\}\cap\\{{\cal
P}_{\lambda^{-}(n)}(B(x_{n,i},\delta^{\prime}r_{n})\geq 1\\},$

we have for all large enough $n$ that

$\inf_{1\leq i\leq m_{n}}\mathbb{P}[E_{n,i}|{\cal
P}_{\lambda(n)}(B(x_{n,i},r_{n}))\leq k(n)]\geq\eta.$

Hence, setting $E_{n}:=\cup_{i=1}^{m_{n}}E_{n,i}$, for all large enough $n$ we
have

$\mathbb{P}[E_{n}^{c}]\leq(1-\eta n^{8\varepsilon-b/d})^{m_{n}}\leq\exp(-\eta
m_{n}n^{8\varepsilon-b/d}).$

By assumption $m_{n}=\nu(r_{n},ar_{n}^{d})=\Omega(r_{n}^{-b})$ so that for
large enough $n$ we have $m_{n}\geq n^{(b/d)-\varepsilon}$, and therefore
$\mathbb{P}[E^{c}_{n}]$ is is summable in $n$.

By Lemma 3.1(d), and Taylor expansion of $H(x)$ about $x=1$ (see the print
version of [5, Lemma 1.4] for details; there may be a typo in the electronic
version), for all $n$ large enough
$\mathbb{P}[Z_{\lambda(n)}<n]\leq\exp(-\frac{1}{9}n^{1/2})$. Similarly
$\mathbb{P}[Z_{\lambda^{-}(n)}>n]\leq\exp(-\frac{1}{9}n^{1/2})$. If $E_{n}$
occurs, and $Z_{\lambda^{-}(n)}\leq n$, and $Z_{\lambda(n)}\geq n$, then for
some $i\leq m_{n}$ there is at least one point of $\mathcal{X}_{n}$ in
$B(x_{n,i},\delta^{\prime}r_{n})$ and at most $k(n)$ points of
$\mathcal{X}_{n}$ in $B(x_{n,i},r_{n})$, and hence
$L_{n,k(n)}>(1-\delta^{\prime})r_{n}$. Hence by the union bound

$\mathbb{P}[L_{n,k(n)}\leq
r_{n}(1-\delta^{\prime})]\leq\mathbb{P}[E_{n}^{c}]+\mathbb{P}[Z_{\lambda(n)}<n]+\mathbb{P}[Z_{\lambda^{-}(n)}>n],$

which is summable in $n$ by the preceding estimates. Therefore by the Borel-
Cantelli lemma,

$\displaystyle\mathbb{P}[\liminf(nL_{n,k(n)}^{d}/\log n)\geq
u(1-\delta^{\prime})^{d}]=1,~{}~{}~{}~{}~{}u<a^{-1}\hat{H}_{\beta}(b/d),\delta^{\prime}\in(0,1),$

so the result follows for this case too. ∎

###  3.2 Proof of Theorem 2.1

In this subsection we assume, as in Theorem 2.1, that $A$ is a compact convex
finite polytope in $\mathbb{R}^{d}$. We also assume that the probability
measure $\mu$ has density $f$ with respect to Lebesgue measure on
$\mathbb{R}^{d}$, and that $f|_{A}$ is continuous at $x$ for all $x\in\partial
A$, and that $f_{0}>0$, recalling from (2.3) that $f_{0}:={\rm
ess~{}inf}_{x\in A}f(x)$. Also we let $k(n)$ satisfy (2.2) for some
$\beta\in[0,\infty]$. Let ${\rm Vol}$ denote $d$-dimensional Lebesgue measure

######  Lemma 3.3.

There exists $\varepsilon^{\prime}>0$ depending only on $f_{0}$ and $A$, such
that (3.1) holds.

###### Proof.

Let $B_{0}$ be a (fixed) ball contained in $A$, and let $b$ denote the radius
of $B_{0}$. For $x\in A$, let $S_{x}$ denote the convex hull of
$B_{0}\cup\\{x\\}$. Then $S_{x}\subset A$ since $A$ is convex. If $x\notin
B_{0}$, then for $r<b$ the set $B(x,r)\cap S_{x}$ is the intersection of
$B(x,r)$ with a cone having vertex $x$, and since $A$ is bounded the angular
volume of this cone is bounded away from zero, uniformly over $x\in A\setminus
B_{0}$. Therefore $r^{-d}{\rm Vol}(B(x,r)\cap A)$ is bounded away from zero
uniformly over $r\in(0,b)$ and $x\in A\setminus B_{0}$ (and hence over $x\in
A$). Since we assume $f_{0}>0$, (3.1) follows. ∎

Recall that $\nu(r,a)$ was defined just before Proposition 3.2. Recall that
for each face $\varphi\in\Phi^{*}(A)$ we denote the angular volume of $A$ at
$\varphi$ by $\rho_{\varphi}$, and set $f_{\varphi}:=\inf_{\varphi}f(\cdot)$
(if $\varphi\in\Phi(A)$) or $f_{\varphi}=f_{0}$ (if $\varphi=A$).

######  Lemma 3.4.

Let $\varphi\in\Phi^{*}(A)$. Assume $f|_{A}$ is continuous at $x$ for all
$x\in\varphi$. Then, almost surely:

$\displaystyle\liminf_{n\to\infty}\left(nL^{d}_{n,k(n)}/k(n)\right)$
$\displaystyle\geq(\rho_{\varphi}f_{\varphi})^{-1}~{}~{}~{}$
$\displaystyle{\rm if}~{}\beta=\infty;$ (3.3)
$\displaystyle\liminf_{n\to\infty}\left(nL^{d}_{n,k(n)}/\log n\right)$
$\displaystyle\geq(\rho_{\varphi}f_{\varphi})^{-1}\hat{H}_{\beta}(D(\varphi)/d)~{}~{}~{}$
$\displaystyle{\rm if}~{}\beta<\infty.$ (3.4)

###### Proof.

Let $a>f_{\varphi}$. Take $x_{0}\in\varphi$ such that $f(x_{0})<a$. If
$D(\varphi)>0$, assume also that $x_{0}\in\varphi^{o}$. By the assumed
continuity of $f|_{A}$ at $x_{0}$, for all small enough $r>0$ we have
$\mu(B(x_{0},r))\leq a\rho_{\varphi}r^{d}$, so that
$\nu(r,a\rho_{\varphi}r^{d})=\Omega(1)$ as $r\downarrow 0$. Hence, by
Proposition 3.2 (taking $b=0$), if $\beta=\infty$ then almost surely
$\liminf_{n\to\infty}nL_{n,k(n)}^{d}/k(n)\geq 1/(a\rho_{\varphi})$, and (3.3)
follows.

If $\beta<\infty$ and if $D(\varphi)=0$, then by Proposition 3.2 (with $b=0$),
almost surely $\liminf_{n\to\infty}(nL_{n,k(n)}^{d}/\log
n)\geq\hat{H}_{\beta}(0)/(a\rho_{\varphi})$, and hence (3.4) in this case.

Now suppose $\beta<\infty$ and $D(\varphi)>0$. Take $\delta>0$ such that
$f(x)<a$ for all $x\in B(x_{0},2\delta)\cap A$, and such that moreover
$B(x_{0},2\delta)\cap A=B(x_{0},2\delta)\cap(x_{0}+{\cal K}_{\varphi})$ (the
cone ${\cal K}_{\varphi}$ was defined in Section 2). Then for all $x\in
B(x_{0},\delta)\cap\varphi$ and all $r\in(0,\delta)$, we have $\mu(B(x,r))\leq
a\rho_{\varphi}r^{d}$.

There is a constant $c>0$ such that for small enough $r>0$ we can find at
least $cr^{-D(\varphi)}$ points $x_{i}\in B(x_{0},\delta)\cap\varphi$ that are
all at a distance more than $2r$ from each other, and therefore
$\nu(r,a\rho_{\varphi}r^{d})=\Omega(r^{-D(\varphi)})$ as $r\downarrow 0$. Thus
by Proposition 3.2 we have

$\liminf_{n\to\infty}\left(nL_{n,k(n)}^{d}/k(n)\right)\geq(a\rho_{\varphi})^{-1}\hat{H}_{\beta}(D(\varphi)/d),$

almost surely, and (3.4) follows. ∎

If we assumed $f|_{A}$ to be continuous on all of $A$, we would not need the
next lemma because we could instead use Lemma 3.4 for $\varphi=A$ as well as
for lower-dimensional faces. However, in Theorem 2.1 we make the weaker
assumption that $f|_{A}$ is continuous at $x$ only for $x\in\partial A$. In
this situation, we also require the following lemma to deal with $\varphi=A$.

######  Lemma 3.5.

It is the case that

$\displaystyle\mathbb{P}[\liminf(nL_{n,k(n)}^{d}/k(n))$ $\displaystyle\geq
1/(\theta_{d}f_{0})]=1$ $\displaystyle{\rm if}~{}\beta=\infty;$ (3.5)
$\displaystyle\mathbb{P}[\liminf_{n\to\infty}(nL_{n,k(n)}^{d}/\log n)$
$\displaystyle\geq\hat{H}_{\beta}(1)/(\theta_{d}f_{0})]=1$ $\displaystyle{\rm
if}~{}\beta<\infty.$ (3.6)

###### Proof.

Let $\alpha>f_{0}$. Then by taking $B=A$ in [8, Lemma 6.4],

$\displaystyle\liminf_{r\downarrow 0}r^{d}\nu(r,\alpha\theta_{d}r^{d})>0.$
(3.7)

Set $r_{n}:=(k(n)/(n\theta_{d}\alpha))^{1/d}$ if $\beta=\infty$, and set
$r_{n}:=(\hat{H}_{\beta}(1)(\log n)/(n\theta_{d}\alpha))^{1/d}$ if
$\beta<\infty$.

If $\beta=\infty$, then by (3.7) we can apply Proposition 3.2 (taking
$a=\alpha\theta_{d}$ and $b=0$) to deduce that
$\liminf_{n\to\infty}nL_{n,k(n)}^{d}/k(n)\geq(\theta_{d}\alpha)^{-1}$, almost
surely, and (3.5) follows.

Suppose instead that $\beta<\infty$. By (3.7),
$\nu(r,\alpha\theta_{d}r^{d})=\Omega(r^{-d})$ as $r\downarrow 0$. Hence by
Proposition 3.2, almost surely $\liminf_{n\to\infty}\left(nL_{n,k(n)}^{d}/\log
n\right)\geq(\alpha\theta_{d})^{-1}\hat{H}_{\beta}(1)$. The result follows by
letting $\alpha\downarrow f_{0}$. ∎

###### Proof of Theorem 2.1.

First suppose $\beta<\infty$. It is clear from (2.1) and (2.12) that
$L_{n,k}\leq R_{n,k+1}$ for all $n,k$. Also by (2.2) we have $(k(n)+1)/\log
n\to\beta$ as $n\to\infty$. Therefore using [8, Theorem 4.2] for the second
inequality below, we obtain almost surely that

$\displaystyle\limsup_{n\to\infty}\left(\frac{nL_{n,k(n)}^{d}}{\log
n}\right)\leq\limsup_{n\to\infty}\left(\frac{nR_{n,k(n)+1}^{d}}{\log
n}\right)\leq\max_{\varphi\in\Phi^{*}(A)}\left(\frac{\hat{H}_{\beta}(D(\varphi)/d)}{f_{\varphi}\rho_{\varphi}}\right).$
(3.8)

Alternatively, this upper bound could be derived using (2.9) and the
asymptotic upper bound on $M_{n}$ that we shall derive in the next section for
the proof of Theorem 2.5.

By Lemmas 3.5 and 3.4, we have a.s. that

$\displaystyle\liminf_{n\to\infty}\left(nL_{n,k(n)}^{d}/\log
n\right)\geq\max_{\varphi\in\Phi^{*}(A)}\left(\frac{\hat{H}_{\beta}(D(\varphi)/d)}{f_{\varphi}\rho_{\varphi}}\right),$
(3.9)

and combining this with (3.8) yields (2.6).

Now suppose $\beta=\infty$. In this case, again using the inequality
$L_{n,k}\leq R_{n,k+1}$ and [8, Theorem 4.2], we obtain instead of (3.8) that
a.s.

$\displaystyle\limsup_{n\to\infty}\left(nL_{n,k(n)}^{d}/k(n)\right)\leq\max_{\varphi\in\Phi^{*}(A)}\left(\frac{1}{f_{\varphi}\rho_{\varphi}}\right).$
(3.10)

Also by Lemmas 3.5 and 3.4, instead of (3.9) we have a.s. that

$\displaystyle\liminf_{n\to\infty}\left(nL_{n,k(n)}^{d}/k(n)\right)\geq\max_{\varphi\in\Phi^{*}(A)}\left(\frac{1}{f_{\varphi}\rho_{\varphi}}\right),$

and combining this with (3.10) yields (2.5). ∎

###  3.3 A general upper bound

In this subsection we present an asymptotic upper bound for $M_{n,k(n)}$. As
we did for the lower bound in Section 3.1, we shall give our result
(Proposition 3.6 below) in a more general setting; we assume that $A$ is a
general metric space endowed with two Borel measures $\mu$ and $\mu_{*}$
(possibly the same measure, possibly not). Assume that $\mu$ is a probability
measure and that $\mu_{*}$ is a doubling measure, meaning that there is a
constant $c_{*}$ (called a doubling constant for $\mu_{*}$) such that
$\mu_{*}(B(x,2r))\leq c_{*}\mu_{*}(B(x,r))$ for all $x\in A$ and $r>0$. We
shall require further conditions on $A$: an ordering condition (O), a
condition on balls (B), a topological condition (T) and a geometrical
condition (G) as follows:

  * (O)

There is a total ordering of the elements of $A$.

  * (B)

For all $x\in A$ and $r>0$, the ball $B(x,r)$ is connected.

  * (T)

The space $A$ is unicoherent (see [5, Section 9.1]), and also connected.

  * (G)

There exists $\delta_{1}>0$, and $K_{0}\in(1,\infty)$, such that for all
$r<\delta_{1}$ and any $x\in A$, the number of components of $A\setminus
B(x,r)$ is at most two, and if there are two components, at least one of these
components has diameter at most $K_{0}r$.

Given $D\subset A$ and $r>0$, we write $D_{r}$ for $\\{y\in A:\,{\rm
dist}(y,D)\leq r\\}$. Also, let $\kappa(D,r)$ be the $r$-covering number of
$D$, that is, the minimal $m\in\mathbb{N}$ such that $D$ can be covered by $m$
balls centred in $D$ with radius $r$.

As before, given $\mu$ we assume $X_{1},X_{2},\ldots$ to be independent
$\mu$-distributed random elements of $A$ with the $k$-connectivity threshold
$M_{n,k}$ defined to be the minimal $r$ such that $G(\mathcal{X}_{n},r)$ is
$k$-connected, with $\mathcal{X}_{n}:=\\{X_{1},\ldots,X_{n}\\}$.

######  Proposition 3.6 (General upper bound).

Suppose that $(A,\mu,\mu_{*})$ are as described above and $A$ satisfies
conditions (O), (B), (T), (G). Let $\ell\in\mathbb{N}$ and let $d>0$. For each
$j\in[\ell]$ let $a_{j}>0,b_{j}\geq 0$. Suppose that for each
$K\in\mathbb{N}$, there exists $r_{0}(K)>0$ such that for all
$r\in(0,r_{0}(K))$, there is a partition $\\{T(j,K,r),j\in[\ell]\\}$ of $A$
with the following two properties. Firstly for each fixed $K\in\mathbb{N}$,
$j\in[\ell]$, we have

$\displaystyle\kappa(T(j,K,r),r)=O(r^{-b_{j}})~{}~{}~{}{\rm
as}~{}~{}r\downarrow 0,$ (3.11)

and secondly, for all $K\in\mathbb{N},$ $j\in[\ell]$, $r\in(0,r_{0}(K))$ and
any $G\subset A$ intersecting $T(j,K,r)$ with ${\rm diam}(G)\leq Kr$, we have

$\displaystyle\mu(G_{r}\setminus G)\geq a_{j}r^{d}.$ (3.12)

Assume (2.2). Then, almost surely,

$\displaystyle\limsup_{n\to\infty}\big{(}nM^{d}_{n,k(n)}/k(n)\big{)}$
$\displaystyle\leq\max_{j\in[\ell]}(a_{j}^{-1})$ $\displaystyle{\rm
if}~{}\beta=\infty;$
$\displaystyle\limsup_{n\to\infty}\big{(}nM_{n,k(n)}^{d}/\log n\big{)}$
$\displaystyle\leq\max_{j\in[\ell]}(a_{j}^{-1}\hat{H}_{\beta}(b_{j}/d))$
$\displaystyle{\rm if}~{}\beta<\infty.$

Later we shall use Proposition 3.6 in the case where $A$ is a convex polytope
in $\mathbb{R}^{d}$ to prove Theorem 2.5, taking $\mu$ to be the measure with
density $f$ and taking $\mu_{*}$ to be the restriction of Lebesgue measure to
$A$ (in fact, if $f$ is bounded above then we could take $\mu_{*}=\mu$
instead). The sets in the partition each represent a region near to a
particular face $\varphi\in\Phi^{*}(A)$ (if $\varphi=A$ the corresponding set
in the partition is an interior region). In this case, coefficients $a_{j}$ in
the measure lower bound (3.12) depend heavily on the geometry of the
determining cone near a particular face.

As a first step towards proving Proposition 3.6, we spell out some useful
consequences of the measure doubling property. In this result (and again
later) we use $|\cdot|$ to denote the cardinality (number of elements) of a
set.

######  Lemma 3.7.

Let $\mu_{*}$ be a doubling measure on the metric space $A$, with doubling
constant $c_{*}$. We have the following.

(i) For any $\varepsilon\in(0,1)$, there exists
$\rho(\varepsilon)\in\mathbb{N}$ such that $\kappa(B(x,r),\varepsilon
r)\leq\rho(\varepsilon)$ for all $x\in A,r\in(0,\infty)$.

(ii) For all $r\in(0,1)$ and all $D\subset A$, we can find $\mathcal{L}\subset
D$ with $|\mathcal{L}|\leq\kappa(D,r/5)$, such that
$D\subset\cup_{x\in\mathcal{L}}B(x,r)$, and moreover the balls $B(x,r/5)$,
$x\in\mathcal{L}$, are disjoint.

###### Proof.

To prove (i), let $x\in A,r>0$. By the Vitali covering lemma, we can find a
set $\mathcal{U}\subset B(x,r)$ such that balls $B(y,\varepsilon
r/5),y\in\mathcal{U}$ are disjoint and that
$B(x,r)\subset\cup_{y\in\mathcal{U}}B(y,\varepsilon r)$. Set
$\rho(\varepsilon):=\lceil
c_{*}^{\lceil\log_{2}(15/\varepsilon)\rceil}\rceil$. Then by using the
doubling property of $\mu_{*}$ repeatedly, we have
$\mu_{*}(B(y,3r))\leq\rho(\varepsilon)\mu_{*}(B(y,r/5))$ for all $y\in A$.
Moreover $B(x,2r)\subset B(y,3r)$ for all $y\in\mathcal{U}$. Also
$\cup_{y\in\mathcal{U}}B(y,\varepsilon r/5)\subset B(x,2r)$ and the union is
disjoint. Thus

$\displaystyle|\mathcal{U}|\mu_{*}(B(x,2r))\leq\sum_{y\in\mathcal{U}}\mu_{*}(B(y,3r))\leq\rho(\varepsilon)\sum_{y\in\mathcal{U}}\mu_{*}(B(y,\varepsilon
r/5))\leq\rho(\varepsilon)\mu_{*}(B(x,2r)),$

and therefore $|\mathcal{U}|\leq\rho(\varepsilon)$; the claim about
$\kappa(B(x,r),\varepsilon r)$ follows.

Now we prove (ii). Let $\mathcal{L}^{0}\subset D$ with
$|\mathcal{L}^{0}|=\kappa(D,r/5)$ and with
$B\subset\cup_{x\in\mathcal{L}}B(x,r/5)$. By the Vitali covering lemma, we can
find $\mathcal{L}\subset\mathcal{L}^{0}$ such that
$D\subset\cup_{x\in\mathcal{L}}B(x,r)$ and the balls
$B(x,r/5),x\in\mathcal{L},$ are disjoint, and (ii) follows. ∎

Given countable $\sigma\subset A$, $r>0$ and $k\in\mathbb{N}$, we say that
$\sigma$ is $(r,k)$-connected if the geometric graph $G(\sigma,r)$ is
$k$-connected. Assuming condition (B) holds, we see that $\sigma$ is $(r,1)$
connected if and only if $\sigma_{r/2}$ is a connected subset of $A$.

######  Lemma 3.8 (Peierls argument).

Assume (O). Let $\ell\in\mathbb{N}$, $a\in[1,\infty)$. Let $r\in(0,1/a)$ and
$n\in\mathbb{N}$. Let $\mathcal{L}\subset A$ with the property that
$|\mathcal{L}\cap B(x,r)|\leq\ell$ for all $x\in A$, and let
$x_{0}\in\mathcal{L}_{r}$. Then the number of $(ar,1)$-connected subsets of
$\mathcal{L}$ containing $x_{0}$ with cardinality $n$ is at most $c^{n}$,
where $c$ depends only on $\ell$, $a$ and $c_{*}$.

###### Proof.

First we claim that $|\mathcal{L}\cap B(x,ar)|\leq\ell\rho(1/a)$ for all $x\in
A$, where $\rho(1/a)$ is as given in Lemma 3.7-(i). Indeed, we can cover
$B(x,ar)$ by $\rho(1/a)$ balls of radius $r$, and each of these balls contains
at most $\ell$ points of $\mathcal{L}$.

There is a standard algorithm (of constructing a non-decreasing sequence of
lists) for counting the connected sets of $\mathbb{Z}^{d}$; see [5, Lemma 9.3]
for details of the algorithm.

The algorithm remains valid in this general setting, with the lexicographical
ordering replaced by the total ordering of $A$ (using assumption (O)). This
algorithm has to stop at time $n$ (cardinality of the set), and at each step
the number of possibilities for the set of the added elements is bounded by
$2^{\ell\rho(1/a)}$ (all possible subsets of the set of points of
$\mathcal{L}$ within distance $ar$ from a fixed point); hence the number of
$ar$-connected sets of cardinality $n$ is at most $2^{\ell\rho(1/a)n}$. ∎

Preparing for a proof of Proposition 3.6, we recall a condition that is
equivalent to $k$-connectedness of a graph $G$. We say that non-empty sets
$U,W\subset V$ in a graph $G$ with vertex set $V$ form a $k$-separating pair
if (i) the subgraph of $G$ induced by $U$ is connected, and likewise for $W$;
(ii) no element of $U$ is adjacent to any element of $W$; (iii) the number of
vertices of $V\setminus(U\cup W)$ lying adjacent to $U\cup W$ is at most $k$.
We say that $U$ is a $k$-separating set for $G$ if (i) the subgraph of $G$
induced by $U$ is connected, and (ii) at most $k$ vertices of $V\setminus U$
lie adjacent to $U$. The relevance of these definitions is presented in the
following lemma.

######  Lemma 3.9.

[5, Lemma 13.1] Let $G$ be a graph with more than $k+1$ vertices. Then $G$ is
either $(k+1)$-connected, or it has $k$ separating pair, but not both.

By Lemma 3.9, to prove Proposition 3.6 it suffices to prove, for arbitrary
$u>\linebreak\max_{j}a_{j}^{-1}\hat{H}_{\beta}(b_{j}/d)$, the non-existence of
$(k(n)-1)$-separating pairs in $G(\mathcal{X}_{n},r_{n})$ with $r_{n}=(u\log
n/n)^{1/d}$, as $n\to\infty$. Notice that, for any fixed $K\in\mathbb{N}$, if
$(U,W)$ is a $(k-1)$-separating pair, then either both $U$ and $W$ have
diameter at least $Kr_{n}$, or one of them, say $U$, is a $(k-1)$-separating
set of diameter at most $Kr_{n}$. Here by the diameter of a a non-empty set
$U\subset A$ we mean the number ${\rm diam}(U):=\sup_{u,v\in U}\,{\rm
dist}(u,v)$.

The goal is to prove that neither outcome is possible when $n\to\infty$. Let
us first eliminate the existence of a small separating set.

######  Lemma 3.10.

Suppose the assumptions of Proposition 3.6 hold. If $\beta=\infty$, let
$u>\max_{j}a_{j}^{-1}$ and for $n\in\mathbb{N}$, set $r_{n}=(uk(n)/n)^{1/d}$.
If $\beta<\infty$, let
$u>\max_{j\in[\ell]}a_{j}^{-1}\hat{H}_{\beta}(b_{j}/d)$, and for
$n\in\mathbb{N}$ set $r_{n}=(u(\log n)/n)^{1/d}$. For $K\in\mathbb{N}$, let
$E_{n}(K,u)$ be the event that there exists a $(k(n)-1)$-separating set for
$G(\mathcal{X}_{n},r_{n})$ of diameter at most $Kr_{n}$. Then, given any
$K\in\mathbb{N}$, almost surely $E_{n}(K,u)$ occurs for only finitely many
$n$.

###### Proof.

First assume $\beta<\infty$. The condition on $u$ implies that $ua_{j}>\beta$
and $ua_{j}H(\beta/(ua_{j}))>b_{j}/d$, for each $j\in[\ell]$. Then we can and
do choose $\beta^{\prime}>\beta$ and $\varepsilon\in(0,1/4)$ such that for
each $j\in[\ell]$, $(1-3\varepsilon)^{d}ua_{j}>\beta^{\prime}$ and

$\displaystyle(1-3\varepsilon)^{d}ua_{j}H\Big{(}\frac{\beta^{\prime}}{(1-3\varepsilon)^{d}ua_{j}}\Big{)}>\frac{b_{j}}{d}+\varepsilon.$

For $n\in\mathbb{N}$ define $k^{\prime}(n)=\lceil\beta^{\prime}\log n\rceil$.

Let $K\in\mathbb{N}$, and for $r\in(0,r_{0}(K))$ let $T(j,K,r)$ be as in the
assumptions of Proposition 3.6. For $j\in[\ell]$, we claim that
$\kappa(T(j,K,r_{n}),\varepsilon r_{n}/5)=O(r_{n}^{-b_{j}})$ as $n\to\infty$.
Indeed,

$\kappa(T(j,K,r_{n}),\varepsilon
r_{n}/5)\leq\kappa(T(j,K,r_{n}),r_{n})\sup_{x\in
A}\kappa(B(x,r_{n}),\varepsilon r_{n}/5)\leq\rho\kappa(T(j,K,r_{n}),r_{n}),$

where $\rho=\rho(\varepsilon/5)$ is the constant in Lemma 3.7-(i). The claim
follows from the assumption (3.11).

Choose $n_{0}\in\mathbb{N}$ such that $r_{n}<r_{0}(k)$ for all
$n\in\mathbb{N}$ with $n\geq n_{0}$. By Lemma 3.7-(i), for each $j\in[\ell]$
and $n\in\mathbb{N}$ we can find a set $\mathcal{L}_{n}^{j}\subset
T(j,K,r_{n})$, with $|\mathcal{L}_{n}^{j}|\leq\kappa(T(j,K,r_{n}),\varepsilon
r_{n}/5)=O(r_{n}^{-b_{j}})$, such that
$T(j,K,r_{n})\subset\cup_{x\in\mathcal{L}_{n}^{j}}B(x,\varepsilon r_{n})$ and
that the balls $B(x,r_{n}\varepsilon/5)$, $x\in\mathcal{L}_{n}^{j}$, are
disjoint. Set

$\displaystyle\mathcal{L}_{n}:=\cup_{i=1}^{\ell}\mathcal{L}^{j}_{n}.$ (3.13)

For $n\geq n_{0},j\in[\ell]$ let
$\mathcal{T}_{n}^{j}=\\{\sigma\subset\mathcal{L}_{n}:{\rm diam}(\sigma)\leq
2Kr_{n},\sigma\cap T(j,K,r_{n})\neq\varnothing\\}$. We claim that the
cardinality of $\mathcal{T}^{j}_{n}$ is
$O(|\mathcal{L}_{n}^{j}|)=O(r_{n}^{-b_{j}})$. Indeed, $\sigma\cap
T(j,K,r_{n})\neq\varnothing$ means
$\sigma\cap\mathcal{L}^{j}_{n}\neq\varnothing$. Moreover, as explained below,

$\displaystyle\limsup_{n\to\infty}\sup_{x\in\mathcal{L}_{n}}|B(x,2Kr_{n})\cap\mathcal{L}_{n}|<\infty,$
(3.14)

and ${\rm diam}(\sigma)\leq 2Kr_{n}$. The claim about cardinality follows from
this.

Now we show (3.14). By Lemma 3.7-(i), for $n$ large and for all $x\in A$, we
can cover $B(x,2Kr_{n})$ by $\rho(\varepsilon/(10K))$ balls of radius
$r_{n}\varepsilon/5$, and each of these balls contains at most $\ell$ points
of $\mathcal{L}_{n}$.

For $n\geq n_{0}$ and $\sigma\subset\mathcal{L}_{n}$, set

$\displaystyle
D_{\sigma,n}:=\sigma_{(1-2\varepsilon)r_{n}}\setminus\sigma_{\varepsilon
r_{n}}.$ (3.15)

Let $J\in\mathbb{N}$ with $J>1/\varepsilon$. For $m\in\mathbb{N}$, define
$z(m):=m^{J}$. For $\sigma\subset\mathcal{L}_{z(m)}$, define

$\displaystyle
F_{m}(\sigma)=\\{\mathcal{X}_{z(m)}(D_{\sigma,z(m)})<k^{\prime}(z(m))\\}.$

Now let $n\in\mathbb{N}$ and choose $m=m(n)$ such that $z(m)\leq n<z(m+1)$.
Assume $z(m)\geq n_{0}$. Suppose that $E_{n}(K,u)$ occurs and let $U$ be a
$(k(n)-1)$-separating set of $G(\mathcal{X}_{n},r_{n})$ with ${\rm
diam}(U)\leq Kr_{n}$. We define its ‘pixel version’
$\sigma(U):=\mathcal{L}_{z(m(n))}\cap U_{\varepsilon r_{z(m(n))}}$.

Since $\sigma(U)\subset A$, there exists $j\in[\ell]$ such that $\sigma(U)\cap
T(j,K,r_{z(m(n))})\neq\varnothing$. By our choice of $\varepsilon$, provided
$n$ is large enough we have ${\rm diam}(\sigma(U))\leq 2Kr_{z(m(n))}$.
Therefore $\sigma(U)\in\cup_{j=1}^{[\ell]}\mathcal{T}^{j}_{z(m(n))}$.

Since $U$ is $(k(n)-1)$-separating for $G(\mathcal{X}_{n},r_{n})$, we have
$\mathcal{X}_{n}(U_{r_{n}}\setminus U)<k(n)$. We claim that
$\mathcal{X}_{n}(D_{\sigma(U),z(m(n))})<k(n)$ provided $n$ is large enough.
Indeed, by the triangle inequality
$\sigma(U)_{(1-2\varepsilon)r_{z(m(n))}}\subset
U_{(1-\varepsilon)r_{z(m(n))}}\subset U_{r_{n}}$ (for $n$ large), while
$U\subset\sigma(U)_{\varepsilon r_{z(n(m))}}$. Thus
$D_{\sigma(U),z(m(n))}\subset U_{r_{n}}\setminus U$, and the claim follows.
Also, provided $n$ is large enough, we have $k(n)\leq k^{\prime}(z(m(n)))$.
Thus we have the event inclusions

$\displaystyle E_{n}(K,u)$
$\displaystyle\subset\cup_{j=1}^{\ell}\cup_{\sigma\in\mathcal{T}^{j}_{z(m(n))}}\\{\mathcal{X}_{n}(D_{\sigma,z(m(n))})<k(n)\\}$
$\displaystyle\subset\cup_{j=1}^{\ell}\cup_{\sigma\in\mathcal{T}^{j}_{z(m(n))}}F_{m(n)}(\sigma).$

By (3.15), for any $n\in\mathbb{N}$ and $\sigma\subset\mathcal{L}_{n}$ we have
$D_{\sigma,n}\supset(\sigma_{\varepsilon
r_{n}})_{(1-3\varepsilon)r_{n}}\setminus\sigma_{\varepsilon r_{n}}$. Hence by
(3.12), for all large enough $n$ and all
$\sigma\in\cup_{j\in[\ell]}\mathcal{T}_{n}^{j}$ we have $\mu(D_{\sigma,n})\geq
a_{j}(1-3\varepsilon)^{d}r_{n}^{d}$. A simple coupling shows that, provided
$m$ is large, we have

$\displaystyle\mathbb{P}[\cup_{j\in[\ell]}\cup_{\sigma\in\mathcal{T}^{j}_{z(m)}}F_{m}(\sigma)]=\sum_{j=1}^{\ell}O(r_{z(m)}^{-b_{j}})\mathbb{P}[{\rm
Bin}(z(m),(1-3\varepsilon)^{d}a_{j}r_{z(m)}^{d})<k^{\prime}(z(m))].$

By Lemma 3.1(b) and our choice of $r_{n}$ and $\varepsilon$, provided $m$ is
large, we have

$\displaystyle\mathbb{P}[\cup_{j\in[\ell]}\cup_{\sigma\in\mathcal{T}^{j}_{z(m)}}F_{m}(\sigma)]$
$\displaystyle=O(1)\sum_{j=1}^{\ell}\exp\Big{(}(b_{j}/d)\log
z(m)-(1-3\varepsilon)^{d}ua_{j}H\big{(}\frac{\beta^{\prime}}{(1-3\varepsilon)^{d}ua_{j}}\big{)}\log
z(m)\Big{)}=O(m^{-J\varepsilon}),$

which is summable in $m$.

It follows from the Borel-Cantelli lemma that almost surely
$\cup_{j\in[\ell]}\cup_{\sigma\in\mathcal{T}^{j}_{z(m)}}F_{m}(\sigma)$ occurs
only for finitely many $m$ which implies that $E_{n}(K,u)$ occurs for only
finitely many $n$. This completes the proof of the case $\beta<\infty$.

Now assume $\beta=\infty$. For the rest of the proof assume also that
$\varepsilon\in(0,1)$ is such that $ua_{j}(1-\varepsilon)^{d}>1$ for all
$j\in[\ell]$. We do not have to go through the subsequence argument as before
because the growth of $k(n)$ is super-logarithmic. Now redefine
$F_{n}(\sigma):=\\{\mathcal{X}_{n}(D_{\sigma,n})<k(n)\\}$. If $E_{n}(K,u)$
happens then we now redefine the pixel version of the separating set $U$ as

$\sigma(U):=\mathcal{L}_{n}\cap U_{\varepsilon r_{n}},$

and enumerate the possible shapes $\sigma$ of the pixel version. Thus we have

$\displaystyle
E_{n}(K,u)\subset\cup_{j=1}^{\ell}\cup_{\sigma\in\mathcal{T}^{j}_{n}}F_{n}(\sigma).$

Using estimates of $|\mathcal{T}^{j}_{n}|$, we have

$\displaystyle\mathbb{P}[E_{n}(K,u)]=\sum_{j=1}^{\ell}O(r_{n}^{-b_{j}})\mathbb{P}[{\rm
Bin}(n,(1-3\varepsilon)^{d}a_{j}r_{n}^{d})<k(n)].$

Noticing $r_{n}^{-1}=O(n^{1/d})$, and applying Lemma 3.1-(b) leads to

$\displaystyle\mathbb{P}[E_{n}(K,u)]=O(n^{b_{j}/d})\sum_{j=1}^{\ell}\exp\Big{(}-(1-3\varepsilon)^{d}a_{j}uk(n)H\big{(}\frac{k(n)}{(1-3\varepsilon)^{d}a_{j}uk(n)}\big{)}\Big{)}$

which is summable in $n$, and the claim follows by the Borel-Cantelli lemma. ∎

The following lemma eliminates the existence of a $(k(n)-1)$-separating pair
with both diameters larger than $Kr_{n}$.

######  Lemma 3.11.

Let the assumptions of Proposition 3.6 hold. If $\beta=\infty$, let
$u>\max_{j}a_{j}^{-1}$ and for $n\in\mathbb{N}$, set $r_{n}=(uk(n)/n)^{1/d}$.
If $\beta<\infty$, let
$u>\max_{j\in[\ell]}a_{j}^{-1}\hat{H}_{\beta}(b_{j}/d)$, and for
$n\in\mathbb{N}$ set $r_{n}=(u(\log n)/n)^{1/d}$. For $K\in\mathbb{N}$ let
$H_{n}(K,u)$ denote the event that there exists a $(k(n)-1)$-separating pair
$(U,W)$ in $G(\mathcal{X}_{n},r_{n})$ such that $\min({\rm diam}(U),{\rm
diam}(W))\geq Kr_{n}$. Then there exists $K_{1}\in\mathbb{N}$ such that almost
surely $H_{n}(K_{1},u)$ occurs for only finitely many $n$.

###### Proof.

Suppose $H_{n}(K,u)$ holds. Then $U_{r_{n}/2}$ and $W_{r_{n}/2}$ are disjoint
and connected in $A$. One of the components of $A\setminus U_{r_{n}/2}$
contains $W$, denoted by $W^{\prime}$. Set $U^{\prime}=A\setminus W^{\prime}$.
Then $U\subset U^{\prime}$, $W\subset W^{\prime}$ and $A=W^{\prime}\cup
U^{\prime}$. Let
$\partial_{W}U:=\overline{W^{\prime}}\cap\overline{U^{\prime}}$. Then
$\partial_{W}U$ is connected by the unicoherence of $A$. Moreover, any
continuous path in $A$ connecting $U$ and $W$ must pass through
$\partial_{W}U$.

Recall $\delta_{1}$ and $K_{0}$ in the assumption (G). We claim (and show in
the next few paragraphs) that

$\displaystyle{\rm
diam}(\partial_{W}U)\geq\frac{1}{2K_{0}+2}\min(\delta_{1}/3,{\rm
diam}(W)/3,{\rm diam}(U)/3).$ (3.16)

Suppose the opposite. Setting $b={\rm diam}(\partial_{W}U)$, we can find $x\in
A$ such that $\partial_{W}U\subset B(x,b)$, and we can find $X\in U\setminus
B(x,b),Y\in W\setminus B(x,b)$. Since $b<\delta_{1}/3$, the number of
components of $A\setminus B(x,b)$ is at most two. There have to be two
components because otherwise $X$ and $Y$ can be connected by a path in $A$
disjoint from $\partial U$, which is a contradiction.

Suppose that $X$ lies in the component of $A\setminus B(x,b)$ having diameter
at most $K_{0}b$, denoted by $Q_{X}$, and $Y$ lies in the other component,
denoted by $Q_{Y}$ (if it is the other way round we reverse the roles of $X$
and $Y$ in the rest of this argument). We claim that there exists
$X^{\prime}\in U$ such that $\,{\rm dist}(X,X^{\prime})>(2K_{0}+2)b$. If not,
then for any $X_{1},X_{2}\in U$, we have by triangle inequality that $\,{\rm
dist}(X_{1},X_{2})\leq 2(2K_{0}+2)b$, yielding that ${\rm diam}(U)\leq
2(2K_{0}+2)b$, contradicting ${\rm diam}(U)>3(2K_{0}+2)b$ by the negation of
(3.16).

We claim that $\,{\rm dist}(X,B(x,b))\leq K_{0}b$. To see this, using the
assumed connectivity of $A$, take a continuous path in $A$ from $X$ to $Y$.
The first exit point of this path from $Q_{X}$ lies in $B(x,b)$ (else it would
not be an exit point from $Q_{X}$) but also in the closure of $Q_{X}$, and
hence in $B(X,K_{0}b)$. This yields the latest claim.

We show that $X^{\prime}$ and $Y$ have to be in the same component of
$A\setminus B(x,b)$. To this end, notice first that $X^{\prime}$ cannot be in
$Q_{X}$, because for any $z\in Q_{X}$,

$\displaystyle\,{\rm dist}(X,z)\leq K_{0}b<(2K_{0}+2)b.$

Secondly, $X^{\prime}$ cannot be in $B(x,b)$ either because for any $z\in
B(x,b)$, we have

$\displaystyle\,{\rm dist}(z,X)\leq\,{\rm
dist}(X,B(x,b))+2b\leq(K_{0}+2)b<(2K_{0}+2)b.$

Therefore, $X^{\prime}$ has to be in $Q_{Y}$, and we reach again to a
contradiction that $X^{\prime}$ and $Y$ can be connected by a path in $A$
disjoint from $\partial U$. We have thus proved (3.16).

Let $\varepsilon\in(0,1/9)$ and let $\mathcal{L}_{n}$ be as defined at (3.13)
(the $\varepsilon$ does not have to be the same as it was there). Recall that
$\mathcal{L}_{n}$ has the covering property that for every $x\in A$ we have
${\cal L}_{n}\cap B(x,r_{n}\varepsilon)\neq\varnothing$ and the spacing
property that $|{\cal L}_{n}\cap B(x,r_{n}\varepsilon/3)|\leq\ell$ for all
such $x$.

Define $D_{W}U=\\{x\in\mathcal{L}_{n}:B(x,\varepsilon
r_{n})\cap\partial_{W}U\neq\varnothing\\}$. Then by the covering property of
$\mathcal{L}_{n}$, $(D_{W}U)_{\varepsilon r_{n}}$ is connected and covers
$\partial_{W}U$. That is, $D_{W}U$, as a subset of the metric space $A$, is
$(2\varepsilon r_{n},1)$-connected.

By (3.16) and the occurrence of $H_{n}(K,u)$, we have

$\displaystyle 2\varepsilon r_{n}|D_{W}U|\geq{\rm
diam}(\partial_{W}U)\geq\min(\delta_{1}/3,Kr_{n}/3)/(2K_{0}+2)$

Therefore, provided $n$ is large, we have $|D_{W}U|\geq
K/(6\varepsilon(2K_{0}+2))$.

We claim that there is a constant $c\in(0,\infty)$, independent of $n$, such
that for all $q\in\mathbb{N}$, if $|D_{W}U|=q$ then $D_{W}U$ can take at most
$O(r_{n}^{-\max(b_{j})}c^{q})$ possible ’shapes’. Indeed, given $x_{0}\in{\cal
L}_{n}$, set

$\mathcal{U}_{n,q}(x_{0}):=\\{\sigma\subset\mathcal{L}_{n}:|\sigma|=q,\sigma\mbox{
is $(2\varepsilon r_{n},1)$-connected},x_{0}\in\sigma\\}.$

Then $D_{W}U\in\cup_{j\in[\ell]}\cup_{x_{0}\in
T(j,K,r_{n})\cap\mathcal{L}_{n}}\mathcal{U}_{n,q}(x_{0})$. By Lemma 3.8, we
have $|\mathcal{U}_{n,q}(x_{0})|\leq c^{q}$ for some finite constant $c$.
Recall from the proof of Lemma 3.10 that
$|T(j,K,r_{n})\cap\mathcal{L}_{n}|=O(r_{n}^{-b_{j}})$. The claim follows.

For all $n\in\mathbb{N}$, if $x\in\partial_{W}U$ then $\,{\rm
dist}(x,U)=r_{n}/2$. Therefore by the triangle inequality,
$(D_{W}U)_{\varepsilon r_{n}/5}\subset U_{r}$, while
$U\cap(D_{W}U)_{\varepsilon r_{n}/5}=\varnothing$; hence
$\mathcal{X}_{n}\cap(D_{W}U)_{\varepsilon r_{n}/5}=\varnothing$. This,
together with the the union bound, yields that

$\displaystyle\mathbb{P}[H_{n}(K,u)]\leq\sum_{q\geq
K/(6\varepsilon(2K_{0}+2))}\sum_{\sigma}\mathbb{P}[\mathcal{X}_{n}(\sigma_{\varepsilon
r_{n}/5})<k(n)],$ (3.17)

where the second sum is over all possible shapes
$\sigma\subset\mathcal{L}_{n}$ of cardinality $q$ that are $(2\varepsilon
r_{n},1)$-connected. Since every point in $A$ is covered at most $\ell$ times,
by (3.12) (with $G=\\{z\\}$), there exists $\varepsilon_{1}\in(0,1)$ such that

$\displaystyle\mu(\sigma_{\varepsilon
r_{n}/5})\geq(1/\ell)\sum_{z\in\sigma}\mu(B(z,\varepsilon
r_{n}/5))\geq(q/\ell)\varepsilon_{1}(\varepsilon r_{n}/5)^{d}.$

Suppose $\beta<\infty$. Set
$\varepsilon_{2}:=(\varepsilon_{1}/\ell)(\varepsilon/5)^{d}$. By (3.17) and
Lemma 3.1(b), provided $n$ is large,

$\displaystyle\mathbb{P}[H_{n}(K,u)]\leq\sum_{q\geq
K/(6\varepsilon(2K_{0}+2))}O(r_{n}^{-\max(b_{j})}c^{q})\mathbb{P}[{\rm
Bin}(n,\varepsilon_{2}qr_{n}^{d})<(\beta+1)\log n]$
$\displaystyle=O(1)\sum_{q\geq
K/(6\varepsilon(2K_{0}+2))}c^{q}\exp\Big{(}(\max(b_{j})/d)\log
n-\varepsilon_{2}quH\big{(}\frac{\beta+1}{\varepsilon_{2}qu}\big{)}\log
n\Big{)}.$

By the continuity of $H(\cdot)$ and the fact that $H(0)=1$, there exists
$q_{0}>16/(\varepsilon_{2}u)$ such that for any $q>q_{0}$, we have
$H\big{(}\frac{\beta+1}{q\varepsilon_{2}u}\big{)}>1/2$ and
$qu\varepsilon_{2}>4\max(b_{j})/d$. Choosing $K=6\varepsilon(2K_{0}+2)q_{0}$
so that $q\geq q_{0}$ in the sum, we see that the exponent of the exponential
is bounded above by

$\displaystyle(\max(b_{j})/d)\log n-q\varepsilon_{2}(u/2)\log
n\leq-(qu\varepsilon_{2}/4)\log n.$

Therefore, we have for $n$ large that

$\displaystyle\mathbb{P}[H_{n}(K,u)]$ $\displaystyle=O(1)\sum_{q\geq
q_{0}}c^{q}\exp(-qu(\varepsilon_{2}/4)\log n)$ $\displaystyle=O(1)\sum_{q\geq
q_{0}}\exp(-qu(\varepsilon_{2}/8)\log n)=O(\exp(-q_{0}u(\varepsilon_{2}/8)\log
n))=O(n^{-2}).$

The result in this case follows by applying the Borel-Cantelli lemma.

If $\beta=\infty$, then by (3.17) and the estimates of
$|\cup_{j}\cup_{x_{0}}\mathcal{U}_{n,q}(x_{0})|$ as previously, we have

$\displaystyle\mathbb{P}[H_{n}(K,u)]\leq\sum_{q\geq
K/(6\varepsilon(2K_{0}+2))}O(r_{n}^{-\max(b_{j})}c^{q})\mathbb{P}[{\rm
Bin}(n,(q/\ell)\varepsilon_{1}(\varepsilon r_{n}/5)^{d})<k(n)].$

We have $r_{n}^{-\max(b_{j})}=O(n^{\max(b_{j})/d})$, and by Lemma 3.1-(b),

$\displaystyle\mathbb{P}[H_{n}(K,u)]\leq\sum_{q\geq
K/(6\varepsilon(2K_{0}+2))}c^{q}\exp\Big{(}(\max(b_{j})/d)\log
n-q\varepsilon_{2}uk(n)H(\frac{k(n)}{q\varepsilon_{2}uk(n)})\Big{)}.$

As before, we can choose $K=K_{1}$ (large) so that the $H(\cdot)$ term in
every summand is bounded from below by $1/2$. By the super-logarithmic growth
of $k(n)$, we conclude that $\mathbb{P}[H_{n}(K,u)]\leq n^{-2}$ provided $n$
is large, so that the Borel-Cantelli lemma gives the result in this case too.
∎

###### Proof of Proposition 3.6.

If $\beta=\infty$ then let $u>\max_{j\in[\ell]}(a_{j}^{-1})$ and set
$r(n):=u(k(n)/n)^{1/d}$. If $\beta<\infty$ then let
$u>\max_{j\in[\ell]}(a_{j}^{-1}\hat{H}_{\beta}(b_{j}/d))$ and set
$r_{n}:=(u(\log n)/n)^{1/d}$. By Lemmas 3.10 and 3.11, there exists
$K\in\mathbb{N}$ such that almost surely, $E_{n}(K,u)\cup H_{n}(K,u)$ occurs
for at most finitely many $n$. By Lemma 3.9, if $M_{n,k}>r_{n}$ then
$E_{n}(K,u)\cup H_{n}(K,u)$ occurs. Therefore $M_{n,k(n)}\leq r_{n}$ for all
large enough $n$, almost surely, and the result follows. ∎

###  3.4 Proof of Theorem 2.5

In this subsection we go back to the mathematical framework in Section 2; that
is, we make the assumptions in the statement of Theorem 2.5. In particular we
return to assuming $A$ is a convex polytope in $\mathbb{R}^{d}$ with $d\geq
2$, and the probability measure $\mu$ has a density $f$. We shall check the
conditions required in order to apply Proposition 3.6.

To check these conditions, we shall use the following lemma and notation.

######  Lemma 3.12.

[8, Lemma 6.12] Suppose $\varphi,\varphi^{\prime}$ are faces of $A$ with
$D(\varphi)>0$ and $D(\varphi^{\prime})=d-1$, and with
$\varphi\setminus\varphi^{\prime}\neq\varnothing$. Then
$\varphi^{o}\cap\varphi^{\prime}=\varnothing$ and
$K(\varphi,\varphi^{\prime})<\infty$, where we set

$\displaystyle K(\varphi,\varphi^{\prime}):=\sup_{x\in\varphi^{o}}\frac{\,{\rm
dist}(x,\partial\varphi)}{\,{\rm dist}(x,\varphi^{\prime})}.$ (3.18)

Now define

$\displaystyle
K(A):=\max\\{K(\varphi,\varphi^{\prime}):\varphi,\varphi^{\prime}\in\Phi(A),D(\varphi)>0,D(\varphi^{\prime})=d-1,\varphi\setminus\varphi^{\prime}\neq\varnothing\\}.$
(3.19)

Then $K(A)<\infty$ since $A$ is a finite polytope.

For $j\in\\{0,1,\ldots,d\\}$ let $\Phi_{j}(A)$ denote the collection of
$j$-dimensional faces of $A$. For any $D\subset A$ and $r>0$ set
$D_{r}=\\{x\in A:B(x,r)\cap D\neq\varnothing\\}$.

######  Lemma 3.13.

The restriction of Lebesgue measure to $A$ has the doubling property. Moreover
the conditions (O), (B), (T) and (G) are met.

###### Proof.

First we verify the doubling property. By the proof of Lemma 3.3, there exists
$b>0$ such that $\inf_{x\in A,r\in(0,b]}r^{-d}{\rm Vol}(B(x,r)\cap A)>0$.
Since ${\rm Vol}(B(x,2r)\cap A)$ is at most $2^{d}\theta_{d}r^{d}$ for $r\leq
b$, and is at most ${\rm Vol}(A)$ for all $r$, the doubling property follows.

Points of $A$ can be ordered by using the lexicographic ordering inherited
from $\mathbb{R}^{d}$, thus (O). Since $A$ is convex, for all $x\in A$ and
$r>0$ the set $B(x,r)\cap A$ is convex and hence connected, implying (B). All
convex polytopes are simply connected, and therefore unicoherent [5, Lemma
9.1], hence (T). Condition (G) follows immediately from Proposition 3.14,
which we prove below. ∎

######  Proposition 3.14.

Let $A$ be a convex finite polytope in $\mathbb{R}^{d}$. Let $N(\cdot)$ denote
the number of components of a set. There exists $\delta_{1}>0$ such that for
any $x\in A$ any $r\in(0,\delta_{1})$, we have $N(A\setminus B(x,r))\leq 2$.
Moreover, in the case that $N(A\setminus B(x,r))=2$, the diameter of the
smaller component is at most $cr$, where $c$ is a constant depending only on
$A$.

###### Proof of Proposition 3.14.

Write $B$ for $B(x,r)$. Our first observation is that if $y\in A\setminus B$,
then there is at least one vertex $v\in\Phi_{0}(A)$ such that the line segment
$[y,v]$ is contained in $A\setminus B$. Indeed, if this failed then for each
$v\in\Phi_{0}(A)$ there would exist a point $u(v)\in[y,v]\cap B$. But then
since $A$ is convex, $y$ would lie in the convex hull of
$\\{v:v\in\Phi_{0}(A)\\}$, and therefore also in the convex hull of
$\\{u(v):v\in\Phi_{0}(A)\\}$. Indeed, there exist $\alpha_{v}\geq 0$ with
$\sum_{v\in\Phi_{0}(A)}\alpha_{v}=1$ such that
$y=\sum_{v\in\Phi_{0}(A)}\alpha_{v}v$, and there exists $\beta_{v}\in[0,1]$
such that $u(v)=\beta_{v}y+(1-\beta_{v})v$. Substituting $v$ by $u(v)$ and
rearranging terms shows that $y=\sum_{v}\alpha^{\prime}_{v}u(v)$ with some
nonnegative $\alpha^{\prime}_{v}$ and $\sum_{v}\alpha^{\prime}_{v}=1$, thus
the claim. But then since $B$ is convex we would have $y\in B$, a
contradiction.

We refer to the one-dimensional faces $\varphi\in\Phi_{1}(A)$ as edges of $A$.
Our second observation is that if the number of edges of $A$ that intersect
$B$ is at most 1, then $A\setminus B$ is connected. Indeed, in this case, for
any distinct $v,v^{\prime}\in\Phi_{0}(A)$ there is a path along edges of $A$
from $v$ to $v^{\prime}$ that avoids $B$. For example, if $v,v^{\prime}$ lie
in the same two-dimensional face $\varphi$ of $A$ then since $B$ intersects at
most one edge of the polygon $\varphi$, there is a path from $v$ to
$v^{\prime}$ along the edges of $\varphi$ avoiding $B$. Therefore all
$v\in\Phi_{0}(A)$ lie in the same component of $A\setminus B$, so using the
first observation we deduce that $A\setminus B$ is connected.

Recall the definition of $K(A)$ at (3.19). Our third observation is that if
$\,{\rm dist}(v,B)\geq 3rK(A)$ for all $v\in\Phi_{0}(A)$ then $A\setminus B$
is connected. Indeed, suppose $\,{\rm dist}(v,B)\geq 3rK(A)$ for all
$v\in\Phi_{0}(A)$. Suppose $\varphi,\varphi^{\prime}$ are distinct edges of
$A$ with $B\cap\varphi\neq\varnothing$, and pick $y\in B\cap\varphi$. Then
$\,{\rm dist}(y,\partial\varphi)\geq 3rK(A)$ so that by (3.18), $\,{\rm
dist}(y,\varphi^{\prime})\geq 3rK(A)/K(\varphi,\varphi^{\prime})\geq 3r$.
Hence by the triangle inequality $\,{\rm dist}(B,\varphi^{\prime})\geq
3r-2r=r$, so that $B\cap\varphi^{\prime}=\varnothing$. Hence $B$ intersects at
most one edge of $A$, and by our second observation $A\setminus B$ is
connected.

Suppose $\,{\rm dist}(v,B)\leq 3rK(A)$ for some $v\in\Phi_{0}(A)$. Provided
$r$ is small enough, this cannot happen for more than one $v\in\Phi_{0}(A)$.
If $u,u^{\prime}\in\Phi_{0}(A)\setminus\\{v\\}$, then $v\notin[u,u^{\prime}]$
so $\,{\rm dist}(v,[u,u^{\prime}])>0$. Therefore provided $r$ is small enough,
$[u,u^{\prime}]\subset A\setminus B$. Thus provided $r$ is small enough, all
vertices $u\in\Phi_{0}(A)\setminus\\{v\\}$ lie in the same component of
$A\setminus B$. If also $v$ lies in this component, then (by our first
observation) $A\setminus B$ is connected.

Thus $A\setminus B$ is disconnected only if $v$ lies in a different component
of $A\setminus B$ than all the other vertices. In that case, for $y\in
A\setminus B$, if $[y,v]\subset A\setminus B$ then $y$ is in the same
component as $v$; otherwise (by our first observation) $y$ lies in the same
component as all of the other vertices, and thus $A\setminus B$ has exactly
two components.

If $A\setminus B$ has two components, and $y\in A\setminus B$ with
$\|y-v\|>(3K(A)+2)r$, then we claim $[y,v]\cap B\neq\varnothing$. Indeed, for
each $u\in\Phi_{0}(A)\setminus\\{v\\}$ the ray from $v$ in the direction of
$u$ passes through $B$. But then by an argument based on the convexity of both
$A$ and $B$, the ray from $v$ in the direction of $y$ must also pass through
$B$. Since $\,{\rm dist}(v,B)\leq 3rK(A)$ and ${\rm diam}(B)=2r$, this ray
must pass through $B$ at a distance at most $(3K(A)+2)r$ from $v$, i.e. before
it reaches $y$, and the claim follows. Therefore $y$ lies in the component of
$A\setminus B$ that does not contain $v$, and thus the component containing
$v$ has diameter at most $(3K(A)+2)r$. ∎

To apply Proposition 3.6, we need to define a partition of $A$ for each small
$r>0$, then estimate the corresponding covering numbers and $\mu$-measures in
(3.12).

Taking into account a variety of boundary effects near $\partial A$, one
should consider separately regions near different faces of $A$. It is however
not trivial to construct this partition in such a way that we can obtain tight
$\mu$-measure estimates in (3.12). The matter is complicated by the fact that
the set $G$ in (3.12) that intersects a region near $\varphi$ is potentially
close to a lower dimensional face lying inside $\partial\varphi$. We can avoid
the boundary complications by constructing inductively from regions near to
the highest dimensional face to the lowest, with increasing ’thickness’. The
partition made of $T(\varphi,r)$’s defined below and the left-over interior
region is defined for this purpose.

Let $(K_{j})_{j\in\mathbb{N}}$ be an increasing sequence with $K_{1}=1$, and
with $K_{j+1}>(2K(A)+1)K_{j}$ for each $j\in\mathbb{N}$. For instance, we
could take $K_{j}=(2K(A)+2)^{j-1}$.

Now for each $r>0$ and $\varphi\in\Phi(A)$, define the set

$T(\varphi,r):=\varphi_{rK_{d-D(\varphi)}}\setminus\cup_{\varphi^{\prime}\in\Phi(A):\varphi^{\prime}\subsetneq\varphi}(\varphi^{\prime})_{rK_{d-D(\varphi^{\prime})}},$

where the $T$ stands for ‘territory’. Also define
$T(A,r):=A\setminus\cup_{\varphi\in\Phi(A)}\varphi_{rK_{d-D(\varphi)}}$ For
each $\varphi\in\Phi^{*}(A)$, we have $T(\varphi,r)\neq\varnothing$ for all
$r$ sufficiently small. Hence, there exists $r_{0}>0$ such that for all
$\varphi$ and all $r<r_{0}$, $T(\varphi,r)\neq\varnothing$. Moreover,
territories of distinct faces are disjoint, as we show in the following lemma.

######  Lemma 3.15.

There exists $r_{0}>0$ such that for all $r\in(0,r_{0})$, and any distinct
$\varphi,\varphi^{\prime}\in\Phi^{*}(A)$, it holds that $T(\varphi,r)\cap
T(\varphi^{\prime},r)=\varnothing$. Moreover, if
$\varphi,\varphi^{\prime}\in\Phi(A)$ with
$\varphi\setminus\varphi^{\prime}\neq\varnothing$, and $y\in T(\varphi,r)$,
then $B(y,r)$ does not intersect $\varphi^{\prime}$.

###### Proof.

We can (and do) assume without loss of generality that
$\varphi\setminus\varphi^{\prime}\neq\varnothing$ and
$\varphi^{\prime}\setminus\varphi\neq\varnothing$. Indeed, if
$\varphi\subset\varphi^{\prime}$, then by construction
$T(\varphi^{\prime},r)\cap T(\varphi,r)=\varnothing$.

If $\varphi$ is a vertex, then $\,{\rm dist}(\varphi,\varphi^{\prime})>0$ so
that $T(\varphi,r)\cap T(\varphi^{\prime},r)=\varnothing$ for all $r$ small.
So it suffices to consider the case where $D(\varphi)>0$ and
$D(\varphi^{\prime})>0$.

Let $j:=d-D(\varphi)$ and $j^{\prime}:=d-D(\varphi^{\prime})$. We can and do
assume $j^{\prime}\leq j\leq d-1$.

If there exists $x\in T(\varphi,r)\cap T(\varphi^{\prime},r)$, then we can
find $z\in\varphi,z^{\prime}\in\varphi^{\prime}$ such that $\|x-z\|\leq
rK_{j}$ and $\|x-z^{\prime}\|\leq rK_{j^{\prime}}$. Therefore $\,{\rm
dist}(z,\varphi^{\prime})\leq r(K_{j}+K_{j^{\prime}})\leq 2rK_{j}$.

On the other hand, since $x\in T(\varphi,r)$, $\,{\rm
dist}(x,\partial\varphi)\geq rK_{j+1}$, and so by the triangle inequality,
$rK_{j+1}-rK_{j}\leq\,{\rm dist}(z,\partial\varphi)\leq K(A)\,{\rm
dist}(z,\varphi^{\prime})$, where the last inequality comes from (3.18).
Combining the estimates leads to $K_{j+1}\leq(2K(A)+1)K_{j}$, which is a
contradiction. The first claim follows.

Moving to the second claim, let $\varphi,\varphi^{\prime}\in\Phi(A)$ with
$\varphi\setminus\varphi^{\prime}\neq\varnothing$. Suppose
$y\in\varphi^{\prime}_{r}$. Set

$\tilde{\Phi}:=\\{\psi\in\Phi(A):\psi\subsetneq\varphi^{\prime},y\in\psi_{K_{D-d(\psi)}}\\}.$

If $\tilde{\Phi}=\varnothing$ then $y\in T(\varphi^{\prime},r)$. Otherwise,
choose $\psi\in\tilde{\Phi}$ of minimal dimension. Then $y\in T(\psi,r)$.
Either way, $y\notin T(\varphi,r)$ by the first claim. Therefore
$T(\varphi,r)\cap\varphi^{\prime}_{r}=\varnothing$. ∎

As a last ingredient for applying Proposition 3.6, for each $J>1$ and
$r\in(0,1)$, we construct a partition of $A$ and show (3.12) for all $G$ with
diameter at most $Jr$. The coefficients $a_{j}$ depend on the location of $G$
in relation to faces of $A$.

######  Lemma 3.16.

Let $J\in\mathbb{N}$ and $\varepsilon>0$. Then the following hold:

  * (i)

For each $\varphi\in\Phi(A)$ we have
$\kappa(T(\varphi,2Jr),r)=O(r^{-D(\varphi)})$ as $r\downarrow 0$. Moreover we
have $\kappa(A\setminus\cup_{\varphi\in\Phi(A)}T(\varphi,2Jr),r)=O(r^{-d})$ as
$r\downarrow 0$.

  * (ii)

For all small $r>0$ and any $G\subset A$ with ${\rm diam}(G)\leq Jr$, if it
intersects $T(\varphi,2Jr)$ for some $\varphi\in\Phi^{*}(A)$, then

$\displaystyle\mu(G_{r}\setminus
G)\geq(1-\varepsilon)f_{\varphi}\rho_{\varphi}r^{d}.$ (3.20)

###### Proof.

Item (i) follows by the definition of $T(\varphi,r)$. Indeed, $\varphi$ is
contained in a bounded region within a $D(\varphi)$-dimensional affine space,
and therefore can be covered by $O(r^{-D(\varphi)})$ balls of radius $r$. If
we then take balls of radius $r(1+2JK_{d-D(\varphi)})$ with the same centres,
they will cover $T(\varphi,2Jr)$, and one can then cover each of the larger
balls with a fixed number of balls of radius $r$.

For (ii), let $G\subset A$ with ${\rm diam}(G)\leq Jr$. Suppose first that
$G\cap T(\varphi,2Jr)\neq\varnothing$ for some $\varphi\in\Phi(A)$. Let
$x_{0}\in G\cap T(\varphi,2Jr)$. Then $G_{r}\subset B(x_{0},2Jr)$. By Lemma
3.15, we see that $B(x_{0},2Jr)$ does not intersect any
$\varphi^{\prime}\in\Phi(A)$ with
$\varphi\setminus\varphi^{\prime}\neq\varnothing$. It follows that

$\displaystyle B(x_{0},2Jr)\cap
A=B(x_{0},2Jr)\cap(z_{0}+\mathcal{K}_{\varphi})$ (3.21)

where $\mathcal{K}_{\varphi}$ is the cone determined by $\varphi$ and $z_{0}$
is the point of $\varphi$ closest to $x_{0}$.

Set $D(x,r):=B(x,r)\cap(x+\mathcal{K}_{\varphi})$. We claim that for any $x\in
G$, we have $D(x,r)\subset A$. Indeed, given $y\in D(x,r)$, we can write
$y=z_{0}+(x-z_{0})+(y-x)=:z_{0}+\theta_{1}+\theta_{2}$. Here
$\theta_{1},\theta_{2}\in\mathcal{K}_{\varphi}$. By convexity and scale
invariance of $\mathcal{K}_{\varphi}$, we have
$\theta_{1}+\theta_{2}\in\mathcal{K}_{\varphi}$ so $y\in
z_{0}+\mathcal{K}_{\varphi}$. Also $\|y-x_{0}\|\leq\|y-x\|+\|x-x_{0}\|\leq
2Jr$, and hence $y\in A$ by (3.21), as claimed.

It follows that (with $\oplus$ denoting Minkowski addition)

$\displaystyle\mu(G_{r}\setminus G)\geq\mu((G\oplus D(o,r))\setminus
G)\geq{\rm Vol}((G\oplus D(o,r))\setminus G)\inf_{x\in G\oplus D(o,r)}f(x).$

By the Brunn-Minkowski inequality [5, Section 5.3], we have ${\rm Vol}(G\oplus
D(o,r))\geq{\rm Vol}(G)+{\rm Vol}(D(o,r))={\rm Vol}(G)+\rho_{\varphi}r^{d}$.
The claim (3.20) follows by the continuity of $f$ on $\partial A$.

As for the case $\varphi=A$, suppose now that $G\cap T(A,2Jr)\neq\varnothing.$
Taking $x\in G\cap T(A,2Jr)$ we have $\,{\rm dist}(x,\partial A)\geq 2Jr$, and
hence $\,{\rm dist}(G,\partial A)\geq 2Jr-Jr=Jr$. Therefore $G_{r}\subset A$,
so by the Brunn-Minkowski inequality

$\mu(G_{r}\setminus G)\geq f_{0}{\rm Vol}((G\oplus B(o,r))\setminus G)\geq
f_{0}\theta_{d}r^{d}.$

In this case $f_{\varphi}=f_{0}$ and $\rho_{\varphi}=\theta_{d}$, and the
claim (3.20) follows in this case too, completing the proof of (ii). ∎

###### Proof of Theorem 2.5.

By (2.9), and Theorem 2.1, it suffices to prove the upper bound. We shall do
this by applying Proposition 3.6 in the situation of Theorem 2.5.

By Lemma 3.13, the restriction to $A$ of Lebesgue measure has the doubling
property, and conditions (O), (B), (T) and (G) are satisfied

To apply Proposition 3.6, we need to define (for each $K\in\mathbb{N}$ and
each $r\in(0,r_{0}(K))$) a finite partition $\\{T(j,K,r)\\}$. For this we take
the sets $T(\varphi,2Kr),\varphi\in\Phi^{*}(A)$. By Lemma 3.15, and the
definition of $T(A,r)$, for each $K\in\mathbb{N}$ there exists $r_{0}(K)>0$
such that for $r\in(0,r_{0}(K))$ the sets $T(\varphi,2Kr),$
$\varphi\in\Phi^{*}(A)$, do indeed partition $A$.

For each $\varphi\in\Phi^{*}(A)$, using Lemma 3.16-(i) we have the condition
(3.11) in Proposition 3.6, where the constant denoted $b_{j}$ there is equal
to $D(\varphi)$. Also, using Lemma 3.16-(ii) we have the condition (3.12) in
proposition 3.6, where the constant denoted $a_{j}$ there is equal to
$(1-\varepsilon)f_{\varphi}\rho_{\varphi}$.

Suppose $\beta<\infty$. By applying Proposition 3.6 in the manner described
above we see that for $\varepsilon>0$, we have

$\displaystyle\limsup_{n\to\infty}n(M_{n,k(n)})^{d}/\log
n\leq\max_{\varphi\in\Phi^{*}(A)}\Big{(}\frac{\hat{H}_{\beta}(D(\varphi)/d)}{(1-\varepsilon)f_{\varphi}\rho_{\varphi}}\Big{)},$

and the result follows. If $\beta=\infty$, using corresponding part of
Proposition 3.6 gives the result in this case too. ∎

## References

  * [1] Baccelli, F. and Błaszczyszyn, B. (2009). Stochastic geometry and wireless networks I: Theory. Foundations and Trends in Networking 4, 1–312.
  * [2] Bobrowski, O. (2022). Homological connectivity in random Čech complexes. Probab. Theory Relat. Fields 183, 715–788.
  * [3] Bobrowski, O. and Kahle, M. (2018) Topology of random geometric complexes: a survey. J. Appl. Comput. Topol. 1, 331–364.
  * [4] Last, G. and Penrose, M. (2018). Lectures on the Poisson Process. Cambridge University Press, Cambridge.
  * [5] Penrose, M. (2003) Random Geometric Graphs. Oxford University Press.
  * [6] Penrose, M. D. (1999). A strong law for the largest nearest-neighbour link between random points. J. London Math. Soc. (2) 60, 951–960.
  * [7] Penrose, M. D. (1999) A strong law for the longest edge of the minimal spanning tree. Ann. Probab. 27, 246–260.
  * [8] Penrose, M.D. (2022+) Random Euclidean coverage from within. arXiv:2101.06306, to appear in Probab. Theory Relat. Fields.


# On the Connectivity of the Vietoris-Rips Complex of a Hypercube Graph

Martin Bendersky  Department of Mathematics, Hunter College, CUNY, 695 Park
Avenue New York, NY 10065, U.S.A<EMAIL_ADDRESS>and  Jelena Grbić
School of Mathematical Sciences, University of Southampton, SO17 1BJ
Southampton, UK<EMAIL_ADDRESS>
###### Abstract.

We bring in the techniques of independence complexes and the notion of total
dominating sets of a graph to bear on the question of the connectivity of the
Vietoris-Rips complexes $VR(Q_{n};r)$ of an $n$-hypercube graph. We obtain a
lower bound for the connectivity of $VR(Q_{n};r)$ for an arbitrary
$n$-dimension hypercube and at all scale parameters $r$. The obtained bounds
disprove the conjecture of Shukla that $VR(Q_{n};r)$ is $r$-connected.

###### Key words and phrases:

Vietoris-Rips complexes, hypercubes, connectivity, total domination number of
a graph, independence complex

###### 1991 Mathematics Subject Classification:

Primary: 05E45, 55U10 Secondary: 05C10, 55N31

##  1\. Introduction

Let $Q_{n}$ be the set of vertices of the $n$-hypercube $\mathbb{I}^{n}$,
endowed with the shortest path metric. Thinking of the natural realisation of
the hypercube $\mathbb{I}^{n}$ as the Cartesian product space $[0,1]^{n}$, to
each vertex in $Q_{n}$, we associate a binary string of length $n$. This set
of $2^{n}$ binary strings, which we will also denote by $Q_{n}$, can be
equipped with the Hamming distance, that is, with the metrics which measures
the number of coordinates at which two binary strings of length $n$ differ.

Given the set $Q_{n}$ with the Hamming distance, $d_{H}$ and a rational number
$r\geq 0$, the Vietoris-Rips simplicial complex $VR(Q_{n};r)$ of the
$n$-hypercube graph at a scale parameter $r$ has for its vertex set $Q_{n}$
and $\sigma\subset Q_{n}$ as a simplex if the set diameter of $\sigma$ is at
most $r$. There has been recent increased interest in and progress towards
understanding the topology of the Vietoris-Rips complex $VR(Q_{n};r)$ of the
$n$-hypercube graph with the shortest path metric at scale parameter $r$ ([1],
[2], [5], [8]). Adamaskez and Adams [1] described the homotopy type of
$VR(Q_{n};2)$, Shukla [8] showed that the cohomology of $VR(Q_{n};3)$ is
concentrated in dimensions $4$ and $7$. The homotopy type of $VR(Q_{n};3)$ is
fully described in [5]. In [8] Shukla conjectured that for $n\geq r+2$, the
reduced homology $\widetilde{H}_{i}(VR(Q_{n};r);\mathbb{Z})\neq 0$ if and only
if $i=r+1$ or $r=2^{r}-1$ implying that $VR(Q_{n};r)$ is $r$-connected. Using
computer calculations, in [2] and [3], it was shown that $VR(Q_{6};4)$ is $6$
connected.

In this note we provide a method, using the total domination invariant of a
graph, to determine a lower bound for the connectivity of the Vietoris-Rips
complexes $VR(Q_{n};r)$ for an arbitrary $n$ and $r$. This approach provides
an infinite family of counterexamples to Shukla’s conjecture.

To this end we recall some basic notions and results related to total
dominating sets of a graph and indipendence complexes og a graph.

A graph $G=(V(G);E(G))$ consists of a nonempty set $V(G)$ of objects called
vertices together with a (possibly empty) set $E(G)$ of unordered pairs of
distinct vertices of $G$ called edges. We will only consider simple graphs,
those without directed edges or loops. An isolated vertex is a vertex that is
not an endpoint of any edge.

######  Definition 1.1 ([6]).

A total dominating set of a graph $G$ with no isolated vertices is a subset
$S$ of vertices of $G$ such that every vertex is connected by an edge to a
vertex in $S$.

It is worth emphasising that each vertex in $S$ also needs to be connected by
an edge to another vertex in $S$. For example, in the figure below the set
$S=\\{1,2\\}$ is not a total domination set since the point $\\{1\\}$ is not
connected to any point in $S$, while the set $\\{0,2\\}$ is a domination set
since every point in the vertex set of $G$ is connected to some point in $S$.

$0$$1$$2$

######  Definition 1.2.

The total domination number of G, denoted by $\gamma_{t}(G)$, is the minimal
cardinality amongst all total domination sets of $G$.

Our interest in $\gamma_{t}(G)$ is inspired by a theorem of Chudnovsky [4]
which relates the total domination number of a graph to the connectivity of
its independence complex.

Let $G=(V,E)$ be a graph. The complement of $G$, denoted by $G^{c}=(V,E^{c})$,
is the graph with the vertex set $V$ and $e$ is an edge of $G^{c}$, that is,
$e\in E^{c}$, if $e$ is not an edge in $G$. The independence complex of $G$,
denoted by $I(G)$, is the clique complex of $G^{c}$.

######  Theorem 1.3 ([4], [7]).

If $\gamma_{t}(G)>2k$, then $I(G)$ is $(k-1)$-connected.

For integers $n$ and $r$, and the set $Q_{n}$ of binary strings of length $n$
equipped with the Hamming distance $d_{H}$, we consider the graph $G_{n,r}$
whose vertex set is $Q_{n}$ and there is an edge in $G_{n,r}$ between two
vertices, $a,b\in Q_{n}$ if and only if $d_{H}(a,b)\leq r$. Notice that the
Vietoris-Rips complex $VR(Q_{n};r)$ is the click complex of $G_{n,r}$.

##  2\. Connectivity of Vietoris-Rips Complex

In this section we provide a lower bound for the connectivity of
$VR(Q_{n};r)$. The basis of the bound is a crude estimate for the total
domination number. Recall that the order of a graph is the number of vertices
of the graph, while the order of a vertex is the number of graph edges meeting
at that vertex. The maximal order of any vertex in a graph $G$ is denoted by
$\Delta(G)$.

######  Theorem 2.1 ([6]Theorem 2.11).

If $G$ is a graph of order $m$ with no isolated vertices, then

$\gamma_{t}(G)\geq\frac{m}{\Delta(G)}.$

The estimate in Theorem 2.1 is an immediate consequence of the definition of a
total domination set. Namely, every vertex in $G$ belongs to the open
neighborhood of at least one vertex in a minimal total domination set, that
is, $\gamma_{t}(G)\Delta(G)\geq m$. Equality occurs when each vertex is
connected to a point in the total dominating set by one edge. The figure below
is an example of such a graph.. This graph has total dominating set
$\\{S_{1},\cdots S_{\gamma_{t}(G)}\\}$. The order of each point in the
domination set is $\Delta(G)$. The graph is the union of isomorphic components
each of which has two points from the dominating set and $2\Delta(G)$
vertices. The estimate in Theorem 2.1 becomes a strict inequality if some of
the vertices at the termini of the vertical edges coincide.

$S_{1}$$\overset{\Delta(G)-1}{\mbox{
vertices}}$$\bullet$$\bullet$$\bullet$$\bullet$$S_{2}$$\bullet$$\bullet$$\bullet$$\bullet$$S_{3}$$\bullet$$\bullet$$\bullet$$\bullet$$S_{4}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

As $VR(Q_{n};r)$ is the independence complex of $G_{n,r}^{c}$, we will apply
Theorems 1.3 and 2.1 to the graph $G_{n,r}^{c}$.

######  Lemma 2.2.

The order of any vertex of $G_{n,r}^{c}$ is

$\sum_{i=r+1}^{n}\binom{n}{i}.$

###### Proof.

For any vertex $v\in Q_{n}$, there is are $\binom{n}{i}$ edges from $v$ to
vertices $w$ such that $d_{H}(v,w)=i$. Thus there are
$\sum_{i=r+1}^{n}\binom{n}{i}$ edges from any vertex $v$ to vertices with
Hamming distance $r+1$ or greater. ∎

######  Theorem 2.3.

Let $\alpha_{n,r}=\dfrac{2^{n-1}}{\sum_{i=r+1}^{n}\binom{n}{i}}$. Then
$VR(Q_{n};r)$ is $(k-1)$-connected, where

$k=\begin{cases}\Big{[}\alpha_{n,r}\Big{]}&\mbox{ if }\alpha_{n,r}\mbox{ is
not an integer }\\\ \alpha_{n,r}-1&\mbox{ otherwise.}\end{cases}$

###### Proof.

By Theorem 2.1 and Lemma 2.2,

$\gamma_{t}(G_{n,r}^{c})\geq 2\alpha_{n,r}>2k.$

By Theorem 1.3, $VR(Q_{n};r)=I(G^{c}_{n,r})$ is $(k-1)$-connected. ∎

Theorem 2.3 is a coarse bound. For example, for a fixed $r$, the lower bound
on the connectivity approaches $0$ as $n\to\infty$. In spite this, this
estimate gives an infinite family of counterexamples for which the
connectivity of $VR(Q_{n};r)$ given by Theorem 2.3 is greater than $r+1$.
Moreover, this estimate suggests that the connectivity of $VR(Q_{n};r)$ does
not grow linearly with respect to either $n$ or $r$ and illustrates that for
some $n$ and $r$, $VR(Q_{n};r)$ is highly connected.

We least a few examples.

$n$ | $r$ | connectivity
---|---|---
7 | 5 | 6
8 | 6 | 13
9 | 7 | 24
12 | 10 | 156
18 | 15 | 761
18 | 16 | 6897
20 | 16 | 387
20 | 18 | 24964

We remark that the connectivity of Theorem 2.3 does not violate the non
triviality of $H_{2^{r}-1}(VR(Q_{n};r);\mathbb{Z})$, [2].

The large connectivity we obtain is based on a simple estimate of the total
domination. We expect that the total domination of the graphs $G^{c}_{n,r}$
are significantly larger than provided by Theorem 2.1. For example, Feng’s
computer calculation, [2], shows that $VR(Q_{6},4)$ is $6$-connected and
$H_{7}(VR(Q_{n};r);\mathbb{Z})\neq 0$. This implies that
$\gamma_{t}(G^{c}_{6,4})\leq 16.$ By Theorem 2.3, we can only conclude that
the total domination of $G^{c}_{6,4}$ is greater than equal to 8 and thus
$VR(Q_{6},4)$ is at least $3$-connected. It would be interesting to know how
close the total domination number of $G^{c}_{6,4}$ is to $16$.

In general, describing total domination sets for an arbitrary graph is a
difficult problem. Hypercube graphs are rich in symmetry and one hopes that
the geometry of hypercubes and their duals, cross-polytopes could shed light
on a particularly nice structures of their total domination sets. We do have
the following connection between certain non-trivial homology classes in
$H_{*}(VR(Q_{n};r);\mathbb{Z})$ and total domination sets.

######  Proposition 2.4.

Suppose a non-trivial homology class $a\in H_{m-1}(VR(Q_{n};r);\mathbb{Z})$ is
represented by $\alpha$, the boundary of a cross-polytope on $2m$ vertices.
Then the set of vertices of $\alpha$ is a total domination set of
$G_{n,r}^{c}$

###### Proof.

Suppose the vertices of $\alpha$ are
$\mathcal{C}=\\{v_{1},w_{1},v_{2},w_{2},\ldots,v_{m},w_{m}\\}$, where
$\\{v_{i},w_{i}\\}$ is not an edge in $VR(Q_{n};r)$ and there is an edge
connecting all other vertices in $\mathcal{C}$. The vertices of $\alpha$
represent a matching edge set in $G_{n,r}^{c}$ (that is, a set of edges
without common vertices). If $\mathcal{C}$ was not a total domination set,
then there is a vertex $u$ which is not connected to any vertex of
$\mathcal{C}$ in $G_{n,r}^{c}$. This means that $u*\alpha$, the cone on
$\alpha$, is a subcomplex of $VR(Q_{n};r)$ which contradicts the non-
triviality of $\alpha$. ∎

## References

  * [1] M. Adamaszek, H. Adams, On Vietoris-Rips complexes of Hypercube Graphs, J. Appl. Comput. Topol., 6(2):177–192, 2022.
  * [2] H. Adams, Ẑ. Virk, Lower Bounds on the Homology of the Vietoris-Rips Complexes of Hypercube Graphs. arXiv2309.06222v1.
  * [3] Y. Berman, Private communication.
  * [4] M. Chudnovsky, Systems of disjoint representatives, 2000.
  * [5] ] Z. Feng. Homotopy types of Vietoris-Rips Complexes of Hypercube Graphs, Arxiv: 2305.0708V1.
  * [6] M.A. Henning, A. Yeo Total Domination of Graphs Springer Monographs in Mathematics. Springer, New York, 2013
  * [7] R. Meshulam Domination Numbers and Homology, J. Combin. Theory Ser. A, 102(2):321-330, 2003.
  * [8] S. Shukla. On Vietoris-Rips complexes (with scale 3) of Hypercube Graphs, SIAM J. Discrete Math., 37(3):1472-1495,, 2023.