Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Abstract

How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart). Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993), a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions. Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length $O(g^{3/2}n^{1/2})$ for any triangulated combinatorial surface of genus $g$ with $n$ triangles, and describe an $O(gn)$-time algorithm to compute such a decomposition. Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations.

Appendices

Appendix 1: Discrete Systolic Inequalities in Higher Dimensions

In this appendix, we show that the proofs from Sect. 3 extend almost verbatim to higher dimensions. In the following discussion $(M,T)$ will be a triangulated $d$-manifold.¹ We will denote by $f_d(T)$ the number of $d$-dimensional simplices of $T$ and by $f_0(T)$ the number of vertices. The main difference with the two-dimensional case is that while for surfaces, discrete systolic inequalities in terms of $f_0$ and in terms of $f_d$ are easily seen to be equivalent (by Euler’s formula and double-counting), in higher dimensions the situation is more complicated.

We consider the supremal values of the functionals $\frac{\text {sys}^d}{f_d}$ and $\frac{\text {sys}^d}{f_0}$, where $\text {sys}$ denotes the length of a shortest closed curve in the $1$-skeleton of $(M,T)$ that is non-contractible on the manifold $M$. In particular, we focus on when these quantities are bounded from above. As we surveyed in the introduction, the two-dimensional case of this problem has been studied by topological graph theorists and computational topologists; however, as far as we know, it has never been considered in dimension higher than two in the past. We report the results and open problems that we can derive by generalizing our techniques for surfaces.

1.1 From Continuous to Discrete Systolic Inequalities

To infer discrete systolic inequalities from the Riemannian ones, the obvious approach is, as before, to start with a triangulated manifold $(M,T)$ and to endow $M$ with a metric $m_T$ by deciding that each simplex of $T$ is a regular Euclidean simplex of volume one. (Since the simplices are regular, we glue them by facewise isometries.) Hence, length and volume are naturally defined via the restriction to each Euclidean simplex. Following Gromov [26], we will call such a metric a piecewise Riemannian metric. Unlike the 2-dimensional case, however, foundational work of Kervaire [36] shows that in higher dimensions such a triangulated manifold is not always smoothable. (We will show how to circumvent this difficulty below.)

Theorem 6.1

There exists a constant $C_d$, such that for every triangulated compact manifold $(M,T)$ without boundary of dimension $d$, there exists a piecewise Riemannian metric $m$ on $M$ with volume $f_d(T)$ such that, for every closed curve $\gamma$ in $M$, there exists a homotopic closed curve $\gamma '$ on the $1$-skeleton $G$ of $T$ with

$$\begin{aligned} |\gamma '|_{G}\le C_d |\gamma |_m. \end{aligned}$$

The proof works inductively, pushing curves from the $i$-dimensional skeleton to the $(i-1)$-dimensional one. We start with the following lemma.

Lemma 6.1

Let $\Delta$ be an $i$-dimensional regular simplex, endowed with the Euclidean metric. There exists an absolute constant $C'_i$ such that, for each arc $\gamma$ properly embedded in $\Delta$ with endpoints in $\partial \Delta$, there exists an arc $\gamma '$ embedded on $\partial \Delta$, with the same endpoints as $\gamma$, such that $|\gamma '| \le C'_i|\gamma |$.

Proof of Lemma 6.1

Since the statement of the lemma is invariant by scaling all the distances, we can assume that $\Delta$ is the regular $i$-simplex whose circumscribing sphere bounds the unit ball $B$ in $\mathbb {R}^i$. Let us first consider the bijection $\varphi$ that maps $\Delta$ to $B$ by radial projection (such that the restriction of $\varphi$ to any ray from the origin is a linear function). It is not hard to see that there is a constant $C''_i$ such that, for any arc $\gamma$ in $\Delta$, we have $|\gamma |/{C''_i}\le |\varphi (\gamma )|\le C''_i|\gamma |$ (one can compute the optimal $C''_i$ by writing the map in hyperspherical coordinates and computing the differential).

Therefore, it suffices to prove the lemma for the unit ball $B$ instead of the regular simplex $\Delta$. Let $\beta$ be an arc embedded in $B$. Let $\beta '$ be a shortest geodesic arc on $\partial B$ with the same endpoints as $\beta$. Then we have $|\beta '|\le \frac{\pi }{2}|\beta |$, which proves the result. $\square$

Proof of Theorem 6.1

As we mentioned before, we endow $M$ with the piecewise Riemannian metric obtained by endowing each simplex of dimension $d$ with the geometry of the regular Euclidean simplex of volume $1$. Then, using Lemma 6.1, for every arc $A$ of $\gamma$ in every $d$-simplex, we push $A$ to the ($d-1$)-skeleton of $(M,T)$, and we repeat this procedure inductively until $\gamma$ is embedded in the $1$-skeleton. In the end, the length of $\gamma '$ has increased by at most a multiplicative factor that depends only on $d$. $\square$

The Riemannian systolic inequality in higher dimensions is now stated in the following theorem.

Theorem 6.2

(Gromov [26]) For every $d$, there is a constant $C_d$ such that, for any Riemannian metric $m$ on any essential compact $d$-manifold $M$ without boundary, there exists a non-contractible closed curve of length at most $C_d{{\mathrm{vol}}}(m)^{1/d}$.

For a definition of essential manifold, see [26]. The prime examples of essential manifolds are the so-called aspherical manifolds, which are the manifolds whose universal cover is contractible. These include the $d$-dimensional torus for every $d$, or manifolds that accept a hyperbolic metric and, more generally, manifolds that are locally CAT(0). In particular, all surfaces except the $2$-sphere and the projective plane are aspherical. On the other hand, real projective spaces and lens spaces are examples of essential manifolds that are non-aspherical.

Theorem 6.2 also holds for piecewise Riemannian metrics. Indeed, its proof revolves around two key inequalities: the filling-radius volume inequality and a systole–filling radius inequality. The former relies on a coarea formula which holds for piecewise Riemannian metrics (see [26], Lemma 4.2b]), and the proof of the latter uses no smoothness property either, see [26], pp. 9 and 10]. As a corollary of this refinement to piecewise Riemannian metrics and of our Theorem 6.1, we obtain the following result relating the length of systoles and the number of facets.

Corollary 6.1

Let $(M,T)$ be a triangulated essential compact $d$-manifold without boundary. Then, for some constant $c_d$ depending only on $d$, some non-contractible closed curve in the $1$-skeleton of $T$ has length at most $c_df_d(T)^{1/d}$.

1.2 From Discrete to Continuous Systolic Inequalities

We now turn our attention to the other direction, namely, transforming a discrete systolic inequality into a continuous one.

Theorem 6.3

Let $M$ be a compact Riemannian manifold of dimension $d$ and volume $V$ without boundary, and let $\delta >0$. For infinitely many values of $f_0$, there exists a triangulation $(M,T)$ of $M$ with $f_0$ vertices such that every closed curve $\gamma$ in the $1$-skeleton $G$ of $M$ satisfies

$$\begin{aligned} |\gamma |_m\le (1+\delta )\frac{10}{\sqrt{\pi }}\varGamma (d/2+1)^{1/d} \left( \frac{V}{f_0} \right) ^{1/d} |\gamma |_G. \end{aligned}$$

(Here, $\varGamma$ is the usual Gamma function.) The proof follows the same idea as the proof of Theorem 3.2. We start with the centers of a maximal set of disjoint balls of radius $\varepsilon /2$ in $M$ and want to compute the Delaunay triangulation associated to it, with the hope that if $\varepsilon$ is small enough, we will obtain a triangulation of $M$. However, Delaunay complexes behave differently in higher dimensions, and this hope turns out to be false in many cases. We rely instead on a recent work reported by Boissonnat, Dyer and Ghosh [2] who devised the correct perturbation scheme to triangulate a manifold using a Delaunay complex. We will use the following theorem.

Theorem 6.4

Let $M$ be a compact Riemannian manifold. For a small enough $\varepsilon$, there exists a point set $P \subseteq M$ such that

• (i) for every $x \in M$, there exists $p \in P$ such that $|x-p|_m \le \varepsilon$;

• (ii) for every pair $p \ne p' \in P$, $|p-p'|_m \ge 2\varepsilon /5$;

• (iii) the Delaunay complex of $P$ is a triangulation of $M$.

For completeness, we sketch how to infer this theorem from the paper [2].

Proof of Theorem 6.4

We say that a set of points $P \subseteq M$ is $\varepsilon$-dense if $d(x,P) < \varepsilon$ for $x \in M$; $\mu _0 \varepsilon$-separated if $d(p,q)\ge \mu _0 \varepsilon$ for all distinct $p,q \in P$; and is a $(\mu _0,\varepsilon )$-net if it is $\varepsilon$-dense and $\mu _0 \varepsilon$-separated.

Taking $\mu '_0=1$ and $\varepsilon '$ small enough, we start with a $(\mu _0', \varepsilon ')$-net in $M$, which can be obtained for example by taking the centers of a maximal set of disjoint balls of radius $\varepsilon '/2$. Now, the extended algorithm of Boissonnat et al. [2] outputs a $(\mu _0, \varepsilon )$-net with $\varepsilon \le 5\varepsilon '/4$ and $\mu _0 \ge 2\mu _0'/5$, which will be our point set $P$. These conditions correspond to items (i) and (ii) in our theorem. For $\varepsilon$ small enough, all the hypotheses of their main theorem are fulfilled, and therefore we obtain that the Delaunay complex of the $(\mu _0, \varepsilon )$-net is a triangulation of $M$, which is our item (iii). $\square$

The proof of Theorem 6.3 now follows the same lines as in the $2$-dimensional case.

Proof of Theorem 6.3

Let $\varepsilon >0$ be a constant. Following Theorem 6.4, if $\varepsilon$ is small enough, there exists a point set $P$ whose Delaunay complex triangulates $M$. Let $G$ be the $1$-skeleton of this complex and $\gamma$ be a closed curve embedded in $G$.

By property (i), neighboring points in $G$ are at distance no more than $2\varepsilon$; therefore we have $|\gamma |_m \le 2\varepsilon |\gamma |_G$. There just remains to estimate the value of $\varepsilon$, which we do by estimating the number of balls. By compactness, the scalar curvature of $M$ is bounded from above by some constant $K$. Now, if $\varepsilon$ is small enough, for any $p \in P$, we have

$$\begin{aligned} {{\mathrm{vol}}}(B(p,\varepsilon /5))\ge \frac{\varepsilon ^d}{5^d}\Big (1-\frac{\varepsilon ^2}{6d}K+o(\varepsilon ^4)\Big ){{\mathrm{vol}}}(B^d), \end{aligned}$$

where $B^d$ is the unit Euclidean ball of dimension $d$. This follows from standard estimates on the volume of a ball in a Riemannian manifold, see for example Gromov [28], p. 89]. We recall that ${{\mathrm{vol}}}(B^d)=\frac{\pi ^{d/2}}{\varGamma (d/2+1)}$.

By property (ii), the balls $B(p,\varepsilon /5)$ are disjoint; therefore their number $f_0$ is at most $\frac{ \varGamma (d/2+1)5^d V}{\pi ^{d/2}\varepsilon ^d(1-\varepsilon )}$ if $\varepsilon$ is small enough. Finally, putting together our estimates, we obtain that

$$\begin{aligned} |\gamma |_m\le (1+\delta )\frac{10}{\sqrt{\pi }} \Big (\frac{ \varGamma (d/2+1)}{f_0} V \Big )^{1/d} |\gamma |_G. \end{aligned}$$

$\square$

However, this theorem leads to no immediate corollaries, since unlike the two-dimensional case, we do not know of any discrete systolic inequalities involving $f_0$ in dimensions larger than two. This leads to the following question:

Question 1

Are there manifolds $M$ of dimension $d\ge 3$ for which there exists a constant $c_M$ such that, for every triangulation $(M,T)$, there is a non-contractible closed curve in the $1$-skeleton of $T$ of length at most $c_M f_0(T)^{1/d}$?

Notice that a positive answer to this question for essential compact manifolds without boundary would yield a new proof of Gromov’s systolic inequality.

Remark

In his thesis [38], Kowalick states a theorem that is closely related to our Theorem 6.3, and thus to this question. Essentially, his result is the same as ours, except that $f_0$ is substituted with $f_d$. Precisely, he shows that if for a manifold $M$, there exists $c_M'>0$ such that, for every triangulation $(M,T)$, there is a non-contractible closed curve in the $1$-skeleton of $T$ of length at most $c_M' f_d(T)^{1/d}$, then there exists a constant $s_M$ such that the systole of every Riemannian metric on $M$ is bounded above by $s_M {{\mathrm{vol}}}(M)^{1/d}$. This statement can be derived from our proof without much extra difficulty. It is enough to show that in the triangulations constructed in the proof of Theorem 6.3, for large enough $f_0(T)$, the number $f_d(T)$ is bounded above by $f_0(T)$ up to a multiplicative constant that depends only on the dimension. This follows again from a packing argument and from the bounds on volume growth of small balls. For $\varepsilon$ small enough with respect to the strong convexity radius and the minimal sectional curvature of the manifold, the quotient ${{\mathrm{vol}}}(B(x,2\varepsilon ))/{{\mathrm{vol}}}(B(x,\varepsilon )$ is bounded from above by an absolute constant $k_d$ depending only on the dimension. Since two points in the same facet of our Delaunay complex are at distance at most $2\varepsilon$, we have $f_d(T)\le \frac{{k_d}^d}{d+1} f_0(T)$.

Appendix 2: Lengths of Genus Zero Decompositions

A genus zero decomposition of a surface is a family of disjoint simple closed curves that cut the surface into a (connected) genus zero surface with boundary. Every genus zero decomposition (of a surface with genus at least two) can be extended to a pants decomposition. In this section, we prove the following strengthening of Theorem 5.1:

Theorem 7.1

For any $\varepsilon >0$, the following holds with probability tending to one as $n$ tends to $\infty$: A random (trivalent, unweighted) cross-metric surface with $n$ vertices has no genus zero decomposition of length at most $n^{7/6-\varepsilon }$.

The argument is very similar to the one by Poon and Thite [50], Sect. 2]. As we shall see, this theorem is an immediate consequence of the following proposition:

Proposition 7.1

Let $(S,G^*)$ be a (trivalent, unweighted) cross-metric surface with genus zero and $b\ge 3$ boundary components. Then there exists some pants decomposition $\varGamma$ of $S$ such that each edge of $G^*$ has $O(\log b)$ crossings with each edge of $\varGamma$.

Proof

Define the multiplicity of a set of curves on $(S,G^*)$ to be the maximum number of crossings between an edge of $G^*$ and the set of curves.

Let $T$ be a spanning tree of the boundary components of $(S,G^*)$, i.e., a tree of multiplicity one in $(S,G^*)$ so that each boundary component of $S$ is intersected by exactly one leaf of the tree (Fig. 9a). Draw a path $p$ following the tree $T$, touching it only at the leaves (Fig. 9b, c); such a path $p$ has multiplicity two and touches each boundary component exactly once. Let $B_1,B_2,\ldots ,B_b$ be the boundary components in order along $p$ (oriented arbitrarily).

Fig. 9

The construction of the pants decomposition in Proposition 7.1. a The tree $T$. b The path $p$. c An isomorphic drawing of $p$. d The pants decomposition

Now, we build the pants decomposition (Fig. 9d). First we group the boundary components by pairs, $\{B_1,B_2\}$, $\{B_3,B_4\}$, and so on. Then we cut $S$ into a collection of $\lfloor {b/2}\rfloor$ pairs of pants and a genus zero surface with $\lceil {b/2}\rceil$ boundary components, and we reiterate the process on the latter surface. After $O(\log b)$ iterations, the remaining surface has at most three boundary components, so we have built a pants decomposition $\varGamma$.

We claim that $\varGamma$ has multiplicity $O(\log b)$. Indeed, each closed curve of $\varGamma$ is made of (1) pieces that go around a boundary component and (2) pieces that follow a subpath of $p$. The pieces of type (1) have overall multiplicity $O(\log b)$, because $O(\log b)$ pieces go around a given boundary component and each edge of $G^*$ is incident to at most two boundary components. The pieces of type (2) have overall multiplicity $O(\log b)$, since $O(\log b)$ pieces run along a given subpath of $p$, and because $p$ has multiplicity two in $(S,G^*)$. The result follows. $\square$

Proof of Theorem 7.1

Consider a random cross-metric surface $(S,G^*)$ with $n$ vertices; let $g$ be its genus.

• It may be that $(S,G^*)$ has genus zero or one, but this happens with probability arbitrarily close to zero, provided $n$ is large enough (this follows by combining Lemma 5.1 with Guth et al. [30], Lemma 4])

• Otherwise, if $(S,G^*)$ admits a genus zero decomposition $\varGamma '$ of length at most $n^{7/6-\varepsilon }$, we cut $(S,G^*)$ along $\varGamma '$, obtaining a cross-metric surface with genus zero with $2g\ge 3$ boundary components and $O(n^{7/6-\varepsilon })$ edges. Proposition 7.1 implies that this new cross-metric surface has a pants decomposition $\varGamma$ with length $O(n^{7/6-\varepsilon }\log g)=O(n^{7/6-\varepsilon }\log n)$. The union of $\varGamma$ and $\varGamma '$ is a pants decomposition of $(S,G^*)$ of length at most $O(n^{7/6-\varepsilon }\log n+n^{7/6-\varepsilon })=O(n^{7/6-\varepsilon '})$ for some $\varepsilon '<\varepsilon$ if $n$ is large enough. By Theorem 5.1 above, we conclude that this happens with arbitrarily small probability as $n\rightarrow \infty$. $\square$