title: Emergence of the Circle in a Statistical Model of Random Cubic Graphs
authors: Christy Kelly Carlo Trugenberger Fabio Biancalana
text: 
  	Accurate Deep Potential model for the Al-Cu-Mg alloy in the full concentration space The work of H. W.
  is supported by the National Science Foundation of China under Grant No. 11871110, the National Key Research and Development Program of China under Grants No. 2016YFB0201200 and No. 2016YFB0201203, and Beijing Academy of Artificial Intelligence (BAAI). The work of L. Z. was supported in part by  the Center of Chemistry in Solution and at Interfaces (CSI) funded by the DOE Award de-sc0019394.
      Wanrun Jiang^1,2,  Yuzhi Zhang^3,4, 
   Linfeng Zhang^5,Corresponding author. E-mail: linfengz@princeton.edu ,  and  Han Wang^6,Corresponding author. E-mail: wang_han@iapcm.ac.cn 
  
  ^1Songshan Lake Materials Laboratory,
  Dongguan, Guangdong 523808, People's Republic of China
   ^2Institute of Physics, Chinese Academy of Sciences,
   Beijing 100190, People's Republic of China
    
  ^3Beijing Institute of Big Data Research,
   Beijing 100871, People's Republic of China
  
  ^4Yuanpei College of Peking University,
  
  Beijing 100871, People's Republic of China
  
   
  ^5Program in Applied and Computational Mathematics,
  
  Princeton University, Princeton, NJ 08544, USA
  
  ^6Laboratory of Computational Physics,
  
  Institute of Applied Physics and Computational Mathematics,
  
  Huayuan Road 6, Beijing 100088, People's Republic of China
  
  
      December 30, 2023
  =============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
  
  
  		We consider a formal discretisation of Euclidean quantum gravity defined by a statistical model of random 3-regular graphs and making using of the Ollivier curvature, a coarse analogue of the Ricci curvature. Numerical analysis shows that the Hausdorff and spectral dimensions of the model approach 1 in the joint classical-thermodynamic limit and we argue that the scaling limit of the model is the circle of radius r, S^1_r. Given mild kinematic constraints, these claims can be proven with full mathematical rigour: speaking precisely, it may be shown that for 3-regular graphs of girth at least 4, any sequence of action minimising configurations converges in the sense of Gromov-Hausdorff to S^1_r. We also present strong evidence for the existence of a second-order phase transition through an analysis of finite size effects. This—essentially solvable—toy model of emergent one-dimensional geometry is meant as a controllable paradigm for the nonperturbative definition of random flat surfaces.
  	
  	
  
  § INTRODUCTION
  
  	Discrete models of Euclidean quantum gravity based on dynamical triangulations or random tensors typically converge to either a crumpled phase of infinite Hausdorff dimension or to a phase of branched polymers in the large N limit <cit.>. Indeed if we ignore the crumpled phase which is manifestly pathological, the branched polymer appears to be the principal universal scaling limit of random regularised geometries when the dimension D≠ 2; presumably, this makes it the main fixed point in some associated renormalisation group flow. The branched polymer itself may be characterised as the continuum limit of random discrete one-dimensional objects and for this reason is known as the continuum random tree in the mathematics literature <cit.>; it also has Hausdorff dimension 2 <cit.> and spectral dimension 4/3 <cit.> making it a highly fractal object. The situation is a little more involved for D=2; pure quantum gravity is equivalent to the quantum Liouville theory <cit.> while the spectral and Hausdorff dimensions of these theories are 4 and 2 respectively <cit.>. When coupled to conformal matter of central charge c, however, branched polymers appear as a possible phase of 2D-quantum gravity above the so-called c=1 barrier and are interpreted as a kind of discrete manifestation of a tachyonic instability that leads to the breakdown of the continuum Liouville theory in this regime <cit.>. As such, branched polymers are also generally regarded as a highly pathological model of D-dimensional Euclidean quantum spacetimes. 
  	
  	On the other hand, the formalism of causal dynamical triangulations—see <cit.> for a review—has shown that alternative scaling limits exist: two-dimensional causal dynamical triangulations, for instance, is equivalent to Horava-Lifschitz gravity in two dimensions and the spectral and Hausdorff dimensions both take on their natural values <cit.>. Again building causal structure into the dynamical triangulations model a priori leads to substantial improvements in the geometric character of one of the phases in three dimensions <cit.>, while in 4-dimensions there is both a richer phase structure and at least one phase of reasonably geometric configurations <cit.>. From a practical point of view, the causal dynamical triangulations formalism represents a restriction of configuration space to a particular (non-spherical) topology in order to escape the universality classes of the Brownian map and the branched polymer; in particular, in the causal framework, there is a privileged foliation of spacetime which makes the quantum spacetimes obtained in (for instance) 2D causal dynamical triangulations homotopy cylinders with vanishing Euler characteristic. For compact surfaces, this is an essential condition for the existence of a Lorentzian metric <cit.>, so it is perhaps no surprise that standard Euclidean models which are dominated by contributions of genus zero give distinct non-Lorentzable results.
  	
  	Rather than restricting configuration space to a particular topology by fixing a foliation, an alternative strategy for escaping the universality class of branched polymers involves the expansion of configuration space to include structures which have even less a priori geometry than piecewise linear ones. One class of models that corresponds to such an expansion of configuration space is the class of network models of gravitation which have attracted growing attention from researchers as of late <cit.>. It seems desirable to study such expansions for two reasons: firstly, in order to fully clarify the role of causal structure in suppressing Euclidean pathologies and secondly, because models of emergent and latent network geometry are of independent intrinsic interest in network theory <cit.>. Stating the first point more ambitiously the aim is to present a model in which causal structure itself emerges dynamically at macroscopic scales <cit.>. For sceptics, it is worth stressing that even if this more ambitious aim is not achieved, insights into the role of causal structure can be obtained from an analysis of Euclidean models. This strategy of generalisation of the structures under consideration by way of network models is the one adopted here.
  	
  	Of course any such expansion on phase space comes with new associated difficulties, such as reduced prospects for the recovery of an average approximate geometric structure as well as worsened control of the entropy. Both of these problems are manifest in discrete models with superexponential growth of the size of configuration space in terms of the number of spacetime points; for instance in causal set theory this superexponential growth is explicitly used to justify the nonlocality of the causal set action <cit.>. It was also used as evidence against an early regularisation of random surfaces in terms of lattices imbedded in ℤ^D <cit.>. Nonetheless, from our perspective the issue of the superexponential growth of configuration space is perhaps somewhat moot; in standard random graph models <cit.> it has long been recognised that phase transitions occur in a manner that depends on threshold functions β=β(N) that depend on the system size. From a physical perspective, the bare parameter under variation—which will in general have some relation to the relevant physical couplings of the theory—is thus to be regarded as scale dependent and the phenomenal coupling is a kind of renormalised parameter with the scale dependence factored out. Note that pursuing this line of thought in <cit.> led to area-law scaling for the entropy of the model. This largely resolves the problem of excess entropy in principle; the problem of emergent geometry, however, remains to be addressed.
  	
  	In <cit.> we considered a series of related network models regarded as combinatorial quantum gravity. There we showed that, subject to certain constraints, random 4 and 6-regular graphs spontaneously organised themselves into Ricci-flat graphs that were, on average, locally isomorphic to ℤ^2 and ℤ^3 respectively. (Recall that a k-regular graph is one in which every vertex has k neighbours.) This is in line with naive expectations; taking ℤ^D as the paradigm for a flat discrete D-manifold, we expect to fix the dimension by considering 2D-regular graphs. We also provided some evidence for the existence of a continuous phase transition in the form of a divergent correlation length plot. Nonetheless the numerical analysis presented in that work left many basic questions open including, crucially, the global geometric consistency of observed classical configurations as evidenced, for instance, by spectral and Hausdorff dimension results. Further evidence for the existence and continuous nature of the phase transition is also desirable.
  	
  	Improvements in the code—partly following insights presented in <cit.>—have allowed some of these issues to be addressed, and in a future work we aim to present the case of flat surfaces; here, however, we address a more controllable model in which the configuration space consists of cubic (3-regular) graphs. In this model we have a classification of possible classical configurations and strong indications that in the N→∞ limit, the graphs in question converge to the circle S^1_r of radius r for some fixed r>0. This follows from spectral and Hausdorff dimension results, both of which come out at approximately 1 for large graphs in the classical limit, as well as the observed nature of the classical configurations. We have further circumstantial evidence relating to the orientability of the observed classical configurations. However, we may do rather better in that an additional kinematic constraint—which appears to arise dynamically in the model we consider—allows us to show rigorously that a sequence of classical configurations converges to S^1_r in the sense of Gromov-Hausdorff. We also present strong evidence for the continuous nature of the phase transition by an analysis of finite-size effects. We thus present a model with a continuous phase transition between a phase of random discrete spaces and emergent regular one-dimensional geometry.  This is perhaps evidence for the existence of a nontrivial UV fixed point for gravity, which in the Euclidean context is equivalent to the random structure of spacetime near Planckian scales.
  	
  	The basis for the combinatorial approach to quantum gravity introduced in <cit.> is a rough analogue of the Ricci curvature introduced by Yann Ollivier <cit.>. We discuss the Ollivier curvature more fully in appendix <ref>. It is valid for arbitrary metric measure spaces <cit.> and utilises synthetic notions of curvature that have arisen in optimal transport theory <cit.>. It has also seen wide application in network theory, particularly as a measure of clustering and robustness <cit.>. Intuitively speaking the Ollivier curvature captures the notion that the average distance between two unit-mass balls in a positively curved space is less than the distance between their centres. The first hint that Ollivier curvature may play a role in the context of quantum gravity appears to be in <cit.>, but other than our own work, we have recently seen Ollivier curvature appearing in the context of some much publicised network models of gravity by Wolfram and collaborators <cit.>. From a slightly different perspective, Klitgaard and Loll have generalised the basic intuition of Ollivier curvature to define a notion of quantum Ricci curvature as a quasi-local quantum observable for dynamically triangulated models that is valid at near the Planck scale <cit.>. It is also worth noting that recently, it has been shown that optimal transport ideas have a role to play in classical gravity <cit.>. More generally, optimal transport ideas have seen fruitful application in noncommutative geometry <cit.> and in the renormalisation group flow of the nonlinear σ-model <cit.>.
  	
  	Note that the Ollivier curvature is not the only valid notion of discrete curvature. A closely related coarse notion of curvature has been introduced in the context of optimal transport theory by Sturm <cit.> and Lott and Villani <cit.>; see also <cit.>. Unfortunately the Sturm-Lott-Villani curvature does not generalise easily to discrete spaces because the L^2-Wasserstein space over such spaces lacks geodesics; Erbar and Maas have generalised the Sturm-Lott-Villani curvature to discrete spaces using an alternative metric on the space of probability distributions but its concrete properties are as yet unclear <cit.>. A variety of alternative discrete notions of curvature also exist <cit.>, and it would be interesting to see how far the results obtained here depend on the precise notion of discrete curvature adopted. Indeed, the Forman curvature <cit.>, an alternative notion of curvature defined for networks (strictly speaking regular CW-complexes), is the basis for a recent proposal of network gravity <cit.> where quantum spacetimes are grown according to a stochastic model governed by the discrete Forman curvature.
  	
  	In this paper we adopt a now common perspective in mathematics viz. we essentially interpret emergent geometry in terms of Gromov-Hausdorff convergence <cit.>. (Of course, physically speaking we also require a continuous phase transition—or at least a divergent correlation length—in order to justify the construction of the scaling limit in the first place.) As such, it is worth briefly reflecting on the nature of Gromov-Hausdorff convergence and some of its physical ramifications. Given any metric space (X,𝒟) one can define a finite metric 𝒟_H on the space of compact subsets of X called the Hausdorff metric. The Gromov-Hausdorff distance between two (isometry classes of) compact metric spaces X and Y is the infimum of the Hausdorff distance between the two spaces over all pairs of isometric imbeddings of the spaces X and Y into an arbitrary ambient space Z. The key point to note is that Gromov-Hausdorff convergence characterises the scaling limit invariantly precisely because one minimises over all possible backgrounds; this ensures that discrete manifolds, regarded as sequences of graphs which converge to a given manifold in the sense of Gromov-Hausdorff, are a generally covariant regularisation of their respective scaling limits. There are several technical caveats worth considering at greater length which we discuss in appendix <ref>.
  	
  	In this sense we have a reasonably rigorous interpretation of (Euclidean quantum) spacetimes as (sequences of) graphs. Gromov-Hausdorff convergence however is not sufficient; as stressed in <cit.> we also need at least the convergence of some normalisation of the discrete Einstein-Hilbert action to its continuum counterpart in the Gromov-Hausdorff limit.  This precise convergence question is somewhat subtle and has yet to be answered fully, essentially because the Ollivier curvature depends both on the metric and the measure theoretic structures of the spaces in question, where typically the graph measures are discrete while the requisite manifold measures are continuous. For the models we have studied thus far this has been no obstacle since the curvature of classical configurations vanishes trivially and we wish to characterise Ricci-flat scaling limits by Ollivier-Ricci flat graphs.  That is to say, here we make no claims about quantum gravity in general considering only the generation of flat geometry from random degrees of freedom. We consider the precise relation of the model considered here to quantum gravity below. 
  	
  
  § COMBINATORIAL QUANTUM GRAVITY
  
  	
  
   §.§ The Model
  
      We shall consider a discrete statistical model (Ω,𝒜) defined schematically by the partition function
      
      𝒵[β,𝒜]= ∑_ω∈Ωexp(-β𝒜(ω))
  
      where Ω is some configuration space consisting of graphs, 𝒜:Ω→ℝ is an action functional and  β=β(β̃,N) an a priori N-dependent function which acts as a scale-dependent parameter for the model. We call β the inverse temperature of the system. Typically we will consider Ω consisting of random regular graphs at fixed N subject to an additional constraint discussed subsequently, and investigate different values of N. Note that in principle when we say graph we mean abstract graph, but in practice abstract graphs are somewhat difficult to work with and simulations will use labelled graphs. The number of labellings of an abstract graph ω with N vertices is N!/|Aut(ω)| where Aut(ω) is the automorphism group of ω and so at fixed N we over-count each configuration in the partition function a fixed number of times unless global symmetries are present. Since a typical graph has no nontrivial automorphisms we have neglected this latter consideration. Note that since the Gromov-Hausdorff limit is characterised invariantly, there is in fact no strict need to consider abstract graphs. The action 𝒜 is a discrete Einstein-Hilbert action, defined:
      
      𝒜(ω)=-∑_e∈ E(ω)κ_ω(e)=-1/2∑_u∈ V(ω)∑_v∈ N_ω(u)κ_ω(uv),
  
      where N_ω(u) denotes the set of neighbours of u in ω and κ_ω(e) is the Ollivier curvature of the edge e∈ E(ω). A more complete presentation of the Ollivier curvature is given in appendix <ref>, but for present purposes it is sufficient to recognise that the Ollivier curvature is a coarse version of the Ricci curvature in the following sense:  consider two points x and y in a manifold ℳ that are separated by a sufficiently small distance ℓ, as well as the (unique) vector field X parallel to the geodesic connecting x and y. Then we have:
      
      κ_ℳ(e)∼ℓ^2Ric(X,X)+𝒪(ℓ^3).
  
      In this way the Ollivier curvature represents a discretisation of the manifold Ricci curvature. The action <ref> thus corresponds to a discretisation of the (Euclidean) Einstein-Hilbert action as long as the edges incident to a vertex span the tangent space.
      
      The Ollivier curvature is discrete in that it takes values in the rational numbers ℚ and is also local in the following sense: let ω be a graph; for each edge uv∈ E(ω), we have
      
      κ_ω(uv)=κ_C(uv)(uv)
  
      where C(uv)⊆ω is a subgraph of ω called a core neighbourhood of uv. For our purposes it is sufficient to assume that C(uv) is the induced subgraph of ω with the vertex set
      
      V(C(uv))=N_ω(u)∪ N_ω(v)∪(uv)
  
      where (uv) is the set of non-neighbours of u and v that lie on a pentagon supported by the edge uv. Discreteness and locality are of course naively desirable properties for a quantised gravitational coupling.
      
      It turns out that for certain classes of graph the Ollivier curvature may be evaluated exactly. We shall need a little notation. 
      
          
    * _uv denotes the number of triangles supported on the edge uv.
          
    * Consider the induced subgraph on the set V(C(uv))/uv. This will have K connected components—each roughly corresponding to a cycle—labelled with the lower case letter k. We shall call these connnected components the components of the core neighbourhood.
          
    * □^k_w denotes the number of vertices in the kth component of the core neighbourhood that neighbour w∈u,v such that the shortest cycle support by uv that they lie on is a square.
          
    * ^k_w denotes the same as □^k_w for w∈u,v except the shortest cycle is a pentagon instead of a square.
      
      Using this notation we have the following expression for the Ollivier curvature in cubic graphs <cit.>:
      
      κ_ω(uv)=1/3_uv-1/3[1-_uv-∑_k□^k_u□^k_v]_+-1/3[1-_uv-∑_k(□^k_u+^k_u) (□^k_v+^k_v)]_+
  
      for each edge uv∈ E(ω) where the sum over k runs over the components of the core neighbourhood, a binfa,b and [a]_+max(a,0) for any a∈ℝ. Note that the main property of 3-regular graphs that allows this expression to be derived is the severe restriction on possible core neighbourhoods imposed by regularity of low degree. 
      
      We will not, in general, study the full configuration space of 3-regular graphs, instead imposing additional kinematic constraints on Ω. One particularly attractive constraint, derived in <cit.> is the so-called independent short cycle condition: we say that an edge uv has independent short cycles iff any two short (length less than 5) cycles supported on the edge share no other edges. Graphs satisfying this condition admit an exact expression, independently of any additional constraints on the core neighbourhoods due to regularity. Furthermore the quantities appearing in the exact expression have an unambiguous interpretation in terms of numbers of short cycles. In particular the constraint ensures that
      
      □^k_u=□^k_v       ^k_u=^k_v
  
      for all k. Thus
      
      ∑_k□^k_u□^k_v=□_uv      ∑_k(□^k_u+^k_u) (□^k_v+^k_v)=□_uv+_uv
  
      where □_uv and _uv are the number of squares and pentagons supported on the edge uv respectively. For 3-regular graphs, we may thus express the curvature of an edge as
      
      κ_ω(uv)=1/3_uv-1/3[1-_uv-□_uv]_+-1/3[1-_uv-□_uv-_uv]_+.
  
      This expression for the curvature allows us to rewrite the action. Defining
      
      P=uv∈ E(ω):_uv+□_uv>1       Q=uv∈ E(ω):_uv+□_uv+_uv>1,
  
      we have:
      
      
      𝒜(ω)   =𝒜_MF+𝒜_P+𝒜_Q
      𝒜_MF   =N-3_ω -8/3□_ω -5/3_ω
      𝒜_P   =-1/3∑_uv∈ P(1-_uv-□_uv)
      𝒜_Q   =-1/3∑_uv∈ Q(1-_uv-□_uv-_uv),
  
      
      where _ω, □_ω and _ω denote the total numbers of triangles, squares and pentagons in the graph ω respectively. 𝒜_MF is determined by global quantities and thus represents a kind of mean field contribution to the action.
      
      The precise significance of the independent short cycle condition is not entirely clear. In <cit.> it was a kind of `integrability' constraint insofar as it allows one to write the action rather explicitly. It also functions similarly to standard hard core constraints in statistical mechanics and prevents short cycles from `condensing' on an edge, though to a certain extent this is also guaranteed by regularity. For 3-regular graphs, the main utility of the hard core condition appears to be the dynamical suppression of triangles it entails which we will see is an important requirement for the emergence of geometric structure in the model, though it appears that a somewhat weaker constraint is sufficient for this purpose. 
      
      Having expressions of the form <ref> and <ref> for the Ollivier curvature permits the efficient running of simulations studying statistical models (Ω(N),𝒜), where 𝒜 is the Einstein-Hilbert action above and Ω(N) is the class of cubic graphs on N vertices. (Note that since each ω∈Ω(N) is regular with odd degree, N must be even.) We use elementary Monte Carlo techniques <cit.>, evolving the graphs at each step via edge switches: given the random edges uv and xy in a graph ω such that u x and v y, we construct a new graph ω̃ by breaking the edges uv and xy and forming the edges ux and vy, subject to any additional constraints on the configuration space that we may wish to impose.
      
  
   §.§ The Relation to Euclidean Quantum Gravity
  
       As we have tried to make clear in the introduction, the main purpose of this paper is not to study the problem of (Euclidean) quantum gravity proper but the generation of flat geometries in a model of random graphs. We believe the analogy between the action <ref> and the Einstein-Hilbert action are sufficient to call this model combinatorial quantum gravity, as we have done previously. At the same time it would be false to claim that we have no pretensions to addressing Euclidean quantum gravity and for the purpose of clarity it seems desirable to try and explain the present position of our approach in relation to ordinary Euclidean quantum gravity.
      
       Clearly our hope is that there is some Ollivier curvature based action—which we expect to look rather like the action in equation <ref>—that will act as a discrete regularisation of the Einstein-Hilbert action on graphs ω which are sufficiently close to a manifold ℳ in the sense of Gromov-Hausdorff. As mentioned in the introduction, precise convergence results for the Ollivier curvature are not yet known, and until they are we are somewhat restricted in the exact analysis of quantum gravity in general. The exception is the Ricci-flat sector where the convergence problem is absent—since the discrete and continuous Einstein-Hilbert actions vanish trivially. Thus on this sector Gromov-Hausdorff convergence alone guarantees agreement of our model with ordinary Euclidean quantum gravity.
      
       What are the prospects of a precise convergence result? There are essentially two required steps: first we need to show that the Ollivier curvature is respected by Gromov-Hausorff limits, and secondly we need to specify a discrete action in terms of the Ollivier curvature that converges to the Einstein-Hilbert action. Recently there has been major progress with regards to the first step. In his original work, Ollivier <cit.> demonstrated the stability of the Ollivier curvature under Gromov-Hausdorff limits, in the sense that given a sequence of metric-measure spaces X_n→ X and pairs of points (x_n,y_n)→ (x,y) with (x_n,y_n)∈ X_n× X_n we have κ(x_n,y_n)→κ(x,y). The convergence X_n→ X is, however, Gromov-Hausdorff convergence augmented by additional assumptions controlling the Wasserstein distance between the push-forward measures of the points under isometric imbeddings. The difficulty, of course, is that it is these auxiliiary assumptions which represent the foremost challenge in showing the convergence of Ollivier curvature in general.  Much of this challenge has been addressed in the recent paper <cit.> which shows that there is pointwise convergence of the Ollivier curvature—suitably rescaled—in random geometric graphs in arbitrary Riemannian manifolds. This is the first rigorous demonstration of the convergence of a notion of network curvature to its Riemannian counterpart known to the authors. One interesting feature is the need for two distinct length-scales that that are both sent to 0 in the continuum limit: one is the microscopic `edge' scale defined by the threshold for connecting points obtained by a Poisson point process and the other is an effective curvature scale governing the rescaling of the Ollivier curvature and the radius of the unit balls used for comparison in the random geometric graph. From a gravitational perspective, the kind of point-wise convergence described in <cit.> must be augmented by showing that the limit is in fact generally covariant; on the other hand it is perhaps a stronger requirement than is physically necessary since one expects only physically meaningful quantities to converge in general. Nevertheless this result considerably expands the potential of discrete-curvature quantum gravity models.
      
       Assuming that there is indeed a precise convergence result, we may turn to some general problems of discrete approaches to quantum gravity. One basic question is whether the partition function <ref> gives well-defined dynamics in the N→∞ limit. This of course requires energy-entropy balance, i.e. that β(N)𝒜 and S have the same N-dependence where S is the entropy of the model. In practice we use the energy-entropy balance condition to fix the N-dependence of β; 𝒜 grows as N so we need to know the N-dependence of the entropy. This depends rather strongly on our choice of Ω; in the present paper we consider Ω consisting of random regular graphs, and the number of such graphs on N-vertices is known. Specifically, we have <cit.> that the number of d-regular graphs on N-vertices is
      
      |Ω_N,d|∼(dN)!/(1/2dN)!2^1/2dN(d!)^Nexp(1-d^2/4+𝒪(1/N)).
  
      Using the Stirling approximation, taking the logarithm and using its properties we thus get the following naive estimate for the entropy:
      
      S   ∼1/2dNlog N+𝒪(N)
  
      We do not, however, simply consider random regular graphs, but instead random regular graphs satisfying an additional hard-core constraint. This constraint will have the effect of reducing the number of configurations and may lead to corrections in the entropy, though these—if they exist—are hard to compute. Indeed, below we find numerically that for N large, β is in fact constant with N suggesting that the independent short cycle condition leads to a logarithmic correction to the entropy, at least in the case of 3-regular graphs.  We do not believe that this constant growth of β is a generic feature of the model; instead we see it as a consequence of considering cubic graphs which, as we argue below, correspond to one-dimensional geometries and consequently a severely restricted set of action minimising configurations.
      
      Conceptually the issue of the N-dependence of β is an expression of a well-known issue with local actions in discrete quantum gravity <cit.> and can perhaps be interpreted as an expression of the nonlocality of the dimensionless action β𝒜. From a network theoretic perspective it is an expression of the infinite dimensionality of network phase transitions. To see how these perspectives relate, consider the standard square-lattice Ising model in D-dimensions. Such a model is finite-dimensional because the number of possible local interactions experienced by any bulk spin is fixed regardless of the system size. The average behaviour of these spins then only depends on the value of β, with the same average effect arising from the same value of β for a bulk system whatever the system size. Since it is these local interactions which determine the presence or absence of long-range order in the system we may control the phase of the system with a β-independent of the system size. In a graph, where local interactions are modelled by edges, the number and type of possible interactions depends on the system size and so the parameter β can only have the same average effect on a vertex as the system grows if β also grows with the system size to compensate for the additional possible interactions.
      
      Of course, like any discrete approach to quantum gravity, we must decide whether discreteness is fundamental as in causal set theory, or simply a regularisation technique that may be removed as a cut-off is removed in line with the asymptotic safety scenario. Both points of view require the recovery of a more or less geometric scaling limit, which as argued in the introduction we interpret in terms of Gromov-Hausdorff convergence. We adhere to the—more conservative—latter attitude which further demands a continuous phase transition; the main result of this paper is that both of these aims can be achieved by our model in the Ricci flat sector, i.e. precisely where our model potentially agrees with quantum gravity. 
      
      Finally, let us briefly comment on some defects of the Euclidean approach to quantum gravity. One major well-known problem is that the continuum Euclidean action is not positive definite for D>2 since one may choose a metric with conformal mode undergoing arbitrarily fast variations. Such a problem is of course immediately removed upon discretisation but may reappear in the N→∞ limit. In the model discussed here—which recall is not quantum gravity—this problem does not arise firstly because the Ollivier curvature is bounded between -2 and 1 for unweighted graphs and secondly because the independent short cycle condition effectively excludes positive curvature (negative action) geometries. More generally, as described in sections 1.8 and 1.9 of <cit.>, it is possible that the partition function is concentrated on configurations with bounded action near a non-Gaussian UV fixed point since the effective Euclidean action contains an entropic term coming from the number of configurations which share the same value of the action. Since our claims in this paper essentially amount to the existence of a UV fixed point, it seems quite possible that our approach may permit a similar escape from the problem of unboundedness.
      
       The biggest problem with our approach from the perspective of quantum gravity proper is the fundamentally Euclidean nature of the approach; in particular this refers to the absence of causal structure and difficulties related to giving sense to some notion of `Wick rotation'. A related issue is the unitarity of the resulting quantum theory. We have little concrete to say on these matters at present.
      
  
  § THE CLASSICAL LIMIT
  
      Recall that the Gibbs distribution given a partition function <ref> is
      
      p(ω;β)=1/𝒵[β, 𝒜]exp(-β𝒜(ω)).
  
      In the limit β→ 0, this becomes the uniform distribution on Ω, leading to the standard model of random regular graphs; this model is characterised, in particular, by small world behaviour and sparse short cycles <cit.>. We shall call this limit the random phase.
      
      The opposite limit β→∞ will be called the classical limit. As is well known, in the classical limit the Gibbs distribution is concentrated about minima of the action, justifying the terminology. Heuristically, this conclusion is essentially an application of the Laplace method of approximation <cit.>: suppose that ω_0∈Ω is a minimum of the action, i.e. 𝒜(ω_0)≤𝒜(ω) for all ω∈Ω. We shall denote the set of all such minima by Ω_0. Then
      
      p(ω;β)/p(ω_0;β)=exp(-β(𝒜(ω)-𝒜(ω_0))=exp(-β|𝒜(ω)-𝒜(ω_0|)
  
      for all ω∈Ω. That is to say, the ratio p(ω;β)/p(ω_0;β) decays exponentially for ω∉Ω_0 and contributions to the Gibbs distribution are (exponentially) concentrated about minima of the action as β increases. In particular, taking the limit β→∞ sufficiently rapidly we see that:
      
      p(ω;∞)lim_β→∞p(ω;β)=1/|Ω_0|∑_ω_0∈Ω_0δ_ω_0(ω)
  
      where for any ω_0∈Ω_0, δ_ω_0:Ω→ [0,1] denotes the Dirac mass:
      
      δ_ω_0(ω)={[    1, ω=ω_0;    0, ω≠ω_0 ]..
  
      That is to say, the distribution p(ω;∞) is supported on minima of the action as required; note that in the context of quantum gravity this suggests the identification β∝ħ^-1, since then the (semi)classical limit corresponds to the limit ħ→ 0. We call Ω_0 the classical phase and call configurations ω_0∈Ω_0 classical or tree-level configurations.
      
      The purpose of this section is to study the classical limit of our model in the thermodynamic limit, i.e. as the number of points N in the graphs goes to infinity. We find that as N→∞ the classical configurations converge to a limiting geometry described by a circle S^1_r of some radius r>0. We begin with a classification of the possible classical configurations for given N in section <ref> before arguing that the limit of these configurations is S^1_r in section <ref>. Together these conclusions constitute an argument that the classical limit of the present model is characterised by emergent one-dimensional geometric structure as long as the the continuum limit taken in section <ref> is justified.
      
      More precisely, in section <ref> we show that we may easily define a model in which the classical configurations are either prism graphs or Möbius ladders—essentially discretisations of cylinders and Möbius strips respectively. In particular cubic graphs satisfying the independent short cycle condition have this property. In section <ref>, we then provide numerical evidence that the classical configurations are in fact one-dimensional as N→∞ by looking at the behaviour of the Hausdorff and spectral dimensions of the graphs observed. We obtain further incidental evidence for the one-dimensional nature of the limit by looking at the sequence 𝔬(ω_N) as N→∞, where ω_N is a classical configuration on N vertices and
      
      𝔬(ω)=□_ω 2
  
      for any graph ω. As shown below, this quantity appears to take on the value 1 iff ω_N is not orientable (i.e. a Möbius ladder) and 0 otherwise (i.e. for ω_N a prism graph). We see that 𝔬(ω_N) oscillates between 1 and 0 as we increase N by 2; recalling that a D-dimensional CW-complex is orientable iff its D-th homology group is ℤ and insofar as ω_N is simply a discretisation of either a Möbius strip or a cylinder, the divergence in 𝔬(ω_N) seems to indicate that the second (cellular) homology groups of the classical geometries corresponding to ω_N are unstable under the thermodynamic limit. This is of course to be expected if the limiting geometry has dimension one rather than two, and in this way the divergence provides circumstantial evidence for dimensional reduction in the thermodynamic limit. Finally we note that we may prove rigorously that a sequence of classical configurations in a configuration space with triangles excluded converges in the sense of Gromov-Hausdorff to S^1_r; a precise statement and proof of this result is given in appendix <ref>.
      
  
   §.§ Classical Configurations and the Suppression of Triangles
  
      
      
      
      What are the classical configurations of the model? By the specification <ref>, action minimising configurations maximise the total curvature ∑_e∈ E(ω)κ_ω(e). In <cit.>, Cushing and collaborators have given a classification of positively curved cubic graphs which goes a long way towards a classification of Ω_0. (Note that we say a graph is positively curved iff all its edges have curvature at least zero.) Essentially we find that a positively curved graph is either a discrete cylinder or a discrete Möbius strip. More precisely:
      
      
          
    * Consider a chain of n squares, as in figure <ref>. A prism graph of length n, denoted P_n, is the graph obtained by identifying u≅ x and v≅ y. 
          
    * The Möbius ladder of length n, denoted M_n, is obtained by gluing u≅ y and v≅ x in figure <ref>.
      
      
      With this terminology the classification of Cushing et al. <cit.> may be summarised as follows:
      
          
    * If a 3-regular graph ω has positive Ricci curvature for all vertices then it is either a prism graph P_m for some m≥ 3 or a Möbius ladder M_n for some n≥ 2.
          
    * If m=3 the prism graph P_m has edges e∈ E(P_m) with κ_P_m(e)>0. Otherwise P_m is Ollivier-Ricci flat, i.e. κ_P_m(e)=0 for all e∈ E(P_m).
          
    * Similarly if n=2 the Möbius ladder M_n (which is also the complete graph on 4-vertices K_4) has strictly positive curvature for each edge e∈ E(M_2). Otherwise M_n is Ollivier-Ricci flat.
      
      
      The key point to note is that for large N, a positively curved graph is Ollivier-Ricci flat and hence has total curvature zero. Moreover since the graphs in question have such an obvious geometric interpretation, it is tempting to see this as a model with a geometric classical phase. The issue, of course, is that one can imagine the situation where a graph has both positive and negative curvature edges with positive total curvature. Indeed such configurations may be constructed quite simply, and some examples are given in figure <ref>. Inspection of the expression <ref> immediately shows that triangles necessarily appear in such configurations, and if we are to obtain a model with a classical phase Ω_0(N)=Ω_0∩Ω_N=P_N,M_N where Ω_N denotes the class of 3-regular graphs on N vertices, it is sufficient to ensure that triangles are suppressed. This can of course be achieved by fiat—by restricting to configurations of girth greater than 3 or bipartite graphs, for instance—but following <cit.> we know that the suppression of triangles is a dynamical consequence of the model given the independent short cycle condition.
      
      To see this first note that 𝒜_MF is an extensive quantity, i.e. 𝒜_MF∼ N. The scaling of 𝒜_P and 𝒜_Q depends on the behaviour of |P| and |Q| as N→∞. In <cit.> it was argued that 𝒜_P and 𝒜_Q do play an important role as β→∞, but in the random phase β→ 0, short cycles are sparse and we may analyse the low β dynamics by considering 𝒜_MF alone.
      
      
      
      Naively we expect that 𝒜_MF is minimised by increasing the number of short cycles with the greatest effect coming from an increase in the number of triangles and the least effect coming from an increase in the number of pentagons. Indeed, an edge switch that converts a pentagon to a square leads to a reduction in the action of 1, a pentagon to a triangle a reduction of 4/3 and a switch from a square to a triangle a reduction of 1/3. On these grounds we expect the number of triangles to increase in the random phase. However there is an alternative way of looking at the independent short cycle constraint which leads to different conclusions. In particular the independent short cycle condition can be viewed as an excluded subgraph condition with the abstract graphs in figure <ref> excluded. The key point to note is that the subgraphs <ref> and <ref> ensure that neither can an edge support two triangles nor can it support a triangle and a square. As such any triangle must share each of its edges with a pentagon and the gain in the action of 1/3 that arises from the conversion of a triangle to a square is more than made up for by the potential loss of 3 in the action arising from the conversion of each of the three pentagons to a square. Hence, due to `kinematic' constraints on the configuration space, triangles are strongly unfavoured in the local dynamics of the model in the random phase, and as such we expect them to be absent by the time the geometric phase is reached. On another note we expect pentagons to be similarly suppressed. Figure <ref> indicates that these expectations are corroborated.
      
      
      
      Figure <ref> shows examples of classical configurations observed following simulations run in a configuration space consisting of graphs satisfying the independent short cycle condition. In the simulations we looked at an exponential sweep of different values of β from -10≤log (β)≤ 10 and allowed the graph to `thermalise' for 3N/2=|E(ω)| sweeps at each value of β, where each sweep consists of 3N/2 attempted Monte Carlo updates, i.e. one attempted update per edge on average. As desired one obtains both prism graphs and Möbius ladders indicating that we have an effective model in which the classical configurations are Ω_0(N)=P_N,M_N with high probability. In fact, for smaller configurations (each possible value of N, from N=20 to N=50) we have studied the appearance of prism graphs and Möbius ladders systematically and have not found a single exception to one of these configurations appearing in 100 runs for each graph size. Larger graph sizes have not been studied systematically, but again we have not observed a single configuration ω at β=exp(-10) that is neither a prism graph nor a Möbius ladder, over the course of several runs of each graph size from N=100 to N=500 at intervals of 50 and then from N=500 to N=1000 at intervals of 100.
      
      
      
      
  
      
  
   §.§ Classical Configurations in the Thermodynamic Limit
  
      
      
      
      In the preceding section we provided strong numerical evidence that given a statistical model with configuration space Ω consisting of 3-regular cubic graphs with independent short cycles, the classical phase Ω_0 would consist overwhelmingly of prism graphs and Möbius ladders. This was to be expected: it can be proven that the classical phase consists of these graphs if we restrict to graphs without triangles while a strong heuristic argument and numerical evidence both point to this constraint effectively arising due to the low β dynamics. We now consider the thermodynamic limit N→∞ of the classical configurations, given that ω_N∈Ω_0(N)=P_n,M_m, N=2n. We show that in the thermodynamic limit, the classical configurations are effectively one-dimensional and argue that the correct limiting geometry should in fact be S^1. It turns out that thus intuition can be rigorously formulated in terms of so-called Gromov-Hausdorff limits as we prove in appendix <ref>. 
      
      
      
      The first point to note is that dimensional evidence in the model already considered of 3-regular graphs with independent short cycles suggests that the limiting geometry as N→∞ is one-dimensional. Dimensional data specifically refers to numerical data on the spectral and Hausdorff dimensions d_s(ω) and d_H(ω) of the graphs in question <cit.>; heuristically speaking, these quantities respectively define the dimension experienced by a particle diffusing in a space and the dimension governing the scaling of volume with distance in the space. Moreover both spectral and Hausdorff dimensions have become important quantities in quantum gravity: c.f. e.g. <cit.>. For our purposes, their present significance lies in the fact that we find d_s(ω)∼ d_H(ω)∼ 1 for classical configurations ω∈Ω_0 as N→∞. Figure <ref> shows the relevant plots. We shall briefly describe how the spectral and Hausdorff dimensions are defined here.
      
      The spectral dimension is defined for spaces equipped with a Laplacian L and controls the scaling properties of the eigenvalues of the Laplacian λ∈σ(L); note that σ(L) is the spectrum of the Laplacian which is assumed to be a finite-dimensional operator. Indeed, defining the heat kernel trace as the function
      
      K(t)=trexp(-Lt) = ∑_λ∈σ(L)exp(-λ t)
  
      for t in some open subset of ℝ, we may define the spectral dimension function
      
      d_s(t)=-2dlog K(t)/dlog t.
  
      The spectral dimension of the space on which the Laplacian is defined is then defined as d_s(t) in some limit of t or for some range of values of t. For Riemannian manifolds ℳ, for instance, we are interested in the small t asymptotics where it can be shown that 
      
      K(t)∼ t^-1/2D
  
      where D=(ℳ). Thus if we define
      
      d_s(ℳ)=lim_t→ 0d_s(t)
  
      we find d_s(ℳ)=D. 
      
      For our purposes, we shall calculate the heat kernel trace K(t) taking L as the standard graph Laplacian: 
      
      L=D-A
  
      where D is an N× N-dimensional diagonal matrix with the diagonal given by the graph degree sequence and A is the adjacency matrix. L is a finite symmetric matrix; its spectrum σ(L) thus consists of the N-diagonal components of the diagonalisation of L. This ensures that K(t)→ N as t→ 0 and K(t)→ 0 as t→∞; defining the spectral dimension as either the small or large t limit of d_s(t) thus gives 0 trivially and for graphs such a prescription fails to specify an informative quantity of the space. Nonetheless it is possible to find a reasonable interpretation of the spectral dimension for discrete spaces by finding regions of the value t for which the spectral dimension function d_s(t) plateaus. The case of the torus is an instructive example: figure <ref> shows the characteristic behaviour of the spectral dimension function for our purposes viz. vanishing asymptotics, a peak due to discreteness effects and a plateau at the expected integer dimension. Similar behaviour is displayed by high β configurations in figure <ref> indicating that d_s(ω)≈1 for classical configurations ω∈Ω_0.
      
      Alternatively, the Hausdorff dimension of a metric space equipped with some background measure effectively governs the volume growth of open balls in the space. The assumption is that for large r the volume scales as
      
      vol(B_r(x))∼ r^d_H.
  
      The Hausdorff dimension is then typically defined:
      
      d_H(ω)=lim_r→∞logvol(B_r(x))/log r
  
      In a graph equipped with the shortest path metric, we take the background measure to be the counting measure and the volume of a ball of radius r centred at a vertex u is simply the number of points within a distance r of u. For an unweighted graph this is simply all the points that can be reached from u by a path of length at most ⌊ r⌋, the largest positive integer strictly less than r. If the graph is connected the diameter is finite and B_r(x)=B_R(x) for all r≥ R where R is the diameter of the graph. Thus if we take the above definition d_H(ω)=0 trivially for connected graphs and like the asymptotic definitions of the spectral dimension, the Hausdorff dimension so defined fails to be a useful measure of dimension for discrete spaces. As such we take the modified definition:
      
      d_H(ω)=lim_r→diam(ω)log |B_r(u)|/log r
  
      where u∈ V(ω) and we assume that the diameter is large; the point is that if |B_r(u)|=α r^d_H, then
      
      log |B_r(u)|=d_Hlog r+log(α),
  
      and log(α)/log(r) becomes negligible as r→ R if the diameter R is sufficiently large. In practice, we will estimate d_H(ω) according to equation <ref>, that is by taking the gradient of a plot of log |B_r(u)| against log r, and then take the mean of this estimate over all vertices. This estimate is valid as long as |B_r(u)|∼ r^d_H for most values of r in the relevant range, i.e. as long as the plot of log |B_r(u)| against log r is approximately linear; in fact, for such graphs this approach extends the definition <ref> since it remains valid even if the diameter is small with respect to α. Figure <ref> is a typical example of a plot of log|B_r(u)| against log r, indicating that our estimation procedure for d_H is indeed valid. Calculated values of this estimate for classical configurations of various sizes are given in <ref> and show that the Hausdorff dimension of these configurations is approximately 1 for large N.
      
      
      
      As mentioned above we have additional—somewhat circumstantial—evidence for the one-dimensionality of the limiting geometry coming from the apparent instability of the second cellular homology group of our classical geometries in the thermodynamic limit. The key point is that the classical configurations are decidedly not choosing their topology at random. The situation is somewhat puzzling: Ollivier curvature is a local quantity and should not be able to distinguish between the Möbius ladder and the prism graph of the same size; as such there seems to be nothing in the action to distinguish the two possible classical configurations and from this perspective we perhaps expect Möbius ladders and prism graphs to appear in equal number. The numerical evidence, however, belies this expectation. We have the following anecdotal evidence:
      
          
    * Every run of graphs of sizes N=2n∈100,200,300,400,500,600,700,800,900,1000 resulted in a prism graph. 
          
    * Every run of graphs of sizes N=2n∈150,250,350,450 resulted in a Möbius ladder.
      
      Precise numbers of runs in the above vary from a few to 15 runs for N=100; the data is not systematic but already makes the possibility of random choice between topologies highly implausible. We also see both prism graphs and Möbius ladders for fairly large graphs (about 400 points) and the possibility of topology choice being a finite size effect seems slight. With these points in mind it is worth considering a more systematic study of the orientability of classical configurations obtained in simulations of small graphs: figure <ref> shows the average value of the quantity
      
      s(ω)={[           1, ω orientable;          -1,    otherwise ].
  
      where ω is an observed classical configuration over 100 runs of the code for graphs of size N=2n∈20,22,...,48,50. As can be seen the classical configuration appears to alternate between orientable and nonorientable results as two vertices—or one square—are added to the graph. In particular noting that n=□_ω we see that the quantity 
      
      𝔬(ω)□_ω 2
  
      appears to contain crucial topological information about the tree-level configurations that actually appear in the simulations: ω is orientable if 𝔬(ω)=0 and nonorientable otherwise. It would be curious to see if this can be explained. It is tempting to see some relation to the fact that the diagram
      
      Ω_0r𝔬[swap]dπ   ℤ/2ℤ
      Vect_1(S^1)[swap]urw_1
  
      commutes, where Ω_0 is the set of classical configurations, Vect_1(S^1) the set of line bundles over S^1 and w_1 the first Stieffel-Whitney class; it is well-known that, in particular, w_1 is a bijection and Vect_1(S^1) consists of a cylinder and a Möbius band (the possible classical geometries observed in this model) so π is to be interpreted as a mapping that sends prism graphs to cylinders and Möbius ladders to Möbius strips. 
      
      
      
      Given, then, that our classical configurations are converging to a one-dimensional space, what is the space and in what sense are they converging to that space? The limiting geometry is presumably (hopefully) a connected manifold ℳ. Again, as is well-known this means we have (up to homeomorphism) four possibilities <cit.>:
      
          
    * if ℳ is noncompact and without boundary then ℳ=ℝ.
          
    * if ℳ is noncompact and has a nonvoid boundary then ℳ=ℝ_+.
          
    * if ℳ is closed, i.e. compact and without boundary then ℳ=S^1.
          
    * if ℳ is compact with boundary then ℳ=[0,1].
      
      Note that 1-manifolds with boundary have a privileged set of points corresponding to the boundaries: 0,1=∂ [0,1] and 0=∂ℝ_+. If the limiting geometry were to be one of these manifolds with boundary, then, the classical configurations would also presumably have to be endowed with a privileged set of vertices that converge to boundary points. This cannot be the case insofar as we regard our classical configurations as abstract graphs and the limiting geometries are without boundary i.e. either S^1 or ℝ respectively. 
      
      Naively, since the geometry in question is the limit of a discrete space it is rather more natural to assume that the limit is compact, but in fact it seems clear that the precise geometry obtained in the limit depends on the way that the limit is taken. Suppose we have a cylinder [0,ℓ]× S^1_r, where ℓ>0 and S^1_r is the circle of radius r>0. We may suppose that the cylinder is discretised in terms of a prism graph P_n with the radius
      
      r=nℓ/2π.
  
      Then we have effectively weighted each edge of the prism graph with an edge length ℓ. A priori, we have two natural choices: keep ℓ fixed and let r diverge as n→∞, or alternatively keep r fixed and let ℓ→ 0 as n increases. The former corresponds to the non-compact limit [0,1]×ℝ which is two-dimensional and ruled out by the arguments above. The latter, on the other hand, corresponds to a one-dimensional compact limit S^1_r; it is also heuristically more in line with the idea that P_n is a lattice regularisation of the underlying geometry [0,ℓ]× S^1_r. In particular, insofar as ℓ is a lattice cutoff we wish to take ℓ→ 0 as n→∞. Roughly speaking, the limiting geometry is simply defined as the limit of cylinders [0,ℓ]× S^1_r as the width ℓ→ 0, which is of course simply the circle S^1_r. Similar considerations hold for Möbius strips.
      
      These heuristic considerations on the limiting geometry have a rigorous formulation in terms of Gromov-Hausdorff limits. The fundamental idea of `metric sociology' as Gromov termed it, is that there is a notion of distance between compact metric spaces, that gives us a precise notion of what it means for one compact metric space to converge to another. This is a particularly attractive framework for studying the problem of emergent geometry in a Euclidean context because every compact Riemannian manifold can be obtained as the Gromov-Hausdorff limit of some sequence of graphs <cit.>. We introduce the Gromov-Hausdorff distance in appendix <ref> and show that the classical configurations and geometries discussed here each converge to S^1_r as N→∞.
      
  
  § PHASE STRUCTURE
  
      In the preceding section we investigated the thermodynamic limit of the classical configurations of our model and found that the statistical models under investigation gave rise to the limiting geometry S^1. In physical terms, we in fact took a joint thermodynamic-continuum limit
      
      N→∞      ℓ→ 0
  
      keeping the quantity r=N ℓ/2π constant, with the edge length ℓ a UV cutoff. The factor of 2π is simply a choice of normalisation which ensures that the constant quantity is the radius of the limiting circle and can be dropped without loss of generality. More generally, we are interested in taking a joint thermodynamic and continuum limit N→∞, ℓ(N)→ 0, while preserving some fixed length scale ℓ_0; noting that N is essentially a volume measure, the correct generalisation of the expression <ref> to arbitrary dimensions D is:
      
      ℓ_0=ℓ(N)N^1/D.
  
      We expect N to be large so the physical problem is the justification of the expression <ref>.
      
      Our acquaintance with ordinary statistical mechanics suggests that such an expression holds as β→β_c where β_c is some finite number at which the system in question undergoes a continuous phase transition. In models of quantum geometry one expects quantum fluctuations about classical spacetime geometries in the limit β→β_c and the extent to which quantum geometries preserve the smooth structures characteristic of manifolds is not clear. Of course to rigorously obtain (smooth) manifold limits as observed classical configurations, we must assume that the expression holds exactly as β→∞. 
      
      Thus our aim is to investigate the phase structure of the statistical models defined above. In particular we are looking to find a second-order phase transition. Following <cit.> we note that strong evidence for both the existence and the continuous nature of a transition may be derived by an analysis of finite-size effects. A recent example of this kind of study in a similar context is <cit.> which provides strong evidence that two-dimensional causal set theory experiences a first-order phase transition as an analytic continuation parameter β is varied. In this section we conduct a similar analysis of finite size effects and provide evidence that our models evince a second-order phase transition.
      
  
   §.§ Existence of a Phase Transition and Estimating the Critical Beta
  
      We shall study the phase structure of the theory via an examination of the quantities
      
      ⟨𝒜|_⟩β=∂ (βℱ)/∂β       C = β^2⟨(𝒜-⟨𝒜|_⟩β)^2|_⟩β =-β^2∂^2(βℱ)/∂β^2
  
      where C is called the specific heat of the system. Note that βℱ=-log𝒵. In a phase transition we expect to find some nonanalyticity in the free energy βℱ in the thermodynamic limit and in the Ehrenfest classification the order of the derivative in which a discontinuity is observed gives the order of the phase transition. That is to say in a first-order transition we expect to observe a discontinuity in β𝒜 and a delta-function peak in C, while in a second-order transition we expect β𝒜 to be continuous and the specific heat to contain the discontinuity. Since such symptoms of nonanalyticity only arise in the thermodynamic limit <cit.> the difficulty lies in the assessment of the phase transition in finite systems.
      
      
      
      It has already been argued that two distinct phases exist: the random phase at low β and the classical phase as β→∞. Indeed figure <ref> shows the behaviour of some observables including the action for an exponential range of values of the parameter β and for a large range of graph sizes. The appearance of the two expected regimes as β is varied is quite clear. From the same figure it appears that the phase transition occurs roughly in the region 0.05≤β≤ 20, and in fact we find that if we allow for longer relaxation times the upper value can be somewhat reduced. Figure <ref> shows a plot of the quantity β⟨𝒜|_⟩β in the critical region for a smaller range of graph sizes. While we should not draw too many conclusions on the basis of such plots, there does not appear to be a discontinuity anywhere in the plot and as such we already have an indication that the phase transition is not first-order.
      
      
      
      A key step in the analysis of the phase transition is an estimation of the critical β_c.  In general this procedure is a little subtle since the random graph models under consideration are expected to be infinite-dimensional statistical models. Indeed infinite dimensionality is typical in both random graph models <cit.> and the statistical mechanics of networks <cit.> and is also a feature of discrete quantum gravity models <cit.> essentially as an expression of some expected nonlocality in the system. In practice this leads an N-dependent function β_c with the precise N-dependence to be estimated via finite size scaling arguments as in <cit.>. If β_c(N) appears to converge to some value β_c as N is increased we see that N-dependence of β_c(N) detected is simply a finite-size effect and not a consequence of the infinite dimensionality of random graph models. Conversely if convergence is only observed after factoring out some power of N then we see that infinite dimensionality of the model is at play in addition to finite size effects.
      
      The most natural way to estimate β_c(N) is to find the value of β which maximises C(N) where C(N) denotes a numerical estimate of the specific heat C for graphs of order N. In a first-order transition we expect C to behave as a delta-function singularity at the transition point since, by definition, the action β⟨𝒜|_⟩β has a discontinuity at the transition point. On the other hand, in a second-order transition we expect C to diverge at β_c as a natural consequence of the appearance of critical fluctuations and the divergence of the correlation length <cit.>. In both cases, in finite systems amenable to numerical analysis, the divergences are smeared out into finite peaks which become sharper as N increases. Figure <ref> shows the specific heat at various values graph sizes; we indeed observe sharp peaks forming as N increases.
      
      
      
      Figure <ref> shows the value of β which maximises the specific heat as a function of the graph size. This effectively shows the scaling of the  observed critical point values with N. Fitting against a plot of y=m N^-1+c suggests that the critical value β_c(∞)=1.84± 0.03; more important than the precise value stemming from this quantitative estimate is the qualitative adequacy of the N^-1 fit, in line with earlier expectations, showing that the system is finite-dimensional and thus has a well-defined critical inverse temperature.
      
      
      
      
  
   §.§ The Nature of the Phase Transition
  
      
      As already discussed above, a phase transition is first-order if there is a discontinuity in the quantity β⟨𝒜|_⟩β and second-order if β⟨𝒜|_⟩β is continuous while the specific heat C is discontinuous. Such discontinuities are not easy to spot in finite systems while, as already argued, divergences in C which do manifest in easily detectable traits of plots of finite systems cannot be used to distinguish between the order of the transition. Thus we need to consider other diagnostics if we are to identify the nature of the phase transition in question. 
      
      
      
      One characteristic feature of first-order transitions which is not apparent in second-order transitions is phase coexistence at the critical value β_c: the action at β_c can take on any of at least two distinct values separated by the discontinuity that characterises the transition. Regarded as a random variable the action will thus be distributed as a superposition of the distributions in each of the distinct pure phases. Assuming two distinct pure phases with distributions P_0 and P_1 respectively, the distribution of 𝒜 at the critical temperature is then given
      
      dist_𝒜(E)=α P_0(E)+(1-α)P_1(E)
  
      for some α∈ (0,1), where E is some event. Assuming that we have enough observations we expect both P_0 and P_1 to be normally distributed around (or even entirely concentrated at) some point and the action distribution <ref> takes the form of two superimposed Gaussians, becoming more pronounced as the size of N increases. Assuming that the discontinuity is larger than the effective support of the two Gaussians combined, which will occur if we consider sufficiently large n, we thus expect to observe two distinct peaks in the frequency distribution of the action at the critical value. This can be observed directly by looking at a frequency histogram of the observations of 𝒜, checked for in time-series data where we expect to observe sharp transitions between the two Gaussian centres, or observed in the following modified Binder cumulant:
      
      B = 1/3(1-⟨𝒜^4|_⟩β/⟨𝒜^2|^⟩2_β).
  
      Up to an overall factor, this is one minus the kurtosis of the distribution, and up a constant shift is the coefficient introduced in <cit.>. It can be shown that in a first-order transition, an observable taking the double Gaussian distribution <ref> will have a non-zero minimum at the transition point and will take on the value 0 elsewhere <cit.>. In a second-order transition, on the other hand, the action is distributed according to a single Gaussian with corresponding consequences for the observed frequency histogram and time-series data. In particular we expect B to vanish identically everywhere in a second-order transition. 
      
      
      
      In finite systems, of course, phase coexistence is observed for both first and second-order transitions. However in the former case it is a fundamental feature of the transition while it is simply a finite-size effect in the latter; as such phase coexistence and the associated phenomena become more pronounced as we increase N in a first-order transition and less pronounced in a second-order transition. More concretely, we expect transitions between phases to become less sharp in time-series data, distinct Gaussians to merge and B to approach 0 as N increases in a second-order transition. Figures <ref>, <ref> and <ref> all corroborate these expectations indicating that we indeed have a second-order transition.
      
      
      
       Finally let us consider the divergence of the normalised specific heat. This is characterised in terms of a critical exponent λ defined by:
      
      C/N∼ N^λ.
  
      This may be estimated by looking at the collapse of the normalised specific heat C/N in the critical regime. This is shown in figure <ref> where we have also shown the normalised dimensionless action; we obtain an estimate of λ=0.15. Note that the maximum value of the specific heat is indeed increasing as may be seen from figure <ref>.
      
      
      
      
  
  § CONCLUSION
  
      In conclusion we have presented a toy model of emergent geometry in 1-dimension. From a practical point of view, the key features of the model are the (dynamic or kinematic) suppression of triangles in conjunction and a classification of Ricci-flat graphs enabling us to guarantee that the scaling limit of possible classical configurations is a smooth geometry. The other essential ingredient is the fact that the system undergoes a continuous phase transition. Since Ricci-flat graphs are likely to exhibit significantly different properties from random regular graphs, and the evidence from <cit.> suggests that the continuous phase transition was likely to persist as we increase the degree, difficulties in extending this model are thus concentrated on the classification of Ricci-flat graphs; some nontrivial information is contained in <cit.> but it seems unlikely that we will be able to obtain similarly rigorous results for the case of 4-regular graphs, which in our formalism corresponds to surfaces. Nonetheless there are prospects for similar conclusions to be drawn in the case of surfaces (4-regular graphs) in the form of spectral and Hausdorff dimension results. This will be the topic of a future work. 
      
  
  § ACKNOWLEDGEMENTS
  
      C.K. acknowledges studentship funding from EPSRC under the grant number EP/L015110/1. F.B. acknowledges funding from EPSRC (UK) and the Max Planck Society for the Advancement of Science (Germany).
      
  
  § OLLIVIER CURVATURE
  
      In this appendix we introduce the Ollivier curvature beginning with some basic ideas in optimal transport theory. We rely heavily on <cit.>.
      
  
   §.§ General Features
  
      The Ollivier curvature is closely related to ideas of optimal transport theory in metric measure geometry. Let X be a Polish (separable completely metrisable) space and let 𝒫(X) denote the family of all probability measures on the Borel σ-algebra of X. Given probability measures μ, ν∈𝒫(X), a transport plan from μ to ν is a probability measure ξ on the Borel σ-algebra of X^2 satisfying the following marginal constraints:
      
      
      ∫_X dξ(x,y)f(x)   =∫dμ(x)f(x)
      ∫_X dξ(x,y)f(y)   =∫dν(y)f(y)
  
      
      for all measurable mappings f:X→ℝ. Let Π(μ,ν) denote the set of all transport plans from μ to ν. Roughly speaking a transport plan ξ∈Π(μ,ν) defines a method of transforming a distribution μ of matter into a distribution ν of matter.
      
      Given a (measurable) cost function c:X^2→ℝ, the transport cost of a transport plan ξ∈Π(μ,ν) is defined
      
      W_c(ξ)=∫_Xdξ(x,y)c(x,y).
  
      The optimal transport cost is then
      
      W_c(μ,ν)=inf_ξ∈Π(μ,ν)W_c(ξ).
  
      Given a metric ρ on X (compatible with the topology) the Wasserstein p-distance is defined
      
      W_p(μ,ν)=√(W_ρ^p(μ,ν))
  
      i.e. as the p-th root of the optimal transport cost for cost function given by the pth power of the metric. It can be shown that the Wasserstein p-distances define infinite metrics on the space 𝒫(X). The metrics are finite if we restrict to the space of probability measures with finite nth moments for n≤ p.
      
      The Ollivier curvature is an extension of the Wasserstein distance particular to metric measure spaces, i.e. metric spaces (X,ρ) equipped with a family of probability measures μ_x_x∈ X⊆𝒫(X). We may refer to the family μ_x_x∈ X as a random walk on X. We give two particularly important examples:
      
          
    * Every (connected locally finite) graph G is naturally a metric measure space in the following way: the metric structure is given by the standard geodesic distance between vertices; the random walk on X is given by picking
          
      μ_x^p(y)={[          p,         y=x; 1/d_x(1-p),   y∈ N_G(x);          0,   otherwise ].
  
          for each x∈ X for some p∈ [0,1]. We call this random walk the lazy random walk of idleness p. The lazy random walk of idleness 0 is referred to as the uniform random walk.
          
    * A Riemannian manifold (ℳ,g) is a metric measure space where again the metric is given by the standard geodesic metric and a random walk defined by the assignment:
          
      dμ_x^ε(y)={[ 1/vol(B_ε(x)),      y∈ B_ε(x);             0,      otherwise ].
  
          for each x∈ℳ for some (small) choice of ε>0.
      
      In such contexts, the Ollivier curvature is defined
      
      κ_X(x,y)=1-W_1(μ_x,μ_y)/ρ(x,y)
  
      for all distinct x, y∈ X. Rearranging we see that
      
      W_1(μ_x,μ_y)=(1-κ_X(x,y))ρ(x,y),
  
      i.e. lower bounds on the curvature imply control over the dilatation of the natural imbeddings x↦μ_x. In particular we see that κ_X(x,y)≥ 0 iff W_1(x,y)≤ρ(x,y); for Riemannian manifolds this means that a space is positively curved iff the average distance between two open balls centred at x and y respectively is less than the distance between their centres. This is closely related to the Ricci curvature; indeed for x and y sufficiently close, if u is a vector field generating a geodesic from x to y we have
      
      κ_X(x,y)=ε^2/2(D+2)Ric(u,u)+𝒪(ε^3)+𝒪(ε^2ρ(x,y)),
  
      where D=dim(ℳ). In this sense the Ollivier curvature is a generalisation of the manifold Ricci curvature to much rougher contexts than is typical. 
      
  
   §.§ Discrete Properties
  
      The discrete context has several important consequences for the Ollivier curvature. In particular suppose we are working in a (connected, locally finite, simple, unweighted) graph G equipped with the uniform random walk. Henceforth, the Ollivier curvature is also regarded as a mapping κ_G:E(G)→ℝ on edges; clearly ρ(u,v)=1 for any edge uv∈ E(G) so
      
      κ_G(uv)=1-W_1(μ_u,μ_v),
  
      
      The fundamental effect of discreteness is to give a linear character to the entire problem: by the construction of finite-dimensional free vector spaces, probability measures μ on graphs with finite support may be regarded as real vectors μ∈ [0,1]^n for any n≥ |supp(μ)| such that μ_x=μ(x) for all x∈supp(μ) and 0 otherwise; in particular, assuming that G is equipped with the uniform random walk, the measure μ_u is given by a d_u-dimensional real vector μ_u∈ (0,1]^d_u. Transport plans ξ∈Π(μ_u,μ_v) are then [0,1]-valued matrices satisfying the following discrete marginal constraints:
      
      ξ1_d_v=μ_u      ξ^T1_d_u=μ_v
  
      where 1_n is the n-dimensional column with 1 for each entry. Letting 𝔻(u,v) denote the d_u× d_v-dimensional matrix with entry (x,y)∈ N_G(u)× N_G(v) given by the distance ρ(x,y), we have that the transport cost
      
      W_ρ(ξ)=ξ·𝔻(u,v)
  
      where · denotes the Frobenius (elementwise) inner product. The Wasserstein distance W(μ_u,μ_v) is then defined via a linear programme which gives a general computational framework for exact evaluations of the Ollivier curvature.
      
      The second point to note about the discrete context is the Kantorovitch duality theorem. In particular
      
      
      W_1(μ_u,μ_v)   =sup_f∈𝕃(X,ℝ)∑_x∈ X(μ_u(x)-μ_v(x))f(x)
         =sup_f∈𝕃(X,ℝ)(∑_x∈ N_G(u)f(x)/d_u-∑_y∈ N_G(v)f(y)/d_v)
  
      
      where 𝕃(X,ℝ) is the set of all 1-Lipschitz maps f:X→ℝ. (Recall that a 1-Lipschitz map between two metric spaces (X,ρ_X) and (Y,ρ_Y) is a mapping f:X→ Y such that ρ_Y(f(x),f(y))≤ρ_X(x,y) for all x, y∈ X.) In the discrete context, Kantorovitch duality is simply an expression of the strong duality theorem in linear optimisation theory. Note that Kantorovitch duality—in a somewhat more involved form—generalises to continuous spaces. 
      
      A third key feature of the discrete setting—which does not generalise well beyond the discrete context—is the existence of core neighbourhoods. A core neighbourhood of an edge uv∈ E(G) is a subgraph H⊆ G such that N_G(u)∪ N_G(v)⊆ V(H) and such that ρ_H(x,y)=ρ_G(x,y) for all (x,y)∈ N_G(u)× N_G(v). Then clearly
      
      κ_G(uv)=κ_H(uv)
  
      and for the purposes of calculating the Ollivier curvature one may as well calculated the curvature in the core neighbourhood. The main utility of this notion comes when we realise that the induced subgraph of G defined by 
      
      C(uv)=N_G(u)∪ N_G(v)∪(uv)
  
      is a core neighbourhood, where
      
      (uv)=w∈ V(G):ρ(u,w)=2 and ρ(v,w)=2.
  
      Roughly speaking, C(uv) is the set of all vertices that lie on a triangle, square or pentagon supported by uv, or that neighbour u or v without lying on a short cycle supported by u or v. This is a core neighbourhood because for any (x,y)∈ N_G(u)× N_G(v) we have a 3-path xuvy.
      
      The final key feature of the discrete setting is the discrete nature of the Ollivier curvature. In particular, the Wasserstein distance may be found by optimising of integer-valued 1-Lipschitz maps:
      
      W_1(μ_u,μ_v)=sup_f∈𝕃(X,ℤ)∑_x∈ X(μ_u(x)-μ_v(x))f(x)
  
      This can be shown directly or by using standard ideas of linear optimisation theory.
      
      
  
  § GROMOV-HAUSDORFF DISTANCE
  
      The Gromov-Hausdorff distance is a metric on the space of isometry classes of compact metric spaces. It is a generalisation of the Hausdorff distance between subsets of a metric space. Significantly it defines a notion of convergence between metric spaces and gives a rigorous framework for thinking about emergent geometry in the thermodynamic limit of classes of graph. Much of the material in this appendix is covered in <cit.>; for elementary metric topology also see, for instance, <cit.>.
      
  
   §.§ Metric Topology
  
      First let us recall some standard ideas from metric topology: a metric on a set X is a positive definite, symmetric, subadditive function ρ:X^2→ [-∞,∞], i.e. ρ is a metric on X iff it satisfies the following properties:
      
          
    * Positivity: ρ(x,y)≥ 0 for all x, y∈ X.
          
    * Definiteness: ρ(x,y)=0 iff x=y for all x, y∈ X. Note that a mapping is semidefinite iff ρ(x,x)=0 for all x∈ X.
          
    * Symmetry: ρ(x,y)=ρ(y,x) for all x, y∈ X.
          
    * Subadditivity: ρ(x,y)≤ρ(x,z)+ρ(z,y) for all x, y, z∈ X.
      
      A metric may be thought of as defining the distance between any two points of a space. If instead of definiteness, ρ is just semidefinite then ρ is said to be a pseudometric on X. A (pseudo)metric is said to be finite iff ρ(x,y)< ∞ for all x, y∈ X. A (pseudo)metric space is a pair (X,ρ) where X is a set and ρ a (pseudo)metric on X.
      
      Clearly every (pseudo)metric on X restricts to a (pseudo)metric on subsets of X. Given a pseudometric ρ on X, there is an equivalence relation ≅ on X given by x≅ y iff ρ(x,y)=0. ρ is naturally interpreted as a metric on the quotient X/≅. The resulting metric space is said to be induced by the pseudometric ρ and is denoted X/ρ.
      
      Every pseudometric ρ on a space X gives rise to a topology in the following way: for each x∈ X and each r>0, define the open ball of radius r and centred at x as the set
      
      B_r(x)=y∈ X:ρ(x,y)<r.
  
      The open balls form a base for a topology in X called the metric topology of X. Two metrics ρ_1 and ρ_2 on X give rise to the same topology iff for each x∈ X there are constants α, β>0 such that
      
      αρ_1(x,y)≤ρ_2(x,y)≤βρ_2(x,y)
  
      for each y∈ X. Given two metric spaces (X,ρ_X) and (Y,ρ_Y), an isometry is a distance preserving mapping between X and Y, i.e. a bijection f:X→ Y such that ρ_Y(f(x),f(y))=ρ(x,y) for all x, y∈ X. Two metric spaces are isometric iff they are related by an isometry. Clearly isometric spaces are homeomorphic though the converse does not necessarily hold. 
      
      It turns out that every metric space is first-countable, which, in particular, means that all questions of convergence in metric spaces can be settled by considering the convergence of sequences. Recall that a sequence x_n_n∈ℕ⊆ X is said to converge to a point x∈ X iff for each ε>0 there is an N∈ℕ such that ρ(x,x_m)<ε for all m≥ N. We then call x a limit of the sequence x_n_n∈ℕ. A sequence is said to be convergent iff it has a limit and divergent otherwise. Every metric space is Hausdorff which means that every convergent sequence has a unique limit, denoted:
      
      lim_n→∞x_n.
  
      Roughly speaking, a sequence x_n_n∈ℕ has a limit x iff most of the sequence is arbitrarily close to x, i.e. there are at most a finite number of points in the sequence more than some given distance away from x. 
      
      A sequence x_n_n∈ℕ is said to be Cauchy iff for every ε>0 there exists an integer N∈ℕ such that ρ(x_m,x_n)<ε for every m, n≥ N. Heuristically, a sequence is Cauchy iff most of the points of the sequence lie arbitrarily close to one another. It is clear that every convergent sequence is Cauchy; the converse need not hold. For instance consider the sequence 10^-n_n∈ℕ in the space (0,1]; this is Cauchy but does not converge in the space (0,1] since its limit (in ℝ) is 0. From this example it appears that a Cauchy sequence is one which should converge, but fails to do so because the space fails to contain all the relevant points. This intuition is captured in the notion of completeness: a metric space is said to be (Cauchy) complete iff every Cauchy sequence of the space is convergent. A subset of a metric space is said to be complete iff it is complete as a metric subspace. One example of a complete metric space is the real line ℝ equipped with its standard metric
      
      ρ(x,y)=|x-y|.
  
      
      Every metric (X,ρ) space can be isometrically imbedded in a unique least complete metric space known as the completion of (X,ρ). To construct the completion we define a pseudometric ρ̃ on the space of Cauchy sequences of X via
      
      ρ̃(x_n_n∈ℕ,y_n_n∈ℕ)=lim_n→∞ρ(x_n,y_n)
  
      where the right-hand-side exists since the real numbers are complete. (X,ρ) isometrically imbeds in the metric space induced by ρ̃ which is also the least complete metric space to contain (X,ρ) in this manner.
      
      The closure A of a set A⊆ X is the set of limits of all sequences x_n_n∈ℕ⊆ A while a set is closed iff it is equal to its closure. It is clear that every complete subset of a metric space is closed since every convergent sequence is Cauchy; as a partial converse, every closed subset of a complete metric space is complete as a metric subspace. 
      
      For any set A⊆ X and any ε>0, the ε-thickening of A is defined as the set
      
      A_ε=⋃_x∈ XB_ε(x).
  
      A set A⊆ X is said to be a ε-net in X iff X=A_ε. ε-thickenings and ε-nets will feature prominently in the subsequent.
      
      A set A⊆ X is said to be bounded iff it is contained in some open ball of the space X. X is totally bounded iff for each ε>0, X admits a finite ε-net. Every totally bounded set is bounded. X is said to be compact iff it is complete and totally bounded, while a subset A⊆ X is said to be compact iff it is compact as a metric subspace. Clearly then every compact subset is closed and bounded. The converse does not hold for arbitrary metric spaces, though it does for Euclidean spaces by the Heine-Borel theorem. Note that every compact metric space admits a finite ε-net for each ε>0.
      
      
  
   §.§ Defining the Gromov-Hausdorff Distance
  
      Let (X,ρ) be a (pseudo)metric space, i.e. let ρ be a metric on X. For any x∈ X and any A⊆ X we define
      
      ρ(x,A)=inf_y∈ Aρ(x,y)
  
      This is essentially the smallest distance between x and a point of A. Clearly if x∈ A then ρ(X,A)=0. The Hausdorff distance between two subsets A, B⊆ X is then defined
      
      ρ_H(A,B)=maxsup_x∈ Aρ(x,B),sup_y∈ Bρ_X(y,A).
  
      The Hausdorff distance has an alternative characterisation in terms of ε-thickenings. In particular, it is simple to show that:
      
      ρ_H(A,B)=infε>0:A⊆ B_ε and B⊆ A_ε.
  
      To see this, it is sufficient to note that if A⊆ B_ε for some ε>0, then ρ(x,B)≤ε for each x∈ A and similarly B⊆ A_ε implies ρ(y,A)≤ε for each y∈ B. The suprema/infima then force equality.
      
      The Hausdorff distance defines a pseudometric on the space 𝔭(X) of all subsets of X: positivity, semidefiniteness and symmetry are all trivial. For subadditivity note that
      
      A_ε+ϵ⊆ (A_ε)_ϵ
  
      by the subadditivity of ρ. Thus we have an induced metric space 𝔭(X)/ρ_H. It turns out that we may identify 𝔭(X)/ρ_H with the set ℭ(X) of closed subsets of X. To see this note that:
      
          
    * ρ_H(A,A)=0 for all A⊆ X.
          
    * ρ_H(A,B)≠ 0 for distinct A, B∈ℭ(X).
      
      That is to say, the closed sets of X can be chosen as representatives of the equivalence classes in 𝔭(X)/ρ_H. For the first of these results note that ρ(x,A)=0 for all x∈ A since A⊆A. Similarly, each y∈A is the limit of some sequence of elements in A and thus ρ(y,A)=0, which ensures ρ_H(A,A)=0. For the second statement suppose that ρ_H(A,B)=0, i.e. A⊆ B_ε and B⊆ A_ε for all ε>0. Then A⊆B=B⊆A=A and A=B as required.
      
      We have the following properties that we state without proof:
      
          
    * ρ_H(A,B)<∞ if A and B are bounded.
          
    * (ℭ(X),ρ_H) is a complete (compact) metric space if (X,ρ) is complete (compact).
      
      In particular the first of these properties ensures that ρ_H restricts nicely to a finite metric on the compact subsets of X. We are now ready to define the Gromov-Hausdorff distance:
      
      Let X and Y be compact metric spaces. Then we define the Gromov-Hausdorff distance between X and Y as
      
      ρ_GH(X,Y)=infρ_H^Z(ι_1(X),ι_2(Y))
  
      where the infimum is taken over all triples (Z,ι_1,ι_2) where Z is a metric space and ι_1 and ι_2 are isometric imbeddings of X and Y into Z respectively, and ρ_H^Z is the Hausdorff metric in Z.
      
      Recall that the infimum preserves subadditivity and note that  symmetry and positivity  of the Gromov-Hausdorff distance are trivial. Also if X and Y are isometric, any isometry f:X→ Y defines an isometric imbedding of X into Y such that ρ_H^Y(f(X),Y)=0 and ρ_GH(X,Y)=0, i.e. the Gromov-Hausdorff metric is immediately a finite pseudometric on the Gromov-Hausdorff space of isometry classes of compact metric spaces. In fact it can be shown that if the Gromov-Hausdorff distance between two spaces vanishes then the spaces are isometric, and the Gromov-Hausdorff distance is a finite metric—not just pseudometric—on the Gromov-Hausdorff space.
      
  
   §.§ Gromov-Hausdorff Limits and Emergent Geometry
  
      The purpose of this section is threefold: one we introduce various ways to calculate/estimate the Gromov-Hausdorff distance between two spaces; two, we discuss various ways of approaching Gromov-Hausdorff convergence. These results are used in the next section to show the convergence of classical configurations to S^1_r. Finally we prove two results on the convergence of finite spaces that suggests that Gromov-Hausdorff convergence is a very promising formalism for investigating questions about emergent geometry in general. Note that the material in this section is widely known, but many of the results are simply quoted and not given explicitly in standard references <cit.>. As such we have chosen to present some proofs rather explicitly.
      
      Since the Gromov-Hausdorff distance between two metric spaces X and Y is defined by minimising over all possible imbeddings of X and Y into an ambient metric space Z, the most obvious strategy to obtain an estimate of an upper-bound of the Gromov-Hausdorff distance is of course to construct an explicit isometric imbedding into some given metric space Z. In fact we immediately have the following lemma:
      
      Let X_k_k∈ℕ and Y be compact metric spaces. Given a sequence of metric spaces Z_k_k∈ℕ and isometric imbeddings ι_k^X:X_K→ Z_K_k∈ℕ, ι_k^Y:Y→ Z_K_k∈ℕ, then X_k→ Y in the sense of Gromov-Hausdorff if for each ε>0 there is an N∈ℕ such that ρ_H^Z_n(ι_n^X(X),ι_n^Y(Y))<ε for all n>N.
      
      We use this lemma to show the convergence of cylinders/Möbius strips to the circle in the next section.
      
      Though this approach to Gromov-Hausdorff convergence is immediate from the definition, it is not always practical because actually constructing the required isometric imbeddings can be a little  difficult. Some reformulations of the Gromov-Hausdorff distance give better methods for estimating the Gromov-Hausdorff distance. We introduce these methods here.
      
      The first reformulation of the Gromov-Hausdorff distance is in terms of pseudometrics: 
      
      Let (X,ρ_X) and (Y,ρ_Y) be compact metric spaces.
      
      ρ_GH(X,Y)=infρ_H^X⊔ Y(X,Y)
  
      where the infimum is taken over pseudometrics on ρ:X⊔ Y→ℝ such that ρ|X=ρ_X and ρ|Y=ρ_Y and X⊔ Y denotes the disjoint union of X and Y.
      
      
          Let (Z,ρ_Z) be a metric space and suppose that f:X→ Z and g:Y→ Z are isometric imbeddings. We may define a pseudometric ρ on X⊔ Y by ρ|X× X=ρ_X, ρ|Y× Y=ρ_Y and ρ(x,y)=ρ_Z(f(x),g(y)) for all (x,y)∈ X× Y; ρ obviously inherits positivity, semi-definiteness, symmetry and subadditivity from ρ_X, ρ_Y and ρ_Z but need not be definite since it is possible that f(x)=g(y) for some pair (x,y)∈ X× Y. Thus ρ is a pseudometric on X⊔ Y. Thus infρ_H^X⊔ Y(X,Y)≤ρ_GH(X,Y). On the other hand any pseudometric ρ on X⊔ Y gives rise to a pair of isometric imbeddings f=π∘ι_X and g=π∘ι_Y of X and Y respectively into the induced metric space X⊔ Y/ρ where π:X⊔ Y→ X⊔ Y/ρ is the quotient map and ι_X and ι_Y are the natural imbeddings of X and Y into X⊔ Y respectively.
      
      We now discuss a reformulation in terms of the distortion of correspondences between metric spaces. We begin by introducing the latter notion:
      
      Let X and Y be sets. A correspondence between X and Y is a relation R⊆ X× Y such that the domain and codomain satisfy X=dom(R) and Y=cod(R) respectively, i.e. for each x∈ X there is a y∈ Y such that (x,y)∈ R and vice versa.
      
      
      A relation R⊆ X× Y is a correspondence between X and Y iff there is a set Z and a pair of surjective maps f:Z→ X and g:Z→ Y such that R=(f(z),g(z)):z∈ Z.
      
      
      For necessity suppose that R is a correspondence, let Z=R and let f and g be the projections (x,y)↦ x and (x,y)↦ y respectively. Then f and g are surjections since R is a correspondence as required. Sufficiency is obvious by the surjectivity of the mappings f and g.
      
      
      Let (X,ρ_X) and (Y,ρ_Y) be metric spaces. The distortion of a correspondence R⊆ X× Y is defined
      
      dis(R)sup|ρ_X(x_1,x_2)-ρ_Y(y_1,y_2)|:(x_1,y_1), (x_2,y_2)∈ R.
  
      
      
      Let (X,ρ_X) and (Y,ρ_Y) be metric spaces. 
      
          
    * Let Z a set and let R be a correspondence between X and Y such that R=(f(z),g(z)):z∈ Z for some surjections f:Z→ Z, g:Z→ Y as per proposition <ref>. Then we have
          
      dis(R)= sup_z_1, z_2∈ Z|ρ_X(f(z_1),f(z_2))-ρ_Y(g(z_1),g(z_2))|.
  
          
    * dis(R)=0 iff there is an isometry f:X→ Y such that R=(x,f(x)):x∈ X.
      
      
      
      (i) is trivial. For (ii) note that dis(R) is the supremum of a positive quantity so it vanishes iff |ρ_X(x_1,x_2)-ρ_Y(y_1,y_2)|=0 for all (x_1,y_1), (x_2,y_2)∈ R. Thus for any pair of points (x_1,x_2)∈ X we must have ρ_Y(y_1,y_2)=ρ_X(x_1,x_2) for any y_k∈ Y_x_ky∈cod(R):(x_k,y)∈ R, k∈1,2. We show that R is the graph of a unique bijection f:x↦ y, i.e. f(x)=y iff (x,y)∈ R: in particular ρ_X(x,x)=0 trivially for all x∈ X so ρ_Y(y_1,y_2)=0 for all y_1, y_2∈ Y_x by the preceding claim. But then y_1=y_2 by definiteness and f is a well-defined bijection such that ρ_Y(f(x_1),f(x_2))=ρ_X(x_1,x_2) for all x_1, x_2∈ X and f is an isometry as required. The converse is trivial.
      
      We now show that the Gromov-Hausdorff distance is (up to a constant) the infimum of the distortion of correspondences between the relevant metric spaces:
      
      Let (X,ρ_X) and (Y,ρ_Y) be compact metric spaces. Then
      
      ρ_GH(X,Y)=1/2inf_Rdis(R)
  
      where the infimum is taken over all correspondences between X and Y.
      
      
      We show (i) that if ρ_GH(X,Y)<r then there is a correspondence between X and Y such that dis(R)<2r and (ii) that 2ρ_GH(X,Y)≤dis(R) for any correspondence R between X and Y.
      
          
    * Given ρ_GH(X,Y)<r we may assume without loss of generality that X and Y are subspaces of (Z,ρ_Z) with ρ_Z^H(X,Y)<r; then defining R=(x,y)∈ X× Y:ρ_Z(x,y)<r gives R a correspondence. Then dis(R)<2r by the triangle inequality:
          
      dis(R)≤ |ρ_Z(x_1,y_1)-ρ_Z(x_2,y_2)|≤ρ_Z(x_1,y_1)+ρ_Z(x_2,y_2)<2r
  
          for any x_1, x_2∈ X and y_1, y_2∈ Y.
          
    * Choose some correspondence R and define r1/2dis(R). By lemma <ref> it is sufficient to provide a pseudometric ρ on X⊔ Y such that ρ_H^X⊔ Y(X,Y)≤ r since then ρ_GH(X,Y)≤ρ_H^X⊔ Y(X,Y)≤1/2dis(R). Let us define ρ via ρ|X× X=ρ_X, ρ|Y× Y=ρ_Y and
          
      ρ(x,y)=infr+ρ_X(x,x_1)+ρ_Y(y_1,y):(x_1,y_1)∈ R.
  
          Symmetry and positive semi-definiteness are trivial—note that ρ(x,y)≥ r but x≠ y for x∈ X and y∈ Y since X⊔ Y is the disjoint union of X and Y. For subadditivity we note that we need to check that ρ(x,y)≤ρ(x,z)+ρ(z,y) for x∈ X, y∈ Y and z∈ X∪ Y; subadditivity is a trivial consequence of the subadditivity of ρ_X and ρ_Y in the cases where x, y,:z∈ X or x, y, z∈ Y respectively. Suppose that z∈ X. Then
          
      ρ(x,y)≤ r+ρ_X(x,x_1)+ρ_Y(y_1,y)≤ρ_X(x,z)+(r+ρ_X(z,x_1)+ρ_Y(y_1,y)
  
          for all (x_1,y_1)∈ R, where we have used the subadditivity of ρ_X to write ρ_X(x,x_1)≤ρ_X(x,z)+ρ_X(z,x_1). Taking the infimum over all pairs (x_1,y_1)∈ R on both sides gives the desired result. A similar argument holds if z∈ Y. Thus ρ is a pseudometric on X⊔ Y. 
          
          It remains to show that the Hausdorff distance associated to ρ is bounded above by r: to see this note that every point of X lies within a distance r of some point of Y and vice versa. In particular, given some x∈ X we have some y∈ Y such that (x,y)∈ R since R is a correspondence so r≤ρ(x,y)≤ r+ρ_X(x,x)+ρ_Y(y,y)=r and X⊆ Y_r, the r-thickening of Y. A similar argument shows Y⊆ X_r so ρ_H(X,Y)≤ r as required.
      
      
      We consider one final method to estimate the Gromov-Hausdorff distance. This is in terms of nearly isometric imbeddings:
      
          Let (X,ρ_X) and (Y,ρ_Y) be metric spaces. 
          
              
    * The distortion of a mapping f:X→ Y is defined
              
      dis(f)sup|ρ_Y(f(x),f(y))-ρ_X(x,y))|:(x,y)∈ X^2.
  
              
    * A mapping f:X→ Y is said to be a ε-isometry iff f(X) is a ε-net in Y and dis(f)<ε.
          
      
      
          Let X and Y be compact metric spaces. If ρ_GH(X,Y)<ε then there is a 2ε-isometry f:X→ Y. Similarly if there is a ε-isometry f:X→ Y then ρ_GH(X,Y)<3/2ε.
      
      
          Suppose that ρ_GH(X,Y)<ε; then by theorem <ref> there is a correspondence R⊆ X× Y such that dis(R)<2ε. We may construct a mapping f:X→ Y as a choice function f:X→_x∈ Xy∈ Y:(x,y)∈ R. Clearly dis(f)≤dis(R)<2ε. To see that f(X) is a 2ε-net in Y, for each y∈ Y choose an x∈ X such that (x,y)∈ R. Then
          
      ρ_Y(f(x),y)   =ρ_Y(f(x),y)- ρ_X(x,x)+ρ_X(x,x)
         ≤ |ρ_Y(f(x),y)- ρ_X(x,x)|+ρ_X(x,x)
         ≤ρ_X(x,x)+dis(R)
         <2ε
  
          as required. Now suppose that f:X→ Y is a ε-isometry and construct R⊆ X× Y by
          
      R=(x,y)∈ X× Y:ρ_Y(f(x),y)<ε.
  
          Clearly (x,f(x))∈ R and dom(R)=X; also since f(X) is a ε-net in Y, each y∈ Y lies within ε of f(x) for some x∈ X and cod(R)=Y, i.e. R is a correspondence as required. Now for any pairs (x_1,y_1) and (x_2,y_2)∈ R we have
          
      |ρ_Y(y_1,y_2)-ρ_X(x_1,x_2)|≤ρ_Y(y_1,f(x_1))+ρ_Y(f(x_2),y_2)+|ρ_Y(f(x_1),f(x_2))-ρ_X(x_1,x_2)|≤ 2ε +dis(f)<3ε
  
          where we have used subadditivity in the first step and the definition of R and dis(f) in the second, while the final step follows since f is an ε-isometry and dis(f)<ε. Taking the supremum of both sides over all pairs (x_1,y_2), (x_2,y_2)∈ R gives dis(R)<3ε so the required result follows immediately from theorem <ref>
      
      This gives an essentially complete set of methods for estimating the Gromov-Hausdorff distance. We now turn back to more explicit convergence properties.
      
      We shall show one basic lemma that demonstrates that Gromov-Hausdorff convergence reduces to convergence of finite subsets:
      
          Two compact metric spaces X and Y are said to be (ε,δ)-approximations of one another iff we have finite ε-nets A⊆ X and B⊆ Y of cardinality N such that |ρ_X(x_k,x_ℓ)-ρ_Y(y_k,y_ℓ)|<δ for all k, ℓ∈0,...,N-1.
      
      
          Let X and Y be compact metric spaces. If X is an (ε,δ)-approximation of Y then ρ_GH(X,Y)<2ε+1/2δ. Similarly if ρ_GH(X,Y)<ε then X is a 5ε-approximation of Y.
      
      
          Suppose that X is an (ε,δ)-approximation of Y; then we have ε-nets A⊆ X and B⊆ Y of cardinality N such that such that |ρ_X(x_k,x_ℓ)-ρ_Y(y_k,y_ℓ)|<δ for all k, ℓ∈0,...,N-1. by definition. By the latter property, the correspondence R=(x_k,y_k)∈ A× B:k<N has distortion dis(R)<δ, i.e. ρ_GH(A,B)<1/2δ. Then by subadditivity
          
      ρ_GH(X,Y)≤ρ_GH(X,A)+ρ_GH(A,B)+ρ_GH(B,Y)<2ε+1/2δ.
  
          Now suppose that ρ_GH(X,Y)<ε and let A=x_n_n<N be a finite ε-net in X. By lemma <ref> we have a 2ε-isometry f:X→ Y; define B=f(A)=f(x_k)_k<N. Now
          
      |ρ_Y(f(x_k),f(x_ℓ))-ρ_X(x_k,x_ℓ)|≤dis(f)<2ε
  
          since f is a 2ε-isometry so it is sufficient to show that B is a 5ε-net in Y. In particular, since f(X) is a 2ε-net in Y, for each y∈ Y, there is an x∈ X such that ρ_Y(y,f(x))<2ε, while there is an x_k∈ A such that ρ_X(x,x_k)<ε since A is a ε-net in X. Thus for some k∈0,...,N-1 we have
          
      ρ_Y(y,f(x_k))≤ρ_Y(y,f(x))+ρ_y(f(x),f(x_k))≤ρ_Y(y,f(x))+dis(f)+ρ_X(x,x_k)<5ε.
  
          Since f(x_k)∈ B this proves the statement.
      
      We may now prove two central results from the perspective of emergent geometry. First note that if A is a ε-net in X then ρ_H(A,X)<ε.
      
          
              
    * Every compact metric space is the Gromov-Hausdorff limit of sequence of finite metric spaces.
              
    * Every compact length space is the Gromov-Hausdoff limit of a finite graph.
          
      
      
          Let X be a compact metric space.
          
              
    * For each n∈ℕ^+ take a sequence ε_n→ 0 and choose a finite ε_n-net A_n⊆ X; note that it is possible to choose a finite ε_n-net for each n because X is compact. Then ρ_GH(A_n,X)≤ρ_H(A_n,X)<ε_n for each n and we have the desired result i.e. X is the Gromov-Hausdorff limit of the spaces A_n.
              
    * See the proof of proposition 7.5.5 in <cit.>.
          
      
      
  
   §.§ Gromov-Hausdorff Convergence of Classical Configurations
  
      The aim of this section is to apply the general convergence results in the preceding section in order to show that S^1_r is the Gromov-Hausdorff limit of classical configurations of some statistical model. Let us warm-up by showing that—appropriately scaled—cylinders and Möbius strips converge to the circle:
      
      For each n∈ℕ^+, let Cyl_n=S^1_r×[-ℓ(n)/2,ℓ(n)/2] where S^1_r is the circle of radius r>0 where r is some fixed radius and ℓ(n) is defined as:
      
      ℓ(n)=2π r/n.
  
      Also let Mob_n denote the Möbius strip obtained by gluing the strip [0,ℓ(n)n]× [0,ℓ(n)] along the boundary lines (0,t)≅ (ℓ(n)n,ℓ(n)-t), t∈ [0,ℓ(n)]. The space Cyl_n may be regarded as Riemannian manifolds (with boundary) and thus as metric spaces when equipped with a metric defined via the line element
      
      d s^2=r^2dθ^2+d z^2,
  
      where (θ,z)∈ (-π,π]× [-ℓ(n)/2,ℓ(n)/2]. Since Möbius strips and cylinders are locally identical, mutatis mutandis the same holds for the spaces Mob_n.
      
      
          Let ℳ_n_n∈ℕ^+ denote a sequence of metric spaces such that ℳ_n∈Cyl_n,Mob_n for each n∈ℕ^+.
          Then
          
      lim_n→∞ℳ_n=S^1_r
  
          where convergence is in the sense of Gromov-Hausdorff.
      
      
      We use lemma <ref>; in particular, if we imbed ι:S^1_r↪ℳ_n as the central circle then we have
      
      ρ_GH(S^1_r,ℳ_n)≤ρ_H(ι(S^1_r),ℳ_n)=1/2ℓ(n)=π r/n
  
      since ι(S^1_r)⊆ℳ_n is an R-net in ℳ_n for all R>ℓ(n)/2 but the (ℓ(n)/2)-thickening of ι(S^1_r) does not cover (the boundary of) ℳ_n. Thus if we choose
      
      N= ⌈π r/ε⌉
  
      for any ε>0, this ensures that
      
      1/2ℓ(n)=π r/n<ε
  
      for all n>N as required.
      
      This of course formalises the naive intuition that as the width of a cylinder/Möbius strip vanishes we end up with a circle. 
      
      We have essentially the same result for prism graphs and Möbius ladders:
      
      Let ω_n_n>3 be a sequence of graphs such that ω_n∈P_n^ℓ(n),M_n^ℓ(n) for each value of n, where ℓ(n) is given as in equation <ref> and P_n^ℓ(n) and M_n^ℓ(n) are the graphs P_n and M_n respectively, with each edge weighted ℓ(n). The Gromov-Hausdorff limit of this sequence is S^1_r.
      
      
      We have
      
      ρ_GH(ω_n,S_r^1)≤ρ_GH(ω_n,ℳ_n)+ρ_GH(ℳ_n,S_r^1)=π r/n+ρ_GH(ω_n,ℳ_n)
  
      where ℳ_n is Cyl_n if ω_n=P_n^ℓ(n) and ℳ_n=Mob_n if ω_n=M_n^ℓ(n); to obtain the right-hand side we have applied subadditivity and used equation <ref> calculated in the course of the proof of proposition <ref>. It thus remains to bound ρ_GH(ω_n,ℳ_n); consider the natural imbedding ι:ω_n↪ℳ_n  of ω_n into the boundary. For any two points u, v∈ω_n that lie in the same circle S^1_r×-1/2ℓ(n) or S^1_r×1/2ℓ(n), the distance in both graphs is simply given by the length of the shorter circle segment connecting the two points and ρ_ω_n(u,v)=ρ_ℳ_n(ι(u),ι(v)). However if  u and v lie in distinct circles, i.e. u∈ S^1_r×-1/2ℓ(n) and v∈ S^1_r×1/2ℓ(n) we have a graph distance ρ_ω_n(u,v)=ℓ(n)+rθ where θ is the smaller angle between u and v, while
      
      ρ_ℳ_n(ι(u),ι(v))=√(ℓ(n)^2+r^2θ^2).
  
      Thus
      
      |ρ_ℳ_n(ι(u),ι(v))-ρ_ω_n(u,v)|=(ℓ(n)+rθ)-√(ℓ(n)^2+r^2θ^2).
  
      Maximising over pairs u, v∈ω_n gives
      
      sup |ρ_ℳ_n(ι(u),ι(v))-ρ_ω_n(u,v)|≤π r(1-√(1+ℓ(n)/rπ)) +ℓ(n)=π r(1-√(1+2/n)) +2π r/n.
  
      For n>2 we may use the binomial expansion to obtain
      
      sup |ρ_ℳ_n(ι(u),ι(v))-ρ_ω_n(u,v)|=π r/n+∑_k=2^∞1·(1-2)⋯(1-2(k-1))/k!n^-k.
  
      Thus
      
      ρ_GH(ω_n,S_r^1)≤2π r/n+∑_k=2^∞1·(1-2)⋯(1-2(k-1))/k!n^-k
  
      for all n>2. The right-hand side converges to 0 as n→∞ which shows that ρ_GH(ω_n,S_r^1)→ 0 as n→∞ which proves the statement. 
      
      We thus have the essential convergence result viz. any sequence of prism graphs/Möbius ladders converges to S^1. It remains to show that these graphs constitute the classical (action minimising) configurations. This is immediately achieved if we exclude triangles:
      
      Let (Ω^4(2N),𝒜) be the statistical model where Ω^4(2N) is the class of 3-regular graphs on 2N vertices of girth at least 4 and 𝒜 is the discrete Einstein-Hilbert action <ref>. Then the classical phase Ω_0^4(2N)=Ω_0∩Ω^4(2N)=P_N,M_N.
      
      
          Note that an edge has strictly positive curvature iff it supports a triangle by expression <ref> (whence it has curvature 1/3 or 2/3). Thus if the girth g(ω)>3 there are no triangles in ω and the maximum total curvature is thus 0; this is achieved iff ω is Ricci flat for N>3. Then the result follows by the classification of Cushing et al.
      
      
      Note that triangles must be effectively excluded in some manner due to the examples displayed in figure <ref>. Rather than insisting that the graphs have girth greater than 3, a bipartite model would also suffice and is perhaps a little more natural. In both cases we have suppressed triangles kinematically for certain, whereas ideally this would arise dynamically with high probability. In such a scenario, however, any precise results are likely to require significantly more involved methods for analogous results to be shown.
      
      The two lemmas in conjunction immediately give the following result:
      
          Let Ω^4(2n;ℓ(n)) denote the set of all 3-regular graphs on 2n vertices with girth at least 4 and with uniform edge weight ℓ(n). Also let ω_n denote a sequence of classical configurations of the statistical models (Ω^4(2n;ℓ(n)),𝒜) respectively. Then we have the Gromov-Hausdorff limit ω_n→ S^1_r as n→∞. 
      
      This theorem essentially shows that for large N and large β the Gibbs distribution for our model is concentrated on the circle S^1_r.
      
  
   §.§ General Covariance and Gromov-Hausdorff Limits
  
      We finish with some comments on the generally covariant nature of Gromov-Hausdorff limits. The main point has already been discussed in the introduction viz. Gromov-Hausdorff convergence characterises the limit invariantly essentially because one minimises over all possible metric backgrounds. However there are two technical points to bear in mind insofar as gravitational gauge transformations—typically and somewhat loosely referred to as diffeomorphisms in the physics literature—are generally interpreted as (local) Riemannian isometries connected to the identity. Firstly, it is not immediately obvious mathematically speaking that diffeomorphisms so characterised are in fact isometries with respect to the topological metric (geodesic distance); physically speaking the statement is rather obvious insofar as the geodesic distance between two point particles is essentially the classical action of a point particle along its trajectory and thus should be invariant under gauge transformations. Nonetheless the mathematical result is both nontrivial: the best argument has two steps. First one notes that local Riemannian isometries are also local metric (topological) isometries in the sense that they restrict to metric isometries on suitably chosen open balls; this follows by the naturality of the exponential map. The next step is to show that a bijective local metric isometry is a global isometry for arbitrary length spaces as long as long as the local isometry admit a continuous inverse. This is obviously the case for elements of the diffeomorphism group. If the local isometry does not have a continuous inverse then one can construct counterexamples showing that a local bijective isometry is not necessarily a global isometry. The second point to note is that the Gromov-Hausdorff limit does not simply factor out gauge transformations, it also factors out global symmetries, i.e. the group of connected components of the space of local Riemannian isometries. It is not clear to what extent these global symmetries apply to graphs in the limiting sequence.
      
      We shall briefly substantiate the claims relating to the first point. We shall use the following terminology:
      
          
              
    * Let (ℳ,g) and (𝒩,h) be Riemannian manifolds. A smooth mapping f:ℳ→𝒩 is said to be a Riemannian isometry iff for each p∈ℳ and all u, v∈ T_pℳ we have g_p(u,v)=h_f(p)(f_*u, f_*v). Let Isom_g(ℳ) denote the group of (Lie) group of local isometries equipped naturally with the compact-open topology. A Riemannian isometry f:ℳ→ℳ is a gauge transformation iff it is in the connected component of the identity of Isom_g(ℳ). 
              
    * Let (X,ρ_X) and (Y,ρ_Y) be metric spaces. A local isometry is a continuous mapping f:X→ Y such that for each p∈ X there is an r>0 such that f|B_r(p):B_r(p)→ f(B_r(p))=B_r(f(p)) is an isometry.
              
    * A global isometry or metric isometry is simply an isometry of metric spaces.
          
      
      We recall the definition of the exponential map in a Riemannian manifold:
      
          Let (ℳ,g) be a Riemannian manifold and fix a point p∈ℳ. We define the exponential map exp_p:U→ℳ for each u in some subset U⊆ T_pℳ by letting exp_p(u)=γ_u(1), where γ_u is the unique geodesic such that γ_u(0)=p and γ̇_u=u.
      
      exp_p restricts to a smooth mapping on B_r(0) into B_r(p) for r>0 sufficiently small. Naturality of the exponential map then takes the following form for any local isometry f:ℳ→ℳ: the diagram
      
      U⊆ T_pℳrf_*[swap]dexp_p    f_*U⊆ T_f(p)ℳdexp_f(p)
      ℳ[swap]rf   ℳ
  
      commutes for each p∈ℳ. Since f is a local isometry, the mapping f_*|B_r(0_p):B_r(0_p)→ f_*(B_r(0))=B_r(0_f(p)) is an isometry, so f|B_r(p)=exp_f(p)∘ f_*∘exp_p^-1|B_r(p). Noting that local isometries also preserve geodesics is enough to ensure that f|B_r(p):B_r(p)→ B_r(f(p)) is an isometry. The upshot is the following:
      
      Let f:ℳ→ℳ be a Riemannian isometry of the Riemannian manifold (ℳ,g). Then f is a local isometry.
      
      We now turn to local isometries in length spaces. Recall that a length space is a metric space in which the distance is equal to the infimum over lengths of a class of admissible curves. Both graphs and Riemannian manifolds are length spaces. More precisely, for any metric space (X,ρ_X), one considers a family 𝒞 of admissible curves γ:[a,b]→ X, where γ is at least piecewise continuous. The length of any admissible curve γ∈𝒞 is then defined by:
      
      L(γ)=sup∑_k=0^N-1ρ_X(γ(t_k),γ(t_k+1))
  
      where the supremum is taken over finite partitions a=t_0< t_1< ⋯ < t_N=b of the interval [a,b]. Together with the class 𝒞 of admissible curves the function L defines a length structure on X; associated to any length structure is an induced metric ρ_L:X× X→ℝ defined by
      
      ρ_L(x,y)=inf_γ∈𝒞(x,y) L(γ)       𝒞(x,y)=γ∈𝒞:γ(a)=x  and γ(b)=y.
  
      We call (X,ρ_X) a length space for some class of admissible curves 𝒞 when ρ_X=ρ_L. 
      
      We show that between length spaces, every local isometry preserves the length of curves:
      
          Let (X,ρ_X) and (Y,ρ_Y) be length spaces and let f:X→ Y be a local isometry such that each admissible curve in X is mapped to an admissible curve in Y.[Assuming that X is a topological space, Y is a length space and that f is a local homeomorphism there is a unique length structure on X making f into a local isomorphism mapping admissible curves to admissible curves. Thus our assumptions present no real restriction on possible length spaces.] Then L_X(γ)=L_Y(f∘γ) for any admissible curve γ:[a,b]→ X.
      
      
          Fix some ε>0 and choose a partition t_k_k≤ N of the interval [a,b] such that f|(t_k,t_k+1) is an isometry onto its image for each k∈0,...,N-1 and such that
          
      ∑_k ρ_X(γ(t_k),γ(t_k+1))   ≤ L_X(γ)< ∑_k ρ_X(γ(t_k),γ(t_k+1))+ε
      ∑_k ρ_Y(f(γ(t_k)),f(γ(t_k+1)))   ≤ L_Y(f∘γ)< ∑_k ρ_Y(f(γ(t_k)),f(γ(t_k+1)))+ε.
  
          This is possible because f is a local isometry and the length of an admissible curve is given by the supremum over partitions of the interval. Then
          
      L_Y(f∘γ)-ε   <∑_k ρ_Y(f(γ(t_k)),f(γ(t_k+1)))
         =∑_k ρ_X(γ(t_k),γ(t_k+1))
         ≤ L_X(γ)
         < ∑_k ρ_X(γ(t_k),γ(t_k+1))+ε
         =∑_k ρ_Y(f(γ(t_k)),f(γ(t_k+1)))+ε
         ≤ L_Y(f∘γ)+ε.
  
          Since this holds for all ε>0 we have L_X(γ)=L_Y(f∘γ) as required.
      In general a local isometry is not a global isometry.
      
          The mapping f:ℝ→ S^1 given by
          
      f:t ↦ (cos (t),sin (t))
  
          is a local but not global isometry.
      
      
          f obviously restricts to an isometry on any interval (a,b) such that b-a<π, since ρ_ℝ(x,y)=|x-y|<π for any x, y∈ (a,b) while ρ_S^1(x,y) is equal to rθ, where r=1 is the radius of S^1 and θ the smaller angle between the points f(x) and f(y). Since |x-y|<π, θ=|x-y|. f is obviously not a global isometry since ρ_S^1(f(0),f(2π))=0.
      
      We can show the following, however:
      
          Let (X,ρ_X) and (Y,ρ_Y) be length spaces.
          
              
    * Let f:X→ Y be a local isometry preserving admissible curves. The f is nonexpanding, i.e. ρ_X(x,y)≤ρ_Y(f(x),f(y)) for all x, y∈ X.
              
    * A bijective local isometry preserving admissible curves f:X→ Y is a global isometry iff f^-1:Y→ X is a local isometry preserving admissible curves. 
          
      
      
          
              
    * Since every admissible curve in X is mapped to an admissible curve in Y by f and since ρ_X and ρ_Y are given by infima over admissible curves of the lengths of the curves, the fact that f preserves the length of curves immediately guarantees this statement.
              
    * If f is a global isometry, ρ_X(x_1,x_2)=ρ_Y(y_1,y_2) where y_1=f(x_1) and y_2=f(x_2) for all x_1, x_2∈ X so ρ_Y(y_1,y_2)=ρ_X(f^-1(y_1),f^-1(y_2)) for all y_1, y_2∈ Y. Then f^-1 is a global isometry and thus a local isometry. Conversely, suppose that both f and f^-1 are local isometries preserving admissible curves. Then since f and f^-1 are both nonexpanding we have ρ_X(x,y)≤ρ_Y(f(x),f(y))≤ρ_X(f^-1(f(x)),f^-1(f(y)))=ρ_X(x,y) and f is a global isometry as required.
          
      
      We end with an essential condition for f^-1 to be a local isometry:
      
          Let (X,ρ_X) and (Y,ρ_Y) be length spaces and let f:X→ Y be a bijective local isometry. f^-1:Y→ X is a local isometry iff it is continuous.
      
      
          Local isometries are continuous by definition so necessity is trivial. For sufficiency note that since f^-1 is continuous, f(U) is open for any open set U of X; in particular if f is an isometry when restricted to some neighbourhood U of p∈ X, f^-1 restricts to an isometry on the open neighbourhood f(U) of f(p) making f^-1 a local isometry.
      
      
          Every gauge transformation f:ℳ→ℳ is a global isometry. 
      
      