Convergence of combinatorial gravity

We shall throughout be concerned with metric spaces. For a set $X$, a metric on $X$ will be denoted $\rho_{X}$ unless we specify otherwise. The open ball of radius $r>0$ centred at a point $x\in X$ is denoted

$\displaystyle B_{r}^{X}(x)=\set{y\in X:\rho_{X}(x,y)<r}.$

(1)

The boundary of this ball is then given

$\displaystyle\partial B_{r}^{X}(x)=\set{y\in X:\rho_{X}(x,y)=r}.$

(2)

Later on we shall be concerned with the shell or annulus of radius $R$ and width $r$ centred at $x\in X$, which is defined as the set

$\displaystyle S_{R,r}^{X}(x)=B_{R+r}^{X}(x)\backslash B_{R-r}^{X}(x).$

(3)

We shall use a special notation for Euclidean space $\mathbb{R}^{D}$: the metric is denoted $\rho_{D}$, an open ball of radius $R$ and centre $x\in\mathbb{R}^{D}$ by $B_{r}^{D}(x)$, and the annulus of radius $R$, width $r$ and centre $x\in X$ by $S_{R,r}^{D}(x)$. We also let $B_{r}^{D}:=B_{r}^{D}(0)$ and $S_{R,r}^{D}:=S_{R,r}^{D}(0)$. The volume form on $\mathbb{R}^{D}$ will be denoted ${\rm vol}_{D}$. The volume of the unit ball in $\mathbb{R}^{D}$ is denoted by $\omega_{D}$. The unit $(D-1)$-sphere is the subset of unit vectors in $\mathbb{R}^{D}$ and will be denoted $\mathbb{S}^{D-1}$. For any two points $x_{1},\>x_{2}\in\mathbb{R}^{D}$, we let $\theta_{D}(x_{1},x_{2})$ denote the angle $\angle x_{1}Ox_{2}$ with $O$ the origin; by the cosine rule we have

$\displaystyle\theta_{D}(x_{1},x_{2})=\arccos\left(\frac{||x_{1}||^{2}+||x_{2}||^{2}-||x_{1}-x_{2}||^{2}}{2||x_{1}||\cdot||x_{2}||}\right).$

(4)

It will be convenient to introduce the function $\mathfrak{d}~{}:~{}\mathbb{R}^{D}\backslash\set{0}~{}\rightarrow~{}\mathbb{R}$ which gives the scale factor of the spherical volume element of the normalisation of its argument in Cartesian coordinates: let $x~{}=~{}(R,\varphi_{1},...,\varphi_{D-1})\in\mathbb{R}^{D}\backslash\set{0}$ in spherical coordinates; then

$\displaystyle\mathfrak{d}(x)=\sin^{D-2}(\varphi_{1})\sin^{D-3}(\varphi_{2})\cdots\sin(\varphi_{D-2}).$

(5)

We extend this function to all of $\mathbb{R}^{D}$ by choosing $\mathfrak{d}(0)=0$.

$G$ will always denote a graph, by which we mean a finite, simple, connected, weighted graph. Also $N=|G|$ for the rest of the text. The weights will be given by a weight function $w_{G}:E(G)\rightarrow\mathbb{R}$, where $E(G)$ is the set of edges of $G$. $G$ may be regarded as a metric space, equipped with its geodesic distance: the length of a path $\gamma_{u,v}=v_{0}\cdots v_{n}$ between the vertices $u=v_{0}$ and $v=v_{n}$ is defined as

$\displaystyle L(\gamma_{u,v})=\sum_{k=0}^{n-1}|w(v_{k}v_{k+1})|.$

(6)

Then

$\displaystyle\rho_{G}(u,v)=\inf_{\gamma_{u,v}}L(\gamma_{u,v})$

(7)

where the infimum is taken over all paths $\gamma_{u,v}$ between $u$ and $v$. With this metric $G$ has the discrete topology, i.e. every subset of $G$ is open and hence Borel measurable. We shall assume $G$ is equipped with a natural measure of the volume of a subset given by the counting measure: $|E|$ is the number of points in $E\subseteq G$.

Similarly, $\mathcal{M}$ will always denote a $D$-dimensional Riemannian manifold which is implicitly equipped with some Riemannian metric. This means in particular for each $p\in\mathcal{M}$ we have an inner product $\braket{\cdot,\cdot}_{p}$ on the tangent space $T_{p}\mathcal{M}$; we use the notation $||\cdot||_{p}$ for the associated norm. The angle between two vectors $V_{1},:V_{2}\in T_{p}\mathcal{M}$ is defined

$\displaystyle\theta_{p}^{\mathcal{M}}(V_{1},V_{2})=\arccos\left(\frac{\braket{V_{1},V_{2}}_{p}}{||V_{1}||_{p}\cdot||V_{2}||_{p}}\right).$

(8)

We assume that these local inner products vary smoothly over $\mathcal{M}$ and as such extend immediately to an inner product $\braket{\cdot,\cdot}$ on smooth vector fields of $\mathcal{M}$. Associated to the inner product is a unique metric compatible affine connection $\nabla$ known as the Levi-Civita connection. This defines a notion of differentiation on vector fields on $\mathcal{M}$. Associated to this connection is also a natural volume form ${\rm vol}_{\mathcal{M}}$, and Riemmann, Ricci and scalar curvatures tensors, denoted ${\rm Riem}$, ${\rm Ric}$ and $R$ respectively. A subscript $p\in\mathcal{M}$ on any of these tensors refers to the restriction of the tensor to the point $p\in\mathcal{M}$. The (Riemannian) Einstein-Hilbert action on $\mathcal{M}$ is defined

