$(D+1)$-Colored Graphs – a Review of Sundry Properties

$\boldsymbol{(D+1)}$-Colored Graphs – a Review
of Sundry Properties\star\star$\star$This paper is a contribution to the
Special Issue on Tensor Models, Formalism and Applications. The full
collection is available at
http://www.emis.de/journals/SIGMA/Tensor_Models.html

James P. RYAN

J.P. Ryan

Institute for Mathematics, Astrophysics and Particle Physics, Radboud
University,
Nijmegen, The Netherlands<EMAIL_ADDRESS>
Received March 18, 2016, in final form July 25, 2016; Published online August
02, 2016

We review the combinatorial, topological, algebraic and metric properties
supported by $(D+1)$-colored graphs, with a focus on those that are pertinent
to the study of tensor model theories. We show how to extract a limiting
continuum metric space from this set of graphs and detail properties of this
limit through the calculation of exponents at criticality.

colored graph theory; random tensors; quantum gravity

60C05; 81Q35; 81T17; 83C27

##  1 Introduction

This review focusses on the set of $(D+1)$-colored graphs, examining their
combinatorial, topological, algebraic and metric properties. Such graphs form
a subset of $(D+1)$-regular bipartite multigraphs distinguished by their
admission of a specific edge-labelling. These labels or _colors_ are the key
to their rich structure and the subsequent structural analysis.

Colored graphs arise mainly in two areas of the literature. Historically, they
were first developed as a graph-theoretic tool to address challenges in
piecewise-linear topology. See [13] for an interesting review. More recently,
they have experienced a resurgence of attention in the context of quantum
gravity. As the Feynman graphs of tensor models/tensorial group field theories
[22, 28], they may form the groundwork for the systematic definition of a non-
trivial, physically interesting probability measure over quantum geometries.

From the tensor model perspective, the reason to concentrate a review purely
on graph-theoretic properties is clearly motivated. Despite their striking
similarities, tensors lack many of the powerful tools that are available for
matrices [11]. Thus, tensor model calculations rely for the moment quite
heavily on one’s ability to control and analyze the properties of sufficiently
interesting subsets of $(D+1)$-colored graphs.

The review falls into two parts. Sections 2 and 3 introduce and analyse the
combinatorial, topological and algebraic properties on the whole set of
$(D+1)$-colored graphs. Afterwards, Section 4 narrows the scope to the melonic
subset, which permits a more in-depth analysis of their metric properties.

In Section 2, we shall begin by carefully detailing the structure of
$(D+1)$-colored graphs. From there, we use the colors to construct a topology
on each graph. As a by-product of this construction, we demonstrate that such
graphs encode $D$-dimensional simplicial pseudomanifolds. Thereafter, we show
that the set of $(D+1)$-colored graphs admits several equivalence structures,
one of which is known as combinatorial core equivalence. Each such class has
preferred representatives, known as combinatorial core graphs and we present
an algorithm that reduces a given graph to an equivalent core graph. To finish
this section, we identify a graph’s jackets: specific embedded Riemann
surfaces. They can be used to define an important combinatorial invariant,
known as the degree. We detail some properties of the degree and its
significance for the identification of melonic spheres.

In Section 3, we define the Lie algebraic structure supported by
$(D+1)$-colored graphs. In Section 4, we focus entirely on one combinatorial
core equivalence class: the (rooted) melonic graphs. We examine a metric
structure thereon and most interestingly a continuum limit within this set of
graphs. This limit has associated numbers, known as exponents, that help
identify the limiting continuum metric space. We focus on three exponents: the
susceptibility, Hausdorff dimension and spectral dimension. All three indicate
that continuum metric space coincides with that of branched polymers
spacetimes.

As hinted above, this review rarely mentions its roots in either piecewise
linear topology or tensor models. However, we take more care to highlight
connections to the latter, while rarely, if ever, mention the former. Having
said that, this is by no means a comprehensive review of all tensor model
inspired, graph-theoretic properties. We make no effort to detail the
properties of $(D+1)$-colored graphs with additional labels, which may be
identified as matter [7, 9], dual-weighting [6], richly-geometric [4, 5]. We
refrain from mentioning graph-theoretic properties pertaining to other core
equivalence classes [10, 24] or to multi-orientiable models [30, 31].

###  1.1 Notation

With such intricately labelled structures, a careful notation is required to
decode the richly layered information. The colors associated to the edges are
drawn from $\\{0,1,\dots,D\\}$. We shall be often interested in subsets
$\\{i,j,\dots,k\\}$ and their complements
$\\{\widehat{i},\widehat{j},\dots,\widehat{k}\\}=\\{0,\dots,D\\}\setminus\\{i,j,\dots,k\\}$.

##  2 Combinatorial and topological properties

###  2.1 Closed, open and boundary graphs

Colored graphs are regular bipartite graphs that admit a specific labelling of
the edges. Such graphs come in three varieties – closed, open and boundary.
Such qualifiers hint at a topological structure that we shall detail in due
course. For the moment, we shall content ourselves with providing the
following rather dry definitions:

######  Definition 2.1 (closed graph).

A closed $(D+1)$-colored graph is a graph
${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$ with vertex set ${\mathcal{V}}$
and edge set ${\mathcal{E}}$ such that:

  * •

${\mathcal{V}}$ is bipartite, that is, there is a partition of the vertex set
${\mathcal{V}}=V\cup\bar{V}$, such that for any element $l\in{\mathcal{E}}$,
then $l=\\{v,\bar{v}\\}$ where $v\in V$ and $\bar{v}\in\bar{V}$. Their
cardinalities satisfy $|{\mathcal{V}}|=2|V|=2|\bar{V}|$.

  * •

The edge set is partitioned into $D+1$ subsets
${\mathcal{E}}=\bigcup_{i=0}^{D}E^{i}$, where $E^{i}$ is the subset of edges
with color $i$.

  * •

It is $(D+1)$-regular (i.e., all vertices are $(D+1)$-valent) with all edges
incident to a given vertex having distinct colors.

The elements $v\in V$ ($\bar{v}\in\bar{V}$) are commonly referred to as the
positive (negative) vertices. Given a projection of the graph onto a plane,
one arranges the colors consistently in a clockwise (anti-clockwise) manner.
Moreover, it is worth noticing that the bipartition induces an orientation on
the edges, say from $v$ to $\bar{v}$. See Fig. 1 for an example.

Figure 1: A closed $(D+1)$-colored graph ($D=3$).

######  Definition 2.2 (open graph).

An open $(D+1)$-colored graph is a graph ${\mathcal{G}}$ satisfying some
additional constraints:

  * •

It is bipartite, that is, there is a partition of the vertex set
${\mathcal{V}}=V\cup\bar{V}$, such that for any element $l\in{\mathcal{E}}$,
then $l=\\{v,\bar{v}\\}$ where $v\in V$ and $\bar{v}\in\bar{V}$. Moreover,
their cardinalities also satisfy $|{\mathcal{V}}|=2|V|=2|\bar{V}|$.

  * •

The positive vertices are of two types $V=V_{\rm int}+V_{\partial}$, where
$V_{\rm int}$ is the set of $(D+1)$-valent internal vertices and the elements
of $V_{\partial}$ are 1-valent boundary vertices. A similar distinction holds
for negative vertices.

  * •

The edge set is partitioned into $D+1$ subsets
${\mathcal{E}}=\bigcup_{i=0}^{D}E^{i}$, where $E^{i}$ is the subset of edges
with color $i$. Furthermore, each $E^{i}=E^{i}_{\rm int}\cup E^{i}_{\rm ext}$,
such that internal edges $E^{i}_{\rm int}$ join two internal vertices, while
external edges $E^{i}_{\rm ext}$ join an internal vertex to a boundary vertex.

######  Remark 2.3.

In this text, we consider only _connected_ closed and open graphs. This is not
just for the convenience of subsequent analysis, but is well motivated by
their usage in tensor model theories; the terms in the perturbative expansion
of tensor model cumulants are neatly labelled by connected graphs.

The open graphs induce a boundary graph structure [15] as follows:

######  Definition 2.4 (boundary graph).

The boundary graph ${\mathcal{G}}_{\partial}$ of an open $(D+1)$-colored graph
${\mathcal{G}}$ comprises of:

  * •

the vertex set ${\mathcal{V}}_{\partial}=V_{\partial}\cup\bar{V}_{\partial}$.
We stress that it is not bipartite with respect to this splitting. The
vertices inherit the color from the external edges of ${\mathcal{G}}$ upon
which they lie, so that a more appropriate partition is
${\mathcal{V}}_{\partial}=\bigcup_{i=0}^{D}{\mathcal{V}}_{\partial}^{i}$,
where ${\mathcal{V}}_{\partial}^{i}$ denotes the set of boundary vertices with
color $i$.

  * •

the edge set ${\mathcal{E}}_{\partial}=\mathop{\bigcup_{i\neq
j}}E^{ij}_{\partial}$, where $l^{ij}=\\{v,w\\}\in E^{ij}_{\partial}$ exists if
there is a bi-colored path from $v$ to $w$ in ${\mathcal{G}}$ consisting of
colors $i$ and $j$. Thus, the lines $E^{ij}_{\partial}$ inherit the colors of
the path in ${\mathcal{G}}$.

A cursory investigation of these boundary graphs reveals that they possess a
number of additional properties. The edge $l^{ij}\in E_{\partial}^{ij}$ can
only exist if $l^{ij}=\\{v^{i},w^{i}\\}$ or $\\{v^{i},w^{j}\\}$ or
$\\{v^{j},w^{i}\\}$ or $\\{v^{j},w^{j}\\}$, where
$v^{i},w^{i}\in{\mathcal{V}}_{\partial}^{i}$ and
$v^{j},w^{j}\in{\mathcal{V}}_{\partial}^{j}$. Each boundary vertex is
$D$-valent and for $v^{i}\in{\mathcal{V}}_{\partial}^{i}$, the incident
boundary edges are $l^{ij}$ where $j=\hat{i}$. Several examples are presented
in Fig. 2.

Figure 2: Open 4-color graphs and their corresponding boundary graphs.

######  Remark 2.5.

A priori, the boundary graph ${\mathcal{G}}_{\partial}$ is a very different
beast from the initial graph ${\mathcal{G}}$; afterall, it has colored
vertices and bicolored edges. Moreover, a connected open graph can have a
boundary with several connected components. However, from a topological
perspective, these disparate structures dovetail elegantly. We shall return to
this later.

###  2.2 Cellular structure and pseudomanifolds

Such heavily labelled graphs display a beautiful hierarchy that is key to
their utility [14, 16]. Importantly, it supports a $D$-dimensional topological
structure. We shall now expose this for a generic $(D+1)$-colored graph
${\mathcal{G}}$.

######  Definition 2.6 ($d$-bubble).

The $d$-bubble of ${\mathcal{G}}$ is the maximally connected subgraph
comprising of edges with $d$ fixed colors.

Obviously, $d\in\\{0,\dots,D\\}$. The $d$-bubbles are denoted by
${\mathcal{B}}^{i_{1}\dots i_{d}}_{(\rho)}$; the color indices are ordered
$i_{1}<i_{2}<\dots<i_{d}$ to uniquely identify the particular _species_ of
$d$-bubble, while $\rho$ distinguishes connected components of the same
species. We denote the number of $d$-bubbles of the graph by
${\mathcal{B}}^{[d]}$. One should note that the 0-bubbles are the vertices of
${\mathcal{G}}$, the 1-bubbles are the edges of ${\mathcal{G}}$. The
$2$-bubbles are the faces of ${\mathcal{G}}$.

Figure 3: $3$-bubbles of a graph in $D=3$.

In Fig. 3, we present the $3$-bubbles associated to the graph given in Fig. 1.
The $3$-bubbles are indexed by the colors of their lines, namely from left to
right $123$, $023$, $013$ and $012$. The $2$-bubbles are the subgraphs
catalogued by color pairs $01$, $02$, $03$, $12$, $13$ and $23$. The
$1$-bubbles are the lines $0$, $1$, $2$ and $3$, while the $0$-bubbles are the
vertices.

Constructing the dual complex. These $d$-bubbles are key to defining a
topology, in particular, a $D$-dimensional cellular complex structure. To this
end, we shall construct the dual _finite abstract simplicial complex_. Quite
clearly, the graph complex and the dual complex are the same topological
space. Note that we write ${\mathcal{H}}\subset{\mathcal{G}}$, if
${\mathcal{H}}$ is a subgraph of ${\mathcal{G}}$. To construct the dual
complex [14]:

  * •

We first assemble all the $D$-bubbles of ${\mathcal{G}}$ into a set $A$:

$\displaystyle A=\Bigl{\\{}{\mathcal{B}}^{\widehat{i}}_{(\rho)}\colon
i\in\\{0,\dots,D\\},\;\rho\;\textrm{unrestricted}\Bigr{\\}}.$

  * •

For each $(D+1-d)$-bubble within ${\mathcal{G}}$, $d\in\\{1,\dots,D+1\\}$, we
form the following subset of $A$:

$\displaystyle\sigma^{{\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}}=\Bigl{\\{}{\mathcal{B}}^{\widehat{i}_{k}}_{(\rho)}\colon{\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}\subset{\mathcal{B}}^{\widehat{i}_{k}}_{(\rho)},\;k\in\\{1,\dots,d\\}\Bigr{\\}}\subset
A.$

In fact, for a given $(D+1-d)$-bubble
${\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}$,
there is, for each $k\in\\{1,\dots,d\\}$, a unique $D$-bubble
${\mathcal{B}}^{\widehat{i}_{k}}_{(\rho)}\supset{\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}$.
This is the maximal connected component (in ${\mathcal{G}}$) obtained by
starting from
${\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}$
and adding edges of all colors except $i_{k}$. Thus, the cardinality of
$\sigma^{{\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}}$
is $d$.

  * •

As a result, any subset
$\tau\in\sigma^{{\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}}$
is indexed by a choice of subset $S\subset\\{1,\dots,d\\}$:

$\displaystyle\tau=\Bigr{\\{}{\mathcal{B}}^{\widehat{i}_{k}}_{(\rho)}\,|\,{\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}\subset{\mathcal{B}}^{\widehat{i}_{k}}_{(\rho)},\;k\in\\{1,\dots,d\\}\setminus
S\Bigl{\\}}.$

So
$\tau=\sigma^{{\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d-|S|}}_{(\xi)}}$,
where
${\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d-|S|}}_{(\xi)}$
is the unique subgraph obtained by adding the colors $i_{s}$, $s\in S$, to the
subgraph
${\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}$.

  * •

