# Partial triangulations of surfaces with girth constraints

Stephen C. Power  Dept. Math. Stats.
Lancaster University
Lancaster LA1 4YF
U.K<EMAIL_ADDRESS>
###### Abstract.

Barnette and Edelson have shown that there are finitely many minimal
triangulations of a connected compact 2-manifold ${\mathcal{M}}$. A similar
finiteness result is obtained for cellular partial triangulations that satisfy
the Maxwell count $3v-e=6$ and girth inequality constraints for certain
embedded cycles. Also a characterisation of cellular ${\mathcal{M}}$-embedded
(3,6)-tight graphs is given in terms of the satisfaction of higher genus girth
inequalities.

MSC2020 Mathematics Subject Classification. 05C10, 52C25

##  1\. Introduction

The following theorem, obtained in 1989, is due to Barnette and Edelson [2],
[3].

######  Theorem 1.1.

There are finitely many minimal triangulations of a compact 2-manifold.

The first paper [2] deals with orientable surfaces while the second paper [3]
obtains the general case, resolves an oversight in [2] and gives a more direct
proof avoiding Mayer-Vietoris sequences for homology groups. A proof of the
theorem is given in Section 2 below and in Section 4 we obtain an analogous
result for partial triangulations that satisfy the girth inequalities of
Definition 3.4. These inequalities are length constraints on embedded cycles
that bound an open disc in ${\mathcal{M}}$ that is not fully triangulated. For
the low genus settings of the projective plane and the torus considered in
[12] and [7] the girth inequalities of Definition 3.4 are sufficient for the
determination of (3,6)-sparsity. In Section 5, which is independent of Section
4, we define higher genus girth inequalities and show, in Theorem 5.8, that a
cellular graph $G$ in ${\mathcal{M}}$ is (3,6)-tight if and only if all higher
genus girth inequalities are satisfied, together with the Maxwell count
$3v-e=6$ for $G$. We expect that the methods of Section 4 can be extended to
higher genus critical cycles.

A compact 2-manifold ${\mathcal{M}}$, as a topological space, is homeomorphic
to a compact surface without boundary. We assume throughout that
${\mathcal{M}}$ is connected. A face of an embedded (finite) graph $G$ in
${\mathcal{M}}$ is a connected component of the complement of $G$ and we
consider a _triangulation_ of ${\mathcal{M}}$ to be an embedded simple graph
in ${\mathcal{M}}$ where every face is a 2-cell (open disc) bounded by a
3-cycle of embedded edges. Such an embedded graph $G$ is a _minimal
triangulation_ if no edge can be topologically contracted, in the natural way,
to give a simple embedded graph with 2 fewer faces. Equivalently, every edge
belongs to a nonfacial 3-cycle that does not form the boundary of an open disc
in ${\mathcal{M}}$. Two triangulations of ${\mathcal{M}}$ are regarded as the
same if their embeddings are unique up to a homeomorphism of ${\mathcal{M}}$.
The embedded graph definition of a triangulation does not require the stricter
condition that each face is uniquely associated with its boundary 3-cycle.
Thus the unique minimal triangulation of the sphere in our sense is $K_{3}$
rather than $K_{4}$. We also note that Barnette [1] has shown that there are 2
minimal triangulations of the real projective plane.

Recall that a triangulation of the sphere is $(3,6)$-tight, in the sense of
Definition 3.6 below. One can view this property as a uniform sparsity
condition for which $3v-e\geq 6$ holds for all subgraphs with at least 3
vertices, together with $3v-e=6$ for $G$ itself. In contrast, satisfaction of
the girth inequalities is a weaker nonuniform sparsity requirement. Classes of
$(3,6)$-tight graphs that admit embeddings in a surface, and their
construction by repeated vertex-splitting moves, are topics of current
interest in the rigidity theory of generic bar-joint frameworks in 3
dimensions, and this provides motivation for our considerations here. The
rigidity connection stems from the fact that vertex-splitting moves preserve
the generic rigidity of such a framework (Whiteley [17]). See, for example,
Cruickshank, Kitson and Power [6], [7], Cruickshank, Kastis, Kitson and
Schulze [5], Jordan [10], Jordan and Tanigawa [11], Kastis and Power [12] and
Kitson and Power [13].

Girth inequalities were introduced in Cruickshank, Kitson and Power [6] in the
setting of block and hole graphs considered earlier by Finbow-Singh and
Whiteley [8]. These graphs arise from surgery on a triangulated sphere whereby
the interiors of some essentially disjoint (ie. nonoverlapping) triangulated
discs are deleted and some of the resulting holes have so-called rigid block
graphs attached at their boundaries. In the case of a graph $G$ with a single
block and single hole and equal boundary lengths $r\geq 4$, a characterisation
of generic rigidity in ${\mathbb{R}}^{3}$ was given in [8] in terms of the
existence of $r$ disjoint paths from the boundary of the hole to the boundary
of the block. In [6] an alternative equivalent characterisation was given in
terms of the elementary girth inequalities of Definition 3.4. Also it was
shown that this is equivalent to the (3,6)-tightness of $G$ if the inserted
block graph is minimally rigid, and that this characterisation holds more
generally for single block graphs with several holes.

For other considerations of minimal triangulations, including the case of
manifolds with boundary and discussions of other methods, see Boulch, de
Verdière and Nakamoto [4]. In particular they obtain a generalisation of
Theorem 1.1 for surfaces with boundary. For a broad background on embedded
graphs see Gross and Tucker [9] and Mohar and Thomassen [15].

##  2\. The Barnette-Edelson theorem.

The overall scheme of the proof in [3] is an induction argument in which the
surface ${\mathcal{M}}$ is cut by a nonplanar 3-cycle of the embedded graph
$G$. If this 3-cycle has an annulus neighbourhood then the resulting 1 or 2
open manifolds, ${\mathcal{M}}^{\prime}$, or ${\mathcal{M}}^{\prime}$ and
${\mathcal{M}}^{\prime\prime}$, determine compact surfaces with boundary, each
component of the boundary having an embedded 3-cycle. If the cutting 3-cycle
has a Möbius strip neighbourhood in ${\mathcal{M}}$ then the resulting compact
surfaces with boundary have an embedded 6-cycle in each boundary component. In
both cases, by capping the boundary components with a topological disc one
obtains 1 or 2 compact surfaces. These lower genus surfaces, say
${\mathcal{M}}_{1}$, or ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$, have
triangulations, $T_{1}$, or $T_{1}$ and $T_{2}$, which are derived from $T$
and from small triangulations of the capping discs. A capping disc for the
cutting cycle has the form of an attached triangle or an attached triangulated
6-cycle. Although, for a minimal triangulation $T$, the derived triangulations
need not be minimal there is a genus bound on the number of disjoint
nonhomotopic 3-cycles with a common base point (see Theorem 2.2 below), and a
similar bound on disjoint homotopic 3-cycles with common base point (Lemma
2.1). These constraints ensure that the derived triangulations are close to
minimal (in the sense of Lemma 2.4).

The following lemma is Lemma 6 of [2]. See also Lemma 6 of [4]. A shrinkable
(or contractible) edge of the triangulation $T$ is one that does not lie on a
3-circuit (3-cycle of edges) other than the two facial 3-cycles that contain
the edge. A 3-circuit of $T$ is _planar_ if it is the boundary of an embedded
open disc in ${\mathcal{M}}$ and is _nonplanar_ otherwise. We may assume
henceforth that ${\mathcal{M}}$ is connected.

######  Lemma 2.1.

If $e$ is an edge in a triangulation $T$ of a compact 2-manifold
${\mathcal{M}}$ and if $e$ lies on four distinct nonplanar 3-circuits, all
homotopic to each other, then $T$ has a shrinkable edge.

Loosely speaking, the hypotheses imply that there is a triangulated planar
patch of $T$ with an edge that is sufficiently interior to this patch that it
cannot lie on a nonfacial 3-cycle. Consequently, for a minimal triangulation
there is a bound on the number of homotopic 3-circuits through a vertex. In
Lemma 3.7 we give a general version of this principle which is also applicable
in the context of certain critical walks in a contraction-minimal graph
embedding.

It is well-known that a nonfacial planar 3-cycle in a triangulation of
${\mathcal{M}}$ contains a contractible edge (see Lemma 1 of Barnette [1] for
example) and so in a minimal triangulation all nonfacial 3-cycles are
nonplanar. The lemma allows us to deduce that if, in a minimal triangulation,
there are many 3-cycles through an edge, then there are many 3-cycles through
that edge which are pairwise nonhomotopic.

A key topological fact used in the proof of Theorem 1.1 is the following genus
bound theorem which gives a limitation on the number of disjoint nonhomotopic
cycles. This is Corollary 1 of [3] which derives from Theorem 1 of [3] (our
Theorem 2.5 below) correcting the oversight from [2]. The genus $g$ is defined
below.

######  Theorem 2.2.

If ${\mathcal{M}}$ is not the sphere or projective plane then any family
${\mathcal{E}}$ of homotopically nontrivial simple pairwise nonhomotopic
curves, meeting only at a common point in ${\mathcal{M}}$, has at most $6g-3$
members when ${\mathcal{M}}$ is orientable, and $3g$ members when
${\mathcal{M}}$ is nonorientable, where $g$ is the genus of ${\mathcal{M}}$.

A corollary is the following genus bound lemma for vertex degrees with which
we may bypass some lemmas from [2].

######  Lemma 2.3.

Let ${\mathcal{M}}$ be a compact 2-manifold with genus $g$. Then there is a
constant $c$ such that the degree of a vertex in a minimal triangulation $T$
of ${\mathcal{M}}$ is no greater than $cg$.

###### Proof.

Suppose that $v$ has degree $m$. Consider the graph $N(v)$ corresponding to
the union of the triangles of $T$ incident to $v$. By minimality there are at
least $m/2-1$ nonplanar 3-cycles through $v$ with various edges not in $N(v)$
but with vertices adjacent to $v$. We call these _periferal edges_. By Lemma
2.1 there must be at least $[(m/2-1)/3]$ of these 3-cycles which are pairwise
nonhomotopic. By shrinking $N(v)$ to $v$, by a path of homeomorphisms of
${\mathcal{M}}$, we see that the periferal embedded edges of these 3-cycles
determine a set of loops at $v$ which are otherwise disjoint. These loops are
also pairwise nonhomotopic and so, by Theorem 2.2, $m\leq cg$ for some
constant $c$. ∎

We next give a proof of Theorem 1.1 assuming Theorem 2.2 and follow this with
a proof of Theorem 2.2.

Let $T^{\prime}$ be a triangulation obtained from the triangulation $T$ by
shrinking a single edge. Then call the reverse operation, $T\to T^{\prime}$,
to be a _vertex-splitting move_ , or, more precisely, a _planar vertex-
splitting move_. The following simple lemma plays a role in the induction
argument of the proof.

######  Lemma 2.4.

Let $T$ be a triangulation of a compact manifold ${\mathcal{M}}$ for which
there are exactly $n$ edges which do not lie on a nonfacial 3-cycle. Then $T$
is obtained from a minimal triangulation by a sequence of at most $n$ vertex-
splitting moves.

###### Proof.

The edge shrinking move and the planar vertex-splitting moves are inverse
operations on the set of triangulations of ${\mathcal{M}}$. It is enough then
to observe that if $T\to T^{\prime}$ is an edge shrinking move between
triangulations and some edge $f$ in $T$ lies on a nonfacial 3-cycle of $T$,
then the corresponding edge in $T^{\prime}$ lies on nonfacial 3-cycle. ∎

###### Proof of Theorem 1.1.

Let ${\mathcal{M}}$ be orientable with genus $g$ and suppose that the number
of minimal triangulations of a compact 2-manifold with lower genus is finite.
Cutting ${\mathcal{M}}$ with a 3-cycle (that is homotopic to a point) with
vertices $x,y,z$ we obtain 1 or 2 manifolds with boundary. Capping boundaries,
as indicated above, yields a compact 2-manifold ${\mathcal{M}}_{1}$, or the
pair ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$, each of which has genus
smaller than $g$.

Suppose first that there is one derived manifold ${\mathcal{M}}_{1}$. It
carries an inherited triangulation $T_{1}$ which need not be minimal. A
shrinkable edge, $f$ say, of $T_{1}$ has the property that it lies on a
3-cycle in ${\mathcal{M}}$ which passes through a vertex of the cutting
3-cycle. By Lemma 2.3 the degrees of these vertices, $x,y$ and $z$, in the
triangulation $T$, are are bounded by $cg$ for some constant $c$. It follows
that the number of such 3-cycles, and therefore the number of shrinkable edges
$f$, is at most $dg$ for some positive constant $d$. Assume, for the induction
hypothesis, that the number of minimal triangulations of of
${\mathcal{M}}_{1}$ is finite. By Lemma 2.4 the number of triangulations
$T_{1}$ of ${\mathcal{M}}_{1}$ obtained by the construction above is finite
and so the number of minimal triangulations $T$ is finite. This argument
establishes the induction step in the orientable case with cut cycle giving a
connected manifold ${\mathcal{M}}_{1}$. The same argument applies when the cut
leads to a pair ${\mathcal{M}}_{1},{\mathcal{M}}_{2}$ and so, since there is
one minimal triangulation for the sphere the theorem follows for orientable
2-manifolds.

In the nonorientable case the capping of the boundaries of ${\mathcal{M}}_{1}$
(or ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$) is by the attachment of
triangulated discs to 6-cycles, and the argument is the same. ∎

An embedded graph $G$ in a compact 2-manifold ${\mathcal{M}}$ is _cellular_ if
its faces, that is, the components of the complement of the union of the
embedded edges, are each homeomorphic to an open disc. The general Euler
formulae for $G$ are

$v-e+f=2-2g\quad\mbox{and}\quad v-e+f=2-g,$

for, respectively, the case of orientable and nonorientable ${\mathcal{M}}$,
where $v,e$ and $f$ denote the number of vertices, faces and edges of $G$. The
genus $g=g({\mathcal{M}})$ is defined to be the maximum number of disjoint
loops whose union has a connected complement in ${\mathcal{M}}$. Moreover, it
can be defined in terms of the standard models for ${\mathcal{M}}$ as the
number of attached handles to a sphere when ${\mathcal{M}}$ is oriented, and
as the number of attached cross caps when ${\mathcal{M}}$ is not oriented.

_Proof of Theorem 2.2._ Let $|{\mathcal{E}}|=n$. Suppose first that the
embedded graph determined by ${\mathcal{E}}$, with a single vertex and $n$
embedded edges, is cellular and the boundary of each face is the union of at
least 3 embedded edges. By Euler’s formula, for orientable ${\mathcal{M}}$, we
have $1-e+f=2-2g$. Also, $2e=\sum_{k}kf_{k}$ where $f_{k}$ is the number of
faces with $k$ edges. Thus $2e\geq 3f,$

$e\leq 1+f+2g-2\leq 2e/3+2g-1$

and so $e\leq 6g-3$. The genus bound in the nonorientable case is obtained in
the same way.

It remains to apply Theorem 2.5 below which is essentially Theorem 1 of [3].
We say that a loop edge $e$ in a surface is _essential_ if an associated
simple closed curve for it, say $\alpha(t),0\leq t\leq 1$, is not null
homotopic. Also, a pair of loops $e_{1},e_{2}$ with curves $\alpha,\beta$ with
$\alpha(0)=\beta(0)=v$ is said to be a homotopic pair of loops if
$\\{\alpha,\beta\\}$ or $\\{\alpha,-\beta\\}$ is a homotopic pair.

######  Theorem 2.5.

Suppose that ${\mathcal{M}}$ is not the sphere or the projective plane. Then
any family ${\mathcal{E}}=\\{e_{1},\dots,e_{r}\\}$ of pairwise nonhomotopic
essential loops, meeting only at a common point $v$, extends to a similar
family $\tilde{{\mathcal{E}}}$ whose embedded graph $G(\tilde{{\mathcal{E}}})$
is cellular with each face having at least 3 edges.

###### Proof sketch.

Let $U$ be a face of the embedded multigraph $G({\mathcal{E}})$ of
${\mathcal{E}}$. The main idea of the proof is to introduce a loop in
$U\cup\\{v\\}$ in order to extend ${\mathcal{E}}$ to a similar such family for
which $U$ is replaced by 1 or 2 faces that have lower genus. The genus $g(U)$
may be defined directly as the maximum number of disjoint loops in $U$ that do
not disconnect $U$. This is necessarily finite for any open connected subset
$U$ of ${\mathcal{M}}$.

If $g(U)$ is positive then there exists a loop in $U$ that passes through
either a handle or a cross cap of $U$. This loop may modified to give a loop,
$e_{*}$ say, in $\\{v\\}\cup U$, with the relative topology, that passes
through $v$ and the handle or cross cap. It follows that $e_{*}$ is essential
in ${\mathcal{M}}$. Also it is not homotopic to any loop of
${\mathcal{E}}_{0}$. This follows formally on considering the fundamental
group of the closure of $U$ in ${\mathcal{M}}$. A further case by case
analysis shows that $e_{*}$ is not homotopic to any loop in ${\mathcal{E}}$.
For the extended set ${\mathcal{E}}^{\prime}={\mathcal{E}}\cup\\{e_{*}\\}$
with embedded graph $G({\mathcal{E}}^{\prime})$ the face $U$ of
$G({\mathcal{E}}_{0})$ has been replaced by 1 or 2 faces with strictly lower
genus than $g(U)$.

Repeating this argument sufficiently often leads to an extended set
$\tilde{{\mathcal{E}}}$ for which the associated embedded graph has all faces
of genus 0. Further examination, together with the assumption that
${\mathcal{M}}$ is not the projective plane, shows that each face has at least
3 edges. ∎

The Barnette-Edelson theorem has been generalised by Malnic̃ and Nedela [14]
to so-called $k$-minimal triangulations $T$ for $k\geq 3$, meaning that the
edge-width of $T$ is $k$ and each edge lies on an essential $k$-cycle. A
triangulation has _edge-width k_ if the minimal length of an essential cycle
is $k$. See also Theorem 5.4.1 of [15] and the associated discussion.

As we have remarked in the introduction, Theorem 1.1 has been generalised
Boulch et al [4] to surfaces with boundary. (The sketch proof of Lemma 4 of
[4] needed for this may be completed with Theorem 2.5.)

##  3\. Sparse graphs and girth inequalities

Our main interest concerns various families of sparse graphs that satisfy the
Maxwell count $3v-e=6$ for three dimensions. However we also include
associated families for which $3v-e=\alpha$ with $\alpha\geq 6$. Henceforth
$\alpha$ is an integer no less than 6.

######  Lemma 3.1.

Let $G$ be a cellular embedded graph in a compact 2-manifold ${\mathcal{M}}$
that satisfies the global count $3v-e=\alpha$. Then

$\sum(k-3)f_{k}=\alpha+3\mu g-6$

where $\mu=2$ if ${\mathcal{M}}$ is orientable and $\mu=1$ otherwise.

###### Proof.

We have $2e=\sum_{k}kf_{k}$ and $3(2-\mu g)=3v-3e+3f$ and so

$6-3\mu g=e+\alpha-3e+3\sum f_{k}=\alpha-\sum kf_{k}+3\sum f_{k},$

and the identity follows. ∎

In particular, for such cellular graphs there is a bound on both the size and
number of faces with more than 3 edges and this bound depends only on $\alpha$
and the genus of ${\mathcal{M}}$.

Let ${\mathcal{F}}({\mathcal{M}})$ be a family of simple embedded graphs for
the compact 2-manifold ${\mathcal{M}}$. Then $G$ in
${\mathcal{F}}({\mathcal{M}})$ is said to be _contraction-minimal_ if for
every edge $e$ belonging to two facial 3-cycles and no other 3-cycles the
contracted embedded graph $G/e$, defined by the contraction of $e$, does not
belong to ${\mathcal{F}}({\mathcal{M}})$.

The Barnette-Edelson theorem shows that there are finitely many contraction-
minimal embedded graphs in the family ${\mathcal{T}}({\mathcal{M}})$ of
triangulations of ${\mathcal{M}}$. For a simple corollary, consider the family
${\mathcal{T}}({\mathcal{M}},n_{4},\dots,n_{r})$ of _partial triangulations_
that are cellular embedded simple graphs $G$ in ${\mathcal{M}}$ that have
$n_{k}$ faces with closed boundary walks of length $k$, for $4\leq k\leq r$.
We extend earlier terminology by defining a 3-cycle of $G$ to be _planar_ if
it is the boundary cycle of an open disc in ${\mathcal{M}}$ which contains no
nontriangular faces of $G$.

######  Theorem 3.2.

There are finitely many contraction-minimal embedded graphs in the family
${\mathcal{T}}({\mathcal{M}},n_{4},\dots,n_{r})$.

###### Proof.

Let $G$ be contraction-minimal in
${\mathcal{T}}({\mathcal{M}},n_{4},\dots,n_{r})$. Then every edge on 2 facial
3-cycles of $G$ lies on a nonfacial 3-cycle of $G$. Add a vertex and $k$ edges
to each face of $G$ with a closed boundary walk of length $k\geq 4$ to obtain
an embedded simple graph $G^{+}$ in ${\mathcal{T}}({\mathcal{M}})$. Let
${\mathcal{S}}$ be the set of these added edges together with the set of edges
that belongs to these boundary walks of $G$. Then $|{\mathcal{S}}|$ is no
greater than $N=2n_{4}+\dots+2n_{r}$. All other edges of $G^{+}$ lie on
nonfacial 3-cycles. It follows from Lemma 2.4 that $G^{+}$ is obtained from a
minimal triangulation of ${\mathcal{M}}$ by at most $N$ vertex-splitting moves
and so, by the Barnette-Edelson Theorem, the embedded graphs $G^{+}$, and
hence the embedded graph $G$, are finite in number. ∎

###  3.1. Girth inequalities.

Let $c$ be a closed walk in an ${\mathcal{M}}$-embedded simple graph $G$. Then
$c$ is a _planar type closed walk_ if, as an embedded graph, $c$ has a
cellular face $U$ for which $c$ is the boundary walk. Such a closed walk is
said to be a _planar walk for $G$_ if, in addition, $U$ is triangulated by
triangular faces of $G$. Equivalently, the closure of $U$ is the closure of
the union of the triangular faces of $G$ in $U$.

######  Definition 3.3.

Let $G$ be a simple embedded cellular graph for the compact 2-manifold
${\mathcal{M}}$ with nontriangular faces $W_{1},\dots,W_{r}$. Then a planar
type closed walk $c$ in $G$ with face $U$ _satisfies the girth inequality_ if

$|c|-3\geq\sum_{k\in I(U)}(|c_{k}|-3),$

where $I(U)$ is the index set for the boundary walks $c_{k}$ for the
nontriangular faces $W_{k}$ contained $U$. When equality holds $c$ is said to
be a _critical planar type walk for $G$_.

######  Definition 3.4.

A cellular embedded graph $G$ in a compact 2-manifold ${\mathcal{M}}$
satisfies the _planar girth inequalities_ if every planar type closed walk $c$
in $G$ with cellular face $U$ satisfies the girth inequality.

Write ${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$, for $\alpha\geq 6$, for
the family of simple cellular embedded graphs $G$ in ${\mathcal{M}}$ that
satisfy the planar girth inequalities and the freedom count
$f(G)=3v-e=\alpha$.

For a planar type walk $c$ with open disc face $U$ let
$\operatorname{Int}_{G}(c)$, the _interior graph_ of $c$, be the subgraph of
$G$ formed by the union of the edges of $c$ and the edges of $G$ that meet
$U$. Also let $\operatorname{Ext}_{G}(c)$, the _exterior graph_ of $c$ be the
subgraph of $G$ whose edges and vertices do not meet $U$.

######  Lemma 3.5.

Let $c$ be a planar type closed walk for the cellular embedded graph $G$ with
$f(G)=\alpha$. Then the following assertions are equivalent.

(i) $c$ satisfies the girth inequality.

(ii) $f(\operatorname{Ext}_{G}(c))\geq\alpha.$

###### Proof.

By Lemma 3.1 we have

$\sum_{k\geq 4}(k-3)f_{k}=3\mu g+f(G)-6$

and so

$\sum_{k\in I(U)}(|c_{k}|-3)+\sum_{k\notin I(U)}(|c_{k}|-3)=3\mu g+f(G)-6.$

For the cellular embedded graph $\operatorname{Ext}_{G}(c)$ we have,
similarly,

$|c|-3+\sum_{k\notin I(U)}(|c_{k}|-3)=3\mu g+f(\operatorname{Ext}_{G}(c))-6$

and so the equivalence follows. ∎

######  Definition 3.6.

A graph is _$(3,6)$ -sparse_ if it satisfies the local count
$f(G^{\prime})\geq 6$ for each subgraph $G^{\prime}=(V^{\prime},E^{\prime})$
with at least 3 vertices and is _$(3,6)$ -tight_ if in addition $f(G)=6$. The
family ${\mathcal{F}}({\mathcal{M}},6)$ is the family of cellular embedded
graphs in ${\mathcal{M}}$ whose underlying graphs are $(3,6)$-tight.

It follows that if $G$ is (3,6)-tight then it belongs to ${\mathcal{G}}_{\rm
pl}({\mathcal{M}},6)$. The equality
${\mathcal{F}}({\mathcal{M}},6)={\mathcal{G}}_{\rm pl}({\mathcal{M}},6)$ does
not hold in general as we now see for certain partial triangulations $G$
associated with Figure 1.

By the formula above if the torus is partially triangulated with a single
nontriangular face with a closed walk $c$ of length $r$ then $f(G)=r-3$, and
so $r=9$ if $G$ is in ${\mathcal{F}}({\mathcal{M}},6)$. The figure indicates a
partial triangulation $G$ of the double torus ${\mathcal{M}}$, with
$g({\mathcal{M}})=2$ where there are two faces with boundary cycle lengths 8
and 10, and hence $f({\mathcal{M}})=6$. Also, in the partial triangulation
${\mathcal{M}}$ is the join two partially triangulated tori over a common
3-cycle. Since the nontriangular faces are separated by an essential 3-cycle
it follows that a critical walk cannot include vertices that are separated by
this 3-cycle. It is therefore elementary to construct the partial
triangulation so that $G$ satisfies the planar girth inequalities. On the
other hand the subgraph $K_{1}$ obtained by removing edges and vertices to the
right of the separating 3-cycle has freedom $f(K_{1})=5$ and so $G$ is not
(3,6)-tight.

Figure 1. The nontriangular faces of a cellular graph $G$ for the orientable
surface ${\mathcal{M}}$ of genus $2$ with boundary cycles of lengths 8 and 10.

###  3.2. Critical patches and contractible edges

We now obtain a generalisation of Lemma 2.1.

Let $c_{1},c_{2}$ be planar type critical walks in $G$, with $G$ in
${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$, that have common vertices
$v,w$ and subwalks $\pi_{1},\pi_{2}$ from $v$ to $w$ that are disjoint.
Moreover suppose that the concatenation of $\pi_{1}$ and the reversal of
$\pi_{2}$ gives a boundary walk of an open disc that contains only triangular
faces of $G$. Denote the triangulated subgraph determined by these faces as
$P(\pi_{1},\pi_{2})$ and refer to it as a _critical patch_ of $G$. It follows
that $|\pi_{1}|=|\pi_{2}|$, with length $d$ say, and that every path $\pi$ of
edges in the patch from $v$ and $w$ has length at least $d$. If $\pi$ has no
vertices on $c_{1},c_{2}$ except $v,w$ then $\pi$ is said to be an internal
path of $P=P(\pi_{1},\pi_{2})$. With this notation we have the following
lemma.

######  Lemma 3.7.

Let $P$ be a critical patch for $G$ determined by paths $\pi_{1},\pi_{2}$
between $v,w$ with length $d\geq 3$. Also, let ${\mathcal{S}}$ be the set of
all paths in $P$ from $v$ to $w$ with length $d$ and let
${\mathcal{S}}^{\prime}\subset{\mathcal{S}}$ consist of essentially disjoint
paths in the sense that the only vertices common to the 2 paths are $v$ and
$w$. If $G$ is contraction-minimal then there is an independent bound for
$|{\mathcal{S}}^{\prime}|$ and hence an independent bound for
$|{\mathcal{S}}|$.

###### Proof.

The paths of ${\mathcal{S}}^{\prime}$ may be naturally ordered as adjacent
paths, say $\rho_{1},\dots,\rho_{s}$. Consider an edge $e=xy$ of a triangular
face of the form $vxy$ where $vx$ is an edge of $\rho_{i}$. (Figure 2
indicates such an edge when $s=5,d=5$ and $i=3$.) By the hypotheses $e$ lies
on a nonfacial 3-cycle of $G$ or on a critical walk $c$ of $G$. The first
possibility is evidently not possible if $s\geq 3$ and $i\neq 1,s$. Consider
then the subwalk $\tau$ of $c$ in $P$ with vertices $a,b$ on the boundary of
$P$. Then $\\{a,b\\}$ is not the set $\\{v,w\\}$ since this would imply the
existence of a path of length less that $d$ between $v$ and $w$. On the other
hand by Lemma 3.1 there is an independent bound, say $M$, for the length of
$c$. It follows that if $s\geq 2M$ and $i=M$ then there is no path of length
less than $M$ between $a$ and $b$ if $\\{a,b\\}\neq\\{v,w\\}$. It follows that
$s$ is less than $2M$, completing the proof. ∎

$v$$x$$y$$\pi_{2}$$w$$\pi_{1}$

Figure 2. Internally disjoint paths of length 5 in the critical patch
$P(\pi_{1},\pi_{2})$.

In the next lemma since $U_{2}\backslash U_{1}$ contains no nontriangular
faces it is straightforward to apply Lemma 3.7 to obtain an independent bound
on its size.

######  Lemma 3.8.

Let $G$ be a contraction-minimal embedded graph in ${\mathcal{G}}_{\rm
pl}({\mathcal{M}},\alpha)$ and let $c_{1},c_{2}$ be equivalent planar type
critical walks of $G$ with faces $U_{1},U_{2}$ with $U_{1}\subset U_{2}$. Then
there is an independent bound for the number of triangular faces of $G$ in
$U_{2}\backslash U_{1}$.

###### Proof.

Let $e$ be an edge which meets a connected component $W$ of $U_{2}\backslash
U_{1}$. We first show that it is not possible that $e$ has distance greater
that $6g+\alpha$ from the boundary of $W$, where $g$ is the genus of
${\mathcal{M}}$. This distance is defined to be the length of a shortest path
from a vertex of $e$ to a vertex of the boundary of $U_{2}\backslash U_{1}$.
Since $U_{2}\backslash U_{1}$ is triangulated by triangular faces of $G$ the
edge $e$ cannot lie on a critical walk in this case since such a walk has
length no greater than $6g+\alpha$. Similarly $e$ cannot lie on an essential
3-cycle. Also, since $G$ is contraction-minimal $e$ does not lie on a planar
nonfacial 3-cycle. The contraction $G/e$ is therefore simple and lies in
${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$, and so this case does not
occur.

The component $W$ is a critical patch $P$ since its boundary walk is a
concatenation of a subwalk of $c_{1}$ and a subwalk of $c_{2}$. By Lemma 3.7
there is an upper bound for the number of triangular faces of $P$. Since
distinct components $W$ correspond to distinct subwalks of $c_{1},c_{2}$ the
lemma follows. ∎

##  4\. Girth conditions and contraction-minimal graphs

In this section we obtain the following finiteness theorem. As before
$\alpha\geq 6$.

######  Theorem 4.1.

There are finitely many contraction-minimal embedded graphs in
${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$.

In the proof it is shown that there is a bound for the number of edges of a
contraction-minimal graph $G$ that depends only on $\alpha$ and the genus of
${\mathcal{M}}$ and is independent of the size of $G$. Such a bound is
referred to as an _independent bound_.

The first step of the proof, Lemma 4.4, shows that there is an independent
bound for the number of edges interior of a critical planar type walk. This is
used in the proof of Lemma 4.5 which obtains an independent bound for the
number of critical walks. For brevity in the narrative of this section we
refer to a critical planar type walk simply as a critical walk. Finally,
Proposition 4.9, shows that there is an independent bound for the number of
essential 3-cycles in $G$. This last step makes use of Theorem 2.2 in the
proof of the preliminary lemma, Lemma 4.7.

The following terminology will be useful. Let $c_{1},c_{2}$ be a pair of
critical walks in $G$, for the open discs $U_{1}$ and $U_{2}$ respectively.
Then $c_{1},c_{2}$ are _equivalent_ if $U_{1}$ and $U_{2}$ contain the same
set of nontriangular faces of $G$. An equivalent pair $c_{1},c_{2}$ is said to
be _nonseparating_ if only one connected component of the intersection
$U_{1}\cap U_{2}$ contains the nontriangular faces common to $U_{1}$ and
$U_{2}$. Finally, the critical walk $c_{1}$, as well as the open set $U_{1}$,
is said to be _inclusion-maximal_ if there is no nonseparating equivalent pair
$c_{1},c$ where the open disc face $U$ for $c$ strictly contains $U_{1}$.

######  Lemma 4.2.

Let $G$ belong to ${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$ and let
$c_{1},c_{2}$ be nonseparating equivalent critical planar type walks in $G$
with faces $U_{1},U_{2}$ respectively, where $U_{2}\backslash U_{1}$ is
nonempty. Then there is a critical planar type walk $c_{3}$ equivalent to
$c_{1}$, with $c_{1},c_{3}$ nonseparating, and whose face strictly contains
$U_{1}$.

###### Proof.

Suppose that $c_{1},c_{2}$ have subwalks $\pi_{1}$ and $\pi_{2}$ that are
disjoint apart from common endpoints. Also suppose that $\pi$ is the closed
walk formed by the concatenation $\pi_{1}$ and $-\pi_{2}$ (or $\pi_{2}$
according to orientation. Thus $\pi$ forms the boundary walk of an open disc
and we suppose further that it is triangulated by triangular faces of $G$.
Thus $|\pi_{1}|=|\pi_{2}|$ since the closed walks are critical. The open disc
is either a component of $U_{2}\backslash U_{1}^{-}$ or $U_{1}\backslash
U_{2}^{-}$. In the first case we may complete the proof by taking $c_{3}$ to
be $c_{1}$ with $\pi_{1}$ replaced by $-\pi_{2}$ or $\pi_{2}$. Thus we may
assume that the first case does not occur.

$c_{1}$$c_{2}$$w$$v$

Figure 3. Nonseparating equivalent critical planar type walks $c_{1},c_{2}$
for which there are no components of $U_{1}\backslash U_{2}^{-}$ that are
triangulated.

In the second case we can replace $c_{2}$ by a new critical planar type closed
walk $c_{2}^{\prime}$ by replacing $\pi_{2}$ by $\pi_{1}$ or $-\pi_{1}$.
Repeating such replacements we may assume that $c_{1},c_{2}$ have no
triangulated patches formed by such essentially disjoint subwalks
$\pi_{1},\pi_{2}$. Figure 3 gives an illustration of a pair $c_{1},c_{2}$ with
this property. Noting that $c_{1},c_{2}$ are assumed to be equivalent, it now
follows that the intersection $U_{1}\cap U_{2}$ has a single connected
component and this component has a boundary walk formed by the concatenation
of subwalks of $c_{1}$ and $c_{2}$ between 2 vertices, $v,w$. Let
$\gamma_{1},\gamma_{2}$ denote these subwalks. Since the complementary walk to
$\gamma_{2}$, say $\gamma_{2}^{\prime}$, forms a triangulated patch with
$\gamma_{1}$, we have $|\gamma_{1}|=|\gamma_{2}^{\prime}|$ and we may replace
$|\gamma_{1}|$ by $|\gamma_{2}^{\prime}|$ to obtain the desired critical walk
$c_{3}$. ∎

The following corollary is immediate.

######  Corollary 4.3.

Let $G$ belong to ${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$. A critical
planar type walk in $G$ is contained in a nonseparating equivalent critical
planar type walk that is inclusion-maximal.

######  Lemma 4.4.

Let $G$ be a contraction-minimal embedded graph in ${\mathcal{G}}_{\rm
pl}({\mathcal{M}},\alpha)$. Then there is an independent bound for the number
of faces of $G$ in the face of a critical planar type walk.

###### Proof.

Consider a critical walk $c$ of $G$ with open disc $U$. Every edge $e$ of $G$
which meets $U$ has one of the following 3 properties.

(i) $e$ lies on an essential 3-cycle of $G$.

(ii) $e$ lies on a critical walk $c^{\prime}$ with face $U^{\prime}$ that is
not contained in $U$. In this case $c^{\prime}$ has a subwalk $\pi^{\prime}$
between distinct vertices $v,w$ on the boundary of $U$.

(iii) $e$ fails properties (i) and lies on a critical walk $c^{\prime}$ with
face $U^{\prime}$ contained in $U$.

In each case we show that there is an independent bound for the number of
edges $e$ by showing that there is an independent bound for the 3-cycles given
in (i), for the subwalks given in (ii)), and for the critical cycles
$c^{\prime}$ whose faces are contained in $U$.

Considering the second property first, note that the subwalk $\pi$ for an edge
$e$ with property (ii) has no self-intersections in $U$ in the sense that each
vertex of $\pi^{\prime}$ in $U$ belongs to exactly 2 edges of $\pi^{\prime}$.
Let $W_{1},\dots,W_{r}$ be the nontriangular faces of $G$ that are contained
in $U$. It follows that the set of such subwalks $\pi^{\prime}$, between a
specific pair of vertices $v,w$ of $c$, is partitioned into finitely many
subset classes according to the distribution of the particular sets $W_{i}$ in
the two components of the complement of $\pi$ in $U$. Moreover, if two such
subwalks $\pi^{\prime},\pi^{\prime\prime}$ between $v$ and $w$ belonging to
the same partition class, with $c^{\prime}$ and $c^{\prime\prime}$ equivalent
critical walks, then $|\pi^{\prime}|=|\pi^{\prime\prime}|$. This follows since
the regions between $\pi^{\prime}$ and $\pi^{\prime\prime}$ are triangulated.
It follows from Lemma 3.7 that there is an independent bound for the number of
subwalks in the same partition class. Since there is an independent bound for
the number of pairs $v,w$ it follows that there is an independent bound for
the number of subwalks $\pi$ that arise in (ii).

If an edge $e$ has property (i) then it must lie on a 3-cycle with 2 or 3
edges that meet $U$ and which determine a subpath of 2 or 3 edges between
vertices $v,w$ of $c$. The argument of the previous paragraph applies and so
there is an independent bound for such edges.

In the final case we suppose that $c^{\prime},d^{\prime}$ are equivalent
critical cycles with faces $U(c^{\prime}),U(d^{\prime})$ that are subsets of
$U$. In fact we shall initially view $c^{\prime}$ as fixed and $d^{\prime}$ as
variable. The argument is similar in spirit to that for case (ii) above, this
time with Lemma 3.7 ensuring that there is a bound for equivalent critical
cycles with the same partitioning, of the set of $W_{i}$. This partitioning is
referred to below as an _enclosure pattern_.

The intersection $U(c^{\prime})\cap U(d^{\prime})$ has connected components
$X_{i}$ and the complement of the closure of the union $U(c^{\prime})\cup
U(d^{\prime})$ has components $Y_{j}$. Also, the number of these components is
bounded by the length of $c^{\prime}$. The nontriangular faces of $G$ are
distributed in these components in a particular manner, as illustrated in
Figure 4. This distribution may be recorded in terms of the sequence of common
vertices of $c^{\prime},d^{\prime}$, up to cyclic order in $c^{\prime}$,
together with the sequence of associated subsets of nontriangular faces that
they enclose. We refer to this as an enclosure pattern of $d^{\prime}$ with
respect to $c^{\prime}$. In Figure 4 the enclosure pattern is the pair

$(v_{1},v_{2},\dots,v_{6},v_{1}),\quad(\\{W_{1}\\},\\{W_{2},W_{3}\\},\\{W_{4}\\},\emptyset,\emptyset,\emptyset).$

Note now that if for another equivalent pair $c^{\prime},b^{\prime}$ the
enclosure pattern of $b^{\prime}$ is equal to that of $d^{\prime}$ (up cyclic
permutation) then the symmetric difference $U(c^{\prime})\triangle
U(b^{\prime})$ is nonempty and has connected components whose closures are
triangulated. It follows from Lemma 3.8 that there is an independent bound for
the set of such critical cycles $b^{\prime}$ with the given enclosure pattern.

$d^{\prime}$$c$$v_{1}$$W_{1}$$v_{2}$$W_{2}$$W_{3}$$v_{3}$$v_{4}$$v_{5}$$c^{\prime}$$v_{6}$$W_{4}$

Figure 4. The equivalent critical walks $c^{\prime},d^{\prime}$ determine
subwalks of $d^{\prime}$ between consecutive vertices in the cycle
$(v_{1},v_{2},\dots,v_{6},v_{1})$ that enclose nontriangular faces of $G$ (the
unshaded circles) with corresponding sequence
$(\\{W_{1}\\},\\{W_{2},W_{3}\\},\\{W_{4}\\},\emptyset,\emptyset,\emptyset)$.

The set of enclosure patterns is finite and so we have shown that the number
of distinct critical cycles $b^{\prime}$ equivalent to $c^{\prime}$ has an
independent bound. Reversing the roles of $c^{\prime}$ and $d^{\prime}$ it
follows that the set of critical cycles whose equivalence class is not a
singleton has an independent bound.

It suffices then to see that there is an independent bound for the number of
critical cycles $c^{\prime}$, with face $U(c^{\prime})\subset U$, for which
there is no other equivalent critical cycle $b^{\prime}$ with face
$U(b^{\prime})\subset U$. This follows since there are a finitely many
nontriangular faces of $G$. ∎

In the next proof we use the following elementary argument to find an
independent bound for the set, ${\mathcal{C}}(G)$ say, of walks in a
contraction minimal graph $G$ which have a particular property. A partition of
${\mathcal{C}}(G)$ is given into subsets
${\mathcal{C}}_{1}(G),\dots,{\mathcal{C}}_{r}(G)$ where $r$ has an independent
bound and $C_{1}(G)$ has maximal size amongst these subsets and is also
denoted as ${\mathcal{C}}_{1,1}(G)$. A similar partition, also with an
independent bound, can be made for ${\mathcal{C}}_{1,1}(G)$ and giving a
maximal size subset, ${\mathcal{C}}_{1,2}(G)$. Repeating this process gives a
finite sequence

${\mathcal{C}}_{1,1}(G),{\mathcal{C}}_{1,2}(G),\dots,{\mathcal{C}}_{1,N(G)}(G).$

Moreover it is known that $N(G)$ has an independent bound. In the proof this
is the case because of the overlapping property indicated there. It follows
from the pigeonhole principle that the cardinality of the original set
${\mathcal{C}}(G)$ has an independent bound.

######  Lemma 4.5.

Let $G$ be a contraction-minimal graph in ${\mathcal{G}}_{\rm
pl}({\mathcal{M}},\alpha)$. Then there is an independent bound for the number
of critical planar type walks in $G$.

###### Proof.

Consider first the subset of such embedded graphs that have a single
nontriangular face. If $G$ is of this type then all critical walks are
equivalent and by Corollary 4.3(i) there is a maximal critical walk that
contains all other critical walks. By Lemma 4.4 there is an independent bound
for the cardinality of this subset.

Suppose that $G$ has more than 1 nontriangular face and consider first the
finite sequence of critical walks $c_{1},c_{2},\dots$ in $G$ with the
following properties.

(i) the $c_{k}$ are in the same equivalence class for specific pair of
nontriangular faces, say $W_{1},W_{2}$.

(ii) each $c_{k}$ is inclusion maximal.

In particular it follows from inclusion-maximality that the $c_{k}$ are
pairwise separating. Considering $c_{1}$ as a base walk, each $c_{k}$, for
$k\geq 2$, has 2 subwalks that, together with a subwalk of $c_{1}$, enclose
$W_{1}$ and $W_{2}$. Since there is an independent bound for the interior
edges of a critical walk, by Lemma 4.4, there is also an independent bound on
the possibilities for the enclosing subwalks of the $c_{k}$, for $k\geq 2$.
These possibilities partition the set of these $c_{k}$ into subsets, say
${\mathcal{C}}_{1},\dots,{\mathcal{C}}_{m}$. Suppose moreover that
${\mathcal{C}}_{1}$, which we also denote as ${\mathcal{C}}_{1,1}$, has
maximal cardinality, and relabel its critical walks as $c_{2},c_{3},\dots$.
Thus, the enclosing subwalks for $c_{1}$ are the same for each $c_{k}$, for
$k\geq 2$. See Figure 5.

Let $U_{k}$ be the face of $c_{k}$ and $F(U_{k})$ the set of faces of $G$ that
are subsets of $U_{k}$. By the inclusion-maximality of the $c_{k}$ it follows
from Lemma 4.2 that $F(U_{i})\backslash F(U_{j})\neq\emptyset$, for all $i,j$.
Also, since the faces $U_{i}$ are of planar type it follows that outside
$U_{1}$ the sets $U_{i}$ and $U_{j}$ overlap in the sense that the
intersection of $U_{i}\backslash U_{1}$ and $U_{j}\backslash U_{1}$ is
nontrivial. Thus we have the following _overlapping property_ , illustrated in
Figure 5.

$(F(U_{i})\backslash F(U_{1}))\cap(F(U_{2})\backslash
F(U_{1}))\neq\emptyset,\quad\mbox{for all}\quad i\geq 3.$

By Lemma 4.4 the number of subsets of $F(U_{2})\backslash F(U_{1})$ has an
independent bound. Partitioning by these subsets we obtain a maximal set
${\mathcal{C}}_{1,2}$ with relabelled members such that the sets
$F(U_{k})\backslash F(U_{2})$ agree for all $k\geq 3$.

We can repeat this partitioning process which, by Lemma 4.4, must stop in a
finite number of steps with an independent bound. Thus, as in our preliminary
remarks preceding the lemma, it follows that the original finite sequence with
properties (i) and (ii) has an independent bound. Thus, by Lemma 4.4 the set
of critical walks in the equivalence class for $W_{1},W_{2}$ has an
independent bound. In the case of containment of 3 or more nontriangular faces
the argument is the same and the lemma follows. ∎

$c_{1}$$c_{2}$$c_{3}$$U_{3}$$U_{1}$$U_{2}$

Figure 5. The subwalks of $c_{2},c_{3}$ in the closure of $U_{1}$ coincide.
The interiors of $U_{2}\backslash U_{1}$ and $U_{3}\backslash U_{1}$ overlap.

For $G$ in ${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$ let
${\mathcal{M}}(G)$ be the connected compact topological space given by
deleting the nontriangular faces of $G$ from ${\mathcal{M}}$. In particular,
${\mathcal{M}}(G)$ need not be a surface with boundary in the classical sense
that the boundary consists of finitely many disjoint simple loops.

######  Lemma 4.6.

Let ${\mathcal{L}}$ be a set of loops in ${\mathcal{M}}(G)$, based at $v$,
with homotopy classes $[\gamma]_{{\mathcal{M}}(G)}$. Then the natural map
$\theta:[\gamma]_{{\mathcal{M}}(G)}\to[\gamma]_{\mathcal{M}}$ is finite-to-
one.

###### Proof.

Let $r$ be the number of open discs in ${\mathcal{M}}$ whose deletion gives
${\mathcal{M}}(G)$. If $r=1$ then the property is elementary and the general
case follows readily by induction. ∎

######  Lemma 4.7.

Let ${\mathcal{E}}$ be a family of disjoint loops based at $v$ that are
pairwise nonhomotopic in ${\mathcal{M}}(G)$. Then there is an independent
bound for ${\mathcal{E}}$.

###### Proof.

This is immediate from Theorem 2.2 and Lemma 4.6. ∎

Suppose that ${\mathcal{E}}_{3}$ is a family of essential 3-cycles of $G$
which are disjoint apart from a common base vertex $v$ that does not belong to
the boundary of ${\mathcal{M}}(G)$. Then $v$ has incident triangular faces
that form a triangulated disc in ${\mathcal{M}}(G)$. Contracting this closed
disc to the vertex $v$ gives a topological space, ${\mathcal{M}}(G)_{v}$ say,
and a family $\tilde{{\mathcal{E}}_{3}}$ of loops in ${\mathcal{M}}(G)_{v}$
which are disjoint except for a common base point, $v^{\prime}$ say. The space
${\mathcal{M}}(G)_{v}$ is evidently homeomorphic to ${\mathcal{M}}(G)$ if the
distance of $v$ to the boundary of ${\mathcal{M}}(G)$ is at least 2. In
general ${\mathcal{M}}(G)_{v}$ need not be homeomorphic to ${\mathcal{M}}(G)$
but it is also obtained from ${\mathcal{M}}$ by the deletion of a finite
family of disjoint open discs and Lemma 4.7 holds, with the same proof, with
${\mathcal{M}}(G)_{v}$ in place of ${\mathcal{M}}(G)$.

######  Lemma 4.8.

Let $G$, ${\mathcal{E}}_{3}$ and $\tilde{{\mathcal{E}}_{3}}$ be as above and
suppose that $G$ is contraction-minimal. Then there is an independent bound
for the size of ${\mathcal{E}}_{3}$.

###### Proof.

By the critical patch lemma, Lemma 3.7, it will be enough to show that there
is an independent bound for any subset, ${\mathcal{S}}_{3}$ say, of
${\mathcal{E}}_{3}$ consisting of pairwise nonhomotopic 3-cycles. In this case
the corresponding set of loops $\tilde{{\mathcal{S}}}_{3}$ are pairwise
nonhomotopic and so Lemma 4.7 completes the proof. ∎

The proof of the next proposition follows the proof scheme in Section 2 of the
Barnette-Edelson Theorem.

######  Proposition 4.9.

There is an independent bound on the number of essential 3-cycles in a
contraction minimal graph in ${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$.

###### Proof.

Assume that ${\mathcal{M}}$ has genus $g$ and is not the sphere or the
projective plane and that $G$ is a contraction minimal graph in
${\mathcal{G}}_{\rm pl}({\mathcal{M}},\alpha)$. By Lemma 4.5 there is an
independent bound for the number of vertices that lie on a critical walk. In
particular we may assume that there exists an essential 3-cycle $c$ and that
no vertex of $c$ lies on a boundary of ${\mathcal{M}}(G)$. For the induction
step of the proof assume that for all compact 2-manifolds
${\mathcal{M}}^{\prime}$ of genus less than $g$ there is an independent bound
for the number of vertices of a contraction-minimal embedded graph in
${\mathcal{G}}_{\rm pl}({\mathcal{M}}^{\prime},\alpha)$.

As in the proof of Theorem 1.1, cut and cap ${\mathcal{M}}$ by $c$ to create
the surface ${\mathcal{M}}_{1}$ (or pair
${\mathcal{M}}_{1},{\mathcal{M}}_{2}$) and the embedded graph $G_{1}$ (or pair
$G_{1},G_{2}$). Suppose that there is a single connected surface
${\mathcal{M}}_{1}$ with embedded graph $G_{1}$ and that $G$ is orientable.
Thus the freedom number $f(G)$ of $G$ is $\alpha$ and so $f(G_{1})=\alpha+6$.
The embedded graph $G_{1}$ in ${\mathcal{M}}_{1}$ is cellular and it satisfies
the planar girth inequalities since any critical walk $d$ for $G_{1}$ with
open disc face $U$ containing nontriangular faces of $G_{1}$ is also a
critical walk for $G$ for the same nontriangular faces as they appear in $G$.
Thus $G_{1}$ is in ${\mathcal{G}}_{\rm pl}({\mathcal{M}}_{1},\alpha+6)$.

If $e$ is an edge of $G_{1}$ that is not an edge of the two capping 3-cycles
and if $e$ is contractible, with $G_{1}/e$ in ${\mathcal{G}}_{\rm
pl}({\mathcal{M}}_{1},\alpha+6)$, then, as an edge of the contraction minimal
graph $G$ it must lie on an essential 3-cycle or critical walk that passes
through a vertex of $c$. The number of such critical walks has an independent
bound. To complete the proof of the proposition in this case it suffices to
show that the set ${\mathcal{E}}$ of essential 3-cycles of $G$ passing through
a vertex of $c$ has an independent bound. This follows from Lemma 4.8. The
nonorientable case follows in the same way. ∎

Lemma 4.5 and Proposition 4.9 complete the proof of Theorem 4.1 since every
edge of a contraction-minimal graph in ${\mathcal{G}}_{\rm
pl}({\mathcal{M}},\alpha)$ lies on an essential 3-cycle or a critical planar
type walk.

##  5\. Higher genus girth inequalities and (3,6)-tight graphs

In this section we show that a cellular graph $G$ in a (connected) compact
2-manifold ${\mathcal{M}}$ is (3,6)-tight if and only if it satisfies the
Maxwell count $3v-3=6$ and certain higher genus girth inequalities. We
conjecture that for any 2-manifold ${\mathcal{M}}$ there are finitely many
contraction-irreducible cellular $(3,6)$-tight embedded graphs. It seems
likely that this can be obtained, for example, from general genus versions of
the arguments in the previous section.

Let $G$ be an embedded simple graph in ${\mathcal{M}}$. Define a _superface_
of $G$ to be the face of a subgraph $K$ of $G$. Write $G_{U}$ for the subgraph
of $G$ containing the vertices and edges of $G$ that lie in the closure
$U^{-}$. With mild notational abuse write $G_{U}^{c}$ for the complementary
graph $G_{U^{c}}$, where $U^{c}={\mathcal{M}}\backslash U^{-}$. This is the
subgraph determined by the edges of $G$ that are disjoint from $U$. In
particular, $G=G_{U}\cup G_{U}^{c}$ and $G_{U}\cap G_{U}^{c}$ is the graph
$\partial U$ whose edges are the boundary edges of $U$. If $U$ is the only
face of $K$ then $K$ is $\partial U$ and $G_{U}=G,G_{U}^{c}=\partial U$.

######  Definition 5.1.

An ${\mathcal{M}}$-embedded simple graph $G$ with $f(G)=6$ satisfies the
_superface sparsity inequalities_ if $f(G_{U})\geq 6$ for all superfaces $U$
for which $\partial U$ has at least 3 vertices.

If $G$ has only one face then every subgraph also has one face and the
property of the previous definition is equivalent to the property of
$(3,6)$-tightness. On the other hand if $G$ is cellular then the set of
subgraphs $G_{U}$ provide a proper subcollection of the set of all subgraphs
of $G$.

The following theorem is due to Shakir [16] and it gives an insight into the
$(3,6)$-tightness of $G$. In fact it is the “no blocks case” of a more general
equivalence for the higher genus analogues of the block and hole graphs
described in the introduction.

######  Theorem 5.2.

Let $G$ be a embedded graph in the connected compact 2-manifold
${\mathcal{M}}$. Then the following are equivalent.

(i) $G$ is (3,6)-tight.

(ii) $G$ satisfies the superface sparsity inequalities and $f(G)=6$.

###### Proof.

That (i) implies (ii) is immediate. Suppose that (ii) holds and, by way of
contradiction, let $K$ be a maximal subgraph of $G$ with the properties that
$f(K)\leq 5$ and $K$ has at least 3 vertices. Let $U$ be a face of $K$. Since
$f(G)=f(G_{U})+f(G_{U}^{c})-f(\partial U)$ and $f(G)=6$ the condition
$f(G_{U})\geq 6$ is equivalent to $f(G_{U}^{c})-f(\partial U)\leq 0$. Thus,
since $K\cap G_{U}=\partial U$ we have

$f(K\cup G_{U})=f(K)+f(G_{U}^{c})-f(K\cap G_{U})\leq f(K).$

Thus $K=K\cup G_{U}$ by the maximality of $K$. Since this is true for all
faces $U$ of $K$ it follows that $K=G$, a contradiction. ∎

We next derive the connection between the superface sparsity inequalities and
higher genus girth inequalities for the boundary walks of superfaces, as given
in Lemma 5.7.

While ${\mathcal{G}}_{\rm pl}({\mathcal{M}},6)$ contains the family
${\mathcal{F}}({\mathcal{M}},6)$ of $(3,6)$-tight embedded graphs in
${\mathcal{M}}$ the families are distinct for higher genera manifolds, as we
noted in Section 3. In fact, by considering girth constraints for the boundary
walks of faces with limited genus we can identify intermediary families
between ${\mathcal{G}}_{\rm pl}({\mathcal{M}},6)$ and
${\mathcal{F}}({\mathcal{M}},6)$.

Let ${\mathcal{M}},G,K,U$ be as above with the simplification that $K$ is the
boundary graph $\partial U$ of $U$ and let $W$ be the complement of the
closure of $U$. Then ${\mathcal{M}}$ is the union of $U,K,W$. The quantity
$g_{r}({\mathcal{M}})$ in the addition formula of the next lemma is defined as
$g_{r}({\mathcal{M}})=g({\mathcal{M}})$, if ${\mathcal{M}}$ is oriented, and
$g_{r}({\mathcal{M}})=\frac{1}{2}g({\mathcal{M}})$ otherwise, and is known as
the _reduced genus_ of ${\mathcal{M}}$. The reduced genus $g_{r}(U)$ is
similarly defined.

When $\partial U$ is a union of pairwise disjoint cycles the closure $U^{-}$
of $U$ in ${\mathcal{M}}$ is a connected compact surface with boundary, say
${\mathcal{N}}_{U}$, with $s>0$ disjoint boundary cycles. The genus
$g({\mathcal{N}}_{U})$ may be defined as $g(U)$. Also this genus may be
defined in terms of any triangulation of ${\mathcal{N}}_{U}$ by means of the
Euler equation

$v-e+f=2-\mu g({\mathcal{N}}_{U})-s$

where $\mu=2$ (resp. $\mu=1$) if ${\mathcal{N}}_{U}$ is oriented (resp. not
oriented). Thus, in the oriented case
$g({\mathcal{N}}_{U})=g(U)=1-\frac{1}{2}(\chi+s)$ where $\chi=v-e+f$.

######  Lemma 5.3.

If the set of boundary walks of the face $U$ and the open set $W$ coincide and
consist of $s$ cycles then

$g_{r}({\mathcal{M}})=g_{r}(U)+g_{r}(W)+(s-1).$

###### Proof.

The hypotheses imply that $\partial U=\partial W$ and that ${\mathcal{M}}$ is
the join of ${\mathcal{N}}_{U}$ and ${\mathcal{N}}_{W}$ over their common
boundary cycles. The addition formula follows from direct calculation of the
genus values from a triangulation of ${\mathcal{M}}$ that includes the edges
of $\partial U$. ∎

With the notation of Lemma 2.1 we have $\mu
g({\mathcal{M}})=2g_{r}({\mathcal{M}})$, for both cases of $\mu$, and so Lemma
3.1 gives the following general formula for a cellular embedded graph $G$ in a
connected compact 2-manifold ${\mathcal{M}}$:

$\sum_{k}(k-3)f_{k}=6g_{r}({\mathcal{M}})+f(G)-6.$

Let $U$ be a superface of $G$ with triple $U,K,W$ as before, with $K=\partial
U$. Suppose first that that $W_{i}$ is a component of $W$ with boundary
consisting of disjoint cycles $d_{1},\dots,d_{t}$. Then we may consider the
compact 2-manifold, ${\mathcal{M}}_{W_{i}}$ say, obtained by attaching discs
to these cycles. Viewing $G_{W_{i}}$ as an embedded graph in
${\mathcal{M}}_{W_{i}}$ the previous formula gives

$\sum_{k}(|d_{k}|-3)+\sum_{k\in
I(W_{i})}(|c_{k}|-3)=6g_{r}({\mathcal{M}}_{W_{i}})+f(G_{W_{i}})-6$

where $I(W_{i})$ is the set of indices for the faces that lie in $W_{i}$. As
in Section 3, $c_{k}$ is a boundary walk of a face of the cellular graph $G$.
We refer to this equation as the _face walk equation_ for $G_{W_{i}}$.

In particular, if $W$ is connected and $\partial W$ is a union of disjoint
cycles then, recalling that $g_{r}({\mathcal{M}}_{W})=g_{r}(W)$, the face walk
equation for $W$ is

$\sum_{k}(|d_{k}|-3)+\sum_{k\in I(W)}(|c_{k}|-3)=6g_{r}(W)+f(G_{W})-6.$

######  Lemma 5.4.

Let $G$ be a cellular ${\mathcal{M}}$-embedded graph with $f(G)=6$ and let $U$
be a superface of $G$ for which $\partial U$ is the union of $s$ disjoint
cycles and for which the open set $W={\mathcal{M}}\backslash U^{-}$ is
connected and $\partial W=\partial U$. Then the following are equivalent.

(i) $f(G_{W})\geq 6$.

(ii)

$\sum_{k}(|d_{k}|-3)\geq\sum_{k\in I(U)}(|c_{k}|-3)-6(g_{r}(U)+s-1).$

where $d_{1},\dots,d_{s}$ are the common boundary cycles of $U$ and $W$.

###### Proof.

We have $f(G)=6$ and so Lemma 3.1 gives

$\sum_{k\in I(U)}(|c_{k}|-3)+\sum_{k\in
I(W)}(|c_{k}|-3)=6g_{r}({\mathcal{M}}).$

Subtracting this from the face walk equation for $G_{W}$ gives

$\sum_{k}(|d_{k}|-3)-\sum_{k\in
I(U)}(|c_{k}|-3)=6(g_{r}(W)-g_{r}({\mathcal{M}}))+f(G_{W})-6.$

By the addition formula we have

$g_{r}(W)-g_{r}({\mathcal{M}})=-(g_{r}(U)+(s-1))$

and so (ii) holds if and only if (i) holds. ∎

Consider now the case for which $W$ is connected but the boundary walks of $U$
and $W$ are not necessarily disjoint cycles. Perform vertex-splitting
operations on the vertices of each boundary walk $d_{k}$ of $\partial U$, for
$1\leq k\leq s$, to create the embedded graph $G^{\prime}$, containing $G$,
with a superface $U^{\prime}$ that is interior to $U$ and whose boundary
consists of cycles $d_{k}^{\prime}$ of length $|d_{k}|$, for $1\leq k\leq t$.
The boundary of $U^{\prime}$ consists of $s$ disjoint cycles and
$g_{r}(U^{\prime})=g_{r}(U)$. Let $W^{\prime}$ be the complement of the
closure of $U^{\prime}$ and define $g_{r}^{+}(W)$ to be $g_{r}(W^{\prime})$.
Since $\partial U^{\prime}=\partial W^{\prime}$, the addition formula of Lemma
5.3 gives

$g_{r}({\mathcal{M}})=g_{r}(U)+g_{r}^{+}(W)+s-1.$

Noting that $f(G_{W^{\prime}})=f(G_{W})$, Lemma 5.5 now gives the following
more general lemma.

######  Lemma 5.5.

Let $G$ be a cellular ${\mathcal{M}}$-embedded graph with $f(G)=6$ and let $U$
be a superface of $G$ with boundary walks $d_{1},\dots,d_{s}$ and for which
the open set $W={\mathcal{M}}\backslash U^{-}$ is connected. Then the
following are equivalent.

(i) $f(G_{W})\geq 6$.

(ii)

$\sum_{k}(|d_{k}|-3)\geq\sum_{k\in I(U)}(|c_{k}|-3)-6(g_{r}(U)+s-1).$

We refer to a superface $U$ with the property that $W={\mathcal{M}}\backslash
U^{-}$ is connected as a _balanced superface_ of $G$. Note that, as in the
example below, this does not imply that $U$ and $W$ have the same boundary.
Also we refer to the inequality in (ii) as the _higher genus girth inequality_
for the balanced superface $U$. Note that if $s=1$ and the genus of $U$ is
zero then this inequality coincides with the girth inequality for a planar
type closed walk as given in Section 3.

######  Example 5.6.

Consider a partially triangulated torus associated with an embedded graph $G$
as in Figure 6. Note that irrespective of the triangulation there is a
violation of the planar type girth inequalities since $|d_{1}|-3$ is less than
$|c_{1}|-3$. In fact a partial triangulation may be constructed so that the
boundary walk for the superface $U$ is the only planar type closed walk of
length 8 whose face contains the face $X$ of $G$. This illustrates the general
point that it can be necessary to consider closed walks other than cycles to
determine whether girth inequalities hold.

We can use this example to illustrate the previous lemma. vertex-splitting
moves on all the vertices of the boundary walk of $U$ create the embedded
graph $G^{\prime}\supset G$ with superface $U^{\prime}\subset U$. The
superfaces $U^{\prime}$ and
$W^{\prime}={\mathcal{M}}\backslash(U^{\prime})^{-}$ have coinciding
boundaries consisting of a single cycle, $d_{1}^{\prime}$ say, where
$|d_{1}^{\prime}|=|d_{1}|$. The higher genus girth inequality for $U$ is

$|d_{1}|-3\geq|c_{1}|-3-6(0+1-1),$

since $g_{r}(U)=g_{r}(U^{\prime})=0$, and so the inequality is false. Thus the
lemma implies that $f(G_{W})<6.$

XUW9

Figure 6. A partially triangulated torus with embedded graph $G$ with $f(G)=6$
and a single nontriangular face $X$ that is 9-sided. The superface $U$ of $G$
has a boundary walk $d_{1}$ of planar type with length $|d_{1}|=8$.

Suppose now that $U$ is merely a superface rather than a balanced superface so
that the complementary open set $W={\mathcal{M}}\backslash U^{-}$ has
components $W_{1},\dots,W_{\kappa}$, with $\kappa\geq 2$. We define the higher
genus girth inequality for $U$ by the same recipe. Repeating the arguments of
Lemma 5.5 leads to the fact that it is equivalent to the inequality
$\sum_{i=1}^{\kappa}f(G_{W_{i}})\geq 6\kappa$. We state this most general form
in the next lemma.

######  Lemma 5.7.

Let $G$ be a cellular ${\mathcal{M}}$-embedded graph with $f(G)=6$ and let $U$
be a superface of $G$ with boundary walks $d_{1},\dots,d_{s}$ and for which
the complement $W$ of $U^{-}$ has connected components
$W_{1},\dots,W_{\kappa}$. Then the following statements are equivalent.

(i) $\sum_{i=1}^{\kappa}f(G_{W_{i}})\geq 6\kappa$.

(ii) The superface $U$ satisfies the higher genus girth inequality

$\sum_{k=1}^{s}(|d_{k}|-3)\geq\sum_{k\in I(U)}(|c_{k}|-3)-6(g_{r}(U)+s-1).$

Let $\gamma$ be the genus of ${\mathcal{M}}$ and define the families

${\mathcal{G}}_{0}({\mathcal{M}},6)\supseteq{\mathcal{G}}_{1}({\mathcal{M}},6)\supseteq\dots\supseteq{\mathcal{G}}_{\gamma}({\mathcal{M}},6)$

where ${\mathcal{G}}_{k}({\mathcal{M}},6)$ consists of the
${\mathcal{M}}$-embedded cellular graphs with $f(G)=6$ that satisfy the higher
genus girth inequalities for superfaces $U$ with $g(U)\leq k.$

######  Theorem 5.8.

Let ${\mathcal{M}}$ be a connected compact 2-manifold with genus $\gamma$.
Then ${\mathcal{G}}_{\gamma}({\mathcal{M}},6)$ is equal to
${\mathcal{F}}({\mathcal{M}},6)$, the family of cellular embedded
$(3,6)$-tight graphs in ${\mathcal{M}}$.

###### Proof.

The inclusion
${\mathcal{F}}({\mathcal{M}},6)\subseteq{\mathcal{G}}_{\gamma}({\mathcal{M}},6)$
follows from Lemma 5.5 and the implication (i) implies (ii) of Theorem 5.2. On
the other hand let $G$ belong to ${\mathcal{G}}_{\gamma}({\mathcal{M}},6)$ and
let $U$ be a superface of $G$ with the associated decomposition
${\mathcal{M}}=U\cup K\cup W$, as above, with $K=\partial U$ and where $W$ has
components $W_{1},\dots,W_{\kappa}$. Each $W_{i}$ is a balanced superface of
$G$ with complementary open set equal to

$W_{i}^{\prime}=U\cup\bigcup_{j\neq i}W_{j}^{-}$

Since $W_{i}$ is a superface of $G$ it satisfies the higher genus girth
inequality and so, by
Lemma 5.5, $f(G_{W_{i}^{\prime}})\geq 6$ for each $i$. Since $G_{U}$ is equal
to the intersection of $G_{W_{i}^{\prime}}$ for $1\leq i\leq\kappa$, it
follows routinely that $f(G_{U})\geq 6$, as desired. ∎

######  Theorem 5.9.

For each connected compact 2-manifold ${\mathcal{M}}$ the family
$G_{0}({\mathcal{M}},6)$ coincides with $G_{\rm pl}({\mathcal{M}},6)$, and if
${\mathcal{M}}$ is the torus then

$G_{0}({\mathcal{M}},6)=G_{\rm
pl}({\mathcal{M}},6)={\mathcal{G}}_{1}({\mathcal{M}},6)={\mathcal{F}}({\mathcal{M}},6).$

###### Proof.

Let $G$ belongs to $G_{\rm pl}({\mathcal{M}},6)$ and let $U$ be a superface of
$G$ with a single boundary walk $d_{1}$ of planar type. Then $U$ is an open
disc with $g_{r}(U)=0$ and $s=1$ and so $g_{r}(U)+s-1=0$. Thus if $U$ is also
a balanced superface (with $U^{-}$ having connected complement) then the
planar type girth inequality for $d_{1}$ follows from the higher genus girth
inequality for $U$. In general the complement $W$ of $U^{-}$ has components
$W_{1},\dots,W_{\kappa}$. However, since $U$ has a single boundary walk the
vertex-splitting argument on boundary vertices of $U$ gives a superface
$U^{\prime}$ for the resulting graph $G^{\prime}$, with a boundary cycle,
$d_{1}^{\prime}$ say. From this it follows that the complementary open set
$W^{\prime}$ is connected. Since $U^{\prime}$ is thus a balanced superface of
$G^{\prime}$ the planar type girth inequality holds for $d_{1}^{\prime}$ and
therefore for $d_{1}$. Thus $G_{\rm
pl}({\mathcal{M}},6)\subseteq{\mathcal{G}}_{0}({\mathcal{M}},6)$.

Let $G$ belong to ${\mathcal{G}}_{0}({\mathcal{M}},6)$ and let $d_{1}$ be a
planar type walk in $G$ with face $U$. Suppose first that $d_{1}$ is a cycle.
Then $U$ is a balanced superface of $G$ and the higher genus girth inequality
holds for $U$. Since $g_{r}(U)=0$ and $s=1$ the girth inequality holds for
$d_{1}$ as a planar type closed walk. If $d_{1}$ is not a cycle then, once
again, by the vertex-splitting argument, obtain a cycle $d_{1}^{\prime}$ in
$G^{\prime}$ from $d_{1}$ in $G$ and conclude that the girth inequality holds
in general. Thus $G_{0}({\mathcal{M}},6)\subseteq G_{\rm
pl}({\mathcal{M}},6)$.

In view of the previous theorem it now suffices to show that if
${\mathcal{M}}$ is the torus then
${\mathcal{G}}_{0}({\mathcal{M}},6)\subseteq{\mathcal{G}}_{1}({\mathcal{M}},6)$.
Let $G$ belong ${\mathcal{G}}_{0}({\mathcal{M}},6)$ with superface $U$ and
suppose that $g_{r}(U)=1$. The desired higher genus inequality takes the form

$\sum_{k}(|d_{k}|-3)\geq\sum_{k\in I(U)}(|c_{k}|-3)-6s.$

where $d_{1},\dots,d_{s}$ are the boundary walks of $U$. However, this is
evident since $s\geq 1$ and for the torus, as noted in Section 3, we have
$\sum_{k}(|c_{k}|-3)=6$, since $f(G)=6$. On the other hand, if $g_{r}(U)=0$
then the higher genus girth inequality holds for $U$ since $G$ is in
${\mathcal{G}}_{0}({\mathcal{M}},6)$. ∎

###  5.1. Contraction minimal $(3,6)$-tight graphs

From the previous theorem and the main result of Section 4 it follows that
there are finitely many contraction-minimal $(3,6)$-tight cellular graphs for
the torus. In [7] it was shown that there are 2 such graphs that have a single
nontriangular face.

For the projective plane it was shown by direct methods, in Kastis and Power
[12], that there are 8 contraction-minimal (3,6)-tight cellular graphs and
these are shown below, where diametrically opposite vertices are identified.

Figure 7. The 8 contraction-minimal (3,6)-tight graphs for the projective
plane that contain an essential 3-cycle.

## References

  * [1] D. W. Barnette, Generating the triangulations of the projective plane, J. Comb. Theory 33 (1982), 222-230.
  * [2] D. W. Barnette and A. L. Edelson, All orientable 2-manifolds have finitely many minimal triangulations, Israel. J. Math., 62 (1988), 90-98.
  * [3] D. W. Barnette, and A.L. Edelson, All 2-manifolds have finitely many minimal triangulations, Israel J. Math., 67 (1989), 123-128.
  * [4] A. Boulch, E. C de Verdière and A. Nakamoto, Irreducible triangulations of surfaces with boundaries, Graphs and Combinatorics, 29 (2013), 1675-1688.
  * [5] J. Cruickshank, E. Kastis, D. Kitson and B. Schulze, Braced triangulations and rigidity, preprint (2021), arXiv:2107.03829.
  * [6] J. Cruickshank, D. Kitson and S.C. Power, The generic rigidity of triangulated spheres with blocks and holes, J. Combin. Theory Ser. B 122 (2017), 550-577.
  * [7] J. Cruickshank, D. Kitson and S.C. Power, The rigidity of a partially triangulated torus, Proc. London Math. Soc., 2018, https://doi.org/10.1112/plms.12215
  * [8] W. Finbow-Singh and W. Whiteley, Isostatic block and hole frameworks, SIAM J. Discrete Math. 27 (2013), 991-1020.
  * [9] J. L Gross and T. W. Tucker, _Topological graph theory_ , Dover, New York, 2001.
  * [10] T. Jordán, Rigid block and hole graphs with a single block, Discrete Mathematics, 272 Volume 346, 2023.
  * [11] T. Jordán and S. Tanigawa, Global rigidity of triangulations with braces, J. of Comb. Theory, Ser. B, 136 (2019), 249-288.
  * [12] E. Kastis and S. C. Power, Projective plane graphs and 3-rigidity, arxiv.org arXiv:2003.05514.
  * [13] D. Kitson and S. C. Power, The Rigidity of Infinite Graphs II. Graphs and Combinatorics 38, 83 (2022). https://doi.org/10.1007/s00373-022-02486-y
  * [14] A. Malnic̃ and R. Nedela, $k$-minimal triangulations of surfaces, Acta Math. Univ. Comenianae, 64 (1995), 57-76.
  * [15] B. Mohar and C. Thomassen, _Graphs on surfaces_ , Johns Hopkins University, 2001.
  * [16] Q. Shakir, Notes for the talk, _Sparsity of surface facegraphs_ given at the workshop on Graph Rigidity and Applications, Lancaster University, April 2023.
  * [17] W. Whiteley, Vertex splitting in isostatic frameworks, Structural Topology, 16 (1990), 23-30.


$\text{Tamari}(B_{n})$, $\text{Camb}_{\text{bi}}(A_{n})$, and
$J(\Phi_{B_{n}}^{+})$ are open even when we specialize $q=1$.

$\begin{array}[]{|c|c|c|c|}\hline\cr\text{Type}&|W|&\mathsf{Pop}(\mathrm{Weak}(W);1)&\mathsf{Pop}(\mathrm{Weak}(W);q)\\\
\hline\cr A_{2}&6&3&q^{2}+2q\\\ A_{3}&24&11&q^{3}+8q^{2}+2q\\\
A_{4}&120&49&q^{4}+22q^{3}+26q^{2}\\\
A_{5}&720&263&q^{5}+52q^{4}+168q^{3}+42q^{2}\\\
A_{6}&5040&1653&q^{6}+114q^{5}+804q^{4}+692q^{3}+42q^{2}\\\
A_{7}&40320&11877&q^{7}+240q^{6}+3270q^{5}+6500q^{4}+1866q^{3}\\\
\cdots&\cdots&\cdots&\cdots\\\ A_{n}&n!&\href
https://oeis.org/A307030&\text{unknown}\\\ \hline\cr B_{2}&8&5&q^{2}+4q\\\
B_{3}&48&27&q^{3}+20q^{2}+6q\\\ B_{4}&384&191&q^{4}+72q^{3}+118q^{2}\\\
B_{5}&3840&1719&q^{5}+232q^{4}+1136q^{3}+350q^{2}\\\
B_{6}&46080&18585&q^{6}+716q^{5}+8236q^{4}+9032q^{3}+600q^{2}\\\
B_{7}&645120&233857&q^{7}+2172q^{6}+51666q^{5}+135092q^{4}+44926q^{3}\\\
\cdots&\cdots&\cdots&\cdots\\\ B_{n}&2^{n}n!&\text{unknown}&\text{unknown}\\\
\hline\cr D_{3}&24&11&q^{3}+8q^{2}+2q\\\
D_{4}&192&81&q^{4}+40q^{3}+30q^{2}+10q\\\
D_{5}&1920&693&q^{5}+152q^{4}+400q^{3}+140q^{2}\\\
D_{6}&23040&7421&q^{6}+524q^{5}+3692q^{4}+2650q^{3}+554q^{2}\\\
D_{7}&322560&93611&q^{7}+1724q^{6}+27410q^{5}+46162q^{4}+16606q^{3}+1708q^{2}\\\
\cdots&\cdots&\cdots&\cdots\\\
D_{n}&2^{n-1}n!&\text{unknown}&\text{unknown}\\\ \hline\cr
E_{6}&51840&15971&q^{6}+1266q^{5}+7510q^{4}+7194q^{3}\\\ \hline\cr
F_{4}&1152&551&q^{4}+232q^{3}+318q^{2}\\\ \hline\cr
I_{2}(m)&2m&2m-3&q^{2}+(2m-4)q\\\ \hline\cr H_{3}&120&75&q^{3}+56q^{2}+18q\\\
\hline\cr H_{4}&14400&7919&q^{4}+2632q^{3}+5286q^{2}\\\ \hline\cr\end{array}$
Figure 12. Some data for $\mathsf{Pop}(\mathrm{Weak}(W);q)$, where
$\mathrm{Weak}(W)$ is the weak order on the finite Coxeter group $W$ (we did
not compute the data for $E_{7}$ and $E_{8}$). As stated in Conjecture 11.2,
the coefficient of $q^{n-1}$ in $\mathsf{Pop}(\mathrm{Weak}(B_{n});q)$ appears
to be $3^{n}-2n-1$.
$\begin{array}[]{|c|c|c|c|}\hline\cr\text{Type}&\mathrm{Cat}(W)&\mathsf{Pop}(\mathrm{Tamari}(W);1)&\mathsf{Pop}(\mathrm{Tamari}(W);q)\\\
\hline\cr A_{1}&2&1&q\\\ A_{2}&5&2&q^{2}+q\\\ A_{3}&14&4&q^{3}+3q^{2}\\\
A_{4}&42&9&q^{4}+6q^{3}+2q^{2}\\\ A_{5}&132&21&q^{5}+10q^{4}+10q^{3}\\\
A_{6}&429&51&q^{6}+15q^{5}+30q^{4}+5q^{3}\\\ \cdots&\cdots&\cdots&\cdots\\\
A_{n}&\href https://oeis.org/A000108&\href https://oeis.org/A001006\text{
(conj.)}&\href https://oeis.org/A0055151\text{ (conj.)}\\\ \hline\cr
B_{2}&6&3&q^{2}+2q\\\ B_{3}&20&8&q^{3}+6q^{2}+2q\\\
B_{4}&70&22&q^{4}+12q^{3}+9q^{2}\\\
B_{5}&252&61&q^{5}+20q^{4}+36q^{3}+4q^{2}\\\
B_{6}&924&171&q^{6}+30q^{5}+100q^{4}+40q^{3}\\\ \cdots&\cdots&\cdots&\cdots\\\
B_{n}&\href https://oeis.org/A000984&\href https://oeis.org/A025566\text{
(conj.)}&\sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-1}{k}\binom{n+1-k}{k}q^{n-k}\text{
(conj.)}\\\ \hline\cr\end{array}$ Figure 13. Some data supporting Conjecture
11.2 for $\mathsf{Pop}(\mathrm{Tamari}(W);q)$ for Cambrian lattices coming
from linearly-oriented Coxeter elements of types $A$ and $B$.

$\begin{array}[]{|c|c|c|c|c|c|}\hline\cr\text{Type}&\mathrm{Cat}(W)&\mathsf{Pop}(\mathrm{Camb}_{\mathrm{bi}}(W);1)&\mathsf{Pop}(\mathrm{Camb}_{\mathrm{bi}}(W);q)&\mathsf{Pop}(J(\Phi^{+}_{W});1)&\mathsf{Pop}(J(\Phi^{+}_{W});q)\\\
\hline\cr A_{1}&2&1&q&1&q\\\ A_{2}&5&2&q^{2}+q&2&q^{2}+q\\\
A_{3}&14&5&q^{3}+3q^{2}+q&5&q^{3}+3q^{2}+q\\\
A_{4}&42&12&q^{4}+6q^{3}+5q^{2}&13&q^{4}+6q^{3}+5q^{2}+q\\\
A_{5}&132&29&q^{5}+10q^{4}+16q^{3}+2q^{2}&35&q^{5}+10q^{4}+16q^{3}+7q^{2}+q\\\
A_{6}&429&72&q^{6}+15q^{5}+40q^{4}+16q^{3}&97&q^{6}+15q^{5}+40q^{4}+31q^{3}+9q^{2}+q\\\
\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\\ A_{n}&\href
https://oeis.org/A000108&\href https://oeis.org/A089372\text{ (conj.)}&\text{
see \lx@cref{creftypecap~refnum}{conj:enumerations}}&\begin{subarray}{c}\href
https://oeis.org/A082582\\\ \href https://oeis.org/A086581\\\ \href
https://oeis.org/A025242\end{subarray}&\href https://oeis.org/A145904\text{
(conj.)}\\\ \hline\cr B_{2}&6&3&q^{2}+2q&3&q^{2}+2q\\\
B_{3}&20&9&q^{3}+6q^{2}+2q&9&q^{3}+6q^{2}+2q\\\
B_{4}&70&25&q^{4}+12q^{3}+12q^{2}&27&q^{4}+12q^{3}+12q^{2}+2q\\\
B_{5}&252&69&q^{5}+20q^{4}+42q^{3}+6q^{2}&83&q^{5}+20q^{4}+42q^{3}+18q^{2}+2q\\\
B_{6}&924&193&q^{6}+30q^{5}+110q^{4}+52q^{3}&259&q^{6}+30q^{5}+110q^{4}+92q^{3}+24q^{2}+2q\\\
\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\\ B_{n}&\href
https://oeis.org/A000984&\text{unknown}&\text{unknown}&\href
https://oeis.org/A171155\text{ (conj.)}&\href https://oeis.org/A103881\text{
(conj.)}\\\ \hline\cr D_{3}&14&5&q^{3}+3q^{2}+q&5&q^{3}+3q^{2}+q,\\\
D_{4}&50&17&q^{4}+8q^{3}+6q^{2}+2q&17&q^{4}+8q^{3}+6q^{2}+2q\\\
D_{5}&182&47&q^{5}+15q^{4}+23q^{3}+8q^{2}&53&q^{5}+15q^{4}+24q^{3}+11q^{2}+2q\\\
D_{6}&672&131&q^{6}+24q^{5}+67q^{4}+33q^{3}+6q^{2}&167&q^{6}+24q^{5}+70q^{4}+54q^{3}+16q^{2}+2q\\\
\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\\ D_{n}&\href
https://oeis.org/A051924&\text{unknown}&\text{unknown}&\text{unknown}&\text{unknown}\\\
\hline\cr
E_{6}&833&164&q^{6}+30q^{5}+82q^{4}+51q^{3}&210&q^{6}+30q^{5}+89q^{4}+69q^{3}+18q^{2}+3q\\\
\hline\cr
E_{7}&4160&624&q^{7}+56q^{6}+260q^{5}+261q^{4}+46q^{3}&912&q^{7}+56q^{6}+285q^{5}+367q^{4}+166q^{3}+33q^{2}+4q\\\
\hline\cr
E_{8}&25080&2853&q^{8}+112q^{7}+840q^{6}+1344q^{5}+556q^{4}&4787&q^{8}+112q^{7}+926q^{6}+1880q^{5}+1367q^{4}+428q^{3}+67q^{2}+6q\\\
\hline\cr F_{4}&105&40&q^{4}+20q^{3}+19q^{2}&44&q^{4}+20q^{3}+19q^{2}+4q\\\
\hline\cr I_{2}(m)&m+2&m-1&q^{2}+(m-2)q&m-1&q^{2}+(m-2)q\\\ \hline\cr
H_{3}&32&17&q^{3}+12q^{2}+4q&17&q^{3}+12q^{2}+4q\\\ \hline\cr
H_{4}&280&125&q^{4}+56q^{3}+68q^{2}&&\\\ \hline\cr\end{array}$ Figure 14. Some
data supporting Conjecture 11.2 for
$\mathsf{Pop}(\mathrm{Camb}_{\mathrm{bi}}(W);q)$ and
$\mathsf{Pop}(J(\Phi^{+}_{W});q)$, where $\mathrm{Camb}_{\mathrm{bi}}(W)$ is a
Cambrian lattice for a bipartite Coxeter element and $J(\Phi^{+}_{W})$ is the
distributive lattice of order ideals of the positive root poset of type $W$
(nonnesting partitions). For the noncrystallographic types $I_{2}(m)$ and
$H_{3}$, Armstrong’s root posets are used for the nonnesting partitions
[Arm09, Figure 5.15].

###  11.3. Uniquely completely paired lattices

Let $L$ be a lattice. Note that if $j\in\mathcal{J}_{L}$ and
$m\in\mathcal{M}_{L}$, then we have $\mathsf{Pop}^{\downarrow}_{L}(j)=j_{*}$
and $\mathsf{Pop}^{\uparrow}_{L}(m)=m^{*}$, so the sets $\mathcal{M}_{L}(j)$
and $\mathcal{J}_{L}(m)$ defined in Section 3.1 satisfy
$\mathcal{M}_{L}(j)=\max\\{z\in L:\mathsf{Pop}^{\downarrow}_{L}(j)=j\wedge
z\\}$ and $\mathcal{J}_{L}(m)=\min\\{z\in
L:\mathsf{Pop}^{\uparrow}_{L}(j)=j\vee z\\}$. It is reasonable to extend the
notion of _uniquely paired_ in Definition 3.2 to every element of $L$ as
follows.

######  Definition 11.3.

A lattice $L$ is _completely uniquely paired_ if there is a unique bijection
$\lambda:L\to L$ so that $\lambda(x)\in\max\\{z\in
L:\mathsf{Pop}^{\downarrow}_{L}(x)=x\wedge z\\}$ and
$\lambda^{-1}(x)\in\min\\{z\in L:\mathsf{Pop}^{\uparrow}_{L}(x)=x\vee z\\}$
for every $x\in L$.

By Theorem 9.3, if $L$ is both semidistrim and completely uniquely paired,
then the bijection $\lambda$ must be rowmotion—and so it makes sense to use
the name _rowmotion_ for the bijection $\lambda$ in a completely uniquely
paired lattice. While completely uniquely paired lattices have some desired
properties, they generally lack others common to semidistributive and trim
lattices—for example, not all completely uniquely paired lattices have join-
prime elements, which are a major tool for dealing with semidistrim lattices.
Figure 15 illustrates a completely uniquely paired lattice that does not have
a join-prime or meet-prime element. While not every completely uniquely paired
lattice is semidistrim, we expect the converse should hold.

######  Conjecture 11.4.

Every semidistrim lattice is completely uniquely paired.

Figure 15. A uniquely completely paired lattice with no join-prime or meet-
prime elements. See also Figure 8.

###  11.4. Core label orders

In this section, we closely follow the ideas of [M1̈9] in the setting of our
semidistrim lattices. For $L$ a semidistrim lattice and $b\in L$, write

$\mathrm{Shard}_{\mathsf{Pop}}(b)=J_{L}(b)\cap
M_{L}(\mathsf{Pop}^{\downarrow}_{L}(b)),$

so that $\mathrm{Shard}_{\mathsf{Pop}}(b)$ is the set of join-irreducibles
that label the cover relations in the interval $\mathrm{Face}(b)$ (by
Corollary 7.9 and Corollary 7.10). It is reasonable to think of the set
$\mathrm{Shard}_{\mathsf{Pop}}(b)$ as an extension of the edge labeling to
faces, since when $j\in\mathcal{J}_{L}$ with the cover $j_{*}\lessdot j$
labeled by $j$ itself, we recover $\mathrm{Shard}(j)=\\{j\\}$. Similarly, we
define

$\mathrm{Shard}_{\mathsf{Row}}(b)=J_{L}(b)\cap M_{L}(\mathsf{Row}_{L}(b)).$

By Proposition 9.5, we have that
$\mathrm{Shard}_{\mathsf{Row}}(b)\subseteq\mathrm{Shard}_{\mathsf{Pop}}(b)$.

######  Question 11.5.

For which semidistrim lattices $L$ do we have
$\mathrm{Shard}_{\mathsf{Row}}(b)=\mathrm{Shard}_{\mathsf{Pop}}(b)$ for all
$b\in L$? Does this hold when $L$ is the lattice of regions of a real
simplicial hyperplane arrangement?

Define the _pop-core label order_ to be the partial order
$\preceq_{\mathsf{Pop}}$ on $L$ given by $x\preceq_{\mathsf{Pop}}y$ if and
only if
$\mathrm{Shard}_{\mathsf{Pop}}(x)\subseteq\mathrm{Shard}_{\mathsf{Pop}}(y)$.
This definition extends Mühle’s definition of the _core label order_ [M1̈9],
which was formulated as a generalization of Reading’s _shard intersection
order_ [Rea11]. Define the _row-core label order_ by
$x\preceq_{\mathsf{Row}}y$ if and only if
$\mathrm{Shard}_{\mathsf{Row}}(x)\subseteq\mathrm{Shard}_{\mathsf{Row}}(y)$.
In general, we do not have that
$\preceq_{\mathsf{Pop}}=\preceq_{\mathsf{Row}}$—[M1̈9, Figure 7] gives an
example for which $\preceq_{\mathsf{Pop}}$ is not a lattice but
$\preceq_{\mathsf{Row}}$ is a lattice.

It would be interesting to see what properties one can say about the row-core
label orders of semidistrim lattices. In particular, we have the following
question.

######  Question 11.6.

When is the pop-core or row-core label order on a semidistrim lattice a meet-
semilattice?

In order to approach the preceding question, it could be useful to understand
graph-theoretically what the sets $\mathrm{Shard}_{\mathsf{Pop}}(b)$ and/or
$\mathrm{Shard}_{\mathsf{Row}}(b)$ are when we view them as subsets of the
vertex set of the Galois graph. For example, when $L$ is distributive, the
pop-core label order and the row-core label order are equal to each other, and
each is a meet-semilattice because

$\\{\mathrm{Shard}_{\mathsf{Pop}}(b):b\in
L\\}=\\{\mathrm{Shard}_{\mathsf{Row}}(b):b\in L\\}=\mathrm{Ind}(G_{L}).$

## Acknowledgements

N.W. was partially supported by a Simons Foundation Collaboration Grant. C.D.
was supported by a Fannie and John Hertz Foundation Fellowship and an NSF
Graduate Research Fellowship (grant number DGE-1656466). We thank Henri Mühle
for useful correspondence. This work benefited from computations in Sage
[The21] and the combinatorics features developed by the Sage-Combinat
community [SCc08].

## References

  * [ABB+19] A Asinowski, C. Banderier, S. Billey, B. Hackl, and S. Linusson, _Pop-stack sorting and its image: permutations with overlapping runs_ , Acta. Math. Univ. Comenian. 88 (2019), 395–402.
  * [ABH21] A Asinowski, C. Banderier, and B. Hackl, _Flip-sort and combinatorial aspects of pop-stack sorting_ , Discrete Math. Theor. Comput. Sci. 22 (2021).
  * [AHLN18] K. Adaricheva, J. Hyndman, S. Lempp, and J. B. Nation, _Interval dismantlable lattices_ , Order 35 (2018), 133–137.
  * [Arm09] D. Armstrong, _Generalized noncrossing partitions and combinatorics of Coxeter groups_ , vol. 202, American Mathematical Society, 2009.
  * [Bar19] E. Barnard, _The canonical join complex_ , Electron. J. Combin. 26 (2019).
  * [Bjö95] A. Björner, _Topological methods in combinatorics, handbook of combinatorics_ , vol. 2, Elsevier, Amsterdam, 1995.
  * [BR18] E. Barnard and N. Reading, _Coxeter-bicatalan combinatorics_ , J. Algebraic Combin. 47 (2018), 241–300.
  * [BS74] A. Brouwer and A. Schrijver, _On the period of an operator defined on antichains_ , Math. Centr. report ZW24 (1974), 1–13.
  * [CFdF95] P. J. Cameron and D. G. Fon-der Flaass, _Orbits of antichains revisited_ , European J. Combin. 16 (1995), 545–554.
  * [CG19] A. Claesson and B. Á. Guðmundsson, _Enumerating permutations sortable by $k$ passes through a pop-stack_, Adv. Appl. Math. 108 (2019), 79–96.
  * [CGP19] A. Claesson, B. Á Guðmundsson, and J. Pantone, _Counting pop-stacked permutations in polynomial time_ , arXiv preprint arXiv:1908.08910 (2019).
  * [Def21a] C. Defant, _Meeting covered elements in $\nu$-Tamari lattices_, Adv. Appl. Math. (2021), To appear.
  * [Def21b] by same author, _Pop-stack-sorting for Coxeter groups_ , arXiv preprint arXiv:2104.02675 (2021).
  * [DHMP21] A. Dermenjian, C. Hohlweg, T. McConville, and V. Pilaud, _The facial weak order on hyperplane arrangements_ , Discrete Comput. Geom. (2021).
  * [DIR+17] L. Demonet, O. Iyama, N. Reading, I. Reiten, and H. Thomas, _Lattice theory of torsion classes_ , arXiv preprint arXiv:1711.01785 (2017).
  * [DW21a] C. Defant and N. Williams, _Coxeter pop-tsack torsing_ , arXiv preprint arXiv:2106.05471 (2021).
  * [DW21b] by same author, _Crystal pop-stack sorting and type A crystal lattices_ , arXiv preprint arXiv:2109.08251 (2021).
  * [EG21] M. Elder and Y. K. Goh, _$k$ -pop stack sortable permutations and $2$-avoidance_, Electron. J. Combin. 28 (2021).
  * [FJN95] R. Freese, J. Ježek, and J. B. Nation, _Free Lattices_ , American Mathematical Society, Providence, 1995.
  * [GH13] W. Goddard and M. A. Henning, _Independent domination in graphs: A survey and recent results_ , Discrete Math. 313 (2013), 839–854.
  * [GM19] A. Garver and T. McConville, _Lattice properties of oriented exchange graphs and torsion classes_ , Algebr. Represent. Theory 22 (2019), 43–78.
  * [GN81] H. S. Gaskill and J. B. Nation, _Join-prime elements in semidistributive lattices_ , Algebra Universalis 12 (1981), 352–359.
  * [Liu99] L. S-C. Liu, _Left-modular elements and edge labelings_ , Ph.D. thesis, 1999\.
  * [M1̈9] H. Mühle, _The core label order of a congruence-uniform lattice_ , Algebra Universalis 80 (2019).
  * [Mar92] G. Markowsky, _Primes, irreducibles and extremal lattices_ , Order 9 (1992), 265–290.
  * [McC17a] T. McConville, _Crosscut-simplicial lattices_ , Order 34 (2017), 465–477.
  * [McC17b] T. McConville, _Lattice structure of Grid-Tamari orders_ , J. Combin. Theory Ser. A 148 (2017), 27–56.
  * [PRV17] L.-F. Préville-Ratelle and X. Viennot, _An extension of Tamari lattices_ , Trans. Amer. Math. Soc. 369 (2017), 5219–5239.
  * [PS19] L. Pudwell and R. Smith, _Two-stack-sorting with pop stacks_ , Australas. J. Combin. 74 (2019), 179–195.
  * [Rea06] N. Reading, _Cambrian lattices_ , Adv. Math. 205 (2006), 313–353.
  * [Rea07] by same author, _Sortable elements and Cambrian lattices_ , Algebra Universalis 56 (2007), 411–437.
  * [Rea11] Nathan Reading, _Noncrossing partitions and the shard intersection order_ , J. Algebraic Combin. 33 (2011), no. 4, 483–530.
  * [Rea16] by same author, _Lattice theory of the poset of regions_ , Lattice theory: special topics and applications, Springer, 2016, pp. 399–487.
  * [RST21] N. Reading, D. E. Speyer, and H. Thomas, _The fundamental theorem of finite semidistributive lattices_ , Selecta Math. 27 (2021).
  * [SCc08] The Sage-Combinat community, _Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics_ , 2008, http://combinat.sagemath.org.
  * [Sta11] R. P. Stanley, _Enumerative Combinatorics_ , 2 ed., vol. 1, Cambridge University Press, Cambridge, 2011.
  * [Str18] J. Striker, _Rowmotion and generalized toggle groups_ , Discrete Math. Theor. Comput. Sci. 20 (2018).
  * [STT06] A. Sapounakis, I. Tasoulas, and P. Tsikouras, _On the dominance partial ordering on Dyck paths_ , J. Integer Seq. 9 (2006).
  * [SW12] J. Striker and N. Williams, _Promotion and rowmotion_ , European Journal of Combinatorics 33 (2012), no. 8, 1919–1942.
  * [The21] The Sage Developers, _Sagemath, the Sage Mathematics Software System (Version 9.4)_ , 2021, https://www.sagemath.org.
  * [Tho06] H. Thomas, _An analogue of distributivity for ungraded lattices_ , Order 23 (2006), 249–269.
  * [TW19a] H. Thomas and N. Williams, _Independence posets_ , J. Comb. 10 (2019), 545–578.
  * [TW19b] by same author, _Rowmotion in slow motion_ , Proc. Lond. Math. Soc. 119 (2019), 1149–1178.