$\displaystyle\mathcal{A}_{EH}(\mathcal{M})$

$\displaystyle=\int_{\mathcal{M}}{\rm dvol}_{\mathcal{M}}(x)R(x).$

(9)

This action, of course, governs gravitational dynamics in general relativity and is certainly well-defined and finite if $\mathcal{M}$ is compact.

A smooth curve in $\mathcal{M}$ is a smooth mapping $\gamma:(a,b)\rightarrow\mathcal{M}$, where we assume $a<0<b$; we let the tangent vector to the curve at $t\in(a,b)$ be denoted by $\dot{\gamma}_{t}$. We say that a smooth curve $\gamma$ with domain $(a,b)$ connects $p\in\mathcal{M}$ to $q\in\mathcal{M}$ iff we have unique $c,:d\in(a,b)$ such that $p=\gamma(c)$, $q=\gamma(d)$ and $c\leq d$. The length of a curve $\gamma$ between $p$ and $q$ is then given

$\displaystyle L_{p,q}(\gamma)=\int_{t=c}^{t=d}{\rm dt}\braket{\dot{\gamma}_{t},\dot{\gamma}_{t}}_{\gamma(t)}.$

(10)

$\gamma$ is a geodesic iff $\nabla_{\dot{\gamma}_{t}}\dot{\gamma}_{t}=0$ for all $t\in{\rm dom}(\gamma)$; a geodesic is unit-speed off $||\dot{\gamma}_{t}||_{\gamma(t)}=1$ for all $t\in{\rm dom}(\gamma)$. $\mathcal{M}$ is a metric space when equipped with the geodesic distance:

$\displaystyle\rho_{\mathcal{M}}(p,q)=\inf L_{p,q}(\gamma)$

(11)

where the infimum is taken over all curves that connect $p$ and $q$. It turns out that for any point $p\in\mathcal{M}$ and any $V\in T_{p}\mathcal{M}$, there is a maximal domain $(a,b)\subseteq\mathbb{R}$ such that there is a unique geodesic $\gamma$ satisfying ${\rm dom}(\gamma)=(a,b)$, $\gamma(0)=p$ and $\dot{\gamma}_{0}=V$. By making $||\dot{\gamma}_{0}||_{p}=V$ smaller we may extend the domain $(a,b)$ such that for $V$ sufficiently small $1\in(a,b)$. Since the tangent vector $V$ identifies the geodesic uniquely, we can thus define a mapping $\exp_{p}$ known as the exponential map at $p\in\mathcal{M}$ via $\exp_{p}(V)=\gamma(1)$ where $\gamma$ is the unique geodesic such that $\gamma(0)=p$ and $\dot{\gamma}_{0}=V$. The domain of $\exp_{p}$ is some subset of $T_{p}\mathcal{M}$ that contains the origin. A metric ball in $T_{p}\mathcal{M}$ ($\mathcal{M}$) centred at the origin ($p\in\mathcal{M}$) will be called geodesic iff it is a subset of the domain (codomain) of the exponential map at $p$. Note that for sufficiently small balls about the origin in $\mathbb{R}^{D}$, the exponential map is smooth and a radial isometry: the latter in particular means that $\rho_{D}(0,x)=\rho_{\mathcal{M}}(p,\exp_{p}(x))$ for all $x$ sufficiently close to the origin.

Henceforth, we assume that $\mathcal{M}$ is complete, connected and without boundary. From section II.3 onwards, $\mathcal{M}$ will also be compact unless specified otherwise.

We shall use the big O notation—a little loosely—throughout to specify errors: for functions $f,\>g:U\rightarrow\mathbb{R}$, where $U\subseteq\mathbb{R}$ is some suitable subset, we write

$\displaystyle f(x)=\mathcal{O}(g(x))$

(12)

iff $|f(x)|<Kg(x)$ for some constant $K>0$ in some suitable limit of $x$. We are always concerned with limits of $x$ such that $g(x)\rightarrow 0$: typically when we specify $g$ in terms of the variable $x=N\in\mathbb{N}$, we are interested in the limit $N\rightarrow\infty$ and we have a typical form $g(N)=N^{-a}$ for some $a>0$. Otherwise we shall typically specify $x$ in terms of variables such as $\delta,\>\varepsilon,\>\ell$ etc. and we are interested in limits as these variables go to $0$.

The Ollivier curvature utilises ideas from optimal transport theory [57] for its construction so we begin with a review that follows closely the cited reference. We will also need some elementary ideas from measure theory and Riemannian geometry, e.g. c.f. [96, 97] for nice reviews. Finally, we will also use ideas from [63] in this section without much comment.

Let $(X,\rho_{X})$ be a complete separable metric space and let $\mathcal{P}(X)$ denote the set of Borel probability measures on $X$; every measure considered in this text will be of this type, i.e. defined on the Borel $\sigma$-algebra of a complete separable metric space. Recall that for any measurable spaces $(\Omega_{1},\Sigma_{1})$ and $\Omega_{2},\Sigma_{2})$, the pushforward of the measure $\mu:\Sigma_{1}\rightarrow\mathbb{R}$ under a measurable map $f:\Omega_{1}\rightarrow\Omega_{2}$ is defined as the measure

$\displaystyle f_{*}\mu(E)=\mu(f^{-1}(E))$

(13)