The final crucial detail is that the sets
$\sigma^{{\mathcal{B}}^{\widehat{i}_{1}\widehat{i}_{2}\dots\widehat{i}_{d}}_{(\kappa)}}$
are the $(d-1)$-simplices of a finite abstract simplicial complex, defined as

$\displaystyle\Delta=\Big{\\{}\sigma^{{\mathcal{B}}^{\hat{i}_{1}\hat{i}_{2}\dots\hat{i}_{d}}_{(\kappa)}}\,|\,{\mathcal{B}}^{\hat{i}_{1}\hat{i}_{2}\dots\hat{i}_{d}}_{(\kappa)}\subset{\mathcal{G}}\Big{\\}}.$

It is straightforward to verify the defining property of an abstract
simplicial complex: that for all $\sigma\in\Delta$ and $\tau\subset\sigma$,
then $\tau\in\Delta$. The cardinality of $\sigma\in\Delta$ is $d$ (it
corresponds to a $(D+1-d)$-bubble) and so its dimension is $d-1$.

  * •

In fact, since $\Delta$ is _non-branching_ , _strongly connected_ and _pure_ ,
it is a $D$-dimensional simplicial pseudomanifold [14].

######  Remark 2.7 (duality).

The vertices of the graph correspond to the $D$-simplices of the simplicial
complex. The half-lines of a vertex represent the $(D-1)$-simplices bounding a
$D$-simplex and have a color. Any lower-dimensional sub-simplex is colored by
the colors of the $D-1$ simplices sharing it. In Fig. 4 we sketched the dual
complex in $D=3$ dimensions. The vertices are dual to tetrahedra. A triangle
(say $3$) is dual to a line (of color $3$) and separates two tetrahedra. An
edge (say common to the triangles $2$ and $3$) is dual to a face (2-bubble of
colors $2$ and $3$). A vertex (say common to the triangles $0$, $2$ and $3$)
is dual to a $3$-bubble (of colors $0$, $2$ and $3$).

Figure 4: The dual complex in $D=3$.

######  Remark 2.8 (boundary graph).

Let us return for a moment to examine the structure of a boundary graph
${\mathcal{G}}_{\partial}$. Such a graph may have multiple connected
components but each component has a cellular complex structure. For $d\geq 1$
the boundary $d$-bubbles $({\mathcal{B}}_{\partial})^{i_{1}\dots
i_{d+1}}_{(\rho)}$ are the maximally connected components of
${\mathcal{G}}_{\partial}$ formed by boundary vertices $v^{i_{a}}$ and
boundary edges $l^{i_{b}i_{c}}$, where
$i_{a},i_{b},i_{c}\in\\{i_{1},\dots,i_{d+1}\\}$. Following an analogous
construction to that outlined above, but taking into account that the boundary
$d$-bubbles have $d+1$ colors, one can show that each connected component of
${\mathcal{G}}_{\partial}$ is dual to a simplicial complex (and is a
pseudomanifold). In fact, the simplicial complex dual to
${\mathcal{G}}_{\partial}$ is the boundary of the simplicial complex dual to
${\mathcal{G}}$.

Consequently, this motivates the study of these structures homological
properties.

###  2.3 Colored homology

The topological spaces defined by $(D+1)$-colored graphs are amenable to both
a homological and homotopical analysis. The colored homology is defined for
the graph complex [16] as follows:

######  Definition 2.9 (chain group).

The $d$-th chain group is the group finitely generated by the $d$-bubbles

$\displaystyle\alpha_{d}=\sum_{{\cal B}^{i_{1}\dots
i_{d}}_{(\rho)}\subset{\mathcal{G}}}c^{i_{1}\dots i_{d}}_{(\rho)}{\cal
B}^{i_{1}\dots i_{d}}_{(\rho)},\qquad c^{i_{1}\dots
i_{d}}_{(\rho)}\in\mathbb{Z}.$

The chain groups define homology groups via a boundary operator:

######  Definition 2.10 (boundary operator).

The $d$-th boundary operator $\partial_{d}$ acting on a $d$-bubble ${\cal
B}^{i_{1}\dots i_{d}}_{(\rho)}$ is:

  * •

For $d\geq 2$,

$\displaystyle\partial_{d}({\cal B}^{i_{1}\dots
i_{d}}_{(\rho)})=\sum_{q=1}^{d}(-1)^{q+1}\sum_{{\mathcal{B}}^{i_{1}\dots\widehat{i_{q}}\dots
i_{d}}_{(\kappa)}\subset{\cal B}^{i_{1}\dots
i_{d}}_{(\rho)}}{\mathcal{B}}^{i_{1}\dots\widehat{i_{q}}\dots
i_{d}}_{(\kappa)},$

which associates to a $d$-bubble the alternating sum of all $(d-1)$-bubbles
formed by subsets of its vertices.

  * •

For $d=1$, since the edges ${\mathcal{B}}^{i}_{(\rho)}$ connect a positive
vertex $v$ to a negative one $\bar{v}$:

$\displaystyle\partial_{d}{\mathcal{B}}^{i}_{(\rho)}=v-\bar{v}.$

  * •

For $d=0$, $\partial_{0}v=\partial_{0}\bar{v}=0$.

The colored boundary operators extend linearly over chains and thereafter
define a homology as $\partial_{d-1}\circ\partial_{d}=0$ [16]. Thus we define
the $d$-th colored homology group to be
$H_{d}\equiv\operatorname{ker}(\partial_{d})/\operatorname{Im}(\partial_{d+1})$.

These graphs also facilitate a finite presentation of their fundamental group
by associating a generator to all edges of ${\mathcal{G}}$ (apart from those
edges lying on a maximal tree) and a relation to all faces of ${\mathcal{G}}$.

###  2.4 Equivalence: combinatorial and topological

Colored graphs support a class of moves, termed $k$-dipole moves [18, 19, 21],
that have a well controlled effect on their bubble structure. A priori, these
are combinatorial in nature and allow one to set up the notion of
combinatorial equivalence. However, a subset are homeomorphisms of the graph
complex, thus setting the stage for topological equivalence.

######  Definition 2.11 ($k$-dipole).

A $k$-dipole $d_{k}$ is a subset of ${\mathcal{G}}$ comprising of two vertices
$v$, $\bar{v}$ such that:

  * •

$v$ and $\bar{v}$ share $k$ edges colored by
$i_{1},\dots,i_{k}\in{\mathbb{Z}}_{D+1}$;

  * •

$v$ and $\bar{v}$ lie in distinct $(D+1-k)$-bubbles:
$B^{\hat{i}_{1}\dots\hat{i}_{k}}_{(\alpha)}\neq
B^{\hat{i}_{1}\dots\hat{i}_{k}}_{(\beta)}$.

We say that $d_{k}$ _separates_ the bubbles
$B^{\hat{i}_{1}\dots\hat{i}_{k}}_{(\alpha)}$ and
$B^{\hat{i}_{1}\dots\hat{i}_{k}}_{(\beta)}$. Yet more important is how one
manipulates the graph structure with respect to these subsets.

######  Definition 2.12 ($k$-dipole moves).

The process of $k$-dipole contraction:

  * •

deletes the vertices $v_{1}$ and $v_{2}$;

  * •

deletes the edges $i_{1},\dots,i_{k}$;

  * •

connects the remaining edges respecting coloring, see Fig. 5.

The process of $k$-dipole creation is precisely the inverse. We denote by
${\mathcal{G}}/d_{k}$ the graph obtained from ${\mathcal{G}}$ by contracting
$d_{k}$. Note that the separation property makes the identification and
creation of $k$-dipoles somewhat subtle.

Figure 5: The process of $k$-dipole contraction/creation in the case
$i_{p}=p-1$ for all $p\in\\{1,\dots,k\\}$.

######  Definition 2.13 (combinatorial equivalence).

Two graphs as said to be combinatorially equivalent, denoted $\sim^{(c)}$, if
they are related by a sequence of $k$-dipole contractions and creations.

Together with combinatorial equivalence, comes the idea of combinatorial
equivalence class. With the variety of moves available, these classes may have
more or less restrictive membership requirements. One particularly useful set
of classes respects 1-dipole moves. These are known as the _combinatorial core
equivalence classes_.

######  Definition 2.14 (combinatorial core graph).

A combinatorial core graph at order $p$, denoted ${\mathcal{G}}^{(c)}_{p}$, is
a $(D+1)$-colored graph with $2p$ vertices, such that for all colors $i$, it
has a unique $D$-bubble ${\mathcal{R}}^{\widehat{i}}_{(1)}$.

Combinatorial bubble routing algorithm. What is more, every colored graph is
combinatorially equivalent to (at least) one combinatorial core graph via the
contraction of a maximal set of 1-dipoles:

  * •

Designate a root. For a given color $i$, we pick one of the $D$-bubbles
${\mathcal{B}}^{\widehat{i}}_{(\rho)}$ as a root
${\mathcal{R}}^{\widehat{i}}_{(1)}$ bubble. The total number of roots of a
graph is ${\mathcal{R}}^{[D]}=D+1$.

  * •

Identify $\widehat{i}$-connectivity graph. We associate to the bubbles
$\widehat{i}$ of ${\mathcal{G}}$ an $\widehat{i}$-_connectivity graph_. Its
vertices represent the various bubbles ${\mathcal{B}}^{\widehat{i}}_{(\rho)}$.
Its lines are the lines of color $i$ in ${\mathcal{G}}$. They either start and
end on the same bubble ${\mathcal{B}}^{\widehat{i}}_{(\alpha)}$, known as
tadpole lines in the connectivity graph, or they do not. A particularly simple
way to picture the $\widehat{i}$-connectivity graph is to draw ${\mathcal{G}}$
with the lines $j\neq i$ much shorter than the lines $i$.

  * •

Choose a tree. We chose a tree ${\mathcal{T}}^{i}$ in the
$\widehat{i}$-connectivity graph, such that its root is
${\mathcal{R}}^{\widehat{i}}_{(1)}$. We refer to the rest of the lines of
color $i$ as loop lines.

  * •

Contract. All the ${\mathcal{B}}^{[\widehat{i}]}-1$ lines of
${\mathcal{T}}^{i}$ are 1-dipoles and we contract them. We end up with a
connectivity graph with only one vertex corresponding to the root bubble
${\mathcal{R}}^{\widehat{i}}_{(1)}$. The remaining lines of color $i$ cannot
be contracted further (they are tadpole lines in the connectivity graph). The
number of the $D$-bubbles of the other colors is unchanged under these
contractions.

  * •

Repeat. We iterate the previous three points for all colors starting with $D$.
The routing tree ${\mathcal{T}}^{j}$ is chosen in the graph obtained after
contracting ${\mathcal{T}}^{j+1},\dots,{\mathcal{T}}^{D}$. The number of
bubbles of colors $q>j$ are constant under contractions of $1$-dipoles of
color $j$, hence the latter cannot create new 1-dipoles of color $q$. Reducing
a full set of 1-dipoles indexed by $D+1$ routing trees
${\mathcal{T}}^{0},\dots,{\mathcal{T}}^{D}$ we obtain a graph in which all
bubbles are roots. This is precisely a _combinatorial core graph_.

This gives rise to:

######  Definition 2.15 (combinatorial core equivalence class).

A combinatorial core equivalence class is a set of graphs related by sequences
of 1-dipole moves.

######  Remark 2.16 (non-uniqueness of rooting).

The rooting algorithm allows us to pick a representative for each core
equivalence class. However, the combinatorial core graph one obtains by the
above routing procedure is _not_ independent of the routing trees. The same
graph leads to several equivalent core graphs, all at the same order $p$.

We now briefly mention the topological analogue. We shall utilize a
fundamental result from combinatorial topology [12, 27]:

######  Theorem 2.17 (topological $k$-dipole).

Two pseudomanifolds dual to ${\mathcal{G}}$ and ${\mathcal{G}}/d_{k}$ are
homeomorphic if one of the $(D+1-k)$-bubbles
${\mathcal{B}}^{\widehat{i}_{0}\dots\widehat{i}_{k-1}}_{(\alpha)}$ or
${\mathcal{B}}^{\widehat{i}_{0}\dots\widehat{i}_{k-1}}_{(\beta)}$ separated by
the dipole is dual to a sphere $S^{D-k}$.

This allows us to propose another equivalence relation on the set of colored
graphs:

######  Definition 2.18 (topological equivalence).

Two graphs are said to be topologically equivalent, denoted $\sim^{(t)}$, if
they are related by a sequence of topological dipole contraction and creation
moves.

With appropriate modifications, one can define topological core graph,
topological core equivalence class and topological bubble rooting algorithm.
We relinquish the details to other sources [21, 22].

Moreover, $(D+1)$-colored graphs representing manifolds are related, through
the combinatorial/topological bubble routing algorithms to core graphs that
are called crystallizations in the graph-encoded manifold literature [13]. The
combinatorial and topological bubble routing algorithms coincide for
manifolds, since all $D$-bubbles are homeomorphic to spheres and the routing
algorithms only involve dipole contraction111Combinatorial 1-dipole insertion
may produce two non-spherical $D$-bubbles from an initial spherical one..

###  2.5 Jackets and degree

As we have seen, the bubble structure captures the rich topology supported by
these colored graphs. As a result, it tends to be rather intricate and subtle.
We should also like to have a somewhat blunter tool that captures only some of
the information encoded by the colors.

This tool is provided by the _jackets_. Their main advantage is that they are
just ribbon graphs, like those generated by matrix models. As such they are
Riemann surfaces embedded in the cellular complex and thus the subset of
topological information that they capture is nicely encapsulated by their
genera.

######  Definition 2.19 (jacket).

A colored jacket ${\mathcal{J}}$ is a 2-subcomplex of ${\mathcal{G}}$, labeled
by a $(D+1)$-cycle $\tau$, such that:

  * •

${\mathcal{J}}$ and ${\mathcal{G}}$ have identical vertex sets,
${\mathcal{V}}_{\mathcal{J}}={\mathcal{V}}_{\mathcal{G}}$;

  * •

${\mathcal{J}}$ and ${\mathcal{G}}$ have identical edge sets,
${\mathcal{E}}_{\mathcal{J}}={\mathcal{E}}_{\mathcal{G}}$;

  * •

the face set of ${\mathcal{J}}$ is a subset of the face set of
${\mathcal{G}}$:
${\mathcal{F}}_{{\mathcal{J}}}=\\{f\in{\mathcal{F}}_{{\mathcal{G}}}\,|\,f=(\tau^{q}(0),\tau^{q+1}(0)),\,q\in{\mathbb{Z}}_{D+1}\\}$.

######  Remark 2.20 (connectivity and abundance).

It is evident that ${\mathcal{J}}$ and ${\mathcal{G}}$ have the same
connectivity. In actual fact, a given jacket is independent of the overall
orientation of the cycle, meaning that the number of jackets is in one-to-two
correspondence with $(D+1)$-cycles. Therefore, the number of independent
jackets is $D!/2$ and the number of jackets containing a given face is
$(D-1)!$.

######  Remark 2.21 (jackets as ribbon graphs).

The jacket has the structure of a _ribbon graph_. Note that each edge of
${\mathcal{J}}$ lies on the boundary of two of its faces. Thus, it corresponds
to a ribbon line in the ribbon graph. As we said, the ribbon lines separate
two faces, $(\tau^{-1}(i),i)$ and $(i,\tau(i))$ and inherit the color $i$ of
the line in ${\mathcal{J}}$. Ribbon graphs are well-known to correspond to
Riemann surfaces, and so the same holds for jackets. Given this, we can define
the _Euler characteristic_ of the jacket as:
$\chi({\mathcal{J}})=|{\mathcal{F}}_{\mathcal{J}}|-|{\mathcal{E}}_{\mathcal{J}}|+|{\mathcal{V}}_{\mathcal{J}}|=2-2g_{\mathcal{J}}$,
where $g_{{\mathcal{J}}}$ is the _genus_ of the jacket222A moment’s reflection
reveals that the jackets necessarily represent orientable surfaces..

######  Remark 2.22 (examples).

In $D=2$, the (unique) jacket of a $(2+1)$-colored graph is the graph itself.
An example of a graph and its jackets (and their associated cycles) is given
in Fig. 6. For instance the leftmost jacket corresponding to the cycle
$\tau=(0123)$ contains only the faces $01$, $12$, $23$ and $30$.

Figure 6: A vacuum 4-colored graph and its jackets.

######  Remark 2.23 (jackets and $d$-bubbles).

For a $(D+1)$-colored graph ${\mathcal{G}}$, its $D$-bubbles are $D$-colored
graphs ${\mathcal{B}}_{(\rho)}^{\widehat{i}}$. Thus, they also possess
jackets, which we denote by ${\mathcal{J}}_{(\rho)}^{\widehat{i}}$. It is
rather elementary to construct the ${\mathcal{J}}^{\widehat{i}}_{(\rho)}$ from
the ${\mathcal{J}}$. Let us construct the ribbon graph
${\mathcal{J}}^{\widehat{i}}$ consisting of vertex, edge and face sets:

$\displaystyle{\mathcal{V}}_{{\mathcal{J}}^{\widehat{i}}}={\mathcal{V}}_{{\mathcal{J}}},\qquad{\mathcal{E}}_{{\mathcal{J}}^{\widehat{i}}}={\mathcal{E}}_{{\mathcal{J}}}\setminus
E^{i},\qquad\textrm{and}$
$\displaystyle{\mathcal{F}}_{{\mathcal{J}}^{\widehat{i}}}=\big{(}{\mathcal{F}}_{\mathcal{J}}\setminus\big{\\{}\big{(}\tau^{-1}(i),i\big{)},(i,\tau(i))\big{\\}}\big{)}\cup\big{\\{}\big{(}\tau^{-1}(i),\tau(i)\big{)}\big{\\}},$

that is having all vertices of ${\mathcal{G}}$, all lines of ${\mathcal{G}}$
of colors different from $i$ and some faces. Given that the face set of
${\mathcal{J}}$ is specified by a $(D+1)$-cycle $\tau$, the first thing to
notice is that the face set of ${\mathcal{J}}^{\hat{i}}$ is specified by a
$D$-cycle obtained from $\tau$ by deleting the color $i$. The ribbon subgraph
${\mathcal{J}}^{\widehat{i}}$ is the union of several connected components,
${\mathcal{J}}^{\widehat{i}}_{(\rho)}$. Each
${\mathcal{J}}^{\widehat{i}}_{(\rho)}$ is a jacket of the $D$-bubble
${\mathcal{B}}^{\widehat{i}}_{(\rho)}$. Conversely, every jacket of
${\mathcal{B}}^{\widehat{i}}_{(\rho)}$ is obtained from exactly $D$ jackets of
${\mathcal{G}}$. To realize this, consider a jacket
${\mathcal{J}}^{\widehat{i}}_{(\rho)}$. It is specified by a $D$-cycle
(missing the color $i$). On can insert the color $i$ anywhere along the cycle
and thus get $D$ independent $(D+1)$-cycles.

More generally, the $d$-bubbles are $d$-colored graphs and they also possess
jackets which can be obtained from the jackets of ${\mathcal{G}}$.

Consider once again Fig. 6. Applying our procedure to the jacket $(0123)$
leads to the three jackets $(123)$, $(023)$ and $(012)$. Each of these jackets
corresponds to a bubble of Fig. 3 and is a 3-colored graph.

######  Definition 2.24 (degree).

We define:

  * •

the (convergence) degree of a graph ${\mathcal{G}}$ is
$\omega({\mathcal{G}})=\sum_{{\mathcal{J}}}g_{{\mathcal{J}}}$, where the sum
runs over all the jackets ${\mathcal{J}}$ of ${\mathcal{G}}$,

  * •

the degree of a $k$-dipole $d_{k}$ is the lesser of the degrees of the two
$(D+1-k)$-bubbles that it separates.

######  Remark 2.25 (properties of the degree).

The degree displays a number of pertinent properties:

  * •

The degree is a non-negative integer that is readily computable from the graph
(as it is the sum of the genera of the embedded jackets).

  * •

The degree of a graph $\omega({\mathcal{G}})$ and its $D$-bubbles
$\omega\big{(}{\mathcal{B}}^{\widehat{i}}_{(\rho)}\big{)}$ are not
independent, that is, they respect

$\displaystyle\omega({\mathcal{G}})=\frac{(D-1)!}{2}\big{(}p+D-{\mathcal{B}}^{[D]}\big{)}+\sum_{i;\rho}\omega\big{(}{\mathcal{B}}^{\widehat{i}}_{(\rho)}\big{)},$

where $2p$ is the number of vertices in ${\mathcal{G}}$ and
${\mathcal{B}}^{[D]}$ is the total number of $D$-bubbles of all colors.

  * •

The degree of a graph changes under $k$-dipole contraction
${\mathcal{G}}\rightarrow{\mathcal{G}}/d_{k}$. The degree of ${\mathcal{G}}$
and ${\mathcal{G}}/d_{k}$ are related by

