# Thick embeddings of graphs into symmetric spaces via coarse geometry

Benjamin Barrett and David Hume
with an appendix by Larry Guth and Elia Portnoy

###### Abstract

We prove estimates for the optimal volume of thick embeddings of finite graphs
into symmetric spaces, generalising results of Kolmogorov-Barzdin and Gromov-
Guth for embeddings into Euclidean spaces. We distinguish two very different
behaviours depending on the rank of the non-compact factor. For rank at least
2, we construct thick embeddings of $N$-vertex graphs with volume $CN\ln(1+N)$
and prove that this is optimal. For rank at most $1$ we prove lower bounds of
the form $cN^{a}$ for some (explicit) $a>1$ which depends on the dimension of
the Euclidean factor and the conformal dimension of the boundary of the non-
compact factor. The main tool is a coarse geometric analogue of a thick
embedding called a coarse wiring, with the key property that the minimal
volume of a thick embedding is comparable to the “minimal volume” of a coarse
wiring for symmetric spaces of dimension at least $3$. In the appendix it is
proved that for each $k\geq 3$ every bounded degree graph admits a coarse
wiring into $\mathbb{R}^{k}$ with volume at most $CN^{1+\frac{1}{k-1}}$. As a
corollary, the same upper bound holds for real hyperbolic space of dimension
$k+1$ and in both cases this result is optimal.

##  1 Introduction

The focus of this paper is on thick embeddings of graphs as considered by
Kolmogorov-Barzdin and Gromov-Guth [KB93, GG12]. By a graph, we mean a pair
$\Gamma=(V\Gamma,E\Gamma)$ where $V\Gamma$ is a set whose elements are called
vertices, and $E\Gamma$ is a set of unordered pairs of distinct elements of
$V\Gamma$. Elements of $E\Gamma$ are called edges. The topological realisation
of a graph is the topological space obtained from a disjoint union of unit
intervals indexed by $e\in E\Gamma$, whose end points we label using the two
elements contained in $e$. We then identify all endpoints which are labelled
by the same element of $V\Gamma$. We will use $\Gamma$ to refer to both the
graph and its topological realisation.

The idea behind thick embeddings of graphs is that they are the appropriate
embeddings to consider in situations where the graph models a physical object
(i.e. vertices and edges are “thick” and therefore need to remain a prescribed
distance apart). Two key examples are: a brain, where neurons are represented
by vertices and axons by edges; and an electronic network, where components
are vertices and wires are edges. We briefly summarise the relevant results
from [KB93, GG12] in the following two theorems.

######  Theorem 1.1.

Let $\Gamma$ be a finite graph with maximal degree $d$. For each $k\geq 3$,
there is a topological embedding $f_{k}:\Gamma\to\mathbb{R}^{k}$ and a
constant $C=C(d,k)$ with the following properties:

  1. $(i)$

$d_{\mathbb{R}^{k}}(f_{k}(x),f_{k}(y))\geq 1$ whenever $x,y$ are: two distinct
vertices; an edge and a vertex not contained in that edge; or two disjoint
edges.

  2. $(ii)$

$\textup{diam}(f_{3}):=\textup{diam}(\textup{im}(f_{3}))\leq C|\Gamma|^{1/2}$.

  3. $(iii)$

$\textup{diam}(f_{k})\leq C|\Gamma|^{1/(k-1)}\ln(1+|\Gamma|)^{4}$.

Let $Z$ be a metric space. We say a topological embedding $g:\Gamma\to Z$ is
$\varepsilon$-thick if it satisfies the inequality
$d_{Z}(g(x),g(y))\geq\varepsilon$ whenever $x,y$ are as in condition $(i)$.

######  Theorem 1.2.

Let $k\geq 3$. For every $\delta,\varepsilon>0$ and $d\in\mathbb{N}$ there is
a constant $c>0$ such that given any finite graph $\Gamma$ with maximal degree
$d$ and Cheeger constant (cf. Definition 5.2) $\geq\delta$ and any
$\varepsilon$-thick topological embedding $g:\Gamma\to\mathbb{R}^{k}$, we have
$\textup{diam}(g)\geq c^{-1}|\Gamma|^{1/(k-1)}-c$.

When $Z$ admits a measure, we define the volume $\textup{vol}(g)$ of an
$\varepsilon$-thick topological embedding $g:\Gamma\to Z$ to be the measure of
the $1$-neighbourhood of its image111The choice of $1$-neighbourhood is
arbitrary for measure spaces with controlled growth (cf. Definition 4.1)
replacing this by another positive real changes volume by at most some uniform
multiplicative constant.. From Theorem 1.1 we get obvious upper bounds on the
volume of $1$-thick embeddings into $\mathbb{R}^{k}$. Namely,
$\textup{vol}(f_{3})\leq C^{\prime}|\Gamma|^{3/2}$ and
$\textup{vol}(f_{k})\leq C^{\prime}|\Gamma|^{k/(k-1)}\ln(1+|\Gamma|)^{4k}$.

In the main paper, we prove versions of Theorems 1.1 and 1.2 for thick
embeddings into symmetric spaces. The goal of the appendix is to provide sharp
upper bounds for thick embeddings into Euclidean spaces. The main result there
is a complete proof of an optimal version of Theorem 1.1(iii). Such an
argument had previously been sketched by Guth.

######  Theorem 1.3.

Let $d,k\in\mathbb{N}$ with $k\geq 3$. There is a constant $C=C(d,k)$ such
that for every finite graph $\Gamma$ with maximal degree $d$, there is a
$1$-thick topological embedding $f_{k}:\Gamma\to\mathbb{R}^{k}$ which
satisfies

$\textup{diam}(f_{k})\leq
C|\Gamma|^{1/(k-1)}\quad\textrm{and}\quad\textup{vol}(f_{k})\leq
C|\Gamma|^{1+1/(k-1)}.$

###  1.1 Thick embeddings into symmetric spaces

Our main results are analogues of Theorems 1.1 and 1.2 for more general simply
connected Riemannian symmetric spaces. Constructing graph embeddings into a
range of symmetric spaces has applications for machine learning (see [Lo21]
and references therein). In what follows we will assume that our symmetric
spaces are simply connected and Riemannian. The rank of a symmetric space is
the maximal dimension of an isometrically embedded Euclidean subspace. We
recall that each symmetric space $X$ decomposes as a direct product of
symmetric spaces $K\times\mathbb{R}^{d}\times N$ where $K$ is compact and $N$
has no non-trivial compact or Euclidean factor. In the literature, $N$ is
often referred to as the non-compact factor. Our results show a striking
contrast between the situation where the non-compact factor has rank at least
$2$ and the situation where it has rank at most $1$.

We begin with the case where the rank of $N$ is at least $2$, where we provide
matching upper and lower bounds.

######  Theorem 1.4.

Let $X$ be a symmetric space whose non-compact factor has rank $\geq 2$ and
let $d\in\mathbb{N}$. There are constants $\varepsilon,C>0$ which depend on
$X$ and $d$ such that for any finite graph $\Gamma$ with maximal degree at
most $d$, there is an $\varepsilon$-thick topological embedding of $\Gamma$
into $X$ with diameter $\leq C\ln(1+|\Gamma|)$ and volume $\leq
C|\Gamma|\ln(1+|\Gamma|)$.

######  Theorem 1.5.

Let $X$ be a symmetric space whose non-compact factor has rank $\geq 2$ and
let $d\in\mathbb{N}$. For any $d,\varepsilon,\delta>0$ there is a constant
$c=c(d,\varepsilon,\delta)>0$ with the following property. For any finite
graph $\Gamma$ with maximal degree $d$ and Cheeger constant
$h(\Gamma)\geq\delta$ every $\varepsilon$-thick222Unlike topological
embeddings into Euclidean space, there does not seem to be an obvious way to
relate the volumes of optimal topological embeddings with different thickness
parameters. topological embedding $g:\Gamma\to X$ satisfies
$\textup{vol}(g)\geq c|\Gamma|\ln(1+|\Gamma|)$.

Now we turn to the case where the rank of $N$ is at most $1$. When $N$ is a
real hyperbolic space, we also provide upper and lower bounds which match
except in the case of the hyperbolic plane where there is a sublogarithmic
gap.

######  Theorem 1.6.

Let $X=\mathbb{R}^{r}\times\mathbb{H}_{\mathbb{R}}^{q}$ where $q+r\geq 3$. Let
$d\in\mathbb{N}$. There is a constant $C=C(X,d)$ such that for any finite
graph $\Gamma$ with maximal degree at most $d$ there is a $1$-thick
topological embedding of $\Gamma$ into $X$ with volume

$\leq C|\Gamma|^{1+1/(q+r-2)}.$

For $q+r\geq 4$ this follows by composing the topological embedding from
Theorem 1.3 with a suitable coarse embedding
$\mathbb{R}^{r}\times\mathbb{R}^{q-1}\to\mathbb{R}^{r}\times\mathbb{H}_{\mathbb{R}}^{q}$
where $\mathbb{R}^{q-1}$ embeds as a horosphere in
$\mathbb{H}_{\mathbb{R}}^{q}$. The case $q+r=3$ is new and is treated
separately (cf. Theorem 1.8).

The lower bound we prove holds more generally. The rank one symmetric spaces
of non-compact type are real, complex and quaternionic hyperbolic spaces of
dimension at least $2$ ($\mathbb{H}^{q}_{\mathbb{R}}$,
$\mathbb{H}^{q}_{\mathbb{C}}$ and $\mathbb{H}^{q}_{\mathbb{H}}$ respectively)
and the Cayley plane $\mathbb{H}^{2}_{\mathbb{O}}$. These spaces are all
Gromov-hyperbolic, and as such they have a naturally defined boundary. The
conformal dimension of the boundary of $\mathbb{H}^{q}_{F}$ is
$Q=(q+1)\dim_{\mathbb{R}}(F)-2$ [Pan89]. We will not define conformal
dimension in this paper as we do not require it.

######  Theorem 1.7.

Let $X=K\times\mathbb{R}^{r}\times\mathbb{H}^{q}_{F}$, where $K$ is compact
and $q\dim_{\mathbb{R}}(F)+r\geq 3$. Let $d\in\mathbb{N}$. Let $Q$ be the
conformal dimension of the boundary of $\mathbb{H}^{q}_{F}$. For any
$d,\varepsilon,\delta>0$ there is a constant $c=c(d,\varepsilon,\delta)>0$
with the following property. For any graph $\Gamma$ with maximal degree $d$
and Cheeger constant $h(\Gamma)\geq\delta$ every $\varepsilon$-thick
topological embedding $g:\Gamma\to X$ has volume

$\geq\left\\{\begin{array}[]{lll}c|\Gamma|^{1+1/r}\ln(1+|\Gamma|)^{-1/r}&\textup{if}&Q=1,\\\
c|\Gamma|^{1+1/(Q+r-1)}&\textup{if}&Q\geq 2.\end{array}\right.$

This “gap” between the rank at most $1$ and the higher rank case is similar in
flavour to the gap in the separation profiles of symmetric spaces found in
[HMT22]. This is no coincidence. The lower bounds on the volumes of
topological embeddings found in Theorems 1.5 and 1.7 are inverse functions of
the separation profiles of the symmetric spaces333By the separation profile of
a symmetric space we mean either the $1$-Poincaré profile of the symmetric
space as defined in [HMT20] or equivalently, the separation profile as defined
in [BST12] of any graph quasi-isometric to the symmetric space., and our
approach to prove both of these theorems utilises separation profiles in a
crucial way. In order to use separation profiles, we will reformulate the
above theorems in terms of carefully chosen continuous maps (called coarse
wirings) between bounded degree graphs.

We present one further result in this section, which provides upper bounds for
thick embeddings into $\mathbb{H}^{3}_{\mathbb{R}}$ and
$\mathbb{H}^{2}_{\mathbb{R}}\times\mathbb{R}$. The first is asymptotically
optimal and the second within a sublogarithmic error (with the lower bounds
provided by 1.7) but which do not depend on the degree of the graph.

######  Theorem 1.8.

There are $1$-thick topological embeddings of $K_{M}$ (the complete graph on
$M$ vertices) into $\mathbb{H}^{3}_{\mathbb{R}}$ with diameter $\leq
C\ln(1+M)$ and volume $\leq CM^{2}$, and into
$\mathbb{H}^{2}_{\mathbb{R}}\times\mathbb{R}$ with diameter $\leq CM$ and
volume $\leq CM^{2}$, for some $C$ which does not depend on $M$.

###  1.2 Coarse $k$-wirings

######  Definition 1.9.

Let $\Gamma,\Gamma^{\prime}$ be graphs. A wiring of $\Gamma$ into
$\Gamma^{\prime}$ is a continuous map $f:\Gamma\to\Gamma^{\prime}$ such that
the image of each vertex is a vertex and the image of each edge is a walk in
$\Gamma^{\prime}$.

A wiring $f$ is a coarse $k$-wiring if

  1. 1.

the preimage of each vertex in $\Gamma^{\prime}$ contains at most $k$ vertices
in $\Gamma$; and

  2. 2.

each edge $e$ in $\Gamma^{\prime}$ is contained in the image of at most $k$
edges in $\Gamma$.

We consider the image of a wiring $\textup{im}(f)$ to be the subgraph of
$\Gamma^{\prime}$ consisting of all vertices in $f(V\Gamma)$ and all the walks
which are the images of edges under $f$. The diameter of a wiring
$\textup{diam}(f)$ is the diameter of its image (measured with respect to the
shortest path metric in $\Gamma^{\prime}$), the volume of a wiring
$\textup{vol}(f)$ is the number of vertices in its image.

Under mild hypotheses on the target space (cf. Definition 4.1), we can convert
a thick topological embedding into a coarse $k$-wiring.

######  Proposition 1.10.

Let $M$ be a Riemannian manifold with controlled growth and let $Y$ be a graph
quasi-isometric to $M$, let $d\in\mathbb{N}$ and let $T>0$. There exist
constants $C$ and $k$ such for every finite graph $\Gamma$ with maximal degree
$d$ the following holds:

If there is a $T$-thick topological embedding $\Gamma\to M$ with diameter $D$
and volume $V$ then there is a coarse $k$-wiring of $\Gamma$ into $Y$ with
diameter at most $CD$ and volume at most $CV$.

With stronger hypotheses we are able to convert coarse $k$-wirings into thick
topological embeddings.

######  Theorem 1.11.

Let $M$ be a compact Riemannian manifold of dimension $n\geq 3$, let $Y$ be a
graph quasi-isometric to the universal cover $\widetilde{M}$ of $M$ and let
$k,d\in\mathbb{N}$. There exist constants $C$ and $\varepsilon>0$ such that
the following holds:

If there is a coarse $k$-wiring of a finite graph $\Gamma$ with maximal degree
$d$ into $Y$ with diameter $D$ and volume $V$ then there is a
$\varepsilon$-thick embedding of $\Gamma$ into $\widetilde{M}$ with diameter
at most $CD$ and volume at most $CV$.

All of the symmetric spaces we consider are universal covers of compact
Riemannian manifolds. The reason for working with universal covers of compact
manifolds is to use compactness to deduce that finite families of curves which
are disjoint are at least a uniform positive distance apart. We then use deck
transformations of the universal cover to translate these curves and preserve
this uniform disjointness.

Using Proposition 1.10 and Theorem 1.11 we can prove Theorems 1.4, 1.5, 1.6
and 1.7 purely in terms of coarse wirings. We introduce wiring profiles in
order to discuss coarse wirings between infinite graphs.

######  Definition 1.12.

Let $\Gamma$ be a finite graph and let $Y$ be a graph. We denote by
$\textup{wir}^{k}(\Gamma\to Y)$ the minimal volume of a coarse $k$-wiring of
$\Gamma$ into $Y$. If no such coarse $k$-wiring exists, we say
$\textup{wir}^{k}(\Gamma\to Y)=+\infty$.

Let $X$ and $Y$ be graphs. The $k$-wiring profile of $X$ into $Y$ is the
function

$\textup{wir}^{k}_{X\to Y}(n)=\max\left\\{\textup{wir}^{k}(\Gamma\to Y)\
\left|\ \Gamma\leq X,\ |\Gamma|\leq n\right.\right\\}.$

A simple example of a situation where $\textup{wir}^{k}(\Gamma\to Y)=+\infty$
is when $\Gamma$ has a vertex whose degree is greater than $k^{2}$ times the
maximal degree of $Y$.

The reason for working with wiring profiles is that they have three very
useful properties. Firstly, wirings between graphs can be composed and there
is a natural inequality which controls the volume of the composition.

######  Proposition 1.13.

Let $X,Y,Z$ be graphs. Suppose $\textup{wir}^{k}_{X\to Y}$ and
$\textup{wir}^{l}_{Y\to Z}$ take finite values. Then

$\displaystyle\textup{wir}^{kl}_{X\to Z}(n)\leq\textup{wir}^{l}_{Y\to
Z}\left(\textup{wir}^{k}_{X\to Y}(n)\right).$

Secondly, for bounded degree graphs, the wiring profile of $X$ into $Y$ grows
linearly whenever there is a regular map from $X$ to $Y$.

######  Definition 1.14.

Let $X,Y$ be metric spaces and let $\kappa>0$. A map $r:X\to Y$ is
$\kappa$-regular if

  1. 1.

$d_{Y}(r(x),r(x^{\prime}))\leq\kappa(1+d_{X}(x,x^{\prime}))$, and

  2. 2.

the preimage of every ball of radius $1$ in $Y$ is contained in a union of at
most $\kappa$ balls of radius $1$ in $X$.

Quasi-isometric and coarse embeddings between bounded degree graphs are
examples of regular maps.

######  Proposition 1.15.

Let $X$ and $Y$ be graphs with maximal degree $\Delta>0$ and let $r:X\to Y$ be
a $\kappa$-regular map. Then there exists $k=k(\kappa,\Delta)$ such that

$\displaystyle\textup{wir}^{k}_{X\to
Y}(n)\leq\left(\kappa+\frac{1}{2}\right)\Delta n.$

These two propositions naturally combine to show that wiring profiles are
well-behaved with respect to regular maps.

######  Corollary 1.16.

Let $X$, $X^{\prime}$, $Y$ and $Y^{\prime}$ be graphs with maximal degree
$\Delta$ and let $r_{X}:X^{\prime}\to X$ and $r_{Y}:Y\to Y^{\prime}$ be
$\kappa$-regular maps. Then for every $k$ such that $\textup{wir}^{k}_{X\to
Y}$ takes finite values there is some $l$ such that

$\displaystyle\textup{wir}^{l}_{X\to Y^{\prime}}(n)$ $\displaystyle\leq$
$\displaystyle\left(\kappa+\frac{1}{2}\right)\Delta\dot{\textup{wir}}^{k}_{X\to
Y}(n).$ (1) $\displaystyle\textup{wir}^{l}_{X^{\prime}\to Y^{\prime}}(n)$
$\displaystyle\leq$
$\displaystyle\left(\kappa+\frac{1}{2}\right)\Delta\dot{\textup{wir}}^{k}_{X\to
Y}\left(\left(\kappa+\frac{1}{2}\right)\Delta n\right).$ (2)

The third benefit of coarse wirings is that we can find lower bounds on the
wiring profile of two bounded degree graphs in terms of their separation
profiles: a measure of the combinatorial connectivity of their finite
subgraphs introduced in [BST12]. We introduce the following notation from that
paper. Given two functions $f,g:\mathbb{N}\to\mathbb{R}$, we write $f\lesssim
g$ if there is a constant $C$ such that $f(n)\leq Cg(Cn)+C$ holds for all $n$.
We write $f\simeq g$ when $f\lesssim g$ and $g\lesssim f$.

######  Theorem 1.17.

Let $X$ and $Y$ be graphs of bounded degree where $\textup{sep}_{X}\gtrsim
n^{r}\ln(n)^{s}$ and $\textup{sep}_{Y}\simeq n^{p}\ln(n)^{q}$. Then, for any
$k$,

$wir^{k}_{X\to
Y}(n)\gtrsim\left\\{\begin{array}[]{lll}n^{r/p}\ln(n)^{(s-q)/p}&\textup{if}&p>0,\\\
\exp(n^{r/(q+1)}\ln(n)^{s/(q+1)})&\textup{if}&p=0.\end{array}\right.$

The separation profiles of (graphs quasi-isometric to) symmetric spaces have
all been calculated [BST12, HMT20, HMT22] and are all of the form
$n^{p}\ln(n)^{q}$. Combining these calculations with Theorem 1.17 and Theorem
1.11 is sufficient to prove Theorems 1.5 and 1.7.

The coarse geometric approach also has great benefits when computing upper
bounds. For instance, we can deduce the upper bound on volumes of thick
embeddings in Theorem 1.4 from the following theorem.

######  Theorem 1.18.

There is a Cayley graph $Y$ of the lamplighter group
$\mathbb{Z}_{2}\wr\mathbb{Z}$ with the following property. For each
$d\in\mathbb{N}$ there is some $C=C(d)$ such that for any $N$-vertex graph
$\Gamma$ with maximal degree $d$, we have

$\textup{wir}^{2d}(\Gamma\to Y)\leq CN\ln(1+N).$

The deduction works as follows. The graph $Y$ is quasi-isometric to the
Diestel-Leader graph $\textup{DL}(2,2)$ [Woe05]. Next, $\textup{DL}(2,2)$
quasi-isometrically embeds into any symmetric space $M$ whose non-compact
factor has rank $\geq 2$ [HMT22, Proposition 2.8 and Theorem 3.1]. Choose a
graph $X$ which is quasi-isometric to $M$. By Corollary 1.16, there are
constants $l,C^{\prime}$ which depend on $Y$ and $d$ but not $N$ such that
$\textup{wir}^{l}(\Gamma\to X)\leq C^{\prime}N\ln(1+N)$. Theorem 1.4 then
follows from Theorem 1.11 and Theorem 1.18.

It is important to stress that the analogy between thick embeddings and coarse
wirings only holds when there is a bound on the degree of the graphs and the
manifold dimension of the symmetric space is at least $3$. This is evidenced
by Theorem 1.8 which holds independent of the degree of the graph, where no
such result for coarse wirings is possible. On the other hand, in section 6.1,
we will consider coarse wirings into $\mathbb{R}^{2}$ and
$\mathbb{H}_{\mathbb{R}}^{2}$ where only planar graphs admit topological
embeddings.

######  Theorem 1.19.

Let $d\geq 3$ and let $X(d)$ be the disjoint union of all finite graphs with
maximal degree $\leq d$. Let $Y$ and $Z$ be graphs which are quasi-isometric
to $\mathbb{R}^{2}$ and $\mathbb{H}_{\mathbb{R}}^{2}$ respectively. For all
sufficiently large $k$, we have

$\textup{wir}^{k}_{X(d)\to Y}(n)\simeq
n^{2}\quad\textup{and}\quad\exp(n^{1/2})\lesssim\textup{wir}^{k}_{X(d)\to
Z}(n)\lesssim\exp(n).$

The lower bounds both follow from Theorem 1.17, since
$\textup{sep}_{X(d)}(n)\simeq n$ as it contains a family of expanders of at
most exponentially growing size [Hum17]. For the upper bound we will make
direct constructions. We believe that it is possible to improve the bound in
the $p=0$ case of Theorem 1.17 to $\exp(n^{r/q}\ln(n)^{s/q})$. This would have
the consequence that $\textup{wir}^{k}_{X(d)\to Z}(n)\simeq\exp(n)$ in Theorem
1.19.

One very natural question to consider is the dependence of
$\textup{wir}^{k}_{X\to Y}(n)$ (up to $\simeq$) on the parameter $k$. It is
clear that for $k\leq l$, $\textup{wir}^{k}_{X\to
Y}(n)\geq\textup{wir}^{l}_{X\to Y}(n)$ for any pair of bounded degree graphs
$X$ and $Y$, but the converse fails spectacularly [Ra23].

### Acknowledgements

The authors would like to thank Itai Benjamini for suggesting the relationship
between wiring problems and the separation profile which provided the initial
spark for this work, Romain Tessera for suggestions which improved the
exposition, and an anonymous referee for many suggestions and observations
which greatly improved the readability of the paper.

##  2 Thick topological embeddings into products of real hyperbolic and
Euclidean spaces

Our goal in this section is to prove Theorems 1.6 and 1.8, which we do by
directly constructing thick topological embeddings. We start with the proof of
Theorem 1.6 in the case $q+r\geq 4$. We will use the upper halfspace model of
real hyperbolic space
$\mathbb{H}^{q}_{\mathbb{R}}=\left\\{(x_{1},\ldots,x_{q-1};x_{q})\ \left|\
x_{i}\in\mathbb{R},\ x_{q}>0\right.\right\\}$ equipped with the metric

$d_{\mathbb{H}^{q}_{\mathbb{R}}}((x_{1},\ldots,x_{q-1};x_{q}),(y_{1},\ldots,x_{y-1};y_{q}))=\cosh^{-1}\left(1+\frac{\sum_{i=1}^{q}(x_{i}-y_{i})^{2}}{2x_{q}y_{q}}\right).$

###### Proof.

Define $h_{0}=(2(\cosh(1)-1))^{-1/2}$. Consider the map

$\phi_{q,r}:\mathbb{R}^{r}\times\mathbb{R}^{q-1}\to\mathbb{R}^{r}\times\mathbb{H}^{q}_{\mathbb{R}}\quad\textup{given
by}\quad\phi_{q,r}(\underline{x},\underline{y})=(\underline{x},(\underline{y};h_{0})).$

Claim:
$d(\phi_{q,r}(\underline{x},\underline{y}),\phi_{q,r}(\underline{x^{\prime}},\underline{y^{\prime}}))\geq
1$ whenever $\|\underline{x}-\underline{x^{\prime}}\|_{2}\geq 1$ or
$\|\underline{y}-\underline{y^{\prime}}\|_{2}\geq 1$.

###### Proof of Claim.

If $\|\underline{x}-\underline{x^{\prime}}\|_{2}\geq 1$ then this is obvious.
If $\|\underline{y}-\underline{y^{\prime}}\|_{2}\geq 1$, then

$\displaystyle
d(\phi_{q,r}(\underline{x},\underline{y}),\phi_{q,r}(\underline{x^{\prime}},\underline{y^{\prime}}))$
$\displaystyle\geq$ $\displaystyle
d_{\mathbb{H}^{q}_{\mathbb{R}}}((\underline{y};h_{0}),(\underline{y^{\prime}};h_{0}))$
$\displaystyle=$
$\displaystyle\cosh^{-1}\left(1+\frac{\|\underline{y}-\underline{y^{\prime}}\|_{2}^{2}}{2h_{0}^{2}}\right)$
$\displaystyle\geq$
$\displaystyle\cosh^{-1}\left(1+\frac{1}{2h_{0}^{2}}\right)$ $\displaystyle=$
$\displaystyle\cosh^{-1}(1+(\cosh(1)-1))=1.$

∎

Let $\Gamma$ be a finite graph with maximal degree $d$ and let
$\psi=\sqrt{2}.f_{q+r-1}$ where $f_{q+r-1}$ is the $1$-thick topological
embedding of $\Gamma$ into $\mathbb{R}^{q+r-1}$ defined in Theorem 1.3. Let us
first show that $\psi\circ\phi$ is a $1$-thick embedding of $\Gamma$ into
$\mathbb{R}^{r}\times\mathbb{H}^{q}_{\mathbb{R}}$.

The topological embedding $\psi$ is $\sqrt{2}$-thick. If
$\|(\underline{x},\underline{y})-(\underline{x^{\prime}},\underline{y^{\prime}})\|_{2}\geq\sqrt{2}$,
then either $\|\underline{x}-\underline{x^{\prime}}\|_{2}\geq 1$ or
$\|\underline{y}-\underline{y^{\prime}}\|_{2}\geq 1$. Applying the claim, we
see that $\psi\circ\phi$ is $1$-thick.

Finally we bound $\textup{vol}(\psi\circ\phi)$. Firstly note that if
$\|(\underline{x},\underline{y})-(\underline{x^{\prime}},\underline{y^{\prime}})\|_{2}\leq
1$, then

$\displaystyle
d(\phi_{q,r}(\underline{x},\underline{y}),\phi_{q,r}(\underline{x^{\prime}},\underline{y^{\prime}}))$
$\displaystyle=$
$\displaystyle\left(\|\underline{x}-\underline{x^{\prime}}\|_{2}+d_{\mathbb{H}^{q}_{\mathbb{R}}}((\underline{y};h_{0}),(\underline{y^{\prime}};h_{0}))\right)^{1/2}$
$\displaystyle\leq$
$\displaystyle\left(1+\cosh^{-1}\left(1+\frac{\|\underline{y}-\underline{y^{\prime}}\|_{2}^{2}}{2h_{0}^{2}}\right)\right)^{1/2}$
$\displaystyle\leq$
$\displaystyle\left(1+\cosh^{-1}\left(1+\frac{1}{2h_{0}^{2}}\right)\right)^{1/2}=\sqrt{2}.$

Now let $Y$ be a $\frac{1}{2}$-separated $1$-net in $\textup{im}(\psi)$. It
follows from the above equation that $\phi(Y)$ is a $\sqrt{2}$-net in
$\textup{im}(\psi\circ\phi)$. Denote by $\alpha,\beta$ the volumes of the
balls of radius $\frac{1}{4}$ and $\sqrt{2}+1$ in $\mathbb{R}^{q+r-1}$ and
$\mathbb{R}^{r}\times\mathbb{H}^{q}_{\mathbb{R}}$ respectively. We have

$\textup{vol}(\psi\circ\phi)\leq\beta|Y|\quad\textup{and}\quad\alpha|Y|\leq\textup{vol}(\psi).$

Hence, using the volume bounds from Theorem 1.1 as explained after Theorem
1.2, there is a constant $C$ which depends on $q,r,d$ but not $\Gamma$ such
that

$\displaystyle\textup{vol}(\psi\circ\phi)$ $\displaystyle\leq$
$\displaystyle\beta|Y|$ $\displaystyle\leq$
$\displaystyle\beta\alpha^{-1}\textup{vol}(\psi)$ $\displaystyle\leq$
$\displaystyle\beta\alpha^{-1}C^{\prime}|\Gamma|^{1+1/(q+r-2)}\ln(1+\Gamma)^{4(q+r-1)}.$

∎

It remains to tackle the case $q+r=3$. We split the proof into two parts.
Firstly, we build a $1$-thick topological embedding of the complete graph on
$N$ vertices into $[0,N-1]^{2}\times[0,1]$. Then we use embeddings of
$\mathbb{R}^{2}$ into $\mathbb{H}_{\mathbb{R}}^{3}$ and
$\mathbb{H}^{2}_{\mathbb{R}}\times\mathbb{R}$ to construct $1$-thick
topological embeddings.

######  Lemma 2.1.

Let $K_{N}$ denote the complete graph on $N$ vertices. There is a $1$-thick
topological embedding
$f:K_{N}\to[0,N-1]^{2}\times[0,1]\subset(\mathbb{R}^{3},\|\cdot\|_{\infty})$.

###### Proof.

Enumerate the vertices of $K_{N}$ as $v_{0},\ldots,v_{N-1}$. Now we map
$v_{k}$ to $(k,k,0)$. We connect $(k,k,0)$ to $(l,l,0)$ using the following
piecewise linear path $P_{kl}$:

$(k,k,0)\to(l,k,0)\to(l,k,1)\to(l,l,1)\to(l,l,0).$ (3)

Let us verify that this embedding is $1$-thick. Any two distinct vertices
$v_{k}$ and $v_{l}$ are mapped at distance $|k-l|\geq 1$. Next, consider a
path $P_{kl}$ and the image $(i,i,0)$ of a vertex $v_{i}$ with $i\neq k,l$.
Since one of the first two coordinates of the path $P_{kl}$ is always either
$k$ or $l$, we have

$d_{\infty}(P_{kl},(i,i,0))\geq\min\\{|i-k|,|i-l|\\}\geq 1.$

Finally, consider paths $P_{ij},P_{kl}$. Let $(w,x,a)\in P_{ij}$ and
$(y,z,b)\in P_{kl}$ and suppose $d((w,x,a),(y,z,b))<1$.

If $a=1$, then $b>0$, so $w=j$ and $y=k$. Since
$d_{\infty}((w,x,a),(y,z,b))\geq|w-y|$, we have $|j-k|<1$. Thus $j=k$ and the
two paths come from edges which share a vertex.

If $a\in(0,1)$ then $w=x\in\\{i,j\\}$. Since
$d_{\infty}((w,x,a),(y,z,b))\geq\max\\{|w-y|,|x-z|\\}$ and at least one of
$y,z$ is equal to either $k$ or $l$, one of $i,j$ must be equal to one of
$k,l$. Thus the two paths come from edges which share a vertex.

If $a=0$ then either $x=i$ or $w=x=j$. Also $b<1$ so either $z=k$ or $y=z=l$.
If $x=i$ and $z=k$ then the argument from the $a=1$ case holds. Next, suppose
$w=x=j$. Since $z\in\\{k,l\\}$ and $d_{\infty}((w,x,a),(y,z,b))\geq|x-z|$, we
have $j=k$ or $j=l$. If $x=i$ and $y=z=l$, then $i=l$ following the same
reasoning. ∎

Next, we embed $[0,N-1]^{2}\times[0,1]$ into $\mathbb{H}_{\mathbb{R}}^{3}$. We
work in the upper-half space model of
$\mathbb{H}_{\mathbb{R}}^{3}=\left\\{(x,y;z)\ \left|\ z>0\right.\right\\}$.

Consider the map
$\phi:\mathbb{R}^{2}\times[0,1]\to\mathbb{H}_{\mathbb{R}}^{3}$ defined by

$(x,y,a)\mapsto(x,y;h_{0}e^{-a}).$

######  Lemma 2.2.

Let $f:K_{N}\to[0,N-1]^{2}\times[0,1]$ be the $1$-thick topological embedding
from Lemma 2.1. The map $g=\phi\circ f$ is a $1$-thick embedding of $K_{N}$
into $\mathbb{H}_{\mathbb{R}}^{3}$ with diameter $\leq 2\ln N+9$ and volume
$\leq 2039N^{2}$.

###### Proof.

We first prove that $g$ is $1$-thick. Since $f$ is $1$-thick with respect to
the $L^{\infty}$ metric, it suffices to prove that
$d_{\mathbb{H}_{\mathbb{R}}^{3}}(\phi(a_{1},b_{1},c_{1}),\phi(a_{2},b_{2};c_{2}))\geq
1$ whenever $(a_{1},b_{1},c_{1}),(a_{2},b_{2},c_{2})\in[0,n-1]^{2}\times[0,1]$
are at $L^{\infty}$ distance $\geq 1$.

Suppose $\max\\{|a_{2}-a_{1}|,|b_{2}-b_{1}|,|c_{2}-c_{1}|\\}\geq 1$. If
$\max\\{|a_{2}-a_{1}|,|b_{2}-b_{1}|\\}\geq 1$, then

$d_{\mathbb{H}_{\mathbb{R}}^{3}}(\phi(a_{1},b_{1},c_{1}),\phi(a_{2},b_{2},c_{2}))\geq\cosh^{-1}\left(1+\frac{1}{2h_{0}^{2}}\right)=1.$

If $|c_{2}-c_{1}|\geq 1$, then

$\displaystyle
d_{\mathbb{H}_{\mathbb{R}}^{3}}(\phi(a_{1},b_{1},c_{1}),\phi(a_{2},b_{2},c_{2}))$
$\displaystyle\geq$
$\displaystyle\cosh^{-1}\left(1+\frac{h_{0}^{2}(1-e^{-1})^{2}}{2h_{0}^{2}e^{-1}}\right)$
$\displaystyle=$ $\displaystyle\cosh^{-1}(\cosh(1))=1.$

Next we bound the diameter and the volume. For every point $(x,y;z)$ in the
image of $g$, we have $|x|,|y|\leq N-1$ and $h_{1}=h_{0}e^{-1}\leq z\leq
h_{0}$. Thus

$\displaystyle d_{\mathbb{H}_{\mathbb{R}}^{3}}((0,0;h_{0}),(x,y;z))$
$\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(1+\frac{2(N-1)^{2}+h_{0}^{2}(1-e^{-1})^{2}}{2h_{0}^{2}e^{-2}}\right)$
$\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(1+\frac{2e^{2}N^{2}+e^{2}h_{0}^{2}}{2h_{0}^{2}}\right)$
$\displaystyle=$
$\displaystyle\cosh^{-1}\left(1+\frac{e^{2}}{2}+2e^{2}(\cosh(1)-1)N^{2}\right)$
$\displaystyle\leq$ $\displaystyle\cosh^{-1}\left(2e^{2}\cosh(1)N^{2}\right)$
$\displaystyle\leq$ $\displaystyle\ln\left(4e^{2}\cosh(1)N^{2}\right)$
$\displaystyle=$ $\displaystyle 2\ln(N)+\ln(4e^{2}\cosh(1))\leq 2\ln(N)+9.$

Next, we bound the volume. For each point $(x,y;z)$ in the image of $g$ there
is a point $(a,b;h_{0})$ with $a,b\in\\{0,\ldots,N-1\\}$ such that
$|x-a|\leq\frac{1}{2}$, $|y-b|\leq\frac{1}{2}$ and $z\in[h_{0}e^{-1},h_{0}]$.
We have

$\displaystyle d_{\mathbb{H}_{\mathbb{R}}^{3}}((a,b;h_{0}),(x,y;z))$
$\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(1+\frac{\frac{1}{2}^{2}+\frac{1}{2}^{2}+h_{0}^{2}(1-e^{-1})^{2}}{2h_{0}^{2}e^{-2}}\right)$
$\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(1+\frac{1}{4h_{0}^{2}e^{-2}}+\frac{1}{2e^{-2}}\right)$
$\displaystyle=$
$\displaystyle\cosh^{-1}\left(1+\frac{e^{2}\cosh(1)}{2}\right)=:\lambda.$

Thus, the volume of the $1$-neighbourhood of the image of $g$ is at most
$CN^{2}$ where $C$ is the volume of the ball of radius $\lambda+1$ in
$\mathbb{H}_{\mathbb{R}}^{3}$. We have

$C=\pi(\sinh(2(\lambda+1))-2(\lambda+1))\leq 2039$

as required. ∎

Using the same strategy, we can also prove the following.

######  Theorem.

There is a constant $C$ such that for every $N\in\mathbb{N}$, there is a
$1$-thick topological embedding
$g:K_{N}\to\mathbb{R}\times\mathbb{H}^{2}_{\mathbb{R}}$ with
$\textup{diam}(g)\leq CN$ and $\textup{vol}(g)\leq CN^{2}$.

###### Proof.

Repeat the proof of Theorem 1.8 but replace the map $\phi$ by

$\phi:\mathbb{R}^{2}\times[0,1]\to\mathbb{R}\times\mathbb{H}^{2}_{\mathbb{R}}\quad\textup{given
by}\quad\phi(x,y,z)=(x;y,h_{0}e^{-z}).\qed$

##  3 Coarse wiring

In this section, we present some elementary properties of coarse wirings and
construct coarse wirings of finite graphs into a Cayley graph of the
lamplighter group $\mathbb{Z}_{2}\wr\mathbb{Z}$.

Recall that a map $r:X\to Y$ between metric spaces is $\kappa$-regular if
$d_{Y}(r(x),r(y))\leq\kappa(1+d_{X}(x,y))$ for all $x,y\in X$ and the preimage
of every ball of radius $1$ in $Y$ is contained in a union of at most $\kappa$
balls of radius $1$ in $X$. We will first prove Proposition 1.15, we recall
the statement for convenience.

######  Proposition.

Let $X$ and $Y$ be graphs with maximal degree $\Delta$ and let $r:VX\to VY$ be
a $\kappa$-regular map. Then for all sufficiently large $k$ we have

$\displaystyle\textup{wir}^{k}_{X\to
Y}(n)\leq\left(\kappa+\frac{1}{2}\right)\Delta n.$

###### Proof.

Let $\Gamma\subset X$ be a subgraph with $\left\lvert V\Gamma\right\rvert\leq
n$. For $xx^{\prime}\in E\Gamma$ let $P_{xx^{\prime}}$ be any minimal length
path from $r(x)$ to $r(x^{\prime})$ and let
$\Gamma^{\prime}=\bigcup_{E\Gamma}P_{xx^{\prime}}$. We construct a wiring
$f:\Gamma\to\Gamma^{\prime}$ as follows. For each vertex $v\in V\Gamma$ we
define $f(v)=r(v)$. We then map each edge $xx^{\prime}$ continuously to the
path $P_{xx^{\prime}}$.

Since each path $P_{xx^{\prime}}$ contains at most $2\kappa+1$ vertices and
$|E\Gamma|\leq\frac{1}{2}\Delta n$, we have $\left\lvert
V\Gamma^{\prime}\right\rvert\leq n\Delta(\kappa+\frac{1}{2})$.

If $P_{xx^{\prime}}$ contains an edge $e$ then the distance from $r(x)$ to the
initial vertex of $e$ is at most $2\kappa$, so there are at most
$1+\Delta^{2\kappa+1}$ possibilities for $r(x)$; $r$ is at most
$\kappa(1+\Delta)$-to-one so there are at most
$k:=\kappa(1+\Delta)(1+\Delta^{2\kappa+1})$ possibilities for $x$. Therefore
there are at most $k$ edges $xx^{\prime}\in E\Gamma$ such that
$f(xx^{\prime})=P_{xx^{\prime}}$ contains a given edge $e$ of
$E\Gamma^{\prime}$. It follows that $\textup{wir}^{k}(\Gamma\to
Y)\leq(\kappa+\frac{1}{2})\Delta n$. ∎

To deduce Corollary 1.16 from the above proposition, we prove a bound on
compositions of coarse wirings (Proposition 1.13).

######  Proposition.

Suppose $\textup{wir}^{k}_{X\to Y}(N)<\infty$. Then

$\displaystyle\textup{wir}^{kl}_{X\to Z}(N)\leq\textup{wir}^{l}_{Y\to
Z}\left(\textup{wir}^{k}_{X\to Y}(N)\right).$

###### Proof.

If $\textup{wir}^{l}_{Y\to Z}\left(\textup{wir}^{k}_{X\to
Y}(N)\right)=+\infty$ then there is nothing to prove, so assume it is finite.
Let $\Gamma\subset X$ with $\left\lvert V\Gamma\right\rvert\leq N$. Then there
exists a coarse $k$-wiring $\psi$ of $\Gamma$ into $Y$ with
$\textup{vol}(W)\leq\textup{wir}^{k}_{X\to Y}(N)$ and a coarse $l$-wiring
$\psi^{\prime}$ of $\textup{im}(W)$ into $Z$ with
$\textup{vol}(W^{\prime})\leq\textup{wir}^{l}_{Y\to
Z}\left(\textup{wir}^{k}_{X\to Y}(N)\right)$.

We now construct a coarse $kl$-wiring $\psi^{\prime\prime}$ of $\Gamma$ into
$Z$. For each $v\in V\Gamma$, define
$\psi^{\prime\prime}(v)=\psi^{\prime}(\psi(v))$. For each $e\in E\Gamma$, let
$e_{1},\ldots,e_{m}$ be the edge path $P_{e}$. We define
$P^{\prime\prime}_{e}$ to be the concatenation of paths
$P^{\prime}_{e_{1}}P^{\prime}_{e_{2}}\ldots P^{\prime}_{e_{m}}$. We extend
$\psi^{\prime\prime}$ continuously so that the image of $e$ is
$P^{\prime\prime}_{e}$. It is clear that $\psi^{\prime\prime}|_{V\Gamma}$ is
$\leq kl$-to-$1$ and
$\textup{im}(\psi^{\prime\prime})\subseteq\textup{im}(\psi^{\prime})$, so
$\textup{vol}(\psi^{\prime\prime})\leq\textup{vol}(\psi^{\prime})$. Since each
edge in $\textup{im}(\psi^{\prime\prime})$ is contained in at most $l$ of the
paths $P^{\prime}_{e^{\prime}}$ and each $P^{\prime}_{e^{\prime}}$ is used in
at most $k$ of the paths $P_{e}$, we have that each edge in
$\textup{im}(\psi^{\prime\prime})$ is contained in the image of at most $kl$
of the edges in $E\Gamma$, as required. ∎

###### Proof of Corollary 1.16.

This follows immediately from Propositions 1.15 and 1.13. ∎

Finally in this section we prove Theorem 1.18 by constructing coarse wirings
into a Cayley graph of the lamplighter group. This construction is crucial for
Theorem 1.11. We identify $\mathbb{Z}_{2}\wr\mathbb{Z}$ with the semidirect
product $\bigoplus_{\mathbb{Z}}\mathbb{Z}_{2}\rtimes\mathbb{Z}$ and define $Y$
to be the Cayley graph of $\mathbb{Z}_{2}\wr\mathbb{Z}$ using the generating
set $\\{(\delta_{0},0),(0,1),(0,-1)\\}$ where $\delta_{0}(i)=1$ if $i=0$ and
$0$ otherwise. Let us recall the statement of Theorem 1.18.

######  Theorem.

Let $\Gamma$ be an $n$-vertex graph with maximal degree $d$. There is a coarse
$2d$-wiring of $\Gamma$ into $Y$ with diameter at most
$6\lceil\log_{2}(n)\rceil$ and volume at most
$dn\left(3\lceil\log_{2}(n)\rceil+\frac{1}{2}\right)$.

###### Proof.

Set $k=\lceil\log_{2}(n)\rceil$. For each $0\leq i\leq n-1$ and $0\leq j\leq
k-1$ fix $i_{j}\in\\{0,1\\}$ such that $\sum_{j=0}^{k-1}2^{j}i_{j}=i$.

Enumerate the vertices of $\Gamma$ as $v_{0},\ldots,v_{n-1}$. All the points
in the image of the wiring will have their lamplighter position and lamp
functions supported on the set $\\{0,\ldots,2k-1\\}$, so we represent elements
of $\mathbb{Z}_{2}\wr\mathbb{Z}$ by a binary string of length exactly $2k$
(for the element of $\bigoplus_{\mathbb{Z}}\mathbb{Z}_{2}$) with one entry
marked by a hat ($\hat{\ }$) to indicate the position of the lamplighter (for
the element of $\mathbb{Z}$). Note that this set has diameter at most
$6k=6\lceil\log_{2}(n)\rceil$.

Now we map each $v_{i}$ to $\hat{i_{0}}i_{1}\ldots i_{k-1}i_{0}i_{1}\ldots
i_{k-1}$ and for each edge $v_{i}v_{j}$ we assign the path $P_{ij}$ which
travels from left to right correcting the binary string as it goes, then
returns to the leftmost position:

$\displaystyle\hat{i_{0}}i_{1}\ldots i_{k-1}i_{0}i_{1}\ldots i_{k-1}$
$\displaystyle\to$ $\displaystyle\widehat{j_{0}}i_{1}\ldots
i_{k-1}i_{0}i_{1}\ldots i_{k-1}$ (4) $\displaystyle\to$ $\displaystyle
j_{0}\widehat{i_{1}}\ldots i_{k-1}i_{0}i_{1}\ldots i_{k-1}$ (5)
$\displaystyle\ldots$ $\displaystyle\to$ $\displaystyle
j_{0}j_{1}\ldots\widehat{j_{k-1}}i_{0}i_{1}\ldots i_{k-1}$ (6)
$\displaystyle\ldots$ $\displaystyle\to$ $\displaystyle j_{0}j_{1}\ldots
j_{k-1}j_{0}j_{1}\ldots\widehat{j_{k-1}}$ (7) $\displaystyle\to$
$\displaystyle j_{0}j_{1}\ldots
j_{k-1}j_{0}j_{1}\ldots\widehat{j_{k-2}}j_{k-1}$ (8) $\displaystyle\ldots$
$\displaystyle\to$ $\displaystyle\widehat{j_{0}}j_{1}\ldots
j_{k-1}j_{0}j_{1}\ldots j_{k-1}.$ (9)

Now suppose an edge $e$ lies on one of the paths $P_{ij}$. Choose one of the
end vertices and denote the binary string associated to this vertex by
$a_{0}\ldots a_{2k-1}$. We claim that at least one of the following holds:

$i=\sum_{l=0}^{k-1}2^{l}a_{k+l}\ (\dagger)\quad\quad
j=\sum_{l=0}^{k-1}2^{l}a_{l}\ (\ddagger)$

In particular, as the graph $\Gamma$ has maximal degree at most $d$, this
means that there are at most $2d$ paths containing the edge $e$.

If $e$ appears on $P_{ij}$ during stages (4), (5) or (6), then $a_{k+l}=i_{l}$
for $0\leq l\leq k-1$. Thus $(\dagger)$ holds. Otherwise, $e$ appears on
$P_{ij}$ during stages (7), (8) or (9), then $a_{l}=j_{l}$ for $0\leq l\leq
k-1$. Thus $(\ddagger)$ holds.

For the volume estimate, each path $P_{ij}$ meets at most $6k+1$ vertices and
there are $|E\Gamma|\leq\frac{1}{2}nd$ paths. ∎

##  4 From fine wirings to coarse wirings and back

In this section we prove Proposition 1.10 and Theorem 1.11, which describe
circumstances in which one can translate between thick embeddings of a graph
into a metric space and coarse wirings of that graph into a graph quasi-
isometric to the metric space.

###  4.1 Fine to coarse

In this subsection we will prove Proposition 1.10.

######  Definition 4.1.

Let $\mu$ be a measure on a metric space $X$. We say $(X,\mu)$ has controlled
growth if for every $r>0$

$c_{r}:=\inf_{x\in X}\mu(B_{r}(x))>0\quad\textup{and}\quad C_{r}:=\sup_{x\in
X}\mu(B_{r}(x))<+\infty.$

Let us recall the statement.

######  Proposition.

Let $M$ be a Riemannian manifold with controlled growth and let $Y$ be a graph
quasi-isometric to $M$. For any $d\in\mathbb{N}$ and $T>0$, there exists a
constant $k$ depending only on $d$, $M$, $T$ and $Y$ such that if $\Gamma$ is
a finite graph with maximal degree $d$ and there is a $T$-thick embedding
$\phi:\Gamma\to M$ with diameter $D$ and volume $V$ then there is a coarse
$k$-wiring of $\Gamma$ into $Y$ with diameter at most $kD$ and volume at most
$kV$.

###### Proof.

Let $f\colon M\to Y$ be a (possibly discontinuous) quasi-isometry. Let
$\lambda\geq 1$ be such that

  1. 1.

$\frac{1}{\lambda}d_{Y}(f(x_{1}),f(x_{2}))-\lambda\leq
d_{M}(x_{1},x_{2})\leq\lambda d_{Y}(f(x_{1}),f(x_{2}))+\lambda$ for $x_{1}$
and $x_{2}$ in $M$, and

  2. 2.

for any $y\in Y$, there exists $x\in M$ with $d_{Y}(y,f(x))\leq\lambda$.

We show that $f\phi$ can be perturbed to obtain a coarse wiring $\psi$.

For $v\in V\Gamma$, let $\psi(v)$ be any vertex of $Y$ within distance
$\frac{1}{2}$ of $f\phi(v)$. If $w$ is another vertex of $\Gamma$ with
$\psi(w)=\psi(v)$ then $d_{M}(\phi(v),\phi(w))\leq 3\lambda$. But, for any
distinct pair of vertices $v,w$, $d_{M}(\phi(v),\phi(w))\geq T$, so it follows
that at most $C_{3\lambda+T/2}/c_{T/2}$ vertices of $\Gamma$ map under $\psi$
to $\psi(v)$.

We now describe a collection of paths $P_{vv^{\prime}}$ in $Y$ as $v$ and
$v^{\prime}$ range over pairs of adjacent vertices in $\Gamma$. The
restriction of $\phi$ to the edge $vv^{\prime}$ is a continuous path in $M$;
choose a sequence
$\phi(v)=w_{0}^{\prime},\dotsc,w_{n}^{\prime}=\phi(v^{\prime})$ of points on
this path with $n$ minimal such that $d(w_{i}^{\prime},w_{i+1}^{\prime})\leq
2T$ for each $i$. Denote this minimal $n$ by $n_{vv^{\prime}}$. Choose
$w_{0}=\psi(v)$, $w_{n}=\psi(v^{\prime})$ and for each $1\leq i\leq n-1$ let
$w_{i}$ is a vertex of $Y$ within distance $\frac{1}{2}$ of
$f(w_{i}^{\prime})$. For each $i$ we have

$\displaystyle d_{Y}(w_{i},w_{i+1})$ $\displaystyle\leq$ $\displaystyle
1+d_{Y}(f(w^{\prime}_{i}),f(w^{\prime}_{i+1}))$ $\displaystyle\leq$
$\displaystyle 1+\lambda d_{M}(w^{\prime}_{i},w^{\prime}_{i+1})+\lambda^{2}$
$\displaystyle\leq$ $\displaystyle 1+2\lambda T+\lambda^{2}:=L,$

so can be joined by an edge path comprising at most $L$ edges. We define the
path $P_{vv^{\prime}}$ to be the concatenation of these $n_{vv^{\prime}}$
paths of length at most $L$.

We extend $\psi$ to a continuous map which sends each edge $vv^{\prime}$ to
the path $P_{vv^{\prime}}$. We claim that $\psi$ is a coarse wiring with the
appropriate bounds on diameter and volume.

Firstly, we bound the diameter. Note that every point in $\textup{im}(\psi)$
is within distance $(L+1)/2$ of some $f(w^{\prime})$ with
$w^{\prime}\in\textup{im}(\phi)$. Let $x,y\in\textup{im}(\psi)$ and let
$v,w\in\Gamma$ satisfy $d_{Y}(x,f\phi(v)),d_{Y}(y,f\phi(w))\leq(L+1)/2$. We
have

$\displaystyle d_{Y}(x,y)$ $\displaystyle\leq$ $\displaystyle
d_{Y}(x,f\phi(v))+\lambda\left(d_{M}(\phi(v),\phi(w))+\lambda\right)+d_{Y}(f\phi(w),y)$
$\displaystyle\leq$ $\displaystyle
L+1+\lambda.\textup{diam}(\phi)+\lambda^{2}$ $\displaystyle\leq$
$\displaystyle C(T,\lambda).\textup{diam}(\phi).$

The final inequality fails if $\Gamma$ is a single vertex, but the proposition
obviously holds in this situation. Otherwise $\textup{diam}(\phi)\geq T$ and
the inequality holds for a suitable $C$.

Next we bound the volume of the wiring. The bound follows from the two
inequalities

$\textup{vol}(\phi)\geq\frac{c_{T/2}}{2d+1}\left(|V\Gamma|+\sum_{vv^{\prime}\in
E\Gamma}n_{vv^{\prime}}\right)\quad\textup{and}\quad\textup{vol}(\psi)\leq|V\Gamma|+L\sum_{vv^{\prime}\in
E\Gamma}n_{vv^{\prime}}.$

For the second bound, each vertex in $V\Gamma$ contributes at most $1$ vertex
to $\textup{vol}(\psi)$ and each path $P_{vv^{\prime}}$ contributes at most
$Ln_{vv^{\prime}}$ vertices to $\textup{vol}(\psi)$. For the first bound,
notice that the (open) balls of radius $T/2$ around the image of each vertex
are necessarily disjoint. Similarly, the balls of radius $T/2$ centred at any
two points in one of the sequences
$\phi(v)=w_{0}^{\prime},\dotsc,w_{n}^{\prime}=\phi(v^{\prime})$ defined above
are necessarily disjoint: if this were not the case for $w^{\prime}_{j}$ and
$w^{\prime}_{j^{\prime}}$, we must have $|j-j^{\prime}|\geq 2$ since
$d(w^{\prime}_{i},w^{\prime}_{i+1})\geq T$ for all $i$, but then we can remove
$w^{\prime}_{j+1},\ldots,w^{\prime}_{j^{\prime}-1}$ from the above sequence,
contradicting the minimality assumption. Moreover, if two balls of radius
$T/2$ centred at points on sequences corresponding to different edges have
non-trivial intersection, then these edges must have a common vertex since
$\phi$ is a $T$-thick embedding. Thus, the $T$-neighbourhood of the image of
$\phi$ contains a family of $\left(|V\Gamma|+\sum_{vv^{\prime}\in
E\Gamma}n_{vv^{\prime}}\right)$ balls of radius $T/2$, such that no point is
contained in more than $2d+1$ of these balls ($d$ for each end vertex, and an
extra $1$ if the point is within distance $T/2$ of the image of a vertex). As
a result

$\textup{vol}(\phi)\geq\frac{c_{T/2}}{2d+1}\left(|V\Gamma|+\sum_{vv^{\prime}\in
E\Gamma}n_{vv^{\prime}}\right).$

It remains to prove that we have defined a coarse $k$-wiring. It is sufficient
to show that there is a constant $k$ depending only on $\lambda$ and the
growth rates $c$ and $C$ of volumes in $M$ such that any edge of $Y$ is
contained in $P_{vv^{\prime}}$ for at most $k$ edges $vv^{\prime}\in E\Gamma$.

Let $uu^{\prime}$ be an edge of $Y$ contained in at least one path in the
collection $P$. Let $A$ be the subset of $E\Gamma$ comprising edges $e$ such
that $P_{e}$ contains $uu^{\prime}$. As noted during the proof of the diameter
bound every point in $P_{e}$ is contained in the $(L+1)/2$-neighbourhood of
$f(\phi(e))$ so there is a point $x_{e}\in\phi(e)$ such that
$d_{Y}(u,f(x_{e}))\leq(L+1)/2$, and so for any other edge $e^{\prime}\in A$,

$\displaystyle
d_{M}(x_{e},x_{e^{\prime}})\leq\lambda\left(d_{Y}(f(x_{e}),u)+d_{Y}(u,f(x_{e^{\prime}}))\right)+\lambda\leq\lambda(L+2).$

For any edge $e^{\prime}\in A$, $x_{e^{\prime}}$ is within distance $T$ of at
most $2d$ of the points $x_{e^{\prime\prime}}$ for $e^{\prime\prime}\in A$. It
follows that the size of $A$ is at most $2dc_{T/2}^{-1}C_{\lambda(L+2)+T/2}$.
∎

###  4.2 Coarse to fine

The return direction is more sensitive and we are not able to obtain $1$-thick
embeddings in all cases. When the target space is Euclidean this is easily
resolved by rescaling, but in other spaces changing thickness potentially has
a more drastic effect on the volume. Let us recall Theorem 1.11.

######  Theorem.

Let $M$ be a compact Riemannian manifold of dimension $n\geq 3$, let $Y$ be a
graph quasi-isometric to the universal cover $\widetilde{M}$ of $M$ and let
$k,d\in\mathbb{N}$. There exist constants $C$ and $\varepsilon>0$ such that
the following holds:

If there is a coarse $k$-wiring of a finite graph $\Gamma$ with maximal degree
$d$ into $Y$ with diameter $D$ and volume $V$ then there is a
$\varepsilon$-thick embedding of $\Gamma$ into $\widetilde{M}$ with diameter
at most $CD$ and volume at most $CV$.

The proof of this result is completed in several steps. As we are aiming to
construct a topological embedding, the first step is to replace the coarse
$k$-wiring $\Gamma\to Y$ with an injective continuous function $\Gamma\to
Y^{\prime}$ where $Y^{\prime}$ is a “thickening” of $Y$. Exploiting the
symmetries in the universal cover, we choose $Y$ (and its thickening) to be
cocompact with respect to the action of $\pi_{1}(M)$, this reduces the problem
of embedding the thickening of $Y$ to defining finitely many paths in $M$. We
then use the fact that $M$ is compact to obtain a positive lower bound on the
thickness of the topological embedding.

Using Proposition 1.15 and the fact that quasi-isometries of bounded degree
graphs are regular, it suffices to prove Theorem 1.11 for a specific bounded
degree graph quasi-isometric to $\widetilde{M}$.

We require a standard S̆varc-Milnor lemma.

######  Lemma 4.2.

Let $x\in M$. Then, for sufficiently large $L$, the graph
$\mathcal{G}_{x}^{L}$ with vertex set equal to the preimage of $x$ in
$\widetilde{M}$, with vertices connected by an edge if and only if they are
separated by a distance of at most $L$ in $\widetilde{M}$, is quasi-isometric
to $\widetilde{M}$.

Now we assume that $Y=\mathcal{G}_{x}^{L}$ for a suitably chosen $L$. The next
step is to “thicken” $Y$ to a graph $Y^{\prime}$ to obtain injective wirings.

######  Definition 4.3.

A wiring $f:\Gamma\to Y$ of a finite graph $\Gamma$ into a graph $Y$ is called
an injective wiring if $f$ is injective.

######  Definition 4.4.

Given a graph $Y$ and $T\in\mathbb{N}$ we define the $T$-thickening of $Y$ to
be the graph $K_{T}(Y)$ with vertex set $VY\times\left\\{1,\ldots,T\right\\}$
and edges $\\{(v,i),(w,j)\\}$ whenever either $v=w$ and $1\leq i<j\leq T$, or
$\\{v,w\\}\in EY$ and $1\leq i\leq j\leq T$.

######  Lemma 4.5.

For all $d,k\in\mathbb{N}$ there exists some $T$ with the following property.
If there is a coarse $k$-wiring $\psi:\Gamma\to Y$ then there is an injective
wiring $\psi^{\prime}:\Gamma\to K_{T}(Y)$, such that
$\textup{diam}(\psi^{\prime})\leq\textup{diam}(\psi)+2$ and
$\textup{vol}(\psi^{\prime})\leq T\textup{vol}(\psi)$.

###### Proof.

Set $T=k(d+1)$. For each vertex $v\in Y$ enumerate
$\psi^{-1}(v)=\left\\{v_{1},\ldots,v_{m}\right\\}$ for some $m\leq k$. Define
$\psi^{\prime}(v_{l})=(\psi(v),l)$. We now define $\psi^{\prime}$ on the edges
of $\Gamma$. Whenever $vw$ is an edge in $\Gamma$ with $\psi(v)=\psi(w)$ then
there exist $l\neq l^{\prime}$ such that $v=v_{l}$ and $w=v_{l^{\prime}}$ and
we map the corresponding interval in $\Gamma$ with endpoints labelled $v$ and
$w$ isometrically onto the interval with endpoints labelled $(\psi(v),l)$ and
$(\psi(v),l^{\prime})$ in $K_{T}(Y)$.

Define $E^{\prime}$ to be the set of edges in $\Gamma$ whose end vertices are
distinct after applying $\psi$. Enumerate the edges of $E^{\prime}$ as
$e_{1}=v_{1}w_{1},\ldots,e_{n}=v_{n}w_{n}$ and, for each $j$, enumerate (in
order, including non-consecutive repetitions) the vertices contained in the
image of the interval corresponding to $v_{j}w_{j}$ under $\psi$ as
$\psi(v_{j})=v_{j}^{0},\ldots,v_{j}^{n_{j}}=\psi(w_{j})$. Each
$v_{j}^{i}v_{j}^{i+1}$ is an edge in $Y$.

Completely order the $v^{i}_{j}$ so that
$v^{i}_{j}<v^{i^{\prime}}_{j^{\prime}}$ whenever $j<j^{\prime}$ or
$j=j^{\prime}$ and $i<i^{\prime}$. Denote by $n(v^{i}_{j})$ the number of
$v^{i^{\prime}}_{j^{\prime}}<v^{i}_{j}$ such that
$v^{i^{\prime}}_{j^{\prime}}$ and $v^{i}_{j}$ are the same vertex of $Y$. We
extend $\psi^{\prime}$ by mapping the edge $e_{j}$ continuously and
injectively onto the path
$(v_{j}^{0},n(v_{j}^{0})+k+1),(v_{j}^{1},n(v_{j}^{1})+k+1),\ldots,(v_{j}^{n_{j}},n(v_{j}^{n_{j}})+k+1))$.
It is immediate from the construction that $\psi^{\prime}$ is an injective
wiring. It remains to find a uniform bound on $n(v_{j}^{i})$.

Since $\psi$ is a coarse $k$-wiring, each vertex in $Y$ lies in the interior
of at most $kd$ of the $\psi(e)$, so $n(v_{j}^{i})\leq kd-1$ for all $i,j$.
Thus $\psi^{\prime}$ as above is well-defined since $T=k(d+1)$.

Note that if $(x,j),(y,j^{\prime})$ are contained in
$\textup{im}(\psi^{\prime})$ then $(x,1),(y,1)\in\textup{im}(\psi^{\prime})$
and there is a path of length at most $\textup{diam}(\psi)$ connecting $(x,1)$
to $(y,1)$ in $K_{T}(Y)$. Hence
$\textup{diam}(\psi^{\prime})\leq\textup{diam}(\psi)+2$. If
$(x,j)\in\textup{im}(\psi^{\prime})$ for some $j$ then
$x\in\textup{im}(\psi)$. Therefore $\textup{vol}(\psi^{\prime})\leq
T\textup{vol}(\psi)$. ∎

The next step is to find a thick embedding of $K_{T}(Y)$ into $\widetilde{M}$.

######  Lemma 4.6.

Suppose that $M$ is a compact manifold of dimension $n\geq 3$ with fundamental
group $G$ and let $\widetilde{M}$ be the universal cover of $M$. Let $x\in M$
and denote by $Gx$ the orbit of $x$ in $\widetilde{M}$ under $G$. Then for any
$L,T$ there is an embedding of $Y^{\prime}=K_{T}(\mathcal{G}^{L}_{X}(Gx))$
into $\widetilde{M}$ that is equivariant with respect to the action of $G$ on
$\mathcal{M}$ by deck transformations.

This embedding is $\varepsilon$-thick for some $\varepsilon>0$, and there is a
uniform upper bound on the length of the paths obtained as the images of edges
of $Y^{\prime}$ under the embedding.

###### Proof.

Let $B$ be a ball in $M$ centred at $x$ which is homeomorphic to
$\mathbb{R}^{n}$. Fix a topological embedding $f$ of the complete graph on $T$
vertices into $B$. Enumerate the vertices $\\{w_{1},\ldots,w_{T}\\}$. For each
pair $w_{a},w_{b}\in VK_{T}$, and each homotopy class $[\ell]$ in
$\pi_{1}(M,x)$ which has a representative of length at most $L$, choose an arc
$\gamma_{a,b,[\ell]}$ connecting $f(w_{a})$ to $f(w_{b})$ such that the loop
obtained from concatenating $f(w_{a}w_{b})$ and $\gamma_{a,b,[\ell]}$ is in
$[\ell]$ and such that $\gamma_{a,b,[\ell]}$ intersects the union of
$f(K_{T})$ and all arcs previously added only at the points $f(y)$ and $f(z)$.
This is always possible using a general position argument.

Lifting this embedding to $\overline{M}$, we obtain a $G$-equivariant
embedding of $K_{T}(\mathcal{G}^{L}_{X}(Gx))$ into $\widetilde{M}$.
Specifically, the interval with end points $(gx,a)$ and $(gx,b)$ is mapped to
$gf(w_{a}w_{b})$ and if $(gx,a)(g^{\prime}x,b)$ is an edge in $Y^{\prime}$
then by definition the homotopy class corresponding to $g=[\ell]$ has a
representative of length at most $L$. Thus, the image of this edge in
$\widetilde{M}$ is the lift of $\gamma_{a,b,[\ell]}$ starting at $(gx,a)$ and
ending at $(g^{\prime}x,b)$. As the natural covering map $\widetilde{M}\to M$
is $1$-Lipschitz, this topological embedding is $\varepsilon$-thick, where
$\varepsilon=\min\left\\{d_{M}(X,Y)\right\\}$ as $X,Y$ range over the
following:

  * •

$X=\\{f(v)\\}$, $Y=\\{f(w)\\}$ for distinct vertices $v,w\in VK_{T}$; or

  * •

$X=\\{f(v)\\}$ and $Y$ is either $f(yz)$ or $\gamma_{y,z,[\ell]}$ with $v,y,z$
all distinct; or

  * •

$X$ is either $f(vw)$ or $\gamma_{v,w,[\ell]}$ and $Y$ is either $f(yz)$ or
$\gamma_{y,z,[\ell^{\prime}]}$ with $v,w,y,z$ all distinct.

Similarly, since there are only finitely many $G$-orbits of images of edges,
there is a uniform upper bound on the lengths of images of edges. ∎

We are now ready to prove Theorem 1.11.

###### Proof of Theorem 1.11.

Let $M$ be a compact manifold of dimension $n\geq 3$, let $\widetilde{M}$ be
the universal cover of $M$ and let $Y$ be any graph quasi-isometric to
$\widetilde{M}$. Fix $d,k\in\mathbb{N}$ and assume that there is a coarse
$k$-wiring of $\Gamma$ into $Y$ with diameter $D$ and volume $V$. We may
assume $D\geq 1$ as the $D=0$ case is obvious.

By Lemma 4.2 there is some $L$ such that $\mathcal{G}_{x}^{L}$ is quasi-
isometric to $\widetilde{M}$, so by Corollary 1.16(1), there exists some
$l=l(k,d)$ so that there is a coarse $l$-wiring of $\Gamma$ into
$\mathcal{G}_{x}^{L}$ with diameter $\leq lD+l\leq 2lD$ and volume $\leq
lV+l\leq 2lV$.

Now we apply Lemma 4.5: for some $T=T(l,d)$ there is an injective wiring
$\psi$ of $\Gamma$ into $K_{T}(\mathcal{G}_{x}^{L})$ with diameter $\leq
2lD+2\leq 4lD$ and volume $\leq 2TlV$. Composing this injective wiring with
the $\varepsilon$-thick topological embedding $\phi$ of
$K_{T}(\mathcal{G}_{x}^{L})$ into $\widetilde{M}$ gives an $\varepsilon$-thick
embedding $f:\Gamma\to\widetilde{M}$. The diameter of the image of $f$ is
bounded from above by a constant multiple of $\textup{diam}(\psi)$. For the
volume, note that the sum of the lengths of all paths in the wiring is at most
a constant times $\textup{vol}(\psi)$, and the volume of the thick embedding
is at most this sum of lengths multiplied by the maximal volume of a ball of
radius $\varepsilon$ in $M$. Hence the volume of this thick embedding is at
most a constant multiple of $V$. ∎

##  5 Lower bounds on coarse wiring

The goal of this section is to prove Theorem 1.17. We begin by recalling the
definition of the separation profile and its key properties.

###  5.1 Background on the separation profile

Recall that $f\lesssim g$ if there is a constant $C$ such that

$f(x)\leq Cg(Cx)+C\quad\textup{for all}\ x\in X.$

We write $f\simeq g$ if $f\lesssim g$ and $g\lesssim f$.

######  Definition 5.1.

[BST12] Let $\Gamma$ be a finite graph. We denote by $\textup{cut}(\Gamma)$
the minimal cardinality of a set $S\subset V\Gamma$ such that no component of
$\Gamma-S$ contains more than $\frac{1}{2}|V\Gamma|$ vertices. A set $S$
satisfying this property is called a cut set of $\Gamma$.

Let $X$ be a (possibly infinite) graph. We define the separation profile of
$X$ to be the function $\textup{sep}_{X}:[0,\infty)\to[0,\infty)$ given by

$\textup{sep}_{X}(n)=\max\\{\textup{cut}(\Gamma)\mid\Gamma\leq X,\
|V\Gamma|\leq n\\}.$

For convenience, we will define $\textup{sep}_{X}(r)=0$ whenever $r<1$.

######  Definition 5.2.

The Cheeger constant of a finite graph $\Gamma$ is

$h(\Gamma)=\min\\{\frac{|\partial A|}{|A|}\mid A\subseteq V\Gamma,\
|A|\leq\frac{1}{2}|V\Gamma|\\}$

where $\partial A=\\{v\in V\Gamma\mid d_{\Gamma}(v,A)=1\\}$.

###  5.2 Lower bounds on wiring profiles

The key part of the proof of Theorem 1.17 is the following intimidating bound.

######  Proposition 5.3.

Let $X,Y$ be graphs with maximal degrees $\Delta_{X},\Delta_{Y}$ respectively.
If $\textup{wir}^{k}_{X\to Y}(n)<\infty$, then, for all $n\geq 3$,

$\sum_{s\geq 0}\textup{sep}_{Y}(2^{-s}\textup{wir}^{k}_{X\to
Y}(n))\geq\frac{\textup{sep}_{X}(n)}{k\Delta_{Y}}.$

Roughly, the idea is that given a subgraph $\Gamma\leq X$ and an “efficient”
coarse $k$-wiring $\Gamma\to\Gamma^{\prime}$, $\textup{cut}(\Gamma^{\prime})$
can be bounded from above by $\textup{cut}(\Gamma)$ up to a multiplicative
error depending only on $k$. However, we do not know that any cut of this size
equally divides the images of the vertices of $\Gamma$ in $\Gamma^{\prime}$ so
we may need to repeat the procedure on a subgraph of $\Gamma^{\prime}$ with at
most $|\Gamma^{\prime}|/2$ vertices and then again on a subgraph of
$\Gamma^{\prime}$ with at most $|\Gamma^{\prime}|/4$ vertices and so on. This
divide-and-conquer strategy is the reason for the summation on the left hand
side of the equation above.

###### Proof.

Let $n\geq 3$ and choose $\Gamma\leq X$ which satisfies
$\left\lvert\Gamma\right\rvert\leq n$ and
$\textup{cut}(\Gamma)=\textup{sep}_{X}(n)=l$. Since $n\geq 3$, it is always
the case that $l\leq 2\left\lvert\Gamma\right\rvert/3$. By [Hum17, Proposition
2.4] there is some $\Gamma^{\prime\prime}\leq\Gamma$ which satisfies
$\left\lvert\Gamma^{\prime\prime}\right\rvert\geq\frac{1}{2}\left\lvert\Gamma\right\rvert$
and $h(\Gamma^{\prime\prime})\geq\frac{l}{2\left\lvert\Gamma\right\rvert}$.
Let $\psi:\Gamma^{\prime\prime}\to\Gamma^{\prime}$ be a coarse $k$-wiring
where $\Gamma^{\prime}\leq Y$ satisfies
$|\Gamma^{\prime}|=wir^{k}_{Y}(\Gamma^{\prime\prime})$.

Let us recursively define a collection of subsets
$C^{\prime}_{1},C^{\prime}_{2},\ldots,\subseteq V\Gamma^{\prime}$ as follows.
Define $\Gamma^{\prime}_{0}=\Gamma$. Let $C^{\prime}_{s}$ be a cut set of
$\Gamma^{\prime}_{s}$ of minimal size. If for every component $A$ of
$\Gamma^{\prime}_{s}-C^{\prime}_{s}$, we have $|\left\\{v\in V\Gamma\ \left|\
\psi(v)\in A\right.\right\\}|\leq\frac{1}{2}|\Gamma$ then define
$C^{\prime}_{t}=\emptyset$ for all $t>s$ and end the process. Otherwise, set
$\Gamma_{s+1}$ to be the unique connected component of
$\Gamma^{\prime}_{s}-C^{\prime}_{s}$ satisfying $|\left\\{v\in V\Gamma\
\left|\ \psi(v)\in A\right.\right\\}|>\frac{1}{2}|\Gamma$. As
$|\Gamma|<\infty$ this process will always terminate. Define
$C^{\prime}=\bigcup_{s\geq 0}C^{\prime}_{s}$. By construction, for every
connected component $A$ of $\Gamma^{\prime}\setminus C^{\prime}$, we have
$|\left\\{v\in V\Gamma\ \left|\ \psi(v)\in
A\right.\right\\}|\leq\frac{1}{2}|\Gamma$. By definition of cut sets,
$|\Gamma^{\prime}_{s}|\leq 2^{-s}|\Gamma^{\prime}|$, so
$|C^{\prime}_{s}|\leq\textup{sep}_{Y}(2^{-s}|\Gamma^{\prime}|)=\textup{sep}_{Y}(2^{-s}\textup{wir}^{k}_{X\to
Y}(n))$.

Let $C$ be the set of all vertices in $\Gamma$ which are the end vertices of
an edge whose image under $\psi$ contains any vertex in $C^{\prime}$. By
construction $C$ is a cutset for $\Gamma$. Since $\psi$ is a $k$-coarse
wiring, each edge in $\Gamma^{\prime}$ lies in the image of at most $k$ edges
in $\Gamma$, so each vertex in $\Gamma^{\prime}$ lies in the image of at most
$k\Delta_{Y}$ edges in $\Gamma$, where $\Delta_{Y}$ is the maximal degree of
the graph $Y$. Thus $|C|\leq k\Delta_{Y}|C^{\prime}|$.

Combining these observations we see that

$\textup{cut}(\Gamma)\leq|C|\leq k\Delta_{Y}|C^{\prime}|\leq
k\Delta_{Y}\sum_{s\geq 0}\textup{sep}_{Y}(2^{-s}\textup{wir}^{k}_{X\to Y}(n))$

As this holds for all $\Gamma\leq X$ with $\left\lvert\Gamma\right\rvert\leq
n$, we deduce that

$\textup{sep}_{X}(n)\leq k\Delta_{Y}\sum_{s\geq
0}\textup{sep}_{Y}(2^{-s}\textup{wir}^{k}_{X\to Y}(n)).\qed$

In practice, the separation profiles of graphs we are interested in here are
of the form $n^{r}\ln(n)^{s}$ with $r\geq 0$ and $s\in\mathbb{R}$. Restricted
to these functions, Proposition 5.3 says the following.

######  Corollary 5.4.

Suppose $\textup{sep}_{X}(n)\gtrsim n^{r}\ln(n)^{s}$ and
$\textup{sep}_{Y}(n)\simeq n^{p}\ln(n)^{q}$. Then, for all $k$,

$wir^{k}_{X\to
Y}(n)\gtrsim\left\\{\begin{array}[]{lll}n^{r/p}\ln(n)^{(s-q)/p}&\textup{if}&p>0,\\\
\exp(n^{r/(q+1)}\ln(n)^{s/(q+1)})&\textup{if}&p=0.\end{array}\right.$

###### Proof.

If $wir^{k}_{X\to Y}(n)=+\infty$ there is nothing to prove, so assume this is
not the case. Applying our hypotheses to Proposition 5.3, we have

$n^{r}\ln(n)^{s}\lesssim\sum_{i\geq 0}\left(2^{-i}\textup{wir}^{k}_{X\to
Y}(n)\right)^{p}\ln\left(2^{-i}\textup{wir}^{k}_{X\to Y}(n)\right)^{q}.$ (10)

If $p>0$, then the sequence $\left(2^{-i}\textup{wir}^{k}_{X\to
Y}(n)\right)^{p}$ decays exponentially as a function of $i$, so

$\displaystyle n^{r}\ln(n)^{s}$ $\displaystyle\lesssim$
$\displaystyle\ln\left(\textup{wir}^{k}_{X\to Y}(n)\right)^{q}\sum_{i\geq
0}\left(2^{-i}\textup{wir}^{k}_{X\to Y}(n)\right)^{p}$ $\displaystyle\lesssim$
$\displaystyle\textup{wir}^{k}_{X\to Y}(n)^{p}\ln\left(\textup{wir}^{k}_{X\to
Y}(n)\right)^{q}.$

Hence, there is some constant $C>0$ such that

$w:=\textup{wir}^{k}_{X\to Y}(n)^{p}\ln\left(\textup{wir}^{k}_{X\to
Y}(n)\right)^{q}\geq C^{-1}(C^{-1}n)^{r}\ln(C^{-1}n)^{s}-C.$ (11)

Now suppose $\textup{wir}^{k}_{X\to Y}(n)\leq dn^{r/p}\ln(n)^{(s-q)/p}$. Then

$\displaystyle w$ $\displaystyle\leq$ $\displaystyle
d^{p}n^{r}\ln(n)^{s-q}\left(\ln(d)+\frac{r}{p}\ln(n)+\frac{s-q}{p}\ln\ln(n)\right)^{q}$
$\displaystyle\leq$
$\displaystyle\frac{(2r)^{s}d^{p}}{p^{s}}n^{r}\ln(n)^{s-q}\ln(n)^{q}=\frac{(2r)^{s}d^{p}}{p^{s}}n^{r}\ln(n)^{s}$

for sufficiently large $n$. This contradicts $\eqref{eq:wir}$ if $d$ is small
enough and $n$ is large enough. Hence,

$\textup{wir}^{k}_{X\to Y}(n)\gtrsim n^{r/p}\ln(n)^{(s-q)/p}.$

If $p=0$, then by $\eqref{eq:sepwirbd}$ there is some $C>0$ such that

$\displaystyle C^{-1-r}n^{r}\ln(C^{-1}n)^{s}-C$ $\displaystyle\leq$
$\displaystyle\sum_{i=0}^{\ln(\textup{wir}^{k}_{X\to
Y}(n))}\ln\left(2^{-i}\textup{wir}^{k}_{X\to Y}(n)\right)^{q}$
$\displaystyle\leq$ $\displaystyle\ln\left(\textup{wir}^{k}_{X\to
Y}(n)\right)^{q+1},$

Hence $\textup{wir}^{k}_{X\to Y}(n)\gtrsim\exp(n^{r/(q+1)}\ln(n)^{s/(q+1)})$.
∎

##  6 Completing Theorems 1.7, 1.4 and 1.5

In this section we give complete proofs of the main results of the paper.

###### Proof of Theorem 1.7.

Let $M=\mathbb{H}^{q}_{F}\times\mathbb{R}^{r}$ and let $Y$ be a bounded degree
graph which is quasi-isometric to $M$. Fix $d\in\mathbb{N}$ and
$\delta,\epsilon>0$. Enumerate the set of finite graphs with maximal degree
$d$ and Cheeger constant $\geq\delta$ by $\Gamma_{1},\Gamma_{2},\ldots$, with
$|\Gamma_{i}|\leq|\Gamma_{j}|$ whenever $i\leq j$. Let $X$ be the disjoint
union of all the $\Gamma_{i}$. If $X$ is finite, there is nothing to prove. By
[Hum17, Proposition 2.4],
$\textup{sep}_{X}(|\Gamma_{i}|)\geq\frac{\delta}{2}|\Gamma_{i}|$ for all $i$.
Set $Q=(q+1)\dim_{\mathbb{R}}(F)-2$, the conformal dimension of the boundary
of $\mathbb{H}^{q}_{F}$. We have $\textup{sep}_{Y}(n)\simeq
n^{1-1/(r+1)}\ln(n)^{1/(r+1)}$ if $Q=1$ and $\textup{sep}_{Y}(n)\simeq
n^{1-1/(Q+r-1)}$ if $Q\geq 2$, so by Corollary 5.4, for each $k$ there exists
a constant $C$ such that for all $i$,

$\textup{wir}^{k}_{X\to
Y}(|\Gamma_{i}|)\geq\left\\{\begin{array}[]{rcl}C^{-1}|\Gamma_{i}|^{1+1/r}\ln(1+|\Gamma_{i}|)^{-1/r}-C&\textup{if}&Q=1,\\\
C^{-1}|\Gamma_{i}|^{1+1/(Q+r-1)}-C&\textup{if}&Q\geq 2.\end{array}\right.$
(12)

We continue with the $Q=1$ case, the argument for $Q\geq 2$ is very similar.
Now suppose for a contradiction that for every $n$ there is some
$\epsilon$-thick embedding $\Gamma_{i_{n}}\to M$ with volume at most
$\frac{1}{n}|\Gamma_{i}|^{1+1/r}\ln(1+|\Gamma_{i}|)^{-1/r}$. By Proposition
1.10, there is a coarse $k$-wiring of $\Gamma_{i_{n}}$ into $Y$ with volume at
most

$\frac{k}{n}|\Gamma_{i}|^{1+1/r}\ln(1+|\Gamma_{i}|)^{-1/r}$

for some $k=k(d,M,\varepsilon,Y)$. This contradicts $\eqref{eq:wirlbrk1}$ for
large enough $n$. ∎

###### Proof of Theorem 1.4.

Let $\Gamma$ be a finite graph with maximal degree $d$. By Theorem 1.18 there
is a $2d$-coarse wiring of $\Gamma$ into a Cayley graph of
$\mathbb{Z}_{2}\wr\mathbb{Z}$ with volume $\leq
4d|\Gamma|\lceil\log_{2}(1+|\Gamma|)\rceil$. This Cayley graph is quasi-
isometric to $\textup{DL}(2,2)$ [Woe05], and $\textup{DL}(2,2)$ quasi-
isometrically embeds into any graph $X$ quasi-isometric to a symmetric space
whose non-compact factor has rank $\geq 2$ [HMT22, Proposition 2.8 and Theorem
3.1]. Thus, for some $l$ we have

$\textup{wir}^{l}_{\Gamma\to X}\leq C^{\prime}N\ln(1+N).\qed$

###### Proof of Theorem 1.5.

The proof is the same as for Theorem 1.7 replacing (12) with

$\textup{wir}^{k}_{Y\to X}(|\Gamma_{i}|)\geq
C^{-1}|\Gamma_{i}|\ln(1+|\Gamma_{i}|)-C.\qed$

###  6.1 Coarse wirings into two dimensional symmetric spaces

In this section we collect results about coarse wirings into $\mathbb{R}^{2}$
and $\mathbb{H}^{2}_{\mathbb{R}}$. The first is a direct construction of a
coarse wiring, the second a thick embedding into
$\mathbb{H}_{\mathbb{R}}^{2}\times[0,1]$ which is quasi-isometric to
$\mathbb{H}^{2}_{\mathbb{R}}$.

######  Proposition 6.1.

Every $N$-vertex graph with maximal degree $d$ admits a coarse $2d$-wiring
into the standard $2$-dimensional integer lattice $\mathbb{Z}^{2}$ with volume
at most $N^{2}$.

Let $X$ be the disjoint union of all finite graphs with maximal degree $3$.
For any $k$ there is some $C$ such that
$\textup{wir}^{k}_{X\to\mathbb{Z}^{2}}(n)\geq C^{-1}n^{2}-C$.

###### Proof.

The second claim follows immediately from Corollary 5.4 and the fact that
$\textup{sep}_{X}(n)\simeq n$ [Hum17] and
$\textup{sep}_{\mathbb{Z}^{2}}(n)\simeq n^{1/2}$ [BST12].

Let $\Gamma$ be an $n$-vertex graph with maximal degree $d$. Enumerate the
vertices of $\Gamma$ by $v_{0},\ldots,v_{n-1}$. We construct a $d$-wiring of
$\Gamma$ into $\\{0,\ldots,n-1\\}^{2}$ as follows:

Map the vertex $v_{k}$ to the point $(k,k)$. For each edge $v_{i}v_{j}$ (with
$i<j$) we define a path $P_{ij}$ which travels horizontally from $(i,i)$ to
$(j,i)$, then vertically from $(j,i)$ to $(j,j)$.

To see that this is a $1$-thick embedding, note that if a horizontal edge
$(a,b)(a+1,b)$ is in $P_{ij}$ then $b=i$. Similarly, if a vertical edge
$(a,b)(a,b+1)$ appears in $P_{ij}$, then $a=j$. Hence, any two paths
containing a common edge have a common end vertex. Since, by assumption, there
are at most $d$ edges with a given end vertex, we have defined a coarse
$2d$-wiring. The volume estimate is obvious. ∎

######  Proposition 6.2.

Let $Y$ be a graph which is quasi-isometric to $\mathbb{H}_{\mathbb{R}}^{2}$
and let $d\in\mathbb{N}$. There are constants $k=k(Y,d)$ and $C=C(Y,d)$ such
that any $N$-vertex graph $\Gamma$ with maximal degree $d$ admits a coarse
$k$-wiring into $Y$ with volume $\leq CN^{2}\exp(N)$.

Let $X$ be the disjoint union of all finite graphs with maximal degree $3$.
For any $k$ there is some $C$ such that $\textup{wir}^{k}_{X\to Y}(n)\geq
C^{-1}\exp(C^{-1}n^{1/2}))-C$.

###### Proof.

The second claim follows immediately from Corollary 5.4 and the fact that
$\textup{sep}_{X}(n)\simeq n$ [Hum17] and
$\textup{sep}_{\mathbb{H}_{\mathbb{R}}^{2}}(n)\simeq\ln(n)$ [BST12].

We will construct $1$-thick embeddings
$K_{N}\to\mathbb{H}_{\mathbb{R}}^{2}\times[0,1]$ with volume $\leq
C^{\prime}N^{2}\exp(N)$. Since $Y$ is quasi-isometric to
$\mathbb{H}_{\mathbb{R}}^{2}\times[0,1]$, the result will then follow from
Proposition 1.10.

Firstly, recall the definition of the metric in the upper halfspace model of
$\mathbb{H}_{\mathbb{R}}^{2}$:

$d_{\mathbb{H}_{\mathbb{R}}^{2}}((x_{1},y_{1}),(x_{2},y_{2}))=\cosh^{-1}\left(1+\frac{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}{2y_{1}y_{2}}\right).$

We equip $\mathbb{H}_{\mathbb{R}}^{2}\times[0,1]$ with the metric

$d((w,x;a),(y,z;b))=\max\\{d_{\mathbb{H}_{\mathbb{R}}^{2}}((w,x),(y,z)),|a-b|\\}.$

Let us define $h_{0}:=(2(\cosh(1)-1)^{-1/2}>1$.

Claim: If $d((w,x;a),(y,z;b))<1$ and $x,z\leq h_{0}$, then $|a-b|<1$,
$|w-y|<1$ and $|\ln(x/h_{0})-\ln(z/h_{0})|<1$.

###### Proof of Claim.

It is immediate from the definition that $|a-b|<1$. Since $x,z\leq h_{0}$,

$\displaystyle 1$ $\displaystyle>$ $\displaystyle d((w,x;a),(y,z;b))$
$\displaystyle\geq$ $\displaystyle
d_{\mathbb{H}_{\mathbb{R}}^{2}}((w,x),(y,z))$ $\displaystyle\geq$
$\displaystyle\cosh^{-1}\left(1+\frac{(w-y)^{2}}{2h_{0}^{2}}\right)$
$\displaystyle\geq$ $\displaystyle\cosh^{-1}(1+(\cosh(1)-1)(w-y)^{2}).$

Hence $(w-y)^{2}<1$, so $|w-y|<1$. Finally, write $x=h_{0}e^{p}$ and
$z=h_{0}e^{q}$ with $p,q\in\mathbb{R}$. We have

$\displaystyle 1$ $\displaystyle>$ $\displaystyle d((w,x;a),(y,z;b))$
$\displaystyle\geq$ $\displaystyle
d_{\mathbb{H}_{\mathbb{R}}^{2}}((w,x),(y,z))$ $\displaystyle\geq$
$\displaystyle\cosh^{-1}\left(1+\frac{h_{0}^{2}(e^{p}-e^{q})^{2}}{2h_{0}^{2}e^{p+q}}\right)$
$\displaystyle=$
$\displaystyle\cosh^{-1}\left(\frac{1}{2}(e^{p-q}+e^{q-p})\right)=|p-q|.$

Hence $|\ln(x/h_{0})-\ln(z/h_{0})|=|p-q|<1$. ∎

Enumerate the vertices of $K_{N}$ by $v_{0},\ldots,v_{N-1}$. We map $v_{i}$ to
$(i,h_{0}e^{-i};0)$ where $h_{0}=(2(\cosh(1)-1)^{-1/2}$. For $i<j$, we connect
$(i,h_{0}e^{-i};0)$ to $(j,h_{0}e^{-j};0)$ using the path $P_{ij}$ defined as
follows:

$\displaystyle(i,h_{0}e^{-i};0)$ $\displaystyle\to$
$\displaystyle(j,h_{0}e^{-i};0)$ (13) $\displaystyle\to$
$\displaystyle(j,h_{0}e^{-i};1)$ (14) $\displaystyle\to$
$\displaystyle(j,h_{0}e^{-j};1)$ (15) $\displaystyle\to$
$\displaystyle(j,h_{0}e^{-j};0)$ (16)

where the first segment lies in the horocircle $y=h_{0}e^{-i}$ and the others
are geodesics.

We first prove that this embedding is $1$-thick. Let $(w,x;a)\in P_{ij}$ and
$(y,z;b)\in P_{kl}$ with $d((w,x;a),(y,z;b))<1$. Set $p=\ln(x/h_{0})$ and
$q=\ln(z/h_{0})$. From the claim we have $\max\\{|w-y|,|p-q|,|a-b|\\}<1$.

If $a=1$, then $b>0$, so $w=j$ and $y=l$. Since $w,y$ are both integers they
must be equal. Thus $j=l$ and the two paths come from edges which share a
vertex.

If $a\in(0,1)$ then $w=j$ and $p\in\\{-i,-j\\}$. Note that one of the four
equalities $y=k$, $y=l$, $q=-k$, $q=-l$ holds at every point on $P_{kl}$. If
it one of the first two, then $\min\\{|j-k|,|j-l|\\}<1$ and $j\in\\{k,l\\}$,
or if it is one of the last two, then one of $-i,-j$ is equal to one of
$-k,-l$. In any case the two paths share an end vertex.

If $a=0$ then either $p=-i$ or $w=j$ and $p=-j$. Also $b<1$ so either $q=-k$
or $y=l$ and $q=-l$. If $p=-i$, then either $q=-k$ in which case $|-i-(-k)|<1$
by the claim, thus $i=k$; or $q=-l$ in which case $i=l$ by the same reasoning.
Next, suppose $w=j$ and $p=-j$. Since $q\in\\{-k,-l\\}$ we have $j=k$ or
$j=l$. If $p=-i$, $y=l$ and $q=-l$, then $i=l$ following the same reasoning.

Every point in the image of the embedding is of the form $(x,h_{0}e^{-y};z)$
where $|x|,|y|\leq n-1$ and $z\in[0,1]$. Set
$p=\left(\frac{n-1}{2},h_{0};\frac{1}{2}\right)$. We have

$\displaystyle d\left((x,h_{0}e^{-y};z),p\right)$ $\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(1+\frac{\left(\frac{n-1}{2}\right)^{2}+h_{0}^{2}(1-e^{n-1})^{2}}{2h_{0}^{2}e^{-(n-1)}}\right)+\frac{1}{2}$
$\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(1+\frac{\frac{n^{2}}{4}+h_{0}^{2}}{2h_{0}^{2}e^{-(n-1)}}\right)+\frac{1}{2}$
$\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(1+(\frac{n^{2}}{8}+1)e^{n-1}\right)+\frac{1}{2}$
$\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(\frac{\frac{17n^{2}}{8}e^{n-1}}{2}\right)+\frac{1}{2}$
$\displaystyle\leq$
$\displaystyle\cosh^{-1}\left(\cosh(n-1+2\ln(n)+\ln(17)-\ln(8))\right)+\frac{1}{2}$
$\displaystyle=$ $\displaystyle n-1+2\ln(n)+\ln(17)-\ln(8)+\frac{1}{2}\leq
n+2\ln(n)$

Thus, the volume of the wiring is at most $4\pi\sinh^{2}((n+2\ln(n)+1)/2)$:
the volume of the ball of radius $n+2\ln(n)+1$ in
$\mathbb{H}_{\mathbb{R}}^{2}$. We have

$\displaystyle 4\pi\sinh^{2}((n+2\ln(n)+1)/2)$ $\displaystyle\leq$
$\displaystyle 4\pi\left(\frac{\exp((n+2\ln(n)+1)/2)}{2}\right)^{2}$
$\displaystyle\leq$ $\displaystyle\pi\exp(n+2\ln(n)+1)$ $\displaystyle=$
$\displaystyle e\pi n^{2}e^{n}\simeq e^{n}$

as required. ∎

##  7 Questions

One possible way to improve our bounds on thick embeddings of graphs into
other symmetric spaces whose non-compact factor has rank one is via
constructions of thick embeddings into nilpotent Lie groups. A positive
resolution to the following question would show that the lower bounds from
Theorem 1.7 are sharp whenever $Q\geq 2$.

######  Question 7.1.

Let $P$ be a connected nilpotent Lie group with polynomial growth of degree
$p\geq 3$ and let $d\in\mathbb{N}$. Do there exist constants $C,\varepsilon>0$
which depend on $p,d$ such that for any $N$-vertex graph $\Gamma$ with maximal
degree $d$ there is a $\varepsilon$-thick embedding of $\Gamma$ into $P$ with
diameter $\leq CN^{1/(p-1)}$?

Another important example worthy of consideration is a semidirect product of
the Heisenberg group with $\mathbb{R}$, $H\rtimes_{\psi}\mathbb{R}$ where the
action is given by

$\left(\begin{array}[]{ccc}1&x&z\\\ 0&1&y\\\
0&0&1\end{array}\right)\cdot\psi(t)=\left(\begin{array}[]{ccc}1&e^{t}x&z\\\
0&1&e^{-t}y\\\ 0&0&1\end{array}\right).$

######  Conjecture 7.2.

For every $d$ there exist constants $C=C(d)$ and $\varepsilon=\varepsilon(d)$
such that every finite graph $\Gamma$ with maximal degree $d$ admits a
$\varepsilon$-thick embedding into $H\rtimes_{\psi}\mathbb{R}$ with volume
$\leq C|\Gamma|\ln(1+|\Gamma|)$.

An immediate consequence of this conjecture is that the dichotomy at the heart
of [HMT22] is also detected by wiring profiles. Specifically, let $G$ be a
connected unimodular Lie group, let $Y$ be a graph quasi-isometric to $G$ and
let $X$ be the disjoint union of all finite graphs with degree $\leq 3$.
Either $G$ is quasi-isometric to a product of a hyperbolic group and a
nilpotent Lie group, in which case there is some $p>1$ such that for all $k$
sufficiently large $\textup{wir}^{k}_{X\to Y}(N)\gtrsim N^{p}$; or $G$
contains a quasi-isometrically embedded copy of either $\textup{DL}(2,2)$ or
$H\rtimes_{\psi}\mathbb{R}$, in which case for all $k$ sufficiently large
$\textup{wir}^{k}_{X\to Y}(N)\simeq N\ln(N)$.

The lower bound from separation profiles is incredibly useful, and our best
results are all in situations where we can prove that the lower bound in
Theorem 1.17 is optimal. As a result it is natural to record the following:

######  Question 7.3.

For which bounded degree graphs $Y$ does the following hold:

Let $X$ be the disjoint union of all finite graphs with maximal degree $\leq
3$. For all $k$ sufficiently large

$\textup{sep}_{Y}(\textup{wir}^{k}_{X\to Y}(N))\simeq N.$

A starting point would be to determine when the following strengthening of
Proposition 5.3 holds:

######  Question 7.4.

Let $X,Y$ be graphs of bounded degree where $\textup{wir}^{k}_{X\to
Y}(n)<\infty$. Does there exist a constant $C>0$ such that for all $n$

$\textup{sep}_{Y}(\textup{wir}^{k}_{X\to Y}(n))\geq
C^{-1}\textup{sep}_{X}(C^{-1}n)-C?$

We certainly should not expect Theorem 1.17 give the correct lower bound in
all cases. A natural example to consider would be a coarse wiring of an
infinite binary tree $B$ into $\mathbb{Z}^{2}$. The depth $k$ binary tree
$B_{k}$ (with vertices considered as binary strings $v=(v_{1},v_{2},\ldots
v_{m})$ of length $\leq k$) admits a $1$-wiring into $\mathbb{Z}^{2}$ with
volume $\lesssim|B_{k}|\ln|B_{k}|$ as follows

$\psi(v_{1},v_{2},\ldots v_{l})=\left(\sum_{i\in\\{l\mid
v_{l}=0\\}}2^{k-i},\sum_{j\in\\{l\mid v_{l}=1\\}}2^{k-i}\right)$

where the path connecting $\psi(v_{1},v_{2},\ldots v_{l})$ to
$\psi(v_{1},v_{2},\ldots v_{l},0)$ (respectively $\psi(v_{1},v_{2},\ldots
v_{l},1)$) is a horizontal (resp. vertical) line.

######  Question 7.5.

Is it true that for all sufficiently large $k$,
$\textup{wir}^{k}_{B\to\mathbb{Z}^{2}}(N)\simeq N\ln(N)$? Does the lower bound
hold for all coarse wirings $X\to Y$ where $X$ has exponential growth and $Y$
has (at most) polynomial growth?

Since the first version of this paper appeared, this question has been
resolved by Kelly [Kel23], who proved the slightly surprising result that
$\textup{wir}^{1}_{T_{3}\to\mathbb{Z}^{2}}(N)\simeq N$.

It is also natural to ask whether other invariants which behave monotonically
with respect to coarse embedding (and regular maps) provide lower bounds on
wiring profiles.

##  Appendix A Appendix: The Kolmogorov-Barzdin Embedding Theorem in Higher
Dimensions

The goal of this appendix is to prove Theorem 1.3. The main theorem roughly
says that if we have a graph of bounded degree with $V$ vertices, then we can
embed it into an $n$-dimensional Euclidean ball of radius $V^{1/(n-1)}$
without too many edges or vertices intersecting any unit ball. Kolmogorov and
Barzdin proved the theorem in dimension 3 and Guth sketched a proof that
showed how their method generalized to higher dimensions in the language of
thick embeddings. In this appendix we present a full proof using the language
of coarse wirings introduced in the present paper.

######  Theorem A.1.

[KB93],[Gu16] Let $Q^{1}_{r}$ be the path graph with $r$ vertices, and let

$Q^{n}_{r}=Q^{1}_{r}\times Q^{1}_{r}\times\ldots Q^{1}_{r}$

where the graph product is taken $n$ times. If $\Gamma$ is a graph where every
vertex has degree at most $k$, then for some integer $C>0$ that only depends
on $n$ and $k$, and $R=\lceil|V\Gamma|^{\frac{1}{n-1}}\rceil$ there is a
coarse $(k+n)$-wiring,

$f:\Gamma\to Q^{n}_{2CR}.$

Here, the graph product $\Gamma_{1}\times\ldots\times\Gamma_{n}$ is the graph
with vertex set $V\Gamma_{1}\times\ldots\times V\Gamma_{n}$ and edges
$(v_{1},\ldots,v_{n}),(w_{1},\ldots,w_{n})$ whenever there is some $j$ such
that $v_{j}w_{j}\in E\Gamma_{j}$ and $v_{i}=w_{i}$ for all $i\neq j$.

The proof of Theorem 1.3 follows immediately from Theorem A.1 by first
applying 1.11, then rescaling by a factor of $\varepsilon^{-1}$.

We say a few words about our strategy for constructing $f$. If we think of
$Q^{n}_{2CR}$ as a graph embedded in an $n$-cube, then our $f$ maps the
vertices of $\Gamma$ into some face of this cube. The edges of $\Gamma$ are
mapped to paths which each consist of $O(n)$ straight segments of randomly
chosen lengths. It turns out that this $O(n)$ freedom is enough to guarantee
that, with non-zero probability, there is no edge of $Q^{n}_{2CR}$ where too
many of these paths overlap.

In the next section we provide a proof of Theorem A.1 following [Gu16].

##  Appendix B Proof of Theorem A.1

###### Proof.

Let $C$ be some large constant, only depending on $n$, which we will choose
later. We can think of $Q^{n}_{2CR}$ as a graph embedded in the cube
$[0,2CR]^{n}$, where each edge has length $1$. We let $Q^{n-1}_{R}$ be a graph
embedded in the bottom face of this cube. Namely, $Q^{n-1}_{R}$ sits inside
$[0,CR]^{n-1}\times 0\subset[0,2CR]^{n}$, with each edge having length $C$.
Begin by defining $f$ on $V\Gamma$ by embedding all the vertices of $\Gamma$
into $Q^{n-1}_{R}$ in any way we like. Such an embedding is possible since
$R^{n-1}$ is larger than $|V\Gamma|$.

Next we have to extend $f$ to the edges of $\Gamma$. Give the edges of
$\Gamma$ some order, say $\\{e_{i}\\}_{i=1}^{|E\Gamma|}$, and let the
endpoints of $e_{i}$ be $x_{i,-}\in V\Gamma$ and $x_{i,+}\in V\Gamma$. For
many values of $j$, we will construct paths $\gamma(i,j)$ from $f(x_{i,+})$ to
$f(x_{i,-})$. Each $\gamma(i,j)$ will consist of $(2n-1)$ straight segments.
We select $f(e_{1})$ from among the paths $\gamma(1,j)$. Next we select
$f(e_{2})$ from among the paths $\gamma(2,j)$, making sure it does not pass
too close to $\gamma(1,j)$. And so on. At step $i$, we have to see that one of
the paths $\gamma(i,j)$ stays far enough away from the previous paths
$f(e_{1}),\ldots f(e_{i-1})$. In fact, we will show that at step $i$, if we
choose $j$ randomly, the probability that $\gamma(i,j)$ comes too close to one
of the previous paths is less than one half.

To define these paths we will use $x_{i}$ to refer the $i$th coordinate
direction in $[0,2CR]^{n}$. For a set of $n$ integers $j=\\{j_{0},j_{1},\ldots
j_{n-1}\\}\in([0,CR]\cap\mathbb{Z})^{n-1}$ the path $\gamma(i,j)$ has the
following form. Starting at $f(x_{i,+})$, we first draw a segment in the
$x_{n}$ direction with length $j_{0}$. Next we draw a segment in the $x_{1}$
direction with length $j_{1}$. Then we draw a segment in the $x_{2}$ direction
with length $j_{2}$. We continue in this way up to a segment in the $x_{n-2}$
direction of length $j_{n-2}$. We have $(CR+1)^{n-1}$ choices for $j$. Then we
draw a segment in the $x_{n-1}$ direction which ends at the $x_{n-1}$
coordinate of $f(x_{i,-})$. Then we draw a segment in the $x_{n-2}$ direction
which ends at the $x_{n-2}$ coordinate of our target $f(x_{i,-})$, etc.
Finally, we draw a segment in the $x_{n}$ direction which ends at
$f(x_{i,-})$.

We claim that we can choose $j$ so that $\gamma(i,j)$ only intersects
previously selected $f(e_{i})$ in the $x_{n}$ direction or intersects them
perpendicularly. Since each path is made of segments that point in the
coordinate directions, we just have to check that none of the segments
intersects a segment of a previous path going in the same direction. Call a
segment bad if it intersects a segment from a previous path going in the same
direction.

The initial segment of $\gamma(i,j)$, in the $x_{n}$ direction, can intersect
at most $k$ segments in the same direction of $f(e_{1})\ldots f(e_{i-1})$
because $f$ is an embedding on $V\Gamma$ and $\Gamma$ has degree at most $k$
at each vertex. Consider the first segment in the $x_{1}$ direction. On this
segment, the $2\ldots(n-1)$ coordinates are equal to those of $f(x_{i,+})$.
This segment can intersect an $x_{1}$ segment of a previous path
$f(e_{i^{\prime}})$ only if $f(x_{i,+})$ has the same $2\ldots(n-1)$
coordinates as $f(x_{i^{\prime},+})$ or $f(x_{i^{\prime},-})$. This leaves at
most $2Rk$ worrisome values of $i^{\prime}$. But on this segment of
$\gamma(i,j)$, the $n$ coordinate is fixed equal to $j_{0}$. This segment is
bad only if it has the same $x_{n}$ coordinate as a segment in the $x_{1}$
direction in one of the $2Rk$ worrisome values of $i^{\prime}$. But there are
$CR$ choices for $j_{0}$. So, choosing $(j_{0},\ldots,j){n-1})$ uniformly at
random, the probability that this first segment is bad is at most
$\frac{2k}{C}$.

A similar argument holds for the the second segment. This $x_{2}$ segment can
intersect a previous path $f(e_{i^{\prime}})$ only if $f(x_{i,+})$ has the
same $3\ldots(n-1)$ coordinates as $f(x_{i^{\prime},+})$ or
$f(x_{i^{\prime},-})$. This leaves at most $(2Rk)^{2}$ worrisome values of
$i^{\prime}$ . But there are $(CR)^{2}$ choices for $(j_{0},j_{1})$. So the
probability that the second segment is bad is at most $(\frac{2k}{C})^{2}$.

The same reasoning applies for the first $n$ segments. And in fact the same
reasoning applies for the following $n$ segments as well. For instance,
consider the second (and last) segment in the $x_{1}$ direction. Over the
course of this segment, the $2\ldots(n-1)$ coordinates are equal to those of
$f(x_{i,-})$, and so this segment can intersect a segment in the $x_{1}$
direction of a previous path $f(e_{i^{\prime}})$ only if $f(x_{i,-})$ has the
same $2\ldots(n-1)$ coordinates as $f(x_{i^{\prime},+})$ or
$f(x_{i^{\prime},-})$. This leaves at most $2Rk$ worrisome values of
$i^{\prime}$. But there are more than $CR$ choices of $j_{0}$, and so the
probability that this segment is bad is at most $\frac{2k}{C}$. In summary,
there are $2n-1$ segments, and each has probability at most $\frac{2k}{C}$ of
being bad, if $C$ is large. So, by a union bound, for some large $C$ only
depending on $n$ and $k$, more than half the time, all segments in directions
$x_{1}\ldots x_{n-1}$ are good. This gives us a path $f(e_{i})$ which
intersects at most $k$ paths in segments in the $x_{n}$ direction, and
intersects all other previous paths perpendicularly. From the construction, we
see that at most $(k+n)$ of the paths we choose intersect any vertex or edge
of $Q^{n}_{2CR}$. In other words, $f$ is a $(k+n)$-coarse wiring. ∎

## References

  * [BST12] I. Benjamini, O. Schramm, and Á. Timár.  On the separation profile of infinite graphs.  Groups Geom. Dyn., 6(4):639–658, 2012.
  * [GG12] M. Gromov and L. Guth.  Generalizations of the Kolmogorov-Barzdin embedding estimates.  _Duke Math. J._ , 161(13):2549–2603, 2012.
  * [Gu16] L. Guth.  Recent progress in quantitative topology.  _Surveys in Differential Geometry_ , 22(1):191–216, 2017.
  * [Hum17] D. Hume.  A continuum of expanders.  Fund. Math., 238:143–152, 2017.
  * [HMT20] D. Hume, J. M. Mackay, and R. Tessera.  Poincaré profiles of groups and spaces.  Rev. Math. Iberoam., 36(6):1835–1886, 2020.
  * [HMT22] D. Hume, J. M. Mackay, and R. Tessera.  Poincaré profiles of Lie groups and a coarse geometric dichotomy.  GAFA, 32:1063–1133, 2022.
  * [Kel23] S. Kelly.  A Topological Embedding of the Binary Tree into the Square Lattice  Preprint available from arXiv:2311.13195.
  * [KB93] A. N. Kolmogorov and Y. M. Barzdin.  On the realization of networks in three-dimensional space.  In _Selected Works of Kolmogorov_ , Kluwer, Dordrecht, 3:194–202, 1993.
  * [Lo21] F. López, B. Pozzetti, S. Trettel, M. Strube and A. Wienhard.  Symmetric Spaces for Graph Embeddings: A Finsler-Riemannian Approach.  Proceedings of the 38th International Conference on Machine Learning, PMLR 139, 2021.
  * [Pan89] P. Pansu.  Dimension conforme et sphère à l’infini des variétés à courbure négative.  Ann. Acad. Sci. Fenn. Ser. A I Math., 14(2):177–212, 1989.
  * [Ra23] R. Raistrick.  Dependence of the coarse wiring profile on the choice of parameter.  Preprint available from arXiv:2311.08436.
  * [Woe05] W. Woess.  Lamplighters, Diestel-Leader graphs, random walks, and harmonic functions.  Combin. Probab. Comput., 14(3):415–433, 2005.