1. Introduction, definitions
1.1 Results and motivation
By a unimodular random planar graph (URPG), we mean a unimodular random graph that is almost surely planar. Such a graph is called sofic if it has a local weak approximation by a sequence of finite graphs. See Subsection 1.2 for the precise definitions. We will prove the following.
Theorem 1.
Every unimodular random one-ended planar graph
$G$
is sofic.
A subgraph
$H$
of a rooted graph
$(G,o)$
is a unimodular subgraph if their joint distribution (
$G$
with indicator marks for the subgraph) is unimodular. This also implies that
$(H_o,o)$
is unimodular, where
$H_o$
is the component of
$o$
in
$H$
. The local weak limit of convergent unimodular random graphs is unimodular, and by restricting
$G$
to its subgraph induced by vertices of degree at most
$k$
, we get a sequence
$G_k$
that converges to
$G$
, so it is enough to prove the theorem for graphs of bounded degree. Unimodular trees are sofic, as proved by Elek [Reference Elek11] relying on a method by Bowen [Reference Bowen6]. An alternative proof was given in [Reference Benjamini, Lyons and Schramm3]. This implies, as shown by Elek and Lippner in [Reference Elek and Lippner13], that the existence of a unimodular spanning tree is sufficient for soficity. Hence Theorem 1 follows from the next theorem.
Theorem 2.
Every unimodular random one-ended planar graph
$G$
of finite expected degree contains a unimodular spanning tree.
Given a graph
$H$
, an end of
$H$
is an equivalence class of infinite non self-intersecting paths, where two such paths are equivalent if there is a third one that intersects both of them infinitely many times. A unimodular graph has either 0 (the finite case), 1, 2 or infinitely many ends [Reference Aldous and Lyons1].
Our main contribution is the following theorem. We provide the definitions after the theorem.
Theorem 3.
Let
$G$
be a locally finite unimodular random planar graph. Then
$G$
has a unimodular combinatorial embedding into the plane.
A planar map is defined as a proper embedding of a locally finite planar graph
$G$
into an open subset
$U$
of the sphere, up to orientation-preserving homeomorphisms, and with the property that every compact set of
$U$
is intersected by finitely many embedded edges, and every face (component of
$U$
minus the embedded graph) is homeomorphic to an open disk. We call a planar map simply connected if the union of the closure of the faces of the map is homeomorphic to either the entire sphere, or the sphere minus one point. If (after applying the homeomorphism, if necessary) one projects this embedding on the plane stereographically from this exceptional point (or an arbitrary point outside of the embedded graph, if there is no exceptional point), one gets a planar embedding with the property that every compact set is intersected by finitely many edges. We will also apply the term simply connected to an embedding of a graph, if the planar map defined by it is simply connected.
There is a combinatorial definition of embeddings: a combinatorial embedding is a collection of cyclic permutations
$\pi _v$
on the set of edges incident to
$v$
, as
$v\in V(G)$
, and we call this combinatorial embedding planar if there is an embedding of
$G$
into the sphere where the clockwise cyclic order of the edges around
$v$
is
$\pi _v$
. It is clear that every embedding defines a combinatorial embedding (if we take the cyclic permutation of edges by reading them clockwise around the embedded vertex), and conversely, any combinatorial embedding can be generated by some actual embedding, by definition. Using these permutations, one can give a combinatorial definition of faces: walk along edges, and when walking along
$e$
and reaching endpoint
$v$
, continue along
$\pi _v(e)$
. See e.g. [Reference Nachmias16] for a more precise definition. If a combinatorial embedding is generated by a planar map, the faces of the map are in natural bijection with the combinatorial faces. Conversely, a planar combinatorial embedding defines a unique planar map, which can be obtained if for every combinatorial face we take a disk, and glue its boundary along the face. Given a combinatorial embedding, defined by permutations
$\pi _v$
as
$v\in V(G)$
, we call this combinatorial embedding unimodular if the
$\pi _v$
as markings on the vertices define a unimodular marked graph, and if this holds, we also call the resulting rooted planar map unimodular.
In [Reference Angel, Hutchcroft and Nachmias2] Angel, Hutchcroft, Nachmias and Ray prove that every simply connected unimodular random rooted planar map is sofic. A unimodular random map that represents a one-ended graph is automatically simply connected (Proposition 5), hence Theorem 4 applies to it.
In this paper the only type of embeddings that we consider are combinatorial embeddings, and specifically, unimodular ones. About actual embeddings that are unimodular or invariant with regard to the automorphisms of
$G$
or the underlying space, we refer the reader to joint works of the author with Benjamini [Reference Benjamini and Timár4] and with Tóth [Reference Timár and Tóth20].
The next theorem is essentially Theorem 5.13 and Theorem 2 in [Reference Angel, Hutchcroft and Nachmias2].
Theorem 4. (Angel, Hutchcroft, Nachmias, Ray [Reference Angel, Hutchcroft and Nachmias2]). If
$G$
has finite expected degree and it can be represented by a simply connected unimodular random rooted planar map, then the free uniform spanning forest of
$G$
is a unimodular spanning tree almost surely. Consequently,
$G$
is sofic.
Conley, Gaboriau, Marks and Tucker-Drob, [Reference Conley, Gaboriau, Marks and Tucker-Drob8] have proved results related to Theorem 4. In our setup these can be vaguely phrased as follows: a unimodular simply connected planar map has some unimodular spanning tree, under certain mild conditions. Their paper is in the context of Borel graphs, and they consider graphs with a Borel 2-basis for the cycle space, which is equivalent to the existence of a Borel embedding that defines a simply connected planar map by a result of Thomassen [Reference Thomassen18], see [Reference Conley, Gaboriau, Marks and Tucker-Drob8]. They prove that if such an embedding exists and the graph is locally finite and not two-ended, then it has a Borel spanning forest with only one-ended trees. This defines a one-ended spanning tree for the dual graph. In [Reference Conley, Gaboriau, Marks and Tucker-Drob8], it is also shown that Theorem 2 (and hence Theorem 1) holds for the case of planar Cayley graphs.
Suppose that a URPG
$G$
has a unimodular embedding into the plane. Then Theorem 4 provides us with a sufficient condition to be sofic: whenever this embedding is simply connected. The graph structure of
$G$
does not directly determine whether the embedding is simply connected. To see this, consider the Cayley graph corresponding to
$\lt a,b \, |\, a^3, b^3\gt$
, which is the free product of two copies of the 3-element cyclic group. (Recall that if two groups
$G_1=\lt S_1\,|\, R_1\gt$
and
$G_2=\lt S_2\,|\, R_2\gt$
are given in terms of defining relators, where
$S_i$
is a generatings set for
$G_i$
and
$R_i$
are defining relators, then the free product of
$G_1$
and
$G_2$
is
$\lt S_1, S_2\,|\, R_1, R_2\gt$
.) This graph does have unimodular embeddings that are simply connected and that are not (Figure 1 hints the proof of this claim, with the explanation below it). As the next observation shows, for one-ended URPG’s, any unimodular embedding is simply connected. This is close to a characterisation, because ‘most’ URPG’s with 2 or infinitely many ends can only be embedded in the sphere with more than 1 accumulation points of edges, and hence there is no simply connected planar map that would represent them. See Remark 6 for more on the existence of simply connected embeddings.
A representation of (part of the) same infinite graph by a simply connected map (on the left) and by one that is not. The embedding on the left is unimodular (being an atomic probability measure on a single decorated graph), and we can make the one on the right unimodular by deciding for each triangle
$\Delta$
indepedently how its three neighbouring triangles should be mapped with regard to the two components of the sphere minus
$\Delta$
. After making these decisions for every triangle, the combinatorial embedding is determined up to orientation, and one can decide about the latter by a coin flip.
Proposition 5.
Let
$G$
be a one-ended URPG that has a unimodular combinatorial embedding into the plane. Then this embedding defines a simply connected planar map.
Proof.
The planar map defined by a combinatorial embedding of
$G$
can only be a surface that is compact or one-ended (as a topological space). Otherwise one could find finitely many faces whose removal cuts the surface into at least two pieces that each contain infinitely many faces, and hence
$G$
would have at least two ends. The only compact planar surface is the sphere, and the only one-ended planar surface is the sphere minus one point, as explained in Section 7 of [Reference Angel, Hutchcroft and Nachmias2] based on [Reference Biringer and Raimbault5].
Hence, if
$G$
also has finite expected degree, the conclusion of Theorem 4 holds. To illustrate that the one-endedness assumption cannot be omitted in general, note that the Cartesian product of a 3-cycle with a biinfinite path or the Cartesian product of one edge and a 3-regular tree are planar, but they cannot be represented by simply connected planar maps.
Remark 6. One-endedness is a sufficient condition for a locally finite graph to have some simply connected embedding, but not a necessary one. In [Reference Timár and Tóth20] a graph theoretical characterisation is given for the existence of a simply connected embedding. Then it is shown, based on the method of Section 2, that URPG’s that have some simply connected embedding also have a simply connected unimodular combinatorial embedding. (The construction for Theorem 3 may give a unimodular embedding that is not simply connected, unless some extra care is taken.) Theorems 2 and 1 remain true for these URPG’s as well, by the same argument as here.
Theorem 3 has some further corollaries. Without loss of generality we will assume that our URPG is ergodic (extremal), and will skip saying ‘almost surely’.
Corollary 7.
The dichotomy results of Theorem 1 in [Reference Angel, Hutchcroft and Nachmias2] are valid for every unimodular random one-ended planar graph
$G$
. In particular, the following are equivalent.
-
•
$G$
is invariantly amenable;
-
• there is a unimodular planar map with average curvature 0 that represents
$G$
; -
• every harmonic Dirichlet function is a constant;
-
• Bernoulli(
$p$
) percolation has at most one infinite component for every
$p\in [0,1]$
almost surely.
Proof of Theorem
1. Follows from Theorem 2 essentially by [Reference Elek and Lippner13]. See Section 8 of [Reference Angel, Hutchcroft and Nachmias2] for an elaboration of this implication and further references. A brief sketch of the proof is the following. Every unimodular random tree is strongly sofic, i.e., for any unimodular decoration of the tree there exists a sofic approximation by finite decorated graphs. Once we have a unimodular spanning tree
$T$
in a unimodular graph
$G$
, we can encode
$G$
as a unimodular decoration of
$T$
, and from the finite decorated graphs approximating this decorated
$T$
, we can obtain a sequence of finite graphs approximating
$G$
.
In an earlier version of this manuscript [Reference Timár19], we erroneously claimed that we can prove Theorems 1 and 2 without the assumption of one-endedness. The argument was based on a unimodular tree-like decomposition of
$G$
to pieces that are finite or one-ended, but a mistake was found, so it remains open whether such a decomposition exists for an arbitrary unimodular random graph (or at least planar ones), and whether URPG’s with infinitely many ends are sofic.
1.2 Unimodular random graphs, soficity
Given a graph
$H$
,
$x\in V(H)$
,
$r\in{\mathbb{R}}^+$
, denote by
$B(H,x,r)$
the ball of radius
$r$
around
$x$
in
$H$
. Let
$\mathcal{G}_*$
be the set of all locally finite rooted graphs up to rooted isomorphism (isomorphism preserving the root). For a rooted graph
$(G,o)$
, we denote the respective element (equivalence class) of
$\mathcal{G}_*$
by
$[G,o]$
, but if there is no ambiguity, we usually just refer to the equivalence class by
$(G,o)$
or
$G$
. One can make
$\mathcal{G}$
a metric space by defining the distance between two elements
$(G,o)$
and
$(G',o')$
by
$\inf \{2^{-r}\;:\; B(G,o,r)\cong B(G',o',r)\}$
, where
$\cong$
is the relation of being rooted isomorphic. A probability measure on
$\mathcal{G}$
is called a random rooted graph. One may also consider marked rooted graphs, in which case marks (labels) coming from some fixed metric space are also present on some vertices and/or edges. The definitions naturally extend to this setup. Consider a sequence
$G_n$
of finite graphs, and let
$o_n$
be a uniformly chosen vertex of
$G_n$
. We say that
$G_n$
converges to a random rooted graph
$G=(G,o)$
in the local weak (or Benjamini–Schramm) sense if for any finite rooted graph
$(H,o')$
,
$\textbf{P} (B(G_n,o_n,R)\cong (H,o'))\to \textbf{P} (B(G,o,R)\cong (H,o'))$
. In other words, the probability measure corresponding to
$(G_n,o_n)$
weakly converges to the probability measure corresponding to
$(G,o)$
. If a given random rooted graph
$G=(G,o)$
is the Benjamini–Schramm limit of a sequence of finite graphs, we call it sofic.
Similarly to
$\mathcal{G}_*$
, define
$\mathcal{G}_{**}$
as the set of graphs with an ordered pair of vertices, up to isomorphisms preserving the ordered pair. Suppose that
$G_0$
is a finite graph,
$o_0\in V(G)$
a uniformly chosen root, and
$\mu$
the probability measure on
$\mathcal{G}_{*}$
that samples
$(G_0,o_0)$
. For any Borel
$f\;:\;\mathcal{G}_{**}\to [0,\infty ]$
, we have the equation
\begin{equation} \int \sum _{x\in V(G)} f(G,o,x) d\mu ([G,o])=\int \sum _{x\in V(G)} f(G,x,o) d\mu ([G,o]), \end{equation}
because both sides are equal to
$|V(G_0)|^{-1}\sum _{x,y\in V(G_0)} f(G_0,x,y)$
. Given a probability measure
$\mu$
on
$\mathcal{G}_*$
, referred to as a random rooted graph, we say that it is unimodular if (1) holds. It is easy to check that sofic graphs are unimodular. A major open question is whether the converse is also true.
Question 8. (Aldous, Lyons [Reference Aldous and Lyons1]) Is every unimodular random (marked) graph sofic?
Whether the Cayley diagram of a group is sofic is a central question itself, and large classes of groups are known to be sofic; see [Reference Pestov17] for references or [Reference Elek12] for some more recent examples. In the class of planar unimodular random graphs that are known to be sofic are unimodular random trees ( [Reference Bowen6], [Reference Elek11]), or Curien’s Planar Stochastic Hyperbolic Triangulations [Reference Curien9], whose approximability by uniform random triangulations of appropriate genus was shown recently in [Reference Budzinski and Louf7].
2. Unimodular combinatorial planar embeddings for unimodular random planar graphs
In this section, we prove Theorem 3. Our strategy is as follows. First, it is enough to focus on 2-connected graphs, because one can decompose any connected graph to 2-connected components that may intersect only in cut-vertices, and once we have a unimodular combinatorial embedding for all the 2-connected components, we can extend it to one for the entire graph by taking suitable random permutations of the edges on each of these cutvertices independently. Now, for a 2-connected graph we can take its decomposition to 3-connected components (Theorem 10). For the 3-connected components the existence of a unimodular combinatorial embedding is straightforward, because they have a unique combinatorial embedding up to a reversal of orientation (Theorem 9). Then we can put together the combinatorial embedding of the 2-connected supergraph from these, using the mentioned decomposition and some local random choices.
2.1 Some tools: Whitney’s theorem, generalised Tutte decomposition
The following theorem was first proved by Whitney for finite simple graphs, and then generalised (to a broader setting than the one below) by Imrich, [Reference Imrich and Fiedler15]. Recall that having a unique combinatorial embedding up to orientation is the same as having a unique embedding into the plane up to homeomorphisms.
Theorem 9. (Whitney, Imrich). Let
$G$
be a 3-connected locally finite planar simple graph. Then
$G$
has two combinatorial embeddings into the plane, and one arises from the other by inverting all permutations.
Now, if one allows (finite bundles of) parallel edges, the theorem remains valid, with the only modification that all the parallel edges between vertices
$v$
and
$w$
appear in some consecutive order in the
$\pi _v$
and
$\pi _w$
, and the uniqueness of the embedding holds up to arbitrary permutations within these bundles of parallel edges. In what follows, we will apply the theorem in that sense: whenever we take the ‘unique’ combinatorial embedding of the graph, we mean the random embedding where we first (uniquely) embed the corresponding simple graph, and then add the parallel copies of each edge with a uniform random permutation on them.
The Tutte decomposition of a finite graph was developed by Tutte in [Reference Tutte21] and the uniqueness of the decomposition was shown in [Reference Hopcroft and Tarjan14]. In [Reference Droms, Servatius and Servatius10], Droms, Servatius and Servatius extended the results to infinite locally finite graphs. After preparing the necessary terminology, we will quote their result. More details are found in [Reference Droms, Servatius and Servatius10].
Given some graph
$G$
, a block of
$G$
is a maximal 2-connected subgraph of
$G$
(with respect to containment). A multilink is a pair of adjacent vertices together with all of finitely many parallel edges between them. A 3-block is a graph which is a cycle, a finite multilink or a locally finite 3-connected graph, and has at least three edges. We mention that by definition both blocks and 3-blocks are allowed to be infinite.
Suppose that
$A$
and
$B$
are two disjoint graphs, and there is a function
$f$
that picks one edge
$f_A$
from
$A$
, assigns a tail
$f_A^-$
and a head
$f_A^+$
to it, and picks an edge
$f_B$
from
$B$
and assigns a tail
$f_B^-$
and a head
$f_B^+$
to it. Then define the edge amalgam of
$A$
and
$B$
over
$f$
as the union of the graphs on
$A$
and
$B$
, with
$f_A^-$
identified with
$f_B^-$
and
$f_A^+$
identified with
$f_B^+$
, and
$f_A$
and
$f_B$
removed. See Figure 2 for an illustration. We denote the edge amalgam of
$A$
and
$B$
by
$A+_f B$
or simply
$A+B$
. It is easy to check that
$A+B$
is 2-connected if and only if
$A$
and
$B$
are both 2-connected. We call a countable labelled tree
$T$
an edge amalgam tree if every vertex
$\alpha \in V(T)$
is labelled by a graph
$G_\alpha$
(finite or infinite) which are pairwise disjoint, every edge
$\{\alpha,\beta \}\in E(T)$
is labelled by a function
$f=f(\alpha,\beta )$
that defines an edge amalgam of
$G_\alpha$
and
$G_\beta$
, and finally, every edge
$e$
of
$G_\alpha$
is amalgamated to at most one other edge, or more precisely, there is at most one function
$f$
and
$G_\beta$
such that
$G_\alpha$
and
$G_\beta$
get amalgamated along
$e$
(meaning
$f_{G_\alpha }=e$
). If there is exactly one such
$f$
, then we call
$e$
virtual. One can perform amalgamation over all the edges of
$T$
in some order, and the end result will be independent from the order in which the edges of
$T$
are chosen, by the last condition. Moreover, an edge will be present in the final graph
$\Gamma (T)$
if and only if it is not virtual.
Amalgamating two graphs. When both of them come with a combinatorial planar embedding, one obtains a combinatorial embedding of the amalgamated graph.
In [Reference Droms, Servatius and Servatius10] a 3-block tree is defined, as an edge amalgam tree (where the tree may not be locally finite), where every label
$G_\alpha$
is a 3-block, and no two multilinks or two cycles are neighbours in
$T$
. This latter requirement is only important because it ensures the following uniqueness theorem.
Theorem 10. (Droms, Servatius, Servatius, [Reference Droms, Servatius and Servatius10]). To any locally finite 2-connected graph
$G$
there corresponds a unique 3-block tree
$T$
such that
$\Gamma (T)=G$
.
We mention that in [Reference Droms, Servatius and Servatius10] the definition of a 3-block tree contains two more conditions than here, whose importance is explained in the discussion after the defininition in Section 3 of [Reference Droms, Servatius and Servatius10]. The first one (condition 2) is needed to make sure that a 3-block tree always give rise to a 2-connected graph. This is for a direction that we do not need, because we start from a 2-connected graph. The other one (condition 3) is needed to avoid vertices of infinite degree. This possibility is excluded in the setup of Theorem 10). Thus, we decided to take the simplified definition for a 3-block tree, which agrees with the original definition in the setup that we have.
2.2 A unimodular combinatorial embedding
Lemma 11.
If
$G$
is a 3-connected URPG and it is a simple graph, then the combinatorial embedding in Theorem 9 is unimodular. Consequently, Theorem 3 holds for
$G$
.
Proof.
Fix an instance of
$(G,o)$
; we will show that a large enough neighbourhood of
$o$
determines
$\pi _o$
, up to taking the inverse permutations (which we do not mention going forward; we will just flip a coin at the end to decide which of the two to chose). Let
$G_1\leq G_2\leq \ldots$
be a finite exhaustion of
$G$
, with
$o\in G_1$
. Fix a neighbour
$x$
of
$o$
arbitrarily. By the 3-connectedness of
$G$
, there exist three pairwise inner-disjoint paths between
$o$
and
$x$
, and so there is an
$N$
such that
$G_n$
contains all these paths if
$n\gt N$
. In the 3-block tree decomposition of
$G_n$
,
$n\gt N$
,
$o$
and
$x$
have to belong to the same 3-block (otherwise there is a 2-point separating set between them, more specifically, the endpoints of a virtual edge of the block that contains one of them). So, since
$x$
was arbitrary, if
$n$
is large enough, all the neighbours of
$o$
are in the same 3-block
$B_n$
as
$o$
in the 3-block tree decomposition of
$G_n$
, and this 3-block is 3-connected (and not a cycle or multilink, by construction). The
$B_n$
has a unique embedding by Theorem 9. Although
$B_n$
is not a subgraph of
$G_n$
, it is easy to see that it is a topological subgraph of
$G_n$
(that is, one can replace all the virtual edges of
$B_n$
by pairwise inner-disjoint paths in
$G_n$
). Then, it is also a topological subgraph of
$G$
, because
$G_n\leq G$
. Therefore, the topological subgraph of
$G$
that is isomorphic to
$B_n$
is also uniquely embedded in the plane. This implies that the permutation on the neighbours of
$o$
defined by the unique embedding of
$G$
is the same as the one defined by the embedding of
$G_n$
. This holds for any
$n\gt N$
proving our claim.
Lemma 12.
Let
$T$
be a 3-block tree consisting of a single edge
$\{\alpha,\beta \}$
. Then for any combinatorial embedding
$\pi ^{G_\alpha }$
of
$G_\alpha$
and
$\pi ^{G_\beta }$
of
$\mathcal{G}_\beta$
into the plane, there is a combinatorial embedding of
$G_\alpha +G_\beta$
in the plane whose restriction to
$G_\alpha$
is
$\pi ^{G_\alpha }$
, and restriction to
$G_\beta$
is
$\pi ^{G_\beta }$
. Here uniqueness is understood modulo permutations within bundles of parallel edges.
More generally, if
$T$
is a finite 3-block tree and a combinatorial embedding
$\pi ^{G_\alpha }$
is given for every
$G_\alpha$
, then
$\Gamma (T)$
has a unique combinatorial embedding in the plane whose restriction to
$G_\alpha$
is
$\pi ^{G_\alpha }$
for every
$\alpha \in V(T)$
. One can obtain this embedding by repeatedly applying the previous paragraph to the edges of
$T$
, in an arbitrary order.
Proof.
Denote
$A=G_\alpha$
and
$B=G_\beta$
, and let
$\pi ^A$
and
$\pi ^B$
be the respective combinatorial embeddings. Let
$f_A$
,
$f_B$
,
$f_A^-$
,
$f_A^+$
,
$f_B^-$
and
$f_B^+$
be as in the definition of the edge-amalgam tree. Let
$v^-$
be the vertex that
$f_A^-$
and
$f_B^-$
is merged into, after the amalgamation. By symmetry, it suffices to define
$\pi ^{A+B}_{v^-}$
. Suppose that the cyclic permutation
$\pi ^A_{f_A^-}$
is
$(f_A, e_1,\ldots, e_k)$
, and the cyclic permutation
$\pi ^B_{f_B^-}$
is
$(f_B, f_1,\ldots, f_\ell )$
. Then define
$\pi ^{A+B}_{v^-}$
as the permutation
$(e_1,\ldots, e_k, f_1,\ldots, f_\ell )$
.
The second part follows by induction.
Proof of Theorem
3. First suppose that
$G$
is 2-connected. Consider the unique 3-block tree
$T$
that corresponds to
$G$
, as in Theorem 10. Note that we can view
$T$
as a decoration of
$G$
, by defining a set system over
$G$
where every 3-block is represented by a subgraph of
$G$
, the one that results from this 3-block after the repeated amalgamations. This decoration is locally determined by
$G$
: we only have to find 3-connected components. Whether
$x$
and
$y$
are in the same 3-connected component, which happens if and only if there are three inner-disjoint paths between them, can be determined from a large enough neighbourhood, up to a small error. To summarise:
$T$
, if thought of as a decoration of
$G$
, is jointly unimodular with
$G$
, and hence we can rely on it in the following construction.
Given some
$T'\subset T$
, denote by
$\textrm{virt}(T')$
the set of virtual edges in
$\cup _{\alpha \in V(T')}E(G_\alpha )$
. For every
$\alpha \in V(T)$
fix a combinatorial embedding
$\pi ^{G_\alpha }$
of
$G_\alpha$
in the sphere, as follows. If
$G_\alpha$
is a multilink, take a uniform cyclic permutation of its edges; if
$G_\alpha$
is a 3-connected graph, take uniformly one of the two combinatorial embeddings (as in Theorem 9); and if
$G_\alpha$
is a cycle, take its unique combinatorial embedding. Then, by Lemma 12, for any finite subtree
$T'\subset T$
, there exists an embedding of the graph
$\Gamma (T')$
in the sphere such that the orientation that this embedding generates when restricted to
$G_\alpha$
is
$\pi ^{G_\alpha }$
, for every
$\alpha \in V(T')$
. Taking an exhaustion of
$T$
by finite subtrees
$T'$
, this gives rise to an embedding of
$G\cup \textrm{virt}(T)$
with similar properties. For every vertex of
$G$
, the limiting permutation for the combinatorial embedding is reached in a finite number of steps, hence the limit does not depend on the particular exhaustion taken. The resulting combinatorial embedding is unimodular: the only non-deterministic part is the embedding of the 3-blocks at the beginning. When the 3-block is finite, its embedding is trivially unimodular, and when it is infinite 3-connected, then apply Lemma 11.
Suppose now that
$G$
is an arbitrary connected graph. For each 2-block
$C$
pick a unimodular random combinatorial embedding
$\pi ^C$
. Such an embedding exists, as we have just seen. Consider an arbitrary cutvertex
$v\in V(G)$
. Let
$C_1,\ldots,C_k$
be a listing of the 2-connected components of
$G$
that contain
$v$
. Denote by
$N_i$
the edges of
$C_i$
that are incident to
$v$
.
For each
$i\in \{1,\ldots,k\}$
, pick an
$e^i_1\in N_i$
uniformly and independently, and let
$e^i_1,e^i_2,\ldots,$
$e^i_{|N_i|}$
be the listing of the elements of
$N_i$
in the order given by
$\pi ^{C_i}$
. Take a uniform cyclic permutation
$\delta$
of
$\{1,\ldots,k\}$
. Define the cyclic ordering
$e^1_1,e^1_2,\ldots, e^1_{|N_1|},e^{\delta (1)}_1,e^{\delta (1)}_2,\ldots,e^{\delta (1)}_{|N_{\delta (1)}|},\ldots,$
$e^{\delta ^{(k-1)}(1)}_1,e^{\delta ^{(k-1)}(1)}_2,\ldots, e^{\delta ^{(k-1)}(1)}_{|N_{\delta ^{(k-1)}(1)}|}$
on the edges incident to
$v$
, and call this ordering
$\sigma _v$
. Because of the tree-like structure that cutvertices define on a graph
$G$
, the permutations
$(\sigma _v)_{v\in V(G)}$
define a combinatorial embedding of
$G$
into the plane. For similar reasons as in the 2-connected case, the resulting combinatorial embedding is unimodular.