$\displaystyle\omega({\mathcal{G}})=\frac{(D-1)!}{2}\big{(}(D+1)k-k^{2}-D\big{)}+\omega({\mathcal{G}}/d_{k}).$

In particular, the degree is unchanged by any 1-dipole move. As a consequence,
all graphs in a combinatorial core equivalence class have the same degree.

  * •

Let ${\mathcal{G}}$ be a $D+1$ colored graph and
${\mathcal{B}}^{\widehat{D}}_{(\rho)}$ its $D$-bubbles with colors
$\widehat{D}$. Then

$\displaystyle\omega({\mathcal{G}})\geq
D\sum_{\rho}\omega\big{(}{\mathcal{B}}^{\widehat{D}}_{(\rho)}\big{)}.$

######  Remark 2.26 (ramifications of vanishing degree: melonic graphs).

One particular core equivalence class is distinguished by vanishing degree
$\omega({\mathcal{G}})=0$. Of course, the fact that all graphs with vanishing
degree lie in the same core equivalence class must be shown explicitly. This
cannot be taken for granted.

  * •

A simple argument yields that $p+D-{\mathcal{B}}^{[D]}\geq 0$.333The quantity
$p-{\mathcal{B}}^{[D]}$ is conserved by 1-dipole moves. A core graph has at
least two vertices ($p\geq 1$) and ${\mathcal{B}}^{[D]}=D+1$. Thus,
$p+D-{\mathcal{B}}^{[D]}\geq 0$ for core graphs. Since every graph roots to a
core graphs, the result follows. Thus, one has that
$\omega({\mathcal{G}})=0\implies\omega({\mathcal{B}}^{\hat{i}}_{(\rho)})=0$
for all $i$ and all $\rho$, as well as $p+D-{\mathcal{B}}^{[D]}=0$.

  * •

Since a core graph has precisely ${\mathcal{B}}^{[D]}=D+1$, one with vanishing
degree must have $p=1$. There is a unique core graph with 2 vertices, known
affectionately as the _supermelon_. It is illustrated in Fig. 7.

  * •

In $D=2$, the 1-dipole moves allow one to explore the full set of colored
planar graphs. Our interested lies with higher values of $D$, however, so we
shall not explore this further.

  * •

In $D\geq 3$, $\omega({\mathcal{G}})=0$ implies that ${\mathcal{G}}$ contains
an _elementary melon_ , illustrated in Fig. 7. Such a sub-graph can be removed
trivially through 1-dipole reduction. Iterating this process on the resulting
graph means that all graphs with vanishing degree root to the supermelon
through the removal of a sequence of elementary melons. Hence this core
equivalence class is referred to as the class of melonic graphs.

  * •

If $\omega({\mathcal{G}})=0$ then ${\mathcal{G}}$ is dual to a sphere $S^{D}$.
The reciprocal holds in $D=2$. Thus, in all melonic graphs are spheres.

Figure 7: The supermelon (left) and an elementary melon (right).

######  Remark 2.27 (some further results in $D=3$).

Let us focus briefly on the case when $D=3$, where we can readily utilize this
machinery to uncover some further results about the topology of the 4-colored
graphs.

  * •

The jacket structure can tell us more about the topology of the full graph,
namely: _if ${\mathcal{G}}$ possesses a spherical jacket then ${\mathcal{G}}$
is spherical_.

  * •

The jackets have a special significance as splitting surfaces [29]: _if
${\mathcal{G}}$ is a manifold, then its jackets ${\mathcal{J}}$ are Heegaard
surfaces_, where a _Heegaard splitting_ of a compact connected oriented
3-manifold ${\mathcal{M}}$ is an ordered triple
$(\Sigma,{\mathcal{H}}_{1},{\mathcal{H}}_{2})_{\mathcal{M}}$ consisting of a
compact connected oriented surface $\Sigma$ and two handlebodies
${\mathcal{H}}_{1}$, ${\mathcal{H}}_{2}$ such that
$\partial{\mathcal{H}}_{1}=\partial{\mathcal{H}}_{2}=\Sigma$. $\Sigma$ is
known as the _Heegaard surface_ of the splitting.

##  3 Algebraic properties

Colored graphs support a very nuanced algebraic structure [17, 20]. Its
importance for the understanding of tensor models cannot be overstressed. In
principle, it provides a bridge between the apparent discrete world inhabited
by the tensor representation and any potential continuum representation. In
reality, work on this facet of the theory has gone little further than its
definition and the demonstration of its self-consistency.

To begin, we need some basic graph-theoretic concepts:

######  Definition 3.1 (marked graph).

A marked graph $({\mathcal{B}},\bar{v})$ is a $D$-colored graph
${\mathcal{B}}$ paired together with one of its negative vertices $\bar{v}$.

######  Definition 3.2 (graph contraction).

Consider two $D$-colored graphs ${\mathcal{B}}_{1}$ and ${\mathcal{B}}_{2}$
and a positive-negative vertex pair
$(v_{1},\bar{v}_{2})\in{\mathcal{B}}_{1}\times{\mathcal{B}}_{2}$ (or
$(\bar{v}_{1},v_{2})$). Contraction of ${\mathcal{B}}_{1}$ and
${\mathcal{B}}_{2}$ at $(v_{1},\bar{v}_{2})$ is obtained in a two-step
process:

  * •

delete $v_{1}$ and $\bar{v}_{2}$ along with the half-edges emanating from
them;

  * •

reconnect the surviving half-edges in the (unique) manner that preserves the
color structure.

One denotes the resulting $D$-colored graph by
${\mathcal{B}}_{1}\star_{(v_{1},\bar{v}_{2})}{\mathcal{B}}_{2}$. Note that
this definition coincides with that of $0$-dipole contraction for $D$-colored
graphs.

######  Remark 3.3 (property).

Note also that graph contraction has one vital property

$\displaystyle({\mathcal{B}}_{1}\star_{(v,\bar{v}_{2})}{\mathcal{B}}_{2})\star_{(w,\bar{v}_{3})}{\mathcal{B}}_{3}={\mathcal{B}}_{1}\star_{(v,\bar{v}_{2})}({\mathcal{B}}_{2}\star_{(w,\bar{v}_{3})}{\mathcal{B}}_{3}).$
(3.1)

Constructing the bubble algebra:

  * •

Consider the set $S=\\{{\mathcal{L}}_{({\mathcal{B}},\bar{v})}\\}$ of elements
indexed by marked $D$-colored graphs.

  * •

Construct an (infinite-dimensional) vector space over the reals using the
elements of $S$ as basis vectors. Denote this vector space by $X$.

  * •

Endow $X$ with the following non-associative multiplication

$\displaystyle\big{[}{\mathcal{L}}_{({\mathcal{B}}_{1},\bar{v}_{1})},{\mathcal{L}}_{({\mathcal{B}}_{2},\bar{v}_{2})}\big{]}\equiv\sum_{v\in{\mathcal{B}}_{1}}{\mathcal{L}}_{({\mathcal{B}}_{1}\star_{(v,\bar{v}_{2})}{\mathcal{B}}_{2},\bar{v}_{1})}-\sum_{v\in{\mathcal{B}}_{2}}{\mathcal{L}}_{({\mathcal{B}}_{2}\star_{(v,\bar{v}_{1})}{\mathcal{B}}_{1},\bar{v}_{2})}.$

  * •

Impose _bilinearity_ in the first argument by fiat

$\displaystyle\big{[}a{\mathcal{L}}_{({\mathcal{B}}_{1},\bar{v}_{1})}+b{\mathcal{L}}_{({\mathcal{B}}_{2},\bar{v}_{2})},{\mathcal{L}}_{({\mathcal{B}},\bar{v})}\big{]}\equiv
a\big{[}{\mathcal{L}}_{({\mathcal{B}}_{1},\bar{v}_{1})},{\mathcal{L}}_{({\mathcal{B}},\bar{v})}\big{]}+b\big{[}{\mathcal{L}}_{({\mathcal{B}}_{2},\bar{v}_{2})},{\mathcal{L}}_{({\mathcal{B}},\bar{v})}\big{]}$

along with a similar relation for the second argument.

  * •

This bracket is clearly _anticommutative_ , since

$\displaystyle\big{[}{\mathcal{L}}_{({\mathcal{B}}_{1},\bar{v}_{1})},{\mathcal{L}}_{({\mathcal{B}}_{2},\bar{v}_{2})}\big{]}=-\big{[}{\mathcal{L}}_{({\mathcal{B}}_{2},\bar{v}_{2})},{\mathcal{L}}_{({\mathcal{B}}_{1},\bar{v}_{1})}\big{]},$

and this extends to all of $X$ using bilinearity of the bracket.

In fact, with the help of (3.1), the bracket satisfies the _Jacobi identity_

$\displaystyle\big{[}\big{[}{\mathcal{L}}_{({\mathcal{B}}_{1},\bar{v}_{1})},{\mathcal{L}}_{({\mathcal{B}}_{2},\bar{v}_{2})}\big{]},{\mathcal{L}}_{({\mathcal{B}}_{3},\bar{v}_{3})}\big{]}+\big{[}\big{[}{\mathcal{L}}_{({\mathcal{B}}_{2},\bar{v}_{2})},{\mathcal{L}}_{({\mathcal{B}}_{3},\bar{v}_{3})}\big{]},{\mathcal{L}}_{({\mathcal{B}}_{1},\bar{v}_{1})}\big{]}$
$\displaystyle\qquad{}+\big{[}\big{[}{\mathcal{L}}_{({\mathcal{B}}_{3},\bar{v}_{3})},{\mathcal{L}}_{({\mathcal{B}}_{1},\bar{v}_{1})}\big{]},{\mathcal{L}}_{({\mathcal{B}}_{2},\bar{v}_{2})}\big{]}=0.$

In the end, we have the following neat result:

######  Theorem 3.4 (bubble algebra).

The pair $(X,[\cdot,\cdot])$ form a Lie algebra.

The next step is to look for representations of this algebra. One such is
given by the tensor model $D$-bubble observables of a $(D+1)$-colored tensor
model, hence the rather nomenclature. This algebra underpins the symmetries of
the tensor model theory.

Important for the representation theory is the identification of subalgebras,
from which one can induce representations of the full algebra. In this
direction, one has:

######  Theorem 3.5 (melonic subalgebra).

The marked melonic $D$-colored graphs form a subalgebra of the $D$-colored
bubble algebra.

##  4 Melonic graphs: probing deeper into their combinatorial
and metric structures

In order to perform a more detailed analysis, let us restrict ourselves to a
single core equivalence class: the melonic graphs that we introduced earlier.
This is the sole core equivalence class contributing to the leading order of
generic tensor model theories and so a thorough understanding of its
combinatorial and metric properties is of utmost importance.

By definition, melonic graphs are those that reduce to the _supermelon_ core
graph. Thus, they have vanishing degree and differ from the supermelon by a
sequence of 1-dipole moves. But this is a rather redundant prescription as
many sequences lead to the same melonic graph. However, as laid out in Remark
2.26, melonic graphs reduce to the supermelon through the iterative removal of
_elementary melons_. This provides a parsimonious prescription for melonic
graphs.

Rooted melonic graphs. To be precise, we shall construct _rooted melonic
graphs_. A rooted melonic graph is a melonic graph with one edge singled out.
Such rooting is common in combinatorial graph theory, as it simplifies
counting problems. Marking an edge of the supermelon graph essentially yields
an elementary melon of some color $i$ (the color of the distinguished edge).
In the following we shall always root the graphs along an edge of color $0$.

The elementary melons also act as the fundamental building blocks of generic
melonic graphs. To add a bit more nomenclature, an elementary melon consists
of two vertices connected by $D$ edges. Both vertices have one external edge.
Obviously, both external edges possess the same color, say $i$. An elementary
melon has two features: i) an external edge of color $i$ incident to the white
vertex, which is known as the _root edge_ ; ii) $D+1$ edges incident at the
black vertex, which are known as _active edges_ , having distinct colors from
$\\{0,1,\dots,D\\}$.

Rooted melonic graph construction algorithm. One can construct the class
rooted melonic graphs iteratively.

$p=1$:

There is a unique rooted melonic graph with two vertices. It is illustrated in
the bottom left of Fig. 8 and is the _elementary melon of color $0$_.

Figure 8: An elementary melon of color $2$ inserted along the active edge of
color $2$ (for $D=3$). The active edges are drawn using full lines.

$p=2$:

There are $D+1$ melonic graphs with four vertices. One obtains them from the
graph at $p=1$ by replacing an active edge of a given color by an elementary
melon of the same color (as shown in Fig. 8).

$p=k$:

One obtains these graphs from those at $p=k-1$ by replacing some active edge
by an elementary melon of the appropriate color.

The need for a precise prescription cannot be overstressed, since all the
ensemble properties of these graphs, stem from being able to count them
precisely.

As mentioned earlier, the abstract structure of rooted melonic graphs
coincides with that of several other objects, which we shall describe
presently.

Rooted melonic graphs as colored rooted $\boldsymbol{(D+1)}$-ary trees. There
is a simple bijection between the set of rooted melonic graphs and _colored
rooted $(D+1)$-ary trees_. The fundamental building blocks of any colored
rooted $(D+1)$-ary tree are the _elementary vertices_. An elementary vertex of
color $i$ is $(D+2)$-valent with two distinguished features: i) a _root edge_
of color $i$; ii) $D+1$ _active leaves_ each with a distinct color from
$\\{0,\dots,D\\}$. These correspond to the root edge and the active edges of
the elementary melon, respectively. Since this class of trees is also
constructed in an iterative manner, the map is self-evident:

$p=1$:

There is a unique colored rooted $(D+1)$-ary tree with a single elementary
vertex. This is the elementary vertex of color 0. It is illustrated in the
bottom left of Fig. 9.

Figure 9: The elementary vertex of color 2 replacing a leaf of color 2 (for
$D=3$).

$p=2$:

There are $D+1$ such trees with two elementary vertices. One obtains them from
the tree at $p=1$ by replacing a leaf of a given color with an _elementary
vertex_ of the same color (as shown in Fig. 9).

$p=k$:

One obtains these trees from those at $p=k-1$ by replacing a leaf with an
elementary vertex of the same color.

Rooted melonic graphs as colored simplicial $\boldsymbol{D}$-balls. The
description of how any given $(D+1)$-colored graph is dual, in a precise
topological sense, to a unique $D$-dimensional abstract simplicial
pseudomanifold was provided earlier.

Consider cutting a closed $(D+1)$-colored graph along one edge. This results
in an open graph whose dual is a simplicial complex with boundary. This
boundary is a $(D-1)$-sphere constructed from two $(D-1)$-simplices.

Melonic graphs are dual to simplicial $D$-spheres. Rooted melonic graphs,
which are melonic graphs with one edge cut, are dual to simplicial $D$-balls
with the boundary just mentioned. For the want of a better name, we shall call
them _melonic $D$-balls_. One can define them iteratively. The fundamental
building blocks are the _elementary melonic $D$-balls_. These consist of two
$D$-simplices sharing $D$ of their $(D-1)$-simplices. There are two more
$(D-1)$-simplices forming the boundary $(D-1)$-sphere. In the manner outlined
above, the two $D$-simplices are dual to the two vertices of the elementary
melon, while the $(D-1)$-simplices are dual to the edges. Thus, the
$(D-1)$-simplices inherit a single color. An elementary melonic $D$-ball of
color $i$ has two distinguished features: i) an external _root
$(D-1)$-simplex_ of color $i$; ii) $D+1$ _active $(D-1)$-simplices_ (one of
which is on the boundary), each with a distinct color. The iterative
definition proceeds as follows:

$p=1$:

There is a unique $D$-ball comprised of two $D$-simplices. It is the
elementary melonic $D$-ball of color 0. It is illustrated in the bottom left
of Fig. 10.

Figure 10: The melonic $D$-ball at $p=2$ (for $D=3$), obtained by adding an
elementary $D$-ball of color 2.

$p=2$:

There are $D+1$ melonic $D$-balls with four $D$-simplices. One obtains them
from the melonic $D$-ball at $p=1$ by adding an elementary melonic $D$-ball of
a given color (shown in Fig. 10). More precisely, one splits the melonic
$D$-ball arising at $p=1$ along an active $(D-1)$-simplex (or one selects the
active boundary $(D-1)$-simplex). One then glues an elementary melonic
$D$-ball of the appropriate color along the split (or simply on the boundary
$(D-1)$-simplex).

$p=k$:

One obtains them from those at $p=k-1$ by adding an elementary melonic
$D$-ball at some active $(D-1)$-simplex.

######  Remark 4.1 (vertex correspondance).

Let us denote a colored rooted $(D+1)$-ary tree with $p$ elementary vertices
by $\mathcal{T}_{p}$ and its set of elementary vertices by $t_{p}$.

Noting that an elementary $D$-ball has precisely one _internal_ vertex before
it is inserted, one notes that a melonic $D$-ball constructed form $p$
elementary $D$-balls has precisely $p$ internal vertices. We shall denote such
a melonic $D$-ball by $\mathcal{M}_{p}$ and its internal vertex set by
$m_{p}$.

Moreover, given such melonic $D$-ball $\mathcal{M}_{p}$, along with its
associated $(D+1)$-ary tree $\mathcal{T}_{p}$, one notes that their respective
vertex sets are in bijective correspondence, since an elementary tree vertex
corresponds to an elementary $D$-ball, which in turn has one internal vertex
(before insertion).

Branches, words and vertex ordering. Consider again an associated pair
$\mathcal{M}_{p}$ and $\mathcal{T}_{p}$. As a tree, $\mathcal{T}_{p}$ has
_branches_ , joining the _root tree vertex_ to each of the elementary vertices
in $t_{p}$. (Note that the root tree vertex is not in $t_{p}$. Rather it is
the other endpoint of the root edge in the first elementary tree vertex of
color $0$.)

To each elementary tree vertex, one may associate a  _word_ drawn from the
alphabet $\Sigma_{D+1}=\\{0,1,\dots,D\\}$. This word is constructed by listing
left-to-right the colors encountered as one traverses the branch from the root
vertex to the elementary vertex in question. As examples, the word associated
to the root vertex is $(0;\ )$, indicating the root edge of color $0$, while
the word associated to the generic example given in Fig. 11 is
$(0;10132120312)$. In turn, these words have a natural (lexicographical)
ordering, which may be used to convert $t_{p}$ into an ordered set.

Due to the bijection relating $m_{p}$ to $t_{p}$, the internal vertices of the
melonic $D$-ball are ordered. Moreover, each element of $m_{p}$ also inherits
a word from its associated tree vertex. That word is not meaningless in this
context. On the contrary, it captures the sequence of elementary $D$-balls,
each one nested inside the preceding, on route to inserting that internal
vertex.

Figure 11: The words associated to some vertices of a colored rooted
$(D+1)$-ary tree.

###  4.1 Generating rooted melonic $\boldsymbol{D}$-balls and the continuum
limit

Ultimately, finite melonic $D$-balls hold only a limited amount of interest
for us. We wish to know about the configurations in the large-$p$ limit, where
one might conceivably formulate a meaningful continuum limit [8]. Naïvely, one
could imagine that this limit is arrived at by considering configurations with
increasingly large numbers of tetrahedra of diminishing individual size.

Our aim here is to make this initial idea more precise. In that respect, let
us partition the set of melonic $D$-balls according to the number of internal
vertices. At a given value of $p$, we want a method to examine the properties,
_on average_ , of that subset of melonic $D$-balls. A convenient method is to
utilize a generating function approach

$\displaystyle
G(z)=\sum_{\mathcal{M}}z^{p_{\mathcal{M}}}=\sum_{p=0}^{\infty}C^{(D+1)}_{p}z^{p},\qquad\textrm{where}\quad
C^{(D+1)}_{p}=\sum_{\mathcal{M}\colon p_{\mathcal{M}}=p}1,\qquad
z\in\mathbb{C}.$

The first sum is over all melonic $D$-balls, weighted according to the number
of internal vertices. Thus, the subset of melonic $D$-balls with $p$ internal
vertices are all weighted equally allowing the reduction to the second sum,
where $C^{(D+1)}_{p}$ is the cardinality of that subset.

One can expect that $G(z)$ has a finite radius of convergence $z_{c}$. As a
result, one can examine properties of the large-$p$ limit by tuning the
_coupling constant_ $z$ to its _critical value_ $z_{c}$, as it is the
large-$p$ coefficients that determine the behaviour of $G(z)$ in that region.

Thus, our first task is to gain control over the coefficients $C^{(D+1)}_{p}$.
In this regard, it is worth remembering that melonic $D$-balls are in a
precise correspondence with colored rooted $(D+1)$-ary trees and experts have
been counting trees since time immemoriam. A convenient way to count trees is
to develop a consistency relation for the generating function $G(z)$. This is,

$\displaystyle G(z)=1+z[G(z)]^{D+1},$

which is illustrated in Fig. 12. It sums up the fact that the trees comprising
$G(z)$ consist of the tree with just one root edge (and no elementary vertex)
along with those with at least one elementary vertex (weighted by $z$), along
any whose $D+1$ active edges one can insert an arbitrary colored rooted
$(D+1)$-ary tree.

Figure 12: Consistency equation for the generating function $G(z)$.

Expanding the terms and equating the coefficients for the various powers of
$z$, one finds a recurrence relation for the $C^{(D+1)}_{p}$. This recurrence
relation is satisfied by the $(D+1)$-Catalan numbers

$\displaystyle C^{(D+1)}_{p}=\frac{1}{(D+1)p+1}{(D+1)p+1\choose p}.$

Applying Stirling’s formula to the series coefficients, one determines the
large order behaviour

$\displaystyle
G(z)\sim\beta(z_{c})^{-p}p^{-3/2},\qquad\textrm{where}\quad\beta=\dfrac{e}{\sqrt{2\pi}}\sqrt{\frac{D+1}{D^{3}}},\qquad
z_{c}=\dfrac{D^{D}}{(D+1)^{D+1}}.$

As expected, the above series has a finite radius of convergence and the
behaviour of the series in the vicinity of $z_{c}$ is

$\displaystyle
G(z)\sim\left(1-\frac{z}{z_{c}}\right)^{1-\gamma},\qquad\textrm{where}\quad\gamma=\frac{1}{2}.$

The exponent $\gamma$ is known as the _susceptibility_ and is the first
example of a quantity that determines the properties of the continuum limit.

To this point, however, we have only analysed the large-$p$ limit. To obtain a
continuum limit, we need to endow each melonic $D$-ball with a metric. We
shall develop that in more detail later. But for now, all we need is that
under this metric, each melonic $D$-ball becomes an equilateral triangulation.
This means that each tetrahedron has equal volume, known as the _microscopic
volume_ $\nu$. Meanwhile, for a melonic $D$-ball with $p$ internal vertices,
and thus $2p$ tetrahedra, the _macroscopic volume_ is $V_{\mathcal{M}}=2p\nu$.
Thus, we may obtain a finite macroscopic volume if $\nu\rightarrow 0$ as
$p\rightarrow\infty$ in some balanced fashion.

To do this meaningfully, remember that we are interested in the properties of
melonic $D$-balls on average. Thus, it is worth analyzing

$\displaystyle
V(z)\equiv\sum_{\mathcal{M}}(2p_{\mathcal{M}}\nu)z^{p_{\mathcal{M}}}=\sum_{p=0}^{\infty}(2p\nu)C^{(D+1)}_{p}z^{p}=2\nu
z\frac{\partial G}{\partial z}(z)\underset{z\sim z_{c}}{\sim}\nu
z\left(1-\frac{z}{z_{c}}\right)^{-1/2}.$

If we consider taking the microscopic volume $\nu\rightarrow 0$ and
$z\rightarrow z_{c}$ in a balanced fashion such that the macroscopic volume
$V(z_{c}-)$ remains finite. Then, we can realistically call such a limit a
continuum limit.

######  Remark 4.2 (melonic $D$-balls and branched polymer spacetimes).

In total, we shall extract three exponents associated with the continuum limit
of melonic $D$-balls: the susceptibility $\gamma=1/2$, the Hausdorff dimension
$d_{H}=2$ and the spectral dimension $d_{S}=4/3$ (although strictly speaking,
the last refers to the dual rooted melonic graphs). These coincide with the
exponents calculated for so-called _branched polymer spacetimes_ arising in
the dynamical triangulations approach to quantum gravity [2]. These have
undesirable physical properties, among them the non-physical Hausdorff and
spectral dimensions. As a result, one concludes that melonic $D$-balls possess
an uninteresting continuum limit from a physical spacetime viewpoint. However,
these exponents are one of the major ways for testing the physical viability
of any particular phase of a tensor model theory.

###  4.2 Hausdorff dimension

The next exponent pertaining to the continuum limit of melonic $D$-balls is
the Hausdorff dimension:

######  Definition 4.3 (Hausdorff dimension).

For a metric space $X$, the _Hausdorff dimension_ $d_{H}$ captures how the
volume of a ball scales with respect to its geodesic radius. More formally, it
is defined as

$\displaystyle d_{H}=\inf\\{d\geq 0\colon\mathcal{H}_{d}(X)=0\\},$

where $\mathcal{H}_{d}(X)$ is the $d$-dimensional Hausdorff measure on $X$,
that is

$\displaystyle\mathcal{H}_{d}(X)=\inf\bigg{\\{}\delta=\sum_{i}r_{i}^{d}\colon\textrm{the
indexed collection of balls of radius $r_{i}$ covers $X$}\bigg{\\}}.$

Obviously, for the simple example of flat $D$-dimensional Euclidean space:
$V_{D}\sim r^{D}$. Thus

$\displaystyle d_{H}=D.$

It is clear, however, that some work must be done to extract this dimension
for the class of melonic $D$-balls. One may follow the arguments in [1, 23]
for the full picture, which would be too laborious a task to reproduce in its
entirety here. In fact, a detailed statement of the result already takes some
considerable ink. So, with no further ado, the main result is:

######  Theorem 4.4.

Under the uniform distribution, the family of melonic $D$-balls converges in
the Gromov–Hausdorff topology on compact metric spaces to the continuum random
tree

$\displaystyle\left(m_{p},\frac{d_{m_{p}}}{\Lambda_{\Delta}\sqrt{\frac{(D+1)p}{D}}}\right)\underset{p\to\infty}{\longrightarrow}({\cal
T}_{2e},d_{2e}).$

In turn, the Hausdorff dimension of the limiting continuum metric space, the
continuum random tree, is well known to be

$\displaystyle d_{H}=2,$

although this may be read off directly from the above theorem, as we shall see
presently.

Melonic $\boldsymbol{D}$-balls as metric spaces. Consider a melonic $D$-ball
with $p$ internal vertices and its associated $(D+1)$-ary tree, denoted by
$M_{p}$ and $T_{p}$, respectively. As noted earlier, the ordered set of
internal vertices $m_{p}$ is in bijective correspondence with the ordered set
of elementary tree vertices $t_{p}$.

Both of these sets have a natural metric structure inherited from their
respective graphs, namely the graph distance:

######  Definition 4.5 (graph distance).

For any connected graph, the _graph distance_ $d(v_{s},v_{t})$ between two
vertices $v_{s}$ and $v_{t}$ is the minimal number edges in any contiguous
path journeying from $v_{s}$ to $v_{t}$.

The graph distance is a discrete metric and in order to examine the large-$p$
limit as a continuum limit, we need to extend it to a continuum metric. To do
so, one utilizes the order on the set $m_{p}$ ($t_{p}$) to arrange pairs
$m_{p}\times m_{p}$ ($t_{p}\times t_{p}$) as the integer points on
$[0,p-1]\times[0,p-1]$. One then interpolates between these integer points
using a piecewise linear interpolation on the triangles with integer co-
ordinates $(v_{1},v_{2})$, $(v_{1}+1,v_{2})$, $(v_{1},v_{2}+1)$ and
$(v_{1}+1,v_{2}+1)$, $(v_{1}+1,v_{2})$, $(v_{1},v_{2}+1)$. We denote this
metrics by $d_{m_{p}}$ ($d_{t_{p}}$).

To retain a compact space in the large-$p$ limit, rather than just letting the
structure get infinitely large, one requires an $p$-dependent rescaling of the
metric. This motivates the factor $\sqrt{(D+1)p/D}$. Of course, it is the
exponent of this factor that determines the Hausdorff dimension. Afterall, the
volume of the melonic $D$-ball, with respect to $d_{m_{p}}$, is proportional
to $p$ and thus, it is the precisely the rescaling $d_{m_{p}}\rightarrow
d_{m_{p}}/({\rm volume})^{1/d_{H}}$ required to keep the limiting metric space
compact that determines the Hausdorff dimension.

The final factor $\Lambda_{\Delta}$ requires a little more explanation.

Calculating $\boldsymbol{\Lambda_{\Delta}}$. Consider an associated pair
$M_{p}$ and $T_{p}$, along with their vertex sets $m_{p}$ and $t_{p}$. Since
the vertex sets are in bijective correspondence, we shall refer to their
vertices using the same label $v$. Associated to a rooted graph is the notion
of depth:

######  Definition 4.6 (depth).

The _tree depth_ of $v$ is the distance, with respect to $d_{t_{p}}$, of the
associated elementary vertex to the root vertex. The _depth_ of $v$ is the
distance, with respect to $d_{m_{p}}$, of the associated internal vertex to
the internal vertex associated to the first elementary $D$-ball.

The tree depth of $v$ is just length of the branch joining it to the root,
that is, the number of characters in its associated word $w$. Denoting the
quantity by $\widetilde{\Lambda}$, one finds for example:

$\displaystyle\widetilde{\Lambda}(0;10132120312)=12.$

The depth, on the other hand, is not so simple to calculate. However, it can
also be deciphered from the associated word in the following manner. As
explained earlier, a branch within the $(D+1)$-ary tree corresponds to a
nested sequence of elementary $D$-balls within the melonic $D$-ball. As a
result of this nesting, the path of minimal graph distance leading from this
internal vertex to the initial internal vertex lies within this sequence of
elementary $D$-balls. However, the connectivity of the graph causes its value
to deviate form that of the tree depth; the insertion of a $D$-ball does not
mean that the new vertex is necessarily further away from the root vertex. In
fact, consider a nested sequence of elementary $D$-balls and their associated
internal vertices. Pick out the last elementary $D$-ball inserted. Say it has
color $i$ and assume that its associated internal vertex is the first internal
vertex in the sequence that is at depth $r$. All other internal vertices in
that sequence have depth less than $l$.444Internal vertices inserted earlier
certainly do not have depth greater than $r$. Now, within this latest
$D$-ball, insert an arbitrary nested sequence containing at least one
elementary $D$-ball of each color _except_ some color $j\neq i$. It emerges
that the internal vertices associated to this newly inserted sequence all have
depth $r$. Now insert a elementary $D$-ball of color $j$. Its associated
internal vertex has depth $r+1$. We do not elaborate further on the reasoning
here. However, the interested reader can convince oneself quite readily by
drawing out the example given here or by looking in [23].

Now its a matter of laying out an algorithm for calculating the depth from the
associated word. In this regard, let us denote by $W_{D+1}$ the set of words
containing every letter of the alphabet $\Sigma_{D+1}=\\{0,1,\dots,D\\}$ at
least once. Consider a vertex $v$ labelled by the word $w=(0;u_{1}u_{2}\dots
u_{n})$. The depth of $v$ corresponds to division of $w$ into disjoint
adjacent subwords $\tau_{r}$, comprised of letters of depth $r$. Thus,
$\tau_{0}=0$. Then, $\tau_{1}=u_{1}\dots u_{a_{1}}$, with
$u_{1},u_{2},\dots,u_{a_{1}}\neq 0$ and $u_{a_{1}+1}=0$. Furthermore,
$\tau_{r}$, for $r>1$, may be one of two forms: i)
$\tau_{r}=u_{a_{r-1}+1}\dots u_{a_{r}}$ such that $\tau_{r}\notin W_{D+1}$ but
$\tau_{r}u_{a_{r}+1}\in W_{D+1}$; ii) $\tau_{r}=u_{a_{r-1}+1}\dots u_{n}$ if
$u_{a_{r-1}+1}\dots u_{n}\notin W_{D+1}$. This second possibility accounts for
the fact that the last subword might be incomplete.

The depth of a vertex $v$ with word $w=\tau_{0}\tau_{1}\dots\tau_{k}$ is

$\displaystyle\Lambda(w)=k.$

As an example, take the branch of a $(3+1)$-ary tree illustrated in Fig. 11.
The division in subwords goes as follows

$\displaystyle w=(0;10132120312)=(0)(1)(013)(2120)(312).$

Thus, $\Lambda(0;10132120312)=4$.

The distance, with respect to $d_{m_{p}}$, between any two vertices can be
well estimated from their respective depths with respect to their latest
common ancestor. Consider two vertices $v_{1}$ and $v_{2}$ with associated
words $ww_{1}$ and $ww_{2}$. Thus, the two words have $w$ in common, but lie
on different sub-branches thereafter. The following inequality holds:

$\displaystyle|d_{m_{p}}(v_{1},v_{2})-\Lambda(w_{1})-\Lambda(w_{2})|\leq 6.$

Since the right hand side is $p$-independent, the rescaled inequality becomes
increasingly strict as $p$ increases.

Finally for the factor $\Lambda_{\Delta}$, which is just the average ratio
$\Lambda(w)/\widetilde{\Lambda}(w)$ as $p$ becomes large:

######  Lemma 4.7.

Let $u_{1},\dots,u_{p}$ be a sequence of random variables uniformly drawn from
$\Sigma_{D+1}$, and denote $w=0u_{1}\dots u_{p}$. One has

$\displaystyle\frac{1}{p}\Lambda(w)\underset{p\rightarrow\infty}{\rightarrow}\Lambda_{\Delta},\qquad\Lambda_{\Delta}^{-1}=(D+1)\sum_{0\leq
r\leq D}(-1)^{D-r}\binom{D}{r}\frac{r}{(D+1-r)^{2}}.$

Lemma 4.7 declares that, on average, the depth of an internal vertex in a
melonic $D$-ball is, up to a constant rescaling by $\Lambda_{\Delta}$, just
the tree depth in the associated $(D+1)$-ary tree. Loosely speaking, this
factor occurs in Theorem 4.4 to take into account the connectivity of the
melonic $D$-balls, given that the limiting space has a tree-like structure.

Melonic $D$-balls as random variables. In the context of Theorem 4.4, $M_{p}$
is to be viewed as a random variable with uniform distribution upon the space
of melonic $D$-balls with $p$ internal vertices. Thus, by association, the
metric space $\big{(}m_{p},d_{m_{p}}/\Lambda_{\Delta}\sqrt{(D+1)p/D}\big{)}$
is a random variable. Thus, the sequence above is a sequence of random
variables and convergence means convergence in distribution, that is, the
(cumulative) distribution functions associated to the melonic $D$-ball metric
spaces random variables converge to that of the continuum random tree in the
large-$p$ limit.

Note that the generating function mentioned earlier (as well as the tensor
model generating function) weights all melonic $D$-balls with the same number
of internal vertices equally. Thus, a uniform distribution is motivated from
that context.

Continuum random tree. A continuum random tree (CRT)
$(\mathcal{T}_{2e},d_{2e})$ is defined as a rooted real tree encoded by twice
a normalized Brownian excursion $e$ and endowed with a metric $d_{2e}$.

One is probably more familiar with rooted discrete trees, of which the colored
rooted $(D+1)$-ary trees are examples. Colored rooted $(D+1)$-ary trees (like
all discrete trees) have an associated contour walk. Consider such a tree with
$p$ (elementary) vertices. (For simplicity, we shall consider its defoliated
version, that is, all leaves removed.) Starting from the base of the tree, one
traverses the perimeter of the tree, passing from one vertex to the next in
unit time-steps. One considers the following continuous function $f(t)$, with
$f(0)=0$. As one travels, $f(i)=d_{t_{p}}(v)+1$, where $v$ is the vertex one
encounters at the $i$th time-step. (For the value at intermediate times, one
linearly interpolates between the time-steps.) The procedure is illustrated in
Fig. 13. Given the construction, one has that the journey ends at time-step
$2p$, with $f(2p)=0$ and $f(t)>0$ for $0<t<2p$. One has thus associated to any
tree some (fixed) walk $f$. For random trees with $2p$ vertices, the contour
walk becomes a random walk with $2p$ steps.

Figure 13: A defoliated $(D+1)$-ary tree and its associated contour walk.

Any real continuous function $f(t)$, such that $f(0)=f(1)=0$ and $f(t)>0$ for
$0<t<1$, encodes a rooted real tree $\mathcal{T}_{f}$. To get to the tree, one
must set up the following equivalence. For all $s,t\in[0,1]$, set
$m_{f}(s,t)=\inf_{\min(s,t)\leq r\leq\max(s,t)}f(r)$. Then

$\displaystyle s\underset{f}{\sim}t\quad\iff\quad f(s)=f(t)=m_{f}(s,t).$

Then, the rooted real tree is the quotient:
$\mathcal{T}_{f}=[0,1]/\underset{f}{\sim}$. The distance on the tree is given
by555In the interests of clarity, let us calculate the distance between two
points in the tree of Fig. 13. Examining the associated contour walk, the
heights of the 4th and 9th points encountered are $f(4)=4$ and $f(9)=3$,
respectively. Meanwhile, the minimal height along the intervening contour is
$m_{f}(4,9)=2$. Then, the distance between these two points is really the sum
of their respective vertical heights above this minimum
$d_{f}(4,9)=(f(4)-m_{f}(4,9))+(f(9)-m_{f}(4,9))=3$.

$\displaystyle d_{f}(s,t)=f(s)+f(t)-2m_{f}(s,t).$

One can pick out the branching vertices of the tree as those values in $[0,1]$
that are congruent to two or more other values. This real tree differs from a
discrete tree in that one has precise distance information along the edges of
the tree.

The Wiener process is a stochastic process $W_{t}$ (that is a random variable
for every time $t$) such that $W_{0}=0$, $t\to W_{t}$ is almost surely
continuous, $W_{t}$ has independent increments and $W_{t}-W_{s}$ is
distributed on a normal distribution of mean $0$ and variance $\sigma^{2}=t-s$
for $s\leq t$. The normalized Brownian excursion $e_{t}$ is a Wiener process
conditioned to be positive for $0<t<1$ and be at $0$ at time $1$. It is
formally represented by the path integral measure

$\displaystyle
d\mu_{e}=\frac{1}{Z}\bigl{[}dq(t)\bigr{]}\Bigg{|}_{\begin{subarray}{c}q(0)=q(1)=0\\\
q(t)>0\end{subarray}}e^{-\frac{1}{2}\int_{0}^{1}[\dot{q}(t)]^{2}dt},$

with $Z$ a normalization constant.

The CRT $(\mathcal{T}_{2e},d_{2e})$ is the random tree associated to twice a
normalized Brownian excursion $2e$.

Gromov–Hausdorff topology and convergence. Since one considers the convergence
of a sequence of random metric spaces, one must endow the space of metric
spaces along with an appropriate topology. This is provided by the
Gromov–Hausdorff topology on the space of isometry classes of compact metric
spaces.

To begin, one considers a metric space $(E,d_{E})$. The Hausdorff distance
between two compact sets, $K_{1}$ and $K_{2}$, in $E$ is

$\displaystyle
d_{\textrm{Haus}(E)}(K_{1},K_{2})=\inf\big{\\{}r\,|\,K_{1}\subset
K_{2}^{r},\,K_{2}\subset K_{1}^{r}\big{\\}},$

where $K_{i}^{r}=\bigcup_{x\in K_{i}}B_{E}(x,r)$ is the union of open balls of
radius $r$ centered on the points of $K_{i}$.

Now, given two compact metric spaces $(E_{i},d_{i})$, the Gromov–Hausdorff
distance between them is

$\displaystyle
d_{\textrm{GH}}(E_{1},E_{2})=\inf\\{d_{\textrm{Haus}(E)}(\phi_{1}(E_{1}),\phi_{2}(E_{2}))\\},$

where the infimum is taken on all metric spaces $E$ and all isometric
embeddings $\phi_{1}$ and $\phi_{2}$ from $(E_{1},d_{1})$ and $(E_{2},d_{2})$
into $(E,d_{E})$.

It emerges that $\mathbb{K}$, the set of all isometry classes of compact
metric spaces, endowed with the Gromov–Hausdorff distance $d_{\rm GH}$ is a
complete metric space in its own right. Therefore, one may study the
convergence (in distribution) of $\mathbb{K}$-valued random variables.

Of course, the Gromov–Haudorff topology is not the exclusive topology for
these metric spaces, but fortuitously, it is well-adapted to the study of
quantities that are dependent on the size of the melonic $D$-balls, quantities
such as the diameter, the depth, the distance between two random points and so
forth.

###  4.3 Spectral dimension

The third and final exponent that we would like to examine for melonic
$D$-balls is the spectral dimension. The spectral dimension of a manifold is
the dimension experienced by a diffusion process and is extracted by
evaluating the logarithmic derivative of the return probability with respect
to diffusion time

$\displaystyle d_{S}=-2\frac{d\log P(t)}{d\log t}.$

To make this more concrete, let us consider the simple case of diffusion on
$D$-dimensional Euclidean space. The associated heat equation666In more
generality, consider a Riemannian manifold $M$ and a temperature distribution
$f_{0}\colon M\rightarrow\mathbb{R}$. The _heat equation_ evolves $f_{0}$, in
the sense that there exists $f\colon M\times(0,T)\rightarrow\mathbb{R}$ that
solves $\left(\frac{\partial}{\partial t}-\nabla\right)f=0$, and
$f(x,0)=f_{0}(x)$. The _heat kernel_ is $K\colon M\times
M\times(0,T)\rightarrow\mathbb{R}$, which satisfies
$\left(\frac{\partial}{\partial t}-\nabla_{x}\right)K=0$, which initial
condition $\lim\limits_{t\rightarrow 0}K(x,y,t)=\delta(x,y)$. gives rise to a
_heat kernel_

$\displaystyle K(t,x,y)=\frac{1}{4\pi t^{D/2}}e^{-|x-y|^{2}/4t}.$

The spatial coincidence limit gives rise to the _return probability_

$\displaystyle P(t)=\frac{1}{4\pi t^{D/2}},$

from which the result $d_{S}=D$ follows readily. Obviously, the spectral
dimension coincides with the Hausdorff dimension in this elementary case, but
this is not true in general.

Diffusion on graphs. On graphical structures, the diffusion process may be
modelled using a random walker taking one step per unit time, where a step
takes the walker from a vertex to one of its neighbours. The return
probability $P(t)$ is then simply the probability that the walker returns to
her starting point at time $t$.

As one might imagine, the spectral dimension depends non-trivially on the
connectivity of the graph. Moreover, the connectivity of the graph can make
the computation of the return probability very involved. In our case, we wish
to compute the return probability for a generic melonic $D$-ball, which seems
rather intractable. So we are motivated to examine the other representations.
The spectral dimension of colored rooted $(D+1)$-ary trees is a simple
extension of the result in [25]. However, the rooted melonic graphs bear a
closer relationship to the melonic $D$-balls, as they are their topological
dual spaces.

To proceed, consider a rooted melonic graph, with external color 0. Such a
graph is drawn in Fig. 14.

Figure 14: A rooted melonic graph $\mathcal{M}$ with sub-melons
$\mathcal{M}^{i}$.

One denotes it by $\mathcal{M}$. It is worth recounting how $\mathcal{M}$ was
constructed. One started from an initial elementary melon of color $0$, that
is, two vertices sharing $D$ edges. These two original vertices are denoted by
$A$ and $B$, Fig. 14. Thereafter, one repeatedly inserted elementary melons of
various colors. Some were inserted along the active edge of color $0$ at $B$
or nested within earlier insertions. Meanwhile, others were inserted along the
active edges of color $i\in\\{1,\dots,D\\}$ joining $A$ to $B$ or nested
within earlier insertions. Due to this iterative construction, excising
vertices $A$ and $B$ results in $D+1$ disconnected subgraphs that are
themselves rooted melonic graphs, each with a distinct external color. One
denotes this property by
${\mathcal{M}}={\mathcal{M}}^{1}\cup{\mathcal{M}}^{2}\cup\cdots\cup{\mathcal{M}}^{D}\cup{\mathcal{M}}^{0}$,
where ${\mathcal{M}}^{i}$ labelled the rooted melonic graph with external
edges of color $i$.

Any rooted melonic graph has two external vertices, labelled $I$ and $O$. The
rest are the familiar $(D+1)$-valent internal vertices. To calculate the
return probability for a generic graph, one should average over the return
probabilities attached to each vertex. However, rooted melonic graphs possess
a recurrent connectivity structure that renders this unnecessary and
ultimately, we wish to investigate return probabilities to the vertex $I$. To
this end, we shall deal with the return probabilities ($I\rightarrow I$ and
$O\rightarrow O$) and transit probabilities ($I\rightarrow O$ and
$O\rightarrow I$). Utilizing this matrix of probabilities, the recurrent
connectivity permits us to set up a recurrence relation satisfied by these
_return/transit probabilities_. We shall detail this presently.

Generating functions. As usual, we are interested in properties _on average_
(this time over the set of rooted melonic graphs) at large $p$. Thus, we
utilize the convenience of a generating function for the return probabilities
to $I$ at a given $t$, over the set of rooted melonic graphs. Moreover, is it
simpler to extract the spectral dimension by considering the generating
function for return probabilities over the set of all $t$. Thus, we define the
quantity

$\displaystyle
P^{II}(z,y):=\sum_{p=0}^{\infty}\sum_{t=0}^{\infty}\widetilde{P}^{II}_{p}(t)y^{t}z^{p},\qquad\textrm{where}\quad\widetilde{P}^{II}_{p}(t):=\sum_{\mathcal{M}\colon
p_{\mathcal{M}}=p}P^{II}_{\mathcal{M}}(t).$

We may extract the spectral dimension by examining $P^{II}(z,y)$ in the
vicinity of $z\sim z_{c}$ and $y\sim 1$.

######  Theorem 4.8.

The return probability generating function on the set of rooted melonic graphs
satisfies

$\displaystyle\frac{\partial P^{II}}{\partial
z}(z,y)=(1-z/z_{c})^{\Delta(d_{S}/2-1)-\gamma}\left[\Phi\left(\frac{1-y}{(1-z/z_{c})^{\Delta}}\right)+\Phi\left(\frac{1+y}{(1-z/z_{c})^{\Delta}}\right)\right],$

within the disc $|y|<1$, $z_{c}=D^{D}/(D+1)^{D+1}$, $\gamma=1/2$, $\Delta=3/2$
and

$\displaystyle d_{S}=4/3.$

Random walks on a melon. Consider a random walk on a rooted melonic graph
${\mathcal{M}}$. The walker takes one step per unit time. If the walker is at
one of the external points, one can see from Fig. 14 that it steps with
probability one to its unique neighbor. Meanwhile, if the walker is at any of
the internal $(D+1)$-valent vertices, it steps with equal probability,
$\frac{1}{D+1}$, to any one of its $D+1$ neighbors.

Thus, any given walk with $t$ steps takes place with a probability that is
simply the product of the probabilities from each of its $t$ constituent
jumps.

Return/transit random walks. _Return walks_ are walks that start and finish at
the external vertex. _Transit walks_ start at one external vertex and finish
at the other external vertex. Such return/transit random walks have a
generating function, the _return/transit probability generating function_ :
$P^{XY}_{\mathcal{M}}(y)$, where $X\in\\{I,O\\}$, $Y\in\\{I,O\\}$ and
$y\in\mathbb{C}$. This may be expanded as

$\displaystyle
P^{XY}_{\mathcal{M}}(y)=\sum_{t=0}^{\infty}y^{t}P^{XY}_{\mathcal{M}}(t),$

where $P^{XY}_{\mathcal{M}}(t)$ is the probability that the walker arrives at
external vertex $Y$ at time $t$, given that it starts at external vertex $X$
at time 0. This probability is simply a probability weighted sum over relevant
return/transit random walks.

1st-return/1st-transit random walks. _$1$ st-return walks_ are return walks
that spend the intervening period internal vertices. _1st-transit walks_ are
transit walks that spend the intervening period at internal vertices. Again
such 1st-return/1st-transit random walks have a generating function, the _$1$
st-return/$1$st-transit probability generating function_:
$P^{1,XY}_{\mathcal{M}}(y)$, where $X\in\\{I,O\\}$, $Y\in\\{I,O\\}$ and
$y\in\mathbb{C}$. This may be expanded as

$\displaystyle
P^{1,XY}_{\mathcal{M}}(y)=\sum_{t=0}^{\infty}y^{t}P^{1,XY}_{\mathcal{M}}(t),$

where $P^{1,XY}_{\mathcal{M}}(t)$ is the probability that the walker arrives
at external vertex $Y$ at time $t$, given that it starts at external vertex
$X$ at time 0 _and_ spends the intervening time period at internal vertices.
This probability is simply a probability weighted sum over relevant 1st-
return/1st-transit random walks.

######  Remark 4.9 (initial condition).

The simplest rooted melonic graph consists of two external vertices connected
by a line. It will be denoted by $\mathcal{M}_{(0)}$ and its 1st-return/1st-
transit probability generating function is

$\displaystyle P^{1}_{\mathcal{M}_{(0)}}(y)=\begin{pmatrix}0&y\\\
y&0\end{pmatrix}.$

Consistency relations. There are then two important relations:

  * •

_Any return/transit walk can be decomposed as a sequence of $1$st-
return/$1$st-transit walks._ As a result, the return/transit probability
generating function can be expressed in terms of the 1st-return/1st-transit
probability generating function

$\displaystyle
P^{XY}_{\mathcal{M}}(y)=\left[\frac{1}{1-P^{1}_{\mathcal{M}}(y)}\right]^{XY}.$

  * •

_Any $1$st-return/$1$st-transit walks on $\mathcal{M}$ can be decomposed as a
sequence of $1$st-return/$1$st-transit walks on its sub-melons
$\mathcal{M}^{i}$, where $i\in\\{0,\dots,D\\}$._ Again, this relation is
mirrored in the generating functions

$\displaystyle
P^{1}_{\mathcal{M}}=E^{22}P^{1}_{{\mathcal{M}}^{0}}E^{22}+\bigl{(}E^{12}y+E^{22}P^{1}_{{\mathcal{M}}^{0}}E^{11}\bigr{)}$
$\displaystyle\hphantom{P^{1}_{\mathcal{M}}=}{}\times\frac{1}{D+1-\sum\limits_{i=1}^{D}P^{1}_{{\mathcal{M}}^{i}}-E^{11}P^{1}_{{\mathcal{M}}^{0}}E^{11}}\bigl{(}yE^{21}+E^{11}P^{1}_{{\mathcal{M}}^{0}}E^{22}\bigr{)},$
$\displaystyle P^{1}_{\mathcal{M}_{(0)}}=\begin{pmatrix}0&y\\\
y&0\end{pmatrix},$

where

$\displaystyle
E^{ab}_{\alpha\beta}=\delta^{a}_{\alpha}\delta^{b}_{\beta},\qquad
a,b,\alpha,\beta\in\\{1,2\\}.$

Return/transit probability matrix. Finally, consider the space of rooted
melonic graphs. We are interested in computing the return probability of a
random walker, starting from some specified point, with respect to this set of
graphs. We shall specify this point as the external vertex $I$ for every
rooted melonic graph. This return probability is just one element of the
_return/transit probability matrix_

$\displaystyle
P^{XY}(z,y)=\sum_{\mathcal{M}}P^{XY}_{\mathcal{M}}(y)z^{p_{\mathcal{M}}}.$

To prove Theorem 4.8, one must solve the consistency relations above. For
details of the argument, we refer the reader to [23, 25].

##  5 Conclusion

We finish up with a quick word about the future study of $(D+1)$-colored
graphs. Clearly, we have just scratched the surface here. The combinatorial,
topological, algebraic and metric properties deserve a much more extensive
analysis. This could have many benefits: by analyzing a broader set of graphs,
one would hopefully escape the branched polymer phase in the continuum limit.
(In fact, such work has begun [10, 24], but branched polymers have so far
proved resilient.)

One such space is the so-called Brownian sphere [26]. A long-standing open
question is to pin down precisely its spectral dimension (there is a large
amount of evidence that it equals two). Were the Brownian sphere to occur as
the limiting metric space of a sufficiently amenable set of colored graphs,
then one might be able to tackle the problem as we did above for the continuum
random tree.

Of course, from a quantum gravity perspective, one would like to escape
branched polymers in favour of some continuum metric space that has physically
interesting characteristics, as they have done in the causal dynamical
triangulations approach to quantum gravity [3]. In particular, one would like
to recover a macroscopic 4-dimensional universe in some limit. Were this
possible, then the colored graph approach would have a significant advantage
in that one has the bubble Lie algebra (or some subalgebra thereof) at one’s
disposal, from which one could aim to extract the underlying symmetries of the
continuum limit.

## References

  * [1] Albenque M., Marckert J.-F., Some families of increasing planar maps, Electron. J. Probab. 13 (2008), no. 56, 1624–1671, arXiv:0712.0593.
  * [2] Ambjørn J., Durhuus B., Fröhlich J., Diseases of triangulated random surface models, and possible cures, Nuclear Phys. B 257 (1985), 433–449.
  * [3] Ambjørn J., Görlich A., Jurkiewicz J., Loll R., Nonperturbative quantum gravity, Phys. Rep. 519 (2012), 127–210, arXiv:1203.3591.
  * [4] Baratin A., Oriti D., Group field theory with noncommutative metric variables, Phys. Rev. Lett. 105 (2010), 221302, 4 pages, arXiv:1002.4723.
  * [5] Baratin A., Oriti D., Group field theory and simplicial gravity path integrals: a model for Holst–Plebanski gravity, Phys. Rev. D 85 (2012), 044003, 15 pages, arXiv:1111.5842.
  * [6] Benedetti D., Gurau R., Phase transition in dually weighted colored tensor models, Nuclear Phys. B 855 (2012), 420–437, arXiv:1108.5389.
  * [7] Bonzom V., Erbin H., Coupling of hard dimers to dynamical lattices via random tensors, J. Stat. Mech. Theory Exp. 2012 (2012), P09009, 18 pages, arXiv:1204.3798.
  * [8] Bonzom V., Gurau R., Riello A., Rivasseau V., Critical behavior of colored tensor models in the large $N$ limit, Nuclear Phys. B 853 (2011), 174–195, arXiv:1105.3122.
  * [9] Bonzom V., Gurau R., Rivasseau V., The Ising model on random lattices in arbitrary dimensions, Phys. Lett. B 711 (2012), 88–96, arXiv:1108.6269.
  * [10] Bonzom V., Gurau R., Ryan J.P., Tanasa A., The double scaling limit of random tensor models, J. High Energy Phys. 2014 (2014), no. 9, 051, 49 pages, arXiv:1404.7517.
  * [11] Di Francesco P., Ginsparg P., Zinn-Justin J., $2$D gravity and random matrices, Phys. Rep. 254 (1995), 133, hep-th/9306153.
  * [12] Ferri M., Gagliardi C., Crystallisation moves, Pacific J. Math. 100 (1982), 85–103.
  * [13] Ferri M., Gagliardi C., Grasselli L., A graph-theoretical representation of PL-manifolds – a survey on crystallizations, Aequationes Math. 31 (1986), 121–141.
  * [14] Gurau R., Lost in translation: topological singularities in group field theory, Classical Quantum Gravity 27 (2010), 235023, 20 pages, arXiv:1006.0714.
  * [15] Gurau R., Topological graph polynomials in colored group field theory, Ann. Henri Poincaré 11 (2010), 565–584, arXiv:0911.1945.
  * [16] Gurau R., Colored group field theory, Comm. Math. Phys. 304 (2011), 69–93, arXiv:0907.2582.
  * [17] Gurau R., A generalization of the Virasoro algebra to arbitrary dimensions, Nuclear Phys. B 852 (2011), 592–614, arXiv:1105.6072.
  * [18] Gurau R., The $1/N$ expansion of colored tensor models, Ann. Henri Poincaré 12 (2011), 829–847, arXiv:1011.2726.
  * [19] Gurau R., The complete $1/N$ expansion of colored tensor models in arbitrary dimension, Ann. Henri Poincaré 13 (2012), 399–423, arXiv:1102.5759.
  * [20] Gurau R., The Schwinger–Dyson equations and the algebra of constraints of random tensor models at all orders, Nuclear Phys. B 865 (2012), 133–147, arXiv:1203.4965.
  * [21] Gurau R., Rivasseau V., The $1/N$ expansion of colored tensor models in arbitrary dimension, Europhys. Lett. 95 (2011), 50004, 5 pages, arXiv:1101.4182.
  * [22] Gurau R., Ryan J.P., Colored tensor models – a review, SIGMA 8 (2012), 020, 78 pages, arXiv:1109.4812.
  * [23] Gurau R., Ryan J.P., Melons are branched polymers, Ann. Henri Poincaré 15 (2014), 2085–2131, arXiv:1302.4386.
  * [24] Gurau R., Schaeffer G., Regular colored graphs of positive degree, arXiv:1307.5279.
  * [25] Jonsson T., Wheater J.F., The spectral dimension of the branched polymer phase of two-dimensional quantum gravity, Nuclear Phys. B 515 (1998), 549–574, hep-lat/9710024.
  * [26] Le Gall J.-F., Uniqueness and universality of the Brownian map, Ann. Probab. 41 (2013), 2880–2960, arXiv:1105.4842.
  * [27] Lins S., Gems, computers and attractors for $3$-manifolds, Series on Knots and Everything, Vol. 5, World Scientific Publishing Co., Inc., River Edge, NJ, 1995.
  * [28] Oriti D., The quantum geometry of tensorial group field theories, in Symmetries and Groups in Contemporary Physics, Nankai Ser. Pure Appl. Math. Theoret. Phys., Vol. 11, World Sci. Publ., Hackensack, NJ, 2013, 379–384, arXiv:1211.5714.
  * [29] Ryan J.P., Tensor models and embedded Riemann surfaces, Phys. Rev. D 85 (2012), 024010, 9 pages, arXiv:1104.5471.
  * [30] Tanasa A., Multi-orientable group field theory, J. Phys. A: Math. Theor. 45 (2012), 165401, 19 pages, arXiv:1109.0694.
  * [31] Tanasa A., The multi-orientable random tensor model, a review, SIGMA 12 (2016), 056, 23 pages, arXiv:1512.02087.