for all $E\in\Sigma_{2}$. The basic fact about pushforward measures is the following: let $f:\Omega_{1}\rightarrow\Omega_{2}$ be measurable and let $\mu$ be a Borel measure on $\Omega_{1}$. A mapping $g:\Omega_{2}\rightarrow\mathbb{C}$ is $f_{*}\mu$-integrable iff $g\circ f:X\rightarrow\mathbb{C}$ is $\mu$-integrable. Then

$\displaystyle\int_{\Omega_{1}}{\rm d}\mu(x)g(f(x))=\int_{\Omega_{2}}{\rm d}f_{*}\mu(y)g(y).$

(14)

The basic notion in optimal transport theory is that of a transport plan: for any $\mu,\>\nu\in\mathcal{P}(X)$, a transport plan between $\mu$ and $\nu$ is a probability measure $\xi$ on $X\times X$ such that

$\displaystyle(\pi_{1})_{*}\xi=\mu$

$\displaystyle(\pi_{2})_{*}\xi=\nu$

(15)

where $\pi_{1}:(x,y)\mapsto x$ and $\pi_{2}:(x,y)\mapsto y$ are the projections onto the first and second elements respectively. We refer to the equations 15 as marginal constraints and $\mu$ and $\nu$ are said to be marginals of the transport plan $\xi$. Roughly speaking, we may suppose we have a distribution $\mu$ of dirt on $X$ which we wish to transform into a distribution $\nu$; then given measurable subsets $E_{1},\>E_{2}\subseteq X$, the idea is that $\xi(E_{1}\times E_{2})$ denotes the amount of earth to be transported from $E_{1}$ to $E_{2}$ according to the transport plan $\xi$. The marginal constraints are required to ensure that we do indeed have the correct initial and final distributions and that no dirt is somehow lost in the process.

The space of all transport plans between $\mu$ and $\nu$ is denoted $\Pi(\mu,\nu)$. The transport cost of a transport plan $\xi\in\Pi(\mu,\nu)$ is defined

$$\mathcal{T}_{X}(\xi)=\int_{X\times X}{\rm d}\xi(x,y)\rho_{X}(x,y),$$

(16)

while the optimal transport cost is then given

$$\mathcal{T}_{X}(\mu,\nu)=\inf_{\xi\in\Pi(\mu,\nu)}\mathcal{T}_{X}(\xi).$$

(17)

This is also called the Wasserstein distance between $\mu$ and $\nu$. A transport plan $\xi\in\Pi(\mu,\nu)$ is said to be optimal iff $\mathcal{T}_{X}(\xi)=\mathcal{T}_{X}(\mu,\nu)$.

It can be shown that optimal transport plans always exist. Moreover, the mapping $\mathcal{T}:(\mu,\nu)\mapsto\mathcal{T}(\mu,\nu)$ is a metric on $\mathcal{P}(X)$, i.e. $\mathcal{T}$ is positive definite, symmetric and subadditive. There is a slight caveat in that $\mathcal{T}(\mu,\nu)$ is not necessarily finite, but this problem can be avoided if we restrict consideration to spaces with bounded diameter or only consider measures with finite first moment. For the purposes of this paper, both restrictions can in fact be assumed to hold. With this in mind, we note that the Wasserstein distance metrises the topology of weak convergence on the space of all probability measures with finite first moment.

A Riemannian $D$-manifold $\mathcal{M}$ can obviously be regarded as a metric space where the distance $\rho_{\mathcal{M}}(p,q)$ between two points $p,\>q\in\mathcal{M}$ is given by the length of the shortest geodesic between those points. Moreover, since $\mathcal{M}$ comes with a natural volume form ${\rm vol}$, we may define the uniform probability measures

$\displaystyle\mu_{p}^{\delta}(E)=\frac{{\rm vol}(B^{\mathcal{M}}_{\delta}(p)\cap E)}{{\rm vol}(B^{\mathcal{M}}_{\delta}(p))},$

(18)

for any pair $(p,\delta)\in\mathcal{M}\times(0,\infty)$, where $E$ is any (Borel) measurable set of $\mathcal{M}$. The idea is to specify the uniform measure with support given by (the closure of) the (open) ball $B^{\mathcal{M}}_{\delta}(p)$. Equipping $\mathcal{M}$ with such measures for each $p\in\mathcal{M}$ gives $\mathcal{M}$ the structure of a metric measure space, i.e. a metric space equipped with a (Markovian) random walk.

The basic connection between optimal transport and Ricci curvature arises in the following manner: let $p,\>q\in\mathcal{M}$ such that their geodesic distance $\ell=\rho_{\mathcal{M}}(p,q)$ is sufficiently small. For $\delta>0$ sufficiently small (i.e. for $\delta$ less than the injectivity radius), we may identify every point of $B_{\delta}^{\mathcal{M}}(p)$ with an element of $B_{\delta}^{D}\subseteq T_{p}\mathcal{M}\cong\mathbb{R}^{D}$ and similarly for $q$. Parallelly transporting $B_{\delta}^{\mathcal{M}}(p)$ along a minimal geodesic connecting $p$ and $q$ thus gives us a bijection $B_{\delta}^{\mathcal{M}}(p)\cong B_{\delta}^{\mathcal{M}}(q)$ which defines a so-called deterministic transport plan $\xi_{0}\in\Pi(\mu_{p}^{\delta},\mu_{q}^{\delta})$. It turns out that this transport plan is in fact optimal—at least up to negligible errors—i.e. $\mathcal{T}_{\mathcal{M}}(\mu_{p}^{\delta},\mu_{q}^{\delta})=\mathcal{T}_{X}(\xi_{0})$. A fairly basic application of the Jacobi equation, however, gives us the asympotic expression:

$\displaystyle\mathcal{T}_{\mathcal{M}}(\mu_{p}^{\delta},\mu_{q}^{\delta})=\ell\left(1+\frac{\delta^{2}{\rm Ric}_{p}(V,V)}{2(D+2)}+\mathcal{O}(\delta^{2}(\delta+\ell))\right),$

(19)

where $V$ is the velocity of the unique unit-speed geodesic connecting $p$ and $q$ at $p$. Thus, if we define the manifold Ollivier curvature by

$\displaystyle\kappa_{\mathcal{M}}^{\delta}(p,q)=1-\frac{\mathcal{T}_{\mathcal{M}}(\mu_{p}^{\delta},\mu_{q}^{\delta})}{\rho_{\mathcal{M}}(p,q)},$

(20)

we see that

$\displaystyle\kappa_{\mathcal{M}}^{\delta}(p,q)=\frac{\delta^{2}{\rm Ric}_{p}(V,V)}{2(D+2)}+\mathcal{O}(\delta^{2}(\delta+\ell)).$

(21)

In this sense, up to a scale-dependent factor and small corrections, the manifold Ollivier curvature gives the local Ricci curvature.

It should be clear that the manifold Ollivier curvature (Eq. 20) is determined by the metric-measure structure of $\mathcal{M}$ so we have the following generalisation: let $(X,\rho_{X})$ be a complete separable metric space equipped with a random walk $\set{\mu_{x}}_{x\in X}$. The Ollivier curvature of $X$ is then defined as the function

$\displaystyle\kappa_{X}(x,y)=1-\frac{\mathcal{T}_{X}(\mu_{x},\mu_{y})}{\rho_{X}(x,y)},$

(22)

on all sufficiently nearby but distinct points $x,\>y\in X$. Because the domain of $\kappa_{X}$ is not (necessarily) all of $X\times X$, it is convenient to regard $\kappa_{X}$ as a partial function on $X\times X$.

We finish this section by noting that the above definition applies fairly trivially to graphs. Each graph $G$ is regarded as a metric space as described above, so we are only concerned with the specification of the random walk on $G$. There is some freedom in the choice of graph measures; by analogy with the manifold measures Eq. 18 we consider the uniform measures:

$\displaystyle m^{\delta}_{u}(E)=\frac{|B^{G}_{\delta}(u)\cap E|}{|B^{G}_{\delta}(u)|},$

(23)

for any $u\in G$ and all measurable $E\subseteq G$, where $\delta>0$ takes on any (small) strictly positive real-value. Note that since $G$ has the discrete topology, the Borel $\sigma$-algebra of $G$ is simply the set of all subsets of $G$, i.e. every subset of $G$ is measurable. In specifying the measures via Eq. 23, the hope is that the the uniform graph measures $m^{\delta}_{u}$ will approximate the uniform manifold measures $\mu^{\delta}_{u}$, allowing one to approximate the manifold Ollivier curvature by the graph Ollivier curvature. We show below that this is indeed the case.

As mentioned in the introduction, the Gromov-Hausdorff distance between two compact metric spaces $X$ and $Y$ is defined by taking the infimum of the Hausdorff distance between the images of $X$ and $Y$ under isometric embeddings into some ambient metric space $Z$. Thus to introduce the Gromov-Hausdorff distance we begin by introducing the Hausdorff distance between subsets of a metric space. For more general references on the material in this section see [80, 79].

Let $(X,\rho_{X})$ be a metric space. For any point $x\in X$ and any set $A\subseteq X$, we have

$\displaystyle\rho_{X}(x,A)=\inf_{y\in A}\rho_{X}(x,y).$

(24)

The Hausdorff distance between two subsets $A,\>B\subseteq X$ is then defined

$\displaystyle\rho_{H}^{X}(A,B)=\max\set{\sup_{x\in A}\rho_{X}(x,B),\sup_{y\in B}\rho_{X}(y,A)}.$

(25)

There is an alternative formulation of the Hausdorff distance that permits us to introduce some useful notation. Let $B_{\delta}^{X}(x)$ be the (open) $\delta$-ball centred at $x$ for any $x\in X$. We define the $\varepsilon$-thickening of any set $A\subseteq X$ as the set

$\displaystyle A_{\varepsilon}=\bigcup_{x\in A}B_{\varepsilon}^{X}(x)$

(26)

for any $\varepsilon>0$. With this notation we note that

$\displaystyle\rho_{H}^{X}(A,B)=\inf\set{\varepsilon>0:B\subseteq A_{\varepsilon}{\rm and}A\subseteq B_{\varepsilon}}.$

(27)

The positivity, semidefiniteness and symmetry of $\rho_{H}$ are trivial consequences of the definition; note that symmetry requires both $B\subseteq A_{\varepsilon}$ and $A\subseteq B_{\varepsilon}$ since if $A\subseteq B$, $A\subseteq B_{\varepsilon}$ for all $\varepsilon>0$. For subadditivity we note that if $\rho_{H}^{X}(A,C)=\varepsilon$ and $\rho_{H}^{X}(C,B)=\delta$ we have $A\subseteq C_{\varepsilon}$ and $C\subseteq B_{\delta}$ and so $A\subseteq B_{\delta+\varepsilon}$ since $U\subseteq V$ implies $U_{\varepsilon}\subseteq V_{\varepsilon}$ for all $\varepsilon>0$ and all $U,\>V\subseteq X$ and $(U_{\varepsilon})_{\delta}\subseteq U_{\delta+\varepsilon}$ for all $U\subseteq X$ and all $\delta,\>\varepsilon>0$. Similar remarks show that $B\subseteq A_{\delta+\varepsilon}$ and subadditivity follows from the infimum.

$\rho_{H}^{X}$ is thus a pseudometric on the set of subsets of $X$. To show that it is not a metric, let ${\rm cl}(A)$ denote the closure of $A$ and note that $B_{\varepsilon}(x)\cap A\neq\emptyset$ for any $\varepsilon>0$ for any $x\in{\rm cl}(A)\backslash A$. Hence ${\rm cl}(A)\subseteq A_{\varepsilon}$ for all $\varepsilon>0$, while $A\subseteq{\rm cl}(A)$, and $\rho_{H}^{X}(A,{\rm cl}(A))=0$. Taking $A$ not closed shows the failure of definiteness. $\rho_{H}^{X}$ thus defines a metric on the equivalence classes of subsets of $X$, where two subsets $A$ and $B$ of $X$ are equivalent iff $\rho_{H}^{X}(A,B)=0$. It turns out that we may represent these equivalence classes by the closed subsets of $X$: we have already shown that every set is equivalent to its closure so it is sufficient to show that two distinct closed sets are inequivalent. In particular suppose that $A,\>B\subseteq X$ are closed and $A\neq B$, i.e. without loss of generality we may assume that there is an $x\in A\backslash B$. Since $x\notin{\rm cl}(B)=B$, there is an $\varepsilon>0$ such that $B_{\varepsilon}^{X}(x)\cap A=\emptyset$; then $\rho_{H}^{X}(A,B)\geq\varepsilon>0$ and $A$ and $B$ are inequivalent as required.

The Hausdorff distance is thus a metric on the closed subsets of a space; we show that it is a finite metric on the closed and bounded subsets of $X$ if the metric on $X$ is finite: in particular suppose that $A$ and $B$ are bounded, i.e. $A\subseteq B_{r}(x)$ and $B\subseteq B_{R}(y)$ for some $r,\>R>0$ for all $x\in A$ and all $y\in B$. Since $\rho_{X}$ is finite we may pick $(x,y)\in A\times B$ so that $A\subseteq B_{r+R+\rho_{X}(x,y)}$ and $B\subseteq A_{r+R+\rho_{X}(x,y)}$ as required. Since every compact set is both closed and bounded, the Hausdorff dimension naturally induces a finite metric on the compact subsets of a space.

With this in mind we automatically see that if we define the Gromov-Hausdorff distance $\rho_{GH}(X,Y)$ between two compact metric spaces $X$ and $Y$ as the infimum of the Hausdorff distance over isometric embeddings of $X$ and $Y$ into all possible ambient metric spaces $Z$, we have a finite pseudometric on the space of compact metric spaces, and which clearly gives $0$ iff $X$ and $Y$ are isometric.

For the purposes of this paper we shall need a basic result on the characterisation of the Gromov-Hausdorff distance in terms of near isometries. We need the following notions:

1. 1.

   Let $(X,\rho_{X})$ be a metric space. An $\varepsilon$-net in $X$ is a subset $A\subseteq X$ such that $A_{\varepsilon}=X$.

2. 2.

   Now let $(X,\rho_{X})$ and $(Y,\rho_{Y})$ be metric spaces; we define the distortion of a map $f:X\rightarrow Y$ as the quantity

   $\displaystyle\text{dis}(f)=\sup_{(x_{1},x_{2})\in X\times X}|\rho_{Y}(f(x_{1}),f(x_{2}))-\rho_{X}(x_{1},x_{2})|.$

   (28)

3. 3.

   An $\varepsilon$-isometry between $X$ and $Y$ is a mapping $f:X\rightarrow Y$ such that ${\rm dis}(f)\leq\varepsilon$ and $f(X)$ is a $\varepsilon$-net in $Y$.

The basic relation between near isometries and the Gromov-Hausdorff distance that we wish to show is that there is a $\mathcal{O}(\varepsilon)$-isometry between two compact metric spaces $(X,\rho_{X})$ and $(Y,\rho_{Y})$ iff $\rho_{GH}(X,Y)=\mathcal{O}(\varepsilon)$. More precisely

This lemma is a standard result and the interested reader is directed to e.g. the monograph [80] for a proof; it allows us to control the precision of a nearly isometric embedding with the Gromov-Hausdorff distance between two metric spaces.

Our result concerns the following situation: recall that $G$ is a graph on $N$ vertices and $\mathcal{M}$ is a compact Riemannian manifold. We assume that we have an $\varepsilon$-isometry $\iota:G\hookrightarrow\mathcal{M}$. The assumption is that $G$ arises from some random dynamical process that does not fix the background manifold $\mathcal{M}$ a priori; the graph $G$ itself however is a fixed configuration i.e. it has no random structure that we can appeal to.

At its most elementary our main claim is the following:

Outline of Theorem 9: If $\varepsilon=\varepsilon(N)$ is sufficiently small, $N$ sufficiently large and $\iota(G)$ samples $\mathcal{M}$ sufficiently evenly, then there is a discrete Einstein-Hilbert action $\mathcal{A}_{DEH}=\mathcal{A}_{DEH}(G)$ such that the error

$\displaystyle\delta\mathcal{A}(G,\mathcal{M}):=|\mathcal{A}_{DEH}(G)-\mathcal{A}_{EH}(\mathcal{M})|$

(29)

is small where $\mathcal{A}_{EH}$ is the Riemannian Einstein-Hilbert action (Eq. 9). $\mathcal{A}_{DEH}$ is defined in terms of the graph Ollivier curvature and other graph-intrinsic quantities.

As suggested in the introduction, we have long believed that there should be some discrete Einstein-Hilbert action $\mathcal{A}_{DEH}$ such that the above is true and the main challenge is to find the form of $\mathcal{A}_{DEH}$ and specify any conditions that need to be satisfied for the above to hold. A convergence result also follows almost immediately from the above.

It is quite clear that going from the Einstein-Hilbert action to the graph Ollivier curvature requires three main steps:

1. 1.

   The Einstein-Hilbert action $\mathcal{A}_{EH}$ is defined as the integral over $\mathcal{M}$ of the scalar curvature $R$. Thus, if we can approximate integrals over $\mathcal{M}$ via a suitable operation in $G$, we reduce the problem of approximating $\mathcal{A}_{EH}$ to approximating the Ricci scalar $R$ at each point.

2. 2.

   The Ricci scalar $R$ at a point $p\in\mathcal{M}$ is defined as the trace of the Ricci curvature ${\rm Ric}_{p}$ at $p\in\mathcal{M}$. If we can approximate the trace, the problem thus reduces to a finding an approximation of the Ricci curvature at each point $p\in\mathcal{M}$.

3. 3.

   We know that the manifold Ollivier curvature approximates the Ricci curvature. It is thus sufficient for the purpose of theorem 9 to show that the graph Ollivier curvature approximates in some sense the manifold Ollivier curvature.

It turns out that the difficulty associated with each of the three steps above is in ensuring that various graph theoretic measures approximate relevant measures on manifolds. This is no surprise in the case of the Ollivier curvature which is explicitly defined in terms of metric-measure structures. (Recall that in the basic set-up above we have assumed that the graph $G$ approximates the manifold $\mathcal{M}$ as a metric space). This is also trivially the case in the first step where we wish to approximate an integral over $\mathcal{M}$; for the second step, however, the measure theoretic aspect of the problem comes from the fact that taking the trace of a bilinear form essentially involves averaging that bilinear form over the sphere.

Why then is this a problem? The basic issue comes from the fact that a graph $G$ can metrically approximate a manifold $\mathcal{M}$ without necessarily approximating $\mathcal{M}$ well at the measure theoretic level. For instance $\iota(G)$ can be regarded as a sample of points in $\mathcal{M}$ and this sample might be highly uneven with respect to the volume measure in $\mathcal{M}$. In this way natural operations such as sums over points in $G$ correspond to integrals in $\mathcal{M}$, distorted by the sampling density.

At the most naive level these problems are circumvented in two ways. In the case of approximating the Ricci curvature and taking the trace, the manifold measures that we wish to approximate via graph structures are local measures by which we mean that the measures are associated to a given point and supported in some small compact region of that associated point. This allows us to exploit the universal local structure of smooth manifolds and extract suitable local subgraphs of $G$ around each vertex in such a way that the local subgraphs sample the relevant regions of $\mathcal{M}$ evenly under the nearly isometric imbedding $\iota$. In this way, both the Ricci and scalar curvatures at a point $p\in\mathcal{M}$ can be obtained from the Ollivier curvature of a vertex $u\in G$, $p=\iota(u)$. On the other hand, to obtain the full Einstein-Hilbert action, one must integrate over $\mathcal{M}$. Without fixing $\mathcal{M}$ in advance, the only way to obtain a good approximation at this level is to impose a condition on the evenness of the sample $\iota(G)\subseteq\mathcal{M}$. While this can be done using entirely metric constraints—i.e. without reference to the measure theoretic structure of $G$ or $\mathcal{M}$—it imposes severe restrictions on the kinds of sequence of graph converging to $\mathcal{M}$ we can consider and imposes major restrictions on the scope of the present results.

Let us consider each step in slightly more detail. We first consider step $1$, relating to integration over $\mathcal{M}$. A formal statement of the relevant result along with proof is given in appendix A. Essentially the idea is to replace

$\displaystyle\int_{\mathcal{M}}\text{d vol}_{\mathcal{M}}(x)f(x)\leftrightarrow\sum_{u\in G}\omega_{D}\varepsilon^{D}f(\iota(u)),$

(30)

where the right-hand side is interpreted as a kind-of Riemann sum for the function $f$ on the cover $\set{B_{\varepsilon}^{\mathcal{M}}(\iota(u))}_{u\in G}$ of $\mathcal{M}$. In particular, the factor $\omega_{D}\varepsilon^{D}$ corresponds to the volume of the Euclidean $D$-ball of radius $\varepsilon$. Two restrictions have to be imposed however to make this approximation work well. Firstly, $f$ cannot vary too much over the balls $B_{\varepsilon}^{\mathcal{M}}(\iota(u))$, $u\in G$, if it is reasonable to set it constant over the entire ball. Concretely, this can be achieved by restricting the class of functions $f$ under consideration to e.g. those that restrict to $K$-Lipschitz functions on the balls for a suitable Lipschitz constant $K$. Since every smooth function is locally Lipschitz continuous, this restriction on the class of functions $f$ considered is sufficiently generous to allow the approximation to be valid for any smooth function, as long as we are free to decrease $\varepsilon$ (increase $N$). The second condition relates to the fact that the cover $\set{B_{\varepsilon}^{\mathcal{M}}(\iota(u))}_{u\in G}$ is not pairwise disjoint so we need some way to control the overlap error. This is achieved, for instance, by assuming that the balls $\set{B_{\varepsilon(1-\alpha)}^{\mathcal{M}}(\iota(u))}_{u\in G}$ are in fact pairwise disjoint for some $\alpha\in(0,1)$. Note that we will find that we require $\alpha\ll 1$ which places a sever restriction on the class of nearly isometric imbeddings $\iota$ that can be considered.

Two basic steps are required in showing that we may approximate the trace. Fundamentally, we use the fact that the trace in $\mathbb{R}^{D}$ has the following integral representation:

	$\displaystyle{\rm tr}_{D}(T)$	$\displaystyle=\frac{1}{\omega_{D}}\int_{\mathbb{S}^{D-1}}{\rm dvol}_{\mathbb{S}^{D-1}}(x)T(x,x)$
		$\displaystyle=\frac{1}{\omega_{D}}\int_{\mathbb{S}^{D-1}}{\rm d^{D}x}\>\mathfrak{d}(x)T(x,x).$		(31)

(Recall that $\mathfrak{d}$ is a function that assigns to $x$ the Jacobean determinant for spherical coordinates evaluated on $x/||x||$; c.f. Eq. 5.) This can be checked explicitly with an elementary, if tedious, calculation. The factor $\omega_{D}$ arises because the trace of the constant bilinear form $1:(x,x)\mapsto 1$ is $D$ and we have the relation $D\omega_{D}={\rm vol}_{D}(\mathbb{S}^{D-1}).$ In fact, with minimal adjustment we can clearly express Eq. III.1 as an integral over $\partial B_{\ell}^{D}$ for any $\ell>0$:

$\displaystyle{\rm tr}_{D}(T)$

$\displaystyle=\frac{1}{\omega_{D}}\int_{\partial B^{D}_{\ell}}{\rm d^{D}x}\>\mathfrak{d}(x)T\left(\frac{x}{||x||},\frac{x}{||x||}\right).$

(32)

We have thus introduced a scale $\ell>0$ into the problem. The first step in approximating the trace involves discretising this result; to do so, we note that we may choose a set of points $U$ in $\mathbb{R}^{D}$ such that a sum of the integrand over these points constitutes a Riemann sum for the integral Eq. 32. We shall call any such set a trace grid. It is natural to assume that these points lie in the annulus $S_{\ell,r}^{D}$—introducing a secondary scale $r>0$ that determines the thickness of the shell—and that the points are regular in the sense that adjacent points have constant separation. Since we wish to use $S_{\ell,r}^{D}$ to approximate $\partial B_{\ell}^{D}$, we have

$\displaystyle r\ll\ell,$

(33)

while the distance between points is essentially determined by the size $|U|$ of the set $U$. In particular if we let $M\in\mathbb{N}$ be such that

$\displaystyle|U|=2M^{D-1},$

(34)

the angular difference between adjacent points of $U$ will be $\mathcal{O}(M^{-1})$. The metric distance between adjacent points is consequently $\mathcal{O}((\ell+r)M^{-1})=\mathcal{O}(\ell M^{-1})$. We also find that the discretisation error is of order $\mathcal{O}(M^{-1})$.

We now turn to the intrinsic characterisation of the trace approximation above. The idea is that for any $u\in G$, we may recursively construct a set $\tilde{U}\subseteq S_{\ell,r}^{G}(u)\subseteq G$ such that $\iota(\tilde{U})$ is almost $\exp_{p}(U)$, $p=\iota(u)$, for some trace grid $U\subseteq T_{p}\mathcal{M}$. When we say that $\iota(\tilde{U})$ is almost $\exp_{p}(U)$ this means there is a bijection $u\mapsto\tilde{u}$ such that $\rho_{\mathcal{M}}(\exp_{p}(u),\iota(\tilde{u}))<\varepsilon$. In fact we require slightly more since in the specification of the set $\tilde{U}$ we also need to be able to assign angular coordinates to elements of $\tilde{U}$ in such a way that the spherical volume element function $\mathfrak{d}$ can be approximated on $\tilde{U}$. Since $\iota(G)$ is, by assumption, a $\varepsilon$-net in $\mathcal{M}$ it is at some level obvious that we may find a set $\tilde{U}$ and a (surjective) mapping $u\mapsto\tilde{u}$ such that $\rho_{\mathcal{M}}(\exp_{p}(u),\iota(\tilde{u}))<\varepsilon$ for a trace grid $U$. It is a little harder, however, to ensure that this mapping is a bijection: the point is that while the exponential map is a radial isometry it is not a full isometry. Hence even though $\exp_{p}(S_{\ell,r}^{D})=S_{\ell,r}^{\mathcal{M}}(p)$, we may find points in $U$ moved closer together by a distance determined by the distortion of the exponential map. This distortion can be characterised more or less precisely for manifolds with bounded sectional curvature:

$\displaystyle{\rm dis}(\exp_{p}|B_{R}^{D})=\mathcal{O}(R^{3})$

(35)

for geodesic balls $B_{R}^{D}$ with radius $0<R\ll 1$. In particular this means that the points in $U$ are shifted by a distance $\mathcal{O}((\ell+r)^{3})=\mathcal{O}(\ell^{3})$ and adjacent points in $\exp_{p}(U)$ can be as close as $\mathcal{O}(\ell M^{-1}-\ell^{3})$. Thus if $\ell M^{-1}-\ell^{3}\sim\varepsilon$ we may have several points of $\exp_{p}(U)$ nearby the same point of $\iota(G)$; if this occurs sufficiently often then the sum over points in $G$ matched to $\exp_{p}(U)$ will not approximate the sum over $U$ after all and we require:

$\displaystyle(\varepsilon+\ell^{3})M\ll\ell.$

(36)

This constraint is essentially a constraint on $M$: $M$ must be large since the error arising from treating Eq. 32 via a Riemann sum goes with the inverse of $M$. However if $M$ is too large, the points in $U$ become too close together to guarantee that a sum over matching points in $G$ will in fact approximate the Riemann sum of ${\rm tr}_{D}$.

The recursive construction of $\tilde{U}$ itself ultimately boils down to being able to specify a notion of relative angle between points of $G$, essentially via the cosine rule. For sufficiently nearby points we have a precise estimate of the error of this assignment when nearly isometrically imbedded in $\mathcal{M}$; thus if this error is much smaller than the angular separation between adjacent points in $U$, we can reliably pick out elements of $G$ which ‘should be’ adjacent to points $v\in\tilde{U}$ if $\tilde{U}$ is almost a set . Such points will exist if $G$ approximates $\mathcal{M}$ since such points exist in $\mathcal{M}$. Note, however, that the recursive construction of $\tilde{U}$ proceeds intrinsically and as such it should be specified in such a way that the recursion terminates in all graphs; however the recursion will obviously fail to produce a set $\tilde{U}$ satisfying the above properties if $G$ is not Gromov-Hausdorff close to $\mathcal{M}$ since, for instance, there is no need for the points that ‘should be’ adjacent to $v\in\tilde{U}$ to exist.

Finally we note that a similar procedure takes place in the case of the Ollivier curvature: the problem reduces to showing that the uniform measure on the (discrete) set $\iota(B_{\delta}^{G}(u))$ approximates the uniform measure on the ball $B_{\delta}^{\mathcal{M}}(\iota(u))$. Showing that this is in fact the case essentially involves showing that the discrete measure is nearly a uniform discrete measure on an even grid of points in Euclidean space; then known Euclidean semidiscrete optimal transport problems can show that this is near the uniform measure in $\mathbb{R}^{D}$ which is near to the relevant uniform measure in $\mathcal{M}$. Translating between $\mathcal{M}$ and $\mathbb{R}^{D}$ involves the use of the exponential map which introduces an error $\delta^{3}$ according to its distortion on the $\delta$-ball. Also, as in the case of the trace grid above, the evenly spaced points in Euclidean space must be sufficiently separated that they remain identifiable after a distortion of $\varepsilon+\delta^{3}$. The details are discussed in appendix C.

As mentioned above, rigorous statements and proofs of steps $1$ and $3$ have been given in the appendices. Because several notions introduced in the process of taking the trace are required to define the discrete action we shall consider taking the trace in more detail here. Proofs of all theorems etc. in this section are found in appendix B.

In our informal outline above, we proceeded by discretising the Euclidean integral representation of the trace III.1. The idea is to introduce a set of points in $T_{p}\mathcal{M}$ in such a way that summing over these points gives a Riemann sum for the integral 32. More precisely we define Euclidean trace grids as follows:

The point of this definition is that it immediately yields the following:

$\displaystyle\left|\text{ tr}_{D}(T)-\text{ tr}_{U}(T)\right|=\mathcal{O}(M^{-1}),$

(39)

i.e. as long as $M$ is large we may approximate the trace by summing over the points in the trace grid.

The aim is to characterise $\text{ tr}_{U}$ via a sum over some set in $G$. This involves (a) intrinsically specifying a set $\tilde{U}\subseteq G$ such that $\iota(\tilde{U})$ is almost $\exp_{p}(U)$ for some Euclidean trace grid $U\subseteq T_{p}\mathcal{M}$ and (b) finding a way of characterising the summand $\mathfrak{d}(u_{\textbf{m}})T(u_{\textbf{m}},u_{\textbf{m}})$ for each multi-index m via some function on $G$ that can be specified without reference to $\mathcal{M}$. For present purposes, we shall assume that we can in fact do this for the bilinear form $T$—this is the substance of the demonstration that the Ollivier curvature may be approximated—and we need only specify the spherical volume element function $\mathfrak{d}$. It turns out that both of these tasks can be achieved at once: the idea is that for each $u\in G$, we may recursively construct a mapping $\theta_{u}:S_{\ell,r}^{G}(u)\rightarrow U\cup\set{0}$ where $U$ is a Euclidean trace grid, such that if we take $\tilde{U}=\theta_{u}^{-1}(U)\subseteq S_{\ell,r}^{G}(u)$ we have that $\theta_{u}|\tilde{U}$ is an injection and $\exp_{p}(U)$ approximates $\iota(\tilde{U})$. By construction, then, $\tilde{U}$ resolves point (a) and since $\theta_{u}$ obviously assigns each $u\in\tilde{U}$ an angular coordinate (the coordinate of the corresponding point in $U$), we see that the summand of $\text{ tr}_{U}$ can also be well approximated on $\tilde{U}$.

How does one construct the mapping $\theta_{u}$? We begin by noting that given any root point in a Euclidean trace grid $U$—which by rotational invariance of the trace we may identify as $u_{(1,...,1)}\in U$—we can recursively obtain the entire trace grid by successively moving to adjacent points in the grid. In this sense it is sufficient to be able to identify the analogue of adjacent points in the set $\tilde{U}$. It turns out that this may be achieved given knowledge of the relative angle between points in $G$. More precisely we define the following: