On the Twin-Width of Smooth Manifolds

Bonnet, Édouard; Huszár, Kristóf

doi:10.4230/LIPIcs.SoCG.2025.23

On the Twin-Width of Smooth Manifolds

Édouard Bonnet

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France Kristóf Huszár

Institute of Geometry, Graz University of Technology, Austria

Abstract

Building on Whitney’s classical method of triangulating smooth manifolds, we show that every compact $d$ -dimensional smooth manifold admits a triangulation with dual graph of twin-width at most $d^{O(d)}$ . In particular, it follows that every compact $3$ -manifold has a triangulation with dual graph of bounded twin-width. This is in sharp contrast to the case of treewidth, where for any natural number $n$ there exists a closed 3-manifold such that every triangulation thereof has dual graph with treewidth at least $n$ . To establish this result, we bound the twin-width of the dual graph of the $d$ -skeleton of the second barycentric subdivision of the $2d$ -dimensional hypercubic honeycomb. We also show that every compact, piecewise-linear (hence smooth) $d$ -dimensional manifold has triangulations where the dual graph has an arbitrarily large twin-width.

Keywords and phrases:

Smooth manifolds, triangulations, twin-width, Whitney embedding theorem, structural graph parameters, computational topology

Funding:

Kristóf Huszár: Partially supported by the Austrian Science Fund (FWF) grant P 33765-N.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Graph theory ; Mathematics of computing

\rightarrow

Geometric topology

Related Version:

Full Version: https://arxiv.org/abs/2407.10174 [10]

Acknowledgements:

We thank the anonymous reviewers for their helpful comments and for raising interesting questions for future research.

Funding:

The authors have been supported by the French National Research Agency through the project TWIN-WIDTH with reference number ANR-21-CE48-0014.

DOI:

10.4230/LIPIcs.SoCG.2025.23

Event:

41st International Symposium on Computational Geometry (SoCG 2025)

Editors:

Oswin Aichholzer and Haitao Wang

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Structural graph parameters have become increasingly important in computational topology in the past two decades. This is mainly due to the emergence of fixed-parameter tractable (FPT) algorithms for problems on knots, links [13, 36, 37, 39] and 3-manifolds [15, 17, 18, 19, 20],¹¹1Also see [2] for an FPT algorithm checking tightness of (weak) pseudomanifolds in arbitrary dimensions. most of which are known to be NP-hard in general. Although these FPT algorithms may have exponential worst-case running time, on inputs with bounded treewidth they are guaranteed to terminate in polynomial (or even in linear) time.²²2Here the term input refers either to a link diagram $\mathscr{D}$ , or to a 3-manifold triangulation $\mathscr{T}$ . In the first case the treewidth means the treewidth of $\mathscr{D}$ considered as a $4$ -regular graph, in the second case it means the treewidth of the dual graph $\Gamma(\mathscr{T})$ of $\mathscr{T}$ . The running times are measured in terms of the size of the input. The size of a link diagram is defined as the number of its crossings, and the size of a 3-manifold triangulation is the number of its tetrahedra. More definitions are given in Section 2. In addition, some of these algorithms have been implemented in software packages such as Regina, providing practical tools for researchers in topology [12, 14].³³3See [3] for an implemented algorithm to effectively compute certain Khovanov homology groups of knots. This algorithm is conjectured to be FPT in the cutwidth of the input knot diagram, cf. [3, Section 6].

The success of the above algorithms naturally leads to the following question. Given a 3-manifold $\mathscr{M}$ (resp. knot $\mathscr{K}$ ), what is the smallest treewidth that the dual graph of a triangulation of $\mathscr{M}$ (resp. a diagram of $\mathscr{K}$ ) may have?⁴⁴4For links and knots, this question was respectively asked in [37, Section 4] and [16, p. 2694]. Motivated by this challenge, in recent years several results have been obtained that reveal quantitative connections between topological invariants of knots and 3-manifolds, and width parameters associated with their diagrams [22, 35] and triangulations [26, 27, 28, 29, 30, 40], respectively. It turns out that topological properties of 3-manifolds may prohibit the existence of “thin” triangulations.⁵⁵5For non-Haken 3-manifolds of large Heegaard genus [30] or Haken 3-manifolds with a “complicated” JSJ decomposition [29], the dual graph of any triangulation must also have large treewidth.^,⁶⁶6For results where the treewidth of a knot diagram is bounded below by topological properties of the underlying knot, see [22, 35]. At the same time, geometric or topological descriptions of 3-manifolds can also give strong hints on how to triangulate them so that their dual graphs have constant pathwidth or treewidth, or at least bounded in terms of a topological invariant of these 3-manifolds.⁷⁷7This is case with Seifert fibered spaces [28] or hyperbolic 3-manifolds [27, 40].

In this work we establish similar results for another graph parameter called twin-width. Introduced in [11], this notion has been subject of growing interest and found many algorithmic applications in recent years.⁸⁸8For an introduction to twin-width and an overview of its applications, see [6] and the references therein. Namely, on classes of effectively⁹⁹9A class has effectively bounded twin-width if it has bounded twin-width, and contraction sequences of width $O(1)$ (objects witnessing the twin-width upper bound) can be found in polynomial time; see Section 2.1 for the definitions of contraction sequences and twin-width. bounded twin-width, first-order properties can be decided efficiently¹⁰¹⁰10More precisely, there is a fixed-parameter tractable algorithm that, given a first-order sentence $\varphi$ and an $n$ -vertex graph $G$ with a contraction sequence of width $d$ , decides if $G$ satisfies $\varphi$ in time $f(\varphi,d)\cdot n$ , for some computable function $f$ . [11] (also see [8] for improved running times on specific problems definable in first-order logic), first-order queries can be enumerated fast [24], and enhanced approximation algorithms can be designed for several graph optimization problems [4]. Besides, classes of bounded twin-width are fairly general and broad. They for instance include classes of bounded tree-width, and even its dense analogue, clique-width, classes excluding a minor, proper permutation classes, $d$ -dimensional grid graphs [11], some classes of cubic expanders [9], segment intersection graphs without biclique subgraphs of a fixed size [7], and modifications definable in first-order logic (called first-order transductions) of all these classes [11]. We observe that the definition of twin-width can readily be lifted to binary structures (i.e., edge-colored multigraphs).

Our first result shows that a compact $d$ -dimensional smooth manifold always has a triangulation with dual graph of twin-width bounded in terms of $d$ .

Theorem 1.

Any compact $d$ -dimensional smooth manifold $\mathscr{M}$ admits a triangulation (more specifically, a Whitney triangulation¹¹¹¹11We call a triangulation $\mathscr{T}$ of a compact smooth manifold $\mathscr{M}$ a Whitney triangulation of $\mathscr{M}$ , if $\mathscr{T}$ is obtained via Whitney’s method discussed in Section 3.) with dual graph of twin-width at most $d^{O(d)}$ .

Let us emphasize that, in an appropriate computational model, Whitney triangulations of smooth manifolds can be constructed algorithmically [5]. As every 3-manifold is smooth [41] (see also [38]), the next corollary follows immediately from Theorem 1. We recall that $\operatorname{tww}(G)$ denotes the twin-width of a graph $G$ , and $\Gamma(\mathscr{T})$ denotes the dual graph of a triangulation $\mathscr{T}$ .

Corollary 2.

There exists a universal constant $C>0$ such that every compact $3$ -dimensional manifold $\mathscr{M}$ admits a triangulation $\mathscr{T}$ with $\operatorname{tww}(\Gamma(\mathscr{T}))\leqslant C$ .

This is in sharp contrast to the case of treewidth, for which it is known that for every $n\in\mathbb{N}$ there are infinitely many 3-manifolds where the smallest treewidth of the dual graph of every triangulation is at least $n$ [29, 30]. Complementing Theorem 1, we also show that for any fixed $d\geqslant 3$ , the $d$ -dimensional triangulations of large twin-width are abundant (Theorem 19). Moreover we show that any piecewise-linear (hence smooth) manifold of dimension at least three admits triangulations with dual graph of arbitrarily large twin-width.

Theorem 3.

Let $d\geqslant 3$ be an integer. For every compact $d$ -dimensional piecewise-linear manifold $\mathscr{M}$ and natural number $n\in\mathbb{N}$ , there is a triangulation $\mathscr{T}$ of $\mathscr{M}$ with $\operatorname{tww}(\Gamma(\mathscr{T}))\geqslant n$ .

$\blacktriangleright$ Remark 4.

The assumption of $d\geqslant 3$ in Theorem 3 is essential. Indeed, the dual graph of any triangulation of the genus- $g$ surface $S_{g}$ is, in particular, a graph that embeds into $S_{g}$ and such graphs are known to have twin-width bounded above by $c(\sqrt{g}+1)$ for some universal constant $c>0$ [32].¹²¹²12This bound is sharp up to a constant multiplicative factor [32]. For $g=0$ , we know that planar graphs have twin-width at most eight [25], and there are planar graphs with twin-width equal to seven [31].

Outline of the paper.

In Section 2 we review the relevant notions from graph theory and topology. In Section 3 we recall Whitney’s seminal work on triangulating smooth manifolds. This is followed by a detailed proof of Theorem 1 in Section 4. Finally, in Section 5 we prove the complementary results about triangulations with dual graph of large twin-width.

2 Preliminaries

Basic notation.

For a finite set $S$ we let $|S|$ denote its cardinality, while for a real number $x$ we let $|x|$ denote its absolute value. For a positive integer $k\leqslant|S|$ , we let $\binom{S}{k}$ denote the set of $k$ -element subsets of $S$ . For a positive integer $n$ , we let $[n]$ denote the set of all positive integers up to $n$ , and for two real numbers $a\leqslant b$ , we use $[a,b]$ to denote the closed interval $\{x\in\mathbb{R}:a\leqslant x\leqslant b\}$ . For a vector $y=(y_{1},\ldots,y_{d})\in\mathbb{R}^{d}$ we use $\|y\|$ to denote its Euclidean norm, i.e, $\|y\|^{2}=\sum_{i=1}^{d}y_{i}^{2}$ . However, if $\mathscr{X}$ is a (cubical or simplicial) complex, then $\|{\mathscr{X}}\|$ refers to its geometric realization.

2.1 Trigraphs, contraction sequences and twin-width

Following [11, Sections 3 and 4], in this section we review the graph-theoretic notions central to our work and collect some basic, yet important facts about twin-width.

Trigraphs.

A trigraph $G$ is a triple $G=(V,E,R)$ , where $V$ is a finite set of vertices, and $E,R\subseteq\binom{V}{2}$ are two disjoint subsets of pairs of vertices called black edges and red edges, respectively. We also refer to the sets of vertices, black edges and red edges of a given trigraph $G$ as $V(G)$ , $E(G)$ and $R(G)$ , respectively. Any simple graph $G=(V,E)$ may be regarded as a trigraph $(V,E,R)$ with $R=\emptyset$ . For a vertex $v\in V(G)$ the degree $\deg(v)$ of $v$ is the number of edges incident to it, i.e., $\deg(v)=|\{e\in E\cup R:v\in e\}|$ . Additionally, the red degree $\deg_{R}(v)$ of $v$ is the number of red edges incident to it, i.e., $\deg_{R}(v)=|\{e\in R:v\in e\}|$ . A trigraph $G$ for which $\deg_{R}(G)=\max_{v\in V(G)}{\deg_{R}(v)}\leqslant b$ is called a $b$ -trigraph. Given two trigraphs $G=(V,E,R)$ and $G^{\prime}=(V^{\prime},E^{\prime},R^{\prime})$ , we say that $G^{\prime}$ is a subtrigraph of $G$ , if $V^{\prime}\subseteq V$ , $E^{\prime}\subseteq E\cap\binom{V^{\prime}}{2}$ and $R^{\prime}\subseteq R\cap\binom{V^{\prime}}{2}$ .¹³¹³13As usual, subtrigraphs of graphs (those without any red edges) will also be called subgraphs. In addition, if $E^{\prime}=E\cap\binom{V^{\prime}}{2}$ and $R^{\prime}=R\cap\binom{V^{\prime}}{2}$ , then we say that $G^{\prime}$ is an induced subtrigraph of $G$ . For a trigraph $G$ and a subset $S\subseteq V(G)$ of its vertices, $G-S$ denotes the induced subtrigraph of $G$ with vertex set $V(G)\setminus S$ .

Contraction sequences and twin-width.

Let $G=(V,E,R)$ be a trigraph and $u,v\in V$ be two arbitrary distinct vertices of $G$ . We say that the trigraph $G/u,v=(V^{\prime},E^{\prime},R^{\prime})$ is obtained from $G$ by contracting $u$ and $v$ into a new vertex $w$ if 1. $V^{\prime}=(V\setminus\{u,v\})\cup\{w\}$ , 2. $G-\{u,v\}=(G/u,v)-\{w\}$ and 3. for any $x\in V^{\prime}\setminus\{w\}=V\setminus\{u,v\}$ we have

$\blacksquare$

$\{w,x\}\in E^{\prime}$ if and only if $\{u,x\}\in E$ and $\{v,x\}\in E$ ,
$\blacksquare$

$\{w,x\}\notin E^{\prime}\cup R^{\prime}$ if and only if $\{u,x\}\notin E\cup R$ and $\{v,x\}\notin E\cup R$ , and
$\blacksquare$

$\{w,x\}\in R^{\prime}$ otherwise.

We call the trigraph $G/u,v$ a contraction of $G$ . A sequence $\mathfrak{S}=(G_{1},\ldots,G_{m})$ of trigraphs is a contraction sequence if $G_{i+1}$ is a contraction of $G_{i}$ for every $1\leqslant i\leqslant m-1$ . Note that $|V(G_{i+1})|=|V(G_{i})|-1$ . We use the notation “ $\mathfrak{S}\colon G_{1}\leadsto G_{m}$ ” to indicate that the trigraphs $G_{1}$ and $G_{m}$ are initial and terminal entries of the contraction sequence $\mathfrak{S}$ . The width $0pt(\mathfrak{S})$ of a contraction sequence $\mathfrak{S}=(G_{1},\ldots,G_{m})$ is defined as $0pt(\mathfrak{S})=\max_{1\leqslant i\leqslant m}\deg_{R}(G_{i})$ , i.e., the largest red degree of any vertex of any trigraph in $\mathfrak{S}$ . Now, the twin-width $\operatorname{tww}(G)$ of a trigraph $G$ is defined as the smallest width of any contraction sequence $(G_{1},\ldots,G_{|V(G)|})$ with $G_{1}=G$ and $G_{|V(G)|}=\bullet$ , where $\bullet$ denotes the trigraph consisting of a single vertex.

Some properties of twin-width; grid graphs

We conclude this section by collecting some properties of twin-width that we will rely on later. The first one states that twin-width is monotonic under taking induced subtrigraphs and is a simple consequence of the definitions (cf. [11, Section 4.1]).

Proposition 5.

If $H$ is an induced subtrigraph of a trigraph $G$ , then $\operatorname{tww}(H)\leqslant\operatorname{tww}(G)$ .

Smallness.

An infinite class $\mathscr{G}$ of graphs is small if there exists a constant $c>1$ such that for every $n\in\mathbb{N}$ the class $\mathscr{G}$ contains at most $n!c^{n}$ labeled graphs on $n$ vertices. The next theorem says that every graph class of bounded twin-width – i.e., for which there exists a constant $C>0$ , such that $\operatorname{tww}(G)\leqslant C$ for every graph $G$ in the class – is small.

Theorem 6 ([9, Theorem 2.5]).

Every graph class with bounded twin-width is small.

Now let $s$ be a non-negative integer. The $s$ -subdivision of $G$ is the graph $\operatorname{subd}_{s}(G)$ obtained from $G$ by subdividing each edge in $E(G)$ exactly $s$ times. A simple counting argument together with Theorem 6 yields the following:

Proposition 7.

For any fixed integers $k\geqslant 4$ and $s\geqslant 0$ , the class $\operatorname{subd}_{s}(\mathscr{G}_{k})$ of $s$ -subdivisions of $k$ -regular¹⁴¹⁴14A simple graph $G=(V,E)$ is $k$ -regular if every vertex $v\in V$ has degree $\deg(v)=k$ . simple graphs is not small, hence has unbounded twin-width.

This proposition follows from the adaptation of an argument given in the first paragraph of [23, Section 3]. For completeness, we spell out this proof below.

Proof of Proposition 7.

Let $N_{k}(m)$ be the number of labeled $k$ -regular simple graphs on $m$ vertices. Note that if $N_{k}(m)>0$ , then $k m$ is even; which we now assume. It is known (cf. [42, Section 6.4.1]) that, asymptotically

\displaystyle N_{k}(m)\sim\exp\left(\frac{1-k^{2}}{4}\right)\frac{(km)!}{(km/2% )!\cdot 2^{km/2}\cdot(k!)^{m}}=\Omega\left(\frac{(km/2)!}{(k!)^{m}}\right),

(1)

which readily implies that $k$ -regular graphs (for $k\geqslant 3)$ do not form a small class.

Now, let $N_{k}^{(s)}(n)$ be the number of $n$ -vertex graphs in the class $\operatorname{subd}_{s}(\mathscr{G}_{k})$ of $s$ -subdivisions of $k$ -regular simple graphs. If a graph $G\in\operatorname{subd}_{s}(\mathscr{G}_{k})$ has $n$ vertices, then $n=m+\frac{km}{2}s$ , where $m$ is the number of vertices of $G$ of degree $k$ . Note that such a graph $G$ can be obtained by first choosing a $k$ -regular labeled graph $H$ on $m$ vertices, then ordering the remaining $n-m=kms/2$ vertices arbitrarily and evenly distributing them to the edges of $H$ according to some fixed ordering of $E(H)$ . It follows that

\displaystyle N_{k}^{(s)}(n)\geqslant\binom{n}{m}\cdot N_{k}(m)\cdot(n-m)!=n!% \frac{N_{k}(m)}{m!}\overset{\eqref{eq:k-reg}}{=}n!\cdot\Omega\left(\frac{(km/2% )!}{m!\cdot(k!)^{m}}\right).

(2)

Since $k\geqslant 4$ , we have $km/2\geqslant 2m$ . This, together with $(2m)!\geqslant 2^{m}(m!)^{2}$ and (2) implies

\displaystyle N_{k}^{(s)}(n)\geqslant n!\cdot\Omega\left(\frac{m!}{(2\cdot k!)% ^{m}}\right).

(3)

Recall that $m=2n/(2+ks)$ . In particular, $m$ is proportional to $n$ . Hence $m!/(2\cdot k!)^{m}$ grows faster than $c^{n}$ for any fixed constant $c>1$ . Thus the graph class $\operatorname{subd}_{s}(\mathscr{G}_{k})$ is not small. $\hfill\blacktriangleleft$

Grid graphs.

The $d$ -dimensional $n$ -grid $P_{n}^{d}$ is the graph with vertex set $V(P_{n}^{d})=[n]^{d}$ , and $\{u,v\}\in E(P_{n}^{d})$ for two vertices $u=(u_{1},\ldots,u_{d})$ and $v=(v_{1},\ldots,v_{d})$ if and only if $\sum_{i=1}^{d}|u_{i}-v_{i}|=1$ . The next result states that $\operatorname{tww}(P_{n}^{d})\leqslant 3d$ irrespective of the value of $n$ .

Theorem 8 (Theorem 4 in [11]).

For every positive $d$ and $n$ , the $d$ -dimensional $n$ -grid $P_{n}^{d}$ has twin-width at most $3d$ .

The $d$ -dimensional $n$ -grid with diagonals $D_{n,d}$ is the graph with $V(D_{n,d})=[n]^{d}$ , and $\{u,v\}\in E(D_{n,d})$ for two vertices $u=(u_{1},\ldots,u_{d})$ and $v=(v_{1},\ldots,v_{d})$ if and only if $\max_{i=1}^{d}|u_{i}-v_{i}|\leqslant 1$ . Now, for a given trigraph $G=(V,E,R)$ we set $\operatorname{red}(G)=(V,\emptyset,E\cup R)$ . In words, $\operatorname{red}(G)$ is the trigraph obtained from $G$ by replacing every black edge of $G$ by a red edge between the same vertices. With this notation $\operatorname{red}(D_{n,d})$ is the $d$ -dimensional red $n$ -grid with diagonals, i.e., $\operatorname{red}(D_{n,d})=([n]^{d},\emptyset,E(D_{n,d}))$ . Clearly, $\operatorname{tww}(D_{n,d})\leqslant\operatorname{tww}(\operatorname{red}(D_{n% ,d}))$ .

Theorem 9 (Lemma 4.4 in [11]).

For every positive $d$ and $n$ , every subtrigraph of the $d$ -dimensional red $n$ -grid with diagonals $\operatorname{red}(D_{n,d})$ has twin-width at most $2(3^{d}-1)$ .

2.2 Background in topology

For general background in (combinatorial and differential) topology we refer to [43].

2.2.1 Simplicial and cubical complexes

Abstract simplicial complexes.

Given a finite ground set $\mathscr{S}$ , an abstract simplicial complex (or simplicial complex, for short) $\mathscr{X}$ over $\mathscr{S}$ is a downward closed subset of the power set $2^{\mathscr{S}}$ , i.e., $\mathcal{F}\in\mathscr{X}$ and $\mathcal{F}^{\prime}\subset\mathcal{F}$ imply $\mathcal{F}^{\prime}\in\mathscr{X}$ . Any element of $\mathscr{X}$ is called a face or simplex of $\mathscr{X}$ , and for $\sigma\in\mathscr{X}$ the dimension of $\sigma$ is defined as $\dim\sigma=|\sigma|-1$ . The dimension of $\mathscr{X}$ , denoted by $\dim\mathscr{X}$ , is then the maximum dimension of a face of $\mathscr{X}$ . If $\dim\mathscr{X}=d$ , we also say that $\mathscr{X}$ is a simplicial $d$ -complex. For $0\leqslant i\leqslant\dim\mathscr{X}$ , we let $\mathscr{X}(i)=\{\sigma\in\mathscr{X}:\dim\sigma=i\}$ denote the set of $i$ -dimensional faces (or $i$ -faces, or $i$ -simplices) of $\mathscr{X}$ . The $i$ -skeleton $\mathscr{X}_{i}=\bigcup_{j=0}^{i}\mathscr{X}(j)$ of $\mathscr{X}$ is the union of all faces of $\mathscr{X}$ up to dimension $i$ . Note that any simple graph $G=(V,E)$ can be regarded as a $1$ -dimensional simplicial complex $\mathscr{X}_{G}$ with $\mathscr{X}_{G}(0)=\{\{v\}:v\in V\}$ and $\mathscr{X}_{G}(1)=E$ . For $0\leqslant i\leqslant 3$ the $i$ -simplices of a simplicial complex $\mathscr{X}$ are respectively called the vertices, edges, triangles, and tetrahedra of $\mathscr{X}$ .

Geometric realization of simplicial complexes.

Every abstract simplicial complex $\mathscr{X}$ may be realized geometrically as follows. To each abstract $i$ -simplex $\sigma=\{v_{0},v_{1},\ldots,v_{i}\}\in\mathscr{X}$ we associate a geometric $i$ -simplex $\|\sigma\|=[v_{0},v_{1},\ldots,v_{i}]\subset\mathbb{R}^{i}$ defined as the convex hull of $i+1$ affinely independent points in $\mathbb{R}^{i}$ . We equip $\|\sigma\|$ with the subspace topology inherited from $\mathbb{R}^{i}$ . Next, we consider the disjoint union $\bigsqcup_{\sigma\in\mathscr{X}}\|\sigma\|$ of these geometric simplices, and perform identifications along their faces that reflect their relationship in $\mathscr{X}$ . The resulting space $\|\mathscr{X}\|$ , equipped with the quotient topology, is called the geometric realization of $\mathscr{X}$ , see Figure 1. The geometric realization of a simplicial complex is unique up to homeomorphism.

Cubical complexes.

Analogous to simplicial complexes, a cubical complex $\mathscr{X}$ over a ground set $\mathscr{S}$ is a set system $\mathscr{X}\subset 2^{\mathscr{S}}$ that consists of “cubes” instead of simplices. The terminology is the same as in the simplicial case. The only difference is that a geometric $i$ -cube is a topological space homeomorphic to $[0,1]^{i}$ , where $[0,1]$ denotes the closed unit interval.

Cubical or simplicial complexes in this paper will typically be defined geometrically, and as such they will naturally come with a geometric realization.

(a) Geometric

i

-simplices (

i=0,1,2,3

).

(b) Geometric realization of a simplicial 3-complex.

(c) Geometric

i

-cubes (

i=0,1,2,3

).

(d) Geometric realization of a cubical 3-complex.

Figure 1: The geometric perspective on simplicial and cubical complexes.

The hypercubic honeycomb.

Let $n$ and $d$ be positive integers and consider the $d$ -dimensional cube $[1,n]^{d}\subset\mathbb{R}^{d}$ . The $d$ -dimensional hypercubic honeycomb $\mathbf{H}^{d,n}$ is a cubical $d$ -complex that decomposes $[1,n]^{d}$ into $(n-1)^{d}$ geometric cubes. The properties of this familiar object play an important role in this work, so we describe it for completeness. We define $\mathbf{H}^{d,n}$ geometrically, in a bottom-up fashion. First, the vertex set $\mathbf{H}^{d,n}(0)$ consists of precisely those points in $[1,n]^{d}$ , which have only integral coordinates. Next, a $1$ -cube (i.e., an edge) is attached along its endpoints to vertices $u=(u_{1},\ldots,u_{d})$ and $v=(v_{1},\ldots,v_{d})$ in $\mathbf{H}^{d,n}(0)$ if and only if $\sum_{i=1}^{d}|u_{i}-v_{i}|=1$ . Thus the 1-skeleton $\mathbf{H}^{d,n}_{1}$ is just the $d$ -dimensional grid graph $P^{d}_{n}$ encountered in the end of Section 2.1. Finally, the higher dimensional skeleta of $\mathbf{H}^{d,n}$ are induced by its 1-skeleton: for each subcomplex $\mathcal{Y}\subset\mathbf{H}^{d,n}_{i}$ isomorphic to the boundary of a $(i+1)$ -cube, we attach an $(i+1)$ -cube to $\mathbf{H}^{d,n}_{i}$ along $\mathcal{Y}$ . In words, starting from the 1-skeleton $\mathbf{H}^{d,n}_{1}$ , whenever we have the possibility to attach a cube of dimension at least two (because its boundary is already present), we attach it. See, e.g., Figure 2.

Figure 2: Constructing the complex

\mathbf{H}^{2,5}

. Its 1-skeleton

\mathbf{H}^{2,5}_{1}

is isomorphic to the grid

P_{5}^{2}

.

Pure complexes and their dual graphs.

A (cubical or simplicial) complex $\mathscr{X}$ is pure if every face of $\mathscr{X}$ is contained in a face of dimension $\dim\mathscr{X}$ . It follows that, for every $i$ with $0\leqslant i\leqslant\dim\mathscr{X}$ , the $i$ -skeleton $\mathscr{X}_{i}$ of a pure complex $\mathscr{X}$ is also pure. Examples of pure complexes include nonempty graphs without isolated vertices, or triangulations of manifolds (see Section 2.2.3). Given a pure complex $\mathscr{X}$ , the dual graph $\Gamma(\mathscr{X}_{i})=(V,E)$ of its $i$ -skeleton is defined as the graph, where the vertex set $V$ corresponds to the set $\mathscr{X}(i)$ of $i$ -faces, and $\{\sigma,\tau\}\in E$ if and only if $\sigma$ and $\tau$ share an $(i-1)$ -dimensional face in $\mathscr{X}$ , see Figure 3.

(a) A pure simplicial 2-complex

\mathscr{X}

formed by six triangles

\tau_{1}

,

\tau_{2}

,

\tau_{3}

,

\tau_{4}

,

\tau_{5}

, and

\tau_{6}

, four of which meet along a single edge.

(b) The dual graph

\Gamma(\mathscr{X}_{2})

of

\mathscr{X}_{2}

. As

\tau_{6}

shares no edge with any other triangle in

\mathscr{X}

, its corresponding vertex is isolated.

Figure 3: Example of a pure simplicial

2

-complex and its dual graph.

2.2.2 Barycentric subdivisions

Given a (cubical or simplicial) complex $\mathscr{X}$ , its barycentric subdivision is a simplicial complex $\mathscr{X}^{\prime}$ defined abstractly as follows. For the ground set $\mathscr{S}^{\prime}$ of $\mathscr{X}^{\prime}$ we have $\mathscr{S}^{\prime}=\mathscr{X}$ . A $(k+1)$ -tuple $\{\sigma_{0},\ldots,\sigma_{k}\}\subset\mathscr{S}^{\prime}$ forms a $k$ -simplex of $\mathscr{X}^{\prime}$ if and only if $\sigma_{i}\subset\sigma_{j}$ for every $0\leqslant i<j\leqslant k$ . We denote the 2^nd (resp. $\ell$ ^th) iterated barycentric subdivision of a complex $\mathscr{X}$ by $\mathscr{X}^{\prime\prime}$ (resp. $\mathscr{X}^{(\ell)}$ ). See [10, Appendix A] for examples. The following are simple consequences of the definitions.

Observation 10.

For any $0\leqslant l\leqslant k$ , a $k$ -simplex has $\binom{k}{l}$ $l$ -faces.

Observation 11.

The barycentric subdivision of a $k$ -simplex contains $(k+1)!$ $k$ -simplices.

Observation 12.

The barycentric subdivision of a $k$ -cube contains $2^{k}k!$ $k$ -simplices.

See [10, Appendix A] for a proof of Observation 12.

2.2.3 Manifolds and their triangulations

Manifolds can be regarded as higher dimensional analogs of surfaces. A $d$ -dimensional topological manifold with boundary (or $d$ -manifold, for short) is a topological space¹⁵¹⁵15As a topological space a manifold is required to be second countable [43, p. 2] and Hausdorff [43, p. 87]. $\mathscr{M}$ , where every point has an open neighborhood homeomorphic to $\mathbb{R}^{d}$ , or to the closed upper half-space $\{(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}:x_{1}\geqslant 0\}$ . The points of $\mathscr{M}$ that do not have a neighborhood homeomorphic to $\mathbb{R}^{d}$ constitute the boundary $\partial\mathscr{M}$ of $\mathscr{M}$ . If a manifold $\mathscr{M}$ satisfies $\partial\mathscr{M}=\emptyset$ , then $\mathscr{M}$ is called a closed manifold. In this paper $\mathscr{M}$ always denotes a compact manifold.

Smooth manifolds.

The main result of this paper (Theorem 1) applies for manifolds that have an additional property, namely smoothness. As we will not need to work with the actual definition of smoothness, but merely rely on it, we only give a brief definition here. For more background on smooth manifolds, we refer to [43, Chapter 5] and [33].

Given a connected and open subset $U\subset\mathscr{M}$ and a homeomorphism $\varphi\colon U\rightarrow\varphi(U)$ onto an open subset of $\mathbb{R}^{d}$ , the pair $(U,\varphi)$ is called a chart. Given two charts $(U_{\alpha},\varphi_{\alpha})$ and $(U_{\beta},\varphi_{\beta})$ with $U_{\alpha}\cap U_{\beta}\neq\emptyset$ , the map $\tau_{\alpha,\beta}\colon\varphi_{\alpha}(U_{\alpha}\cap U_{\beta})\rightarrow% \varphi_{\beta}(U_{\alpha}\cap U_{\beta})$ defined via $\tau_{\alpha,\beta}=\varphi_{\beta}\circ\varphi_{\alpha}^{-1}$ is called a transition map. A smooth structure on a topological manifold $\mathscr{M}$ with $\partial\mathscr{M}=\emptyset$ is a collection $\mathcal{A}=\{(U_{\alpha},\varphi_{\alpha}):\alpha\in A\}$ of charts that satisfies the following three properties.

1.

The sets $U_{\alpha}$ cover $\mathscr{M}$ , that is $\bigcup_{\alpha\in A}U_{\alpha}=\mathscr{M}$ .
2.

For any $\alpha,\beta\in A$ with $U_{\alpha}\cap U_{\beta}\neq\emptyset$ , the transition map $\tau_{\alpha,\beta}$ is smooth.¹⁶¹⁶16See [43, p. 185] for a discussion of (smooth) maps of manifolds.
3.

The collection $\mathcal{A}$ is maximal in the sense that if $(U,\varphi)$ is a chart and for every $\alpha\in A$ with $U\cap U_{\alpha}\neq\emptyset$ the transition maps $\varphi\circ\varphi_{\alpha}^{-1}$ and $\varphi_{\alpha}\circ\varphi^{-1}$ are smooth, then $(U,\varphi)\in\mathcal{A}$ .

A topological manifold together with a smooth structure is called a smooth manifold. By an appropriate modification of property 2 above, the definition extends to manifolds with non-empty boundary as well. We refer to [43, Section 5.1.1] for details.

Triangulations.

Let $\mathscr{M}$ be a compact topological $d$ -manifold. A simplicial complex $\mathscr{T}$ whose geometric realization $\|\mathscr{T}\|$ is homeomorphic to $\mathscr{M}$ is called a triangulation of $\mathscr{M}$ . It follows that $\mathscr{T}$ is a pure simplicial complex of dimension $d$ (see Section 2.2.1). For $d\leqslant 3$ , every topological $d$ -manifold admits a triangulation [41, 44], however, for $d>3$ this is generally not true (see [38] for an overview). Smooth manifolds can nevertheless always be triangulated, irrespective of their dimension, e.g., by work of Whitney [48, Chapter IV.B] (cf. Section 3).

Given a $d$ -dimensional triangulation $\mathscr{T}$ , recall that its dual graph $\Gamma(\mathscr{T})$ is the graph with vertices corresponding to the $d$ -simplices of $\mathscr{T}$ , and edges to the face gluings, i.e, those $(d-1)$ -simplices of $\mathscr{T}$ that are contained in precisely two $d$ -simplices. Note that $\deg(v)\leqslant d+1$ for any vertex $v$ of $\Gamma(\mathscr{T})$ . The following proposition is a consequence of the definitions.

Proposition 13.

Let $\mathscr{T}$ be a triangulation of a $d$ -manifold $\mathscr{M}$ and $\mathscr{U}$ be a collection of $d$ -simplices of $\mathscr{T}$ that define a submanifold of $\mathscr{M}$ . Then $\Gamma(\mathscr{U})$ is an induced subgraph of $\Gamma(\mathscr{T})$ .

3 Whitney’s method

A seminal result of Whitney states that a smooth $d$ -dimensional manifold $\mathscr{M}$ always admits a smooth embedding into a $2d$ -dimensional Euclidean space.

Theorem 14 (strong Whitney embedding theorem [47, Theorem 5], cf. [33, Theorem 6.19]).

For $d>0$ , every smooth $d$ -manifold admits a smooth embedding into $\mathbb{R}^{2d}$ .

An important consequence of Theorem 14 is that smooth manifolds can be triangulated.

Theorem 15 (triangulation theorem [48, Chapter IV.B], cf. [5, Theorem 1.1]).

Every compact, smooth $d$ -manifold $\mathscr{M}$ embedded in some Euclidean space $\mathbb{R}^{m}$ admits a triangulation.

Next, we give a very brief and high-level overview of Whitney’s method of triangulating smooth manifolds based on [48, Chapter IV.B] sufficient for our purposes. To the interested reader we also recommend [5], where Whitney’s method is recast in a computational setting.

Triangulating smooth manifolds.

Let $\mathscr{M}$ be a compact smooth $d$ -manifold. By Theorem 14 there exists a smooth embedding $\iota\colon\mathscr{M}\rightarrow\mathbb{R}^{2d}$ . Given such an embedding, we choose a sufficiently fine (with respect to $\iota$ ) hypercubic honeycomb decomposition of $\mathbb{R}^{2d}$ , denoted by $L_{0}$ . Next, we pass to the first barycentric subdivision $L$ of $L_{0}$ . (Geometrically, $L$ is obtained from $L_{0}$ by subdividing each $k$ -dimensional hypercube of $L_{0}$ into $(2k)!!$ simplices.) By slightly perturbing the vertices of $L$ we obtain a triangulation $L^{\ast}$ of $\mathbb{R}^{2d}$ , which is combinatorially isomorphic to $L$ , but is in general position with respect to $\iota(\mathscr{M})\subset\mathbb{R}^{2d}$ . Now, by the work of Whitney, $L^{\ast}$ induces a triangulation $\mathscr{T}$ of $\mathscr{M}$ , where, importantly, $\mathscr{T}$ is a subcomplex of the $d$ -skeleton of the barycentric subdivision $(L^{\ast})^{\prime}$ of $L^{\ast}$ .

See Figure 4 for an illustration of this procedure for $d=1$ .

(a) The triangulation

L

and the image

\iota(\mathscr{M})

(blue). The red points indicate the vertices of

L

contained by

\iota(\mathscr{M})

.

(b) The perturbed triangulation

L^{\ast}

, which in general position with respect to

\iota(\mathscr{M})

.

(c) The resulting triangulation

\mathscr{T}

of

\mathscr{M}

(dark green).

\mathscr{T}

is a subcomplex of

(L^{\ast})^{\prime}

.

Figure 4: Illustration of Whitney’s method of triangulating ambient submanifolds (

d=1

).

Similar to Proposition 13, the next proposition is a direct consequence of the definitions.

Proposition 16.

For any Whitney triangulation $\mathscr{T}$ of a compact smooth $d$ -manifold $\mathscr{M}$ , we have that the dual graph $\Gamma(\mathscr{T})$ is an induced subgraph of $\Gamma(((\mathbf{H}^{2d,n})^{\prime\prime})_{d})$ .

4 The proof of Theorem 1

In this section we prove our main result, i.e., every compact smooth $d$ -manifold $\mathscr{M}$ has twin-width $\operatorname{tww}(\mathscr{M})\leqslant d^{O(d)}$ . To streamline the notation, we let $G_{d,n}=\Gamma(((\mathbf{H}^{2d,n})^{\prime\prime})_{d})$ , i.e., $G_{d,n}$ denotes the dual graph of the $d$ -skeleton¹⁷¹⁷17Recall that the dual graph $\Gamma(\mathscr{X})$ of a pure $k$ -dimensional complex $\mathscr{X}$ has vertices corresponding to the $k$ -faces of $\mathscr{X}$ and two vertices are connected if and only if their corresponding $k$ -faces share a $(k-1)$ -face. of the second barycentric subdivision of the hybercubic honeycomb $\mathbf{H}^{2d,n}$ . The result is based on the following property of $G_{d,n}$ .

Theorem 17.

For the twin-width of the dual graph $G_{d,n}=\Gamma(((\mathbf{H}^{2d,n})^{\prime\prime})_{d})$ of the $d$ -skeleton of the second barycentric subdivision of the hypercubic honeycomb $\mathbf{H}^{2d,n}$ we have

\operatorname{tww}(G_{d,n})\leqslant d^{O(d)}.

Before proving Theorem 17, we show how it implies Theorem 1.

Proof of Theorem 1.

Let $\mathscr{M}$ be a compact, smooth $d$ -dimensional manifold. Consider a Whitney triangulation $\mathscr{T}$ of $\mathscr{M}$ . By Proposition 16, $\Gamma(\mathscr{T})$ is an induced subgraph of $G_{d,n}$ and by Theorem 17, $\operatorname{tww}(G_{d,n})\leqslant d^{O(d)}$ . Hence, since twin-width is monotone under taking induced subtrigraphs (Proposition 5), we obtain $\operatorname{tww}(\Gamma(\mathscr{T})))\leqslant\operatorname{tww}(G_{d,n})% \leqslant d^{O(d)}$ . $\hfill\blacktriangleleft$

To complete the proof of Theorem 1, it remains to show Theorem 17.

Proof of Theorem 17.

We establish the theorem by exhibiting a $d^{O(d)}$ -contraction sequence $\mathfrak{S}\colon G_{d,n}\leadsto\bullet$ . We will obtain $\mathfrak{S}$ by concatenating two contraction sequences $\mathfrak{S}_{1}\colon G_{d,n}\leadsto G_{d,n}^{\ast}$ and $\mathfrak{S}_{2}\colon G_{d,n}^{\ast}\leadsto\bullet$ , referred to as the first and the second epoch, where $G_{d,n}^{\ast}$ is an appropriate subtrigraph of $\operatorname{red}(D_{n,2d})$ , the $2d$ -dimensional red $n$ -grid with diagonals. In the following we regard $\mathbf{H}^{2d,n}$ and its subdivisions mainly as abstract complexes, but we will also take advantage of their geometric nature.

Preparations.

Consider the $(2d+1)$ -coloring $\mathscr{C}\colon\mathbf{H}^{2d,n}\rightarrow\{0,\ldots,2d\}$ , where we color the cubes of $\mathbf{H}^{2d,n}$ by their dimension, that is, for $c\in\mathbf{H}^{2d,n}$ we set $\mathscr{C}(c)=\dim(c)$ (Figure 5).

The coloring $\mathscr{C}$ induces a $(2d+1)$ -coloring $\mathscr{C}^{\prime\prime}\colon(\mathbf{H}^{2d,n})^{\prime\prime}\rightarrow% \{0,\ldots,2d\}$ of the simplices of the second barycentric subdivision $(\mathbf{H}^{2d,n})^{\prime\prime}$ as follows. The vertices of the first barycentric subdivision $(\mathbf{H}^{2d,n})^{\prime}$ are in one-to-one correspondence with the cubes in $\mathbf{H}^{2d,n}$ , hence $\mathscr{C}$ induces a coloring $\mathscr{C}^{\prime}_{0}\colon(\mathbf{H}^{2d,n})^{\prime}(0)\rightarrow\{0,% \ldots,2d\}$ via $\mathscr{C}^{\prime}_{0}(v_{c})=\mathscr{C}(c)$ , where $v_{c}$ denotes the vertex of $(\mathbf{H}^{2d,n})^{\prime}$ corresponding to the cube $c\in\mathbf{H}^{2d,n}$ (Figure 5). Geometrically, $v_{c}$ is in the barycenter of the cube $c$ . When we pass to the second barycentric subdivision, the vertices of $(\mathbf{H}^{2d,n})^{\prime}$ become vertices of $(\mathbf{H}^{2d,n})^{\prime\prime}$ , thus there is a natural inclusion $\iota\colon(\mathbf{H}^{2d,n})^{\prime}(0)\rightarrow(\mathbf{H}^{2d,n})^{% \prime\prime}(0)$ . Let $\mathscr{V}=\operatorname{im}(\iota)\subset(\mathbf{H}^{2d,n})^{\prime\prime}(0)$ be the image of $(\mathbf{H}^{2d,n})^{\prime}(0)$ under this inclusion $\iota$ . We color the elements of $\mathscr{V}$ identically to $\mathscr{C}^{\prime}_{0}$ , that is, we consider the coloring $\mathscr{C}^{\prime\prime}_{\mathscr{V}}\colon\mathscr{V}\rightarrow\{0,\ldots% ,2d\}$ defined as $\mathscr{C}^{\prime\prime}_{\mathscr{V}}(v)=\mathscr{C}^{\prime}_{0}(\iota^{-1% }(v))$ , see Figure 5. Now, pick a simplex $\sigma\in(\mathbf{H}^{2d,n})^{\prime\prime}$ and note that $\bigcup_{v\in\mathscr{V}}\overline{\operatorname{st}}(v)=(\mathbf{H}^{2d,n})^{% \prime\prime}$ , i.e., the closed stars of the vertices $v\in\mathscr{V}$ cover $(\mathbf{H}^{2d,n})^{\prime\prime}$ . Let $\mathscr{V}_{\sigma}=\{v\in\mathscr{V}:\sigma\in\overline{\operatorname{st}}(v)\}$ . We now define $\mathscr{C}^{\prime\prime}(\sigma)$ as

\displaystyle\mathscr{C}^{\prime\prime}(\sigma)=\min\{\mathscr{C}^{\prime% \prime}_{\mathscr{V}}(v):v\in\mathscr{V}_{\sigma}\}.

(4)

In words, $\mathscr{C}^{\prime\prime}(\sigma)$ is defined as the smallest dimension of any cube $c\in\mathbf{H}^{2d,n}$ such that $\sigma$ belongs to the closed star of the vertex $\iota(v_{c})$ in $(\mathbf{H}^{2d,n})^{\prime\prime}$ , where $v_{c}$ is the vertex of $(\mathbf{H}^{2d,n})^{\prime}$ corresponding to $c$ . We refer to Figure 5 for an example.

(a) The coloring

\mathscr{C}

of the cubes of

\mathbf{H}^{2d,n}

by their dimension.

(b) The complex

(\mathbf{H}^{2d,n})^{\prime}

with its vertices colored by

\mathscr{C}^{\prime}_{0}

.

(c) The complex

(\mathbf{H}^{2d,n})^{\prime\prime}

with its vertices in

\mathscr{V}

colored by

\mathscr{C}^{\prime\prime}_{\mathscr{V}}

.

(d) The coloring

\mathscr{C}^{\prime\prime}

near the upper left corner of

(\mathbf{H}^{2d,n})^{\prime\prime}

. The four larger disks represent vertices that belong to

\mathscr{V}

.

(e) The coloring

\mathscr{C}^{\prime\prime}

restricted to the

d

-simplices of

(\mathbf{H}^{2d,n})^{\prime\prime}

. The color classes correspond to the families

\mathscr{F}_{0}

,

\mathscr{F}_{1}

and

\mathscr{F}_{2}

.

(f)

\mathscr{C}^{\prime\prime}

The trigraph

G_{d,n}^{\ast}

obtained from

G_{d,n}

by contracting each subtrigraph

C_{i,c}

to a single node. All edges in

G_{d,n}^{\ast}

are red.

Figure 5: (a)–(c) Illustrations of the cubical complex

\mathbf{H}^{2d,n}

for

d=1

and

n=4

, and of its first and second barycentric subdivisions (which are simplicial complexes) displaying the colorings described in the proof of Theorem 17. (d)–(f) Three essential steps in the proof of Theorem 17.

The first epoch.

We start the description of the first epoch $\mathfrak{S}_{1}\colon G_{d,n}\leadsto G_{d,n}^{\ast}$ by considering the restriction $\mathscr{C}^{\prime\prime}_{d}\colon(\mathbf{H}^{2d,n})^{\prime\prime}(d)% \rightarrow\{0,\ldots,2d\}$ of the coloring $\mathscr{C}^{\prime\prime}$ to the $d$ -simplices of $(\mathbf{H}^{2d,n})^{\prime\prime}$ , see Figure 5. Note that for each $i\in\{0,\ldots,2d\}$ , the $i$ -colored $d$ -simplices of $(\mathbf{H}^{2d,n})^{\prime\prime}$ form a family $\mathscr{F}_{i}=\{F_{i,c}:c\in\mathbf{H}^{2d,n}(i)\}$ of pairwise-disjoint connected subcomplexes of the $d$ -skeleton of $(\mathbf{H}^{2d,n})^{\prime\prime}$ , where $F_{i,c}$ denotes the subcomplex induced by the $i$ -colored $d$ -simplices of $(\mathbf{H}^{2d,n})^{\prime\prime}$ belonging to the closed star of the vertex $\iota(v_{c})$ , where $v_{c}$ is the vertex of $(\mathbf{H}^{2d,n})^{\prime}$ corresponding to the $i$ -cube $c$ in $\mathbf{H}^{2d,n}$ (Figure 5). We also let $\mathscr{F}=\bigcup_{i=0}^{2d}\mathscr{F}_{i}$ .

Since $G_{d,n}$ is defined as the dual graph of the $d$ -skeleton of $(\mathbf{H}^{2d,n})^{\prime\prime}$ , the nodes of $G_{d,n}$ are in one-to-one correspondence with the $d$ -simplices of $(\mathbf{H}^{2d,n})^{\prime\prime}$ . Let $\gamma\colon(\mathbf{H}^{2d,n})^{\prime\prime}(d)\rightarrow V(G_{d,n})$ denote the bijection realizing this correspondence. Henceforth, by a slight abuse of notation, we also consider $\mathscr{C}^{\prime\prime}_{d}$ to be a $(2d+1)$ -coloring of $V(G_{d,n})$ via $\mathscr{C}^{\prime\prime}_{d}(v)=\mathscr{C}^{\prime\prime}_{d}(\gamma^{-1}(v))$ . Let $C_{i,c}$ denote the subtrigraph of $G_{d,n}$ induced by the nodes $\{\gamma(\sigma):\sigma\in F_{i,c}\}$ . Note that $\mathscr{C}^{\prime\prime}_{d}$ assigns the color $i$ to all nodes of $C_{i,c}$ . The first epoch $\mathfrak{S}_{1}\colon G_{d,n}\leadsto G_{d,n}^{\ast}$ is merely the contraction sequence, where we contract each $C_{i,c}$ (where $0\leqslant i\leqslant 2d$ and $c$ is running over $\mathbf{H}^{2d,n}$ ) to a single node, in any order, obtaining a trigraph $G_{d,n}^{\ast}$ (Figure 5).

The second epoch.

$\mathfrak{S}_{2}\colon G_{d,n}^{\ast}\leadsto\bullet$ is defined as an optimal contraction sequence of the trigraph $G_{d,n}^{\ast}$ to a single vertex. Since $G_{d,n}^{\ast}$ is a subtrigraph of $\operatorname{red}(D_{n,2d})$ , the $2d$ -dimensional red $n$ -grid with diagonals, by Theorem 9 the width of $\mathfrak{S}_{2}$ is at most $2(3^{2d}-1)$ .

Bounding the width of the first epoch.

We now give a rough estimate to show that the first epoch $\mathfrak{S}_{1}\colon G_{d,n}\leadsto G_{d,n}^{\ast}$ is a $d^{O(d)}$ -contraction sequence. The estimate is based on Claim 18 below, which follows from elementary properties of the hypercubic honeycomb and barycentric subdivisions.

Claim 18.

For any color $i\in\{0,\ldots,2d\}$ and cube $c\in\mathbf{H}^{2d,n}$ , the subcomplex $F_{i,c}$ of $\mathbf{H}^{2d,n}$ (resp. the subtrigraph $C_{i,c}$ of $G_{d,n}$ ) defined above

1.

has less than $h_{1}(d)=4^{d}((2d)!)^{2}\binom{2d}{d}$ $d$ -simplices (resp. nodes), and
2.

less than $h_{2}(d)=9^{d}$ incident subcomplexes $F_{i^{\prime},c^{\prime}}\in\mathscr{F}$ (resp. adjacent subtrigraphs $C_{i^{\prime},c^{\prime}}$ ).

Indeed, these two facts imply that by sequentially contracting each $C_{i,c}$ into a single node, the maximum red degree remains bounded by $O(h_{1}(d)^{3}h_{2}(d))$ throughout the first epoch.

Proof of Claim 18.

To bound the number of $d$ -simplices in $F_{i,c}$ , note that

$\blacksquare$

$F_{i,c}$ is covered by an appropriate translate of a $2d$ -dimensional cube of $\mathbf{H}^{2d}$ ,
$\blacksquare$

the barycentric subdivision of a $2d$ -cube contains $2^{2d}(2d)!$ $2d$ -simplices (Observation 12),
$\blacksquare$

the barycentric subdivision of a $2d$ -simplex contains $(2d)!$ $2d$ -simplices (Observation 11),
$\blacksquare$

a $2d$ -simplex has $\binom{2d}{d}$ faces of dimension $d$ (Observation 10).

Multiplying these numbers, we obtain the first part of the claim.

To bound the number of subcomplexes $F_{i^{\prime},c^{\prime}}\in\mathscr{F}$ incident to $F_{i,c}$ , note that the incidences between these subcomplexes reflect those between the handles in the canonical handle decomposition of $\mathbf{H}^{2d,n}$ obtained by “thickening up” its cubical cells. Thus, the number of subcomplexes in $\mathscr{F}$ incident to $F_{i,c}$ equals $3^{2d}-1$ if $i\in\{0,2d\}$ and $3^{i}+3^{2d-i}-2$ otherwise. Both of these numbers are less than $9^{d}$ , so the second part of the claim also holds. $\hfill\vartriangleleft$

The width of $\mathfrak{S}$ is the maximum of the widths of $\mathfrak{S}_{1}$ and $\mathfrak{S}_{2}$ , hence $\operatorname{tww}(G_{d,n})\leqslant d^{O(d)}$ . $\hfill\blacktriangleleft$

5 Triangulations with dual graph of arbitrary large twin-width

In Section 4 we showed that every compact, smooth $d$ -manifold admits a triangulation with dual graph of twin-width at most $d^{O(d)}$ . In this section we prove complementary results, showing that triangulations with dual graphs of large twin-width are abundant. We shed light on this fact in two ways. First, we show that for any fixed dimension $d\geqslant 3$ , the class of $(d+1)$ -regular graphs that can be dual graphs of triangulated $d$ -manifolds is not small. Second, we show that the $d$ -dimensional ball admits triangulations with a dual graph of arbitrarily large twin-width, which extends to every piecewise-linear (hence smooth) $d$ -manifold. Both of these results rely on counting arguments, and thus are not constructive.

5.1 The class of dual graphs of triangulations is not small

Let us fix an integer $d\geqslant 3$ . Following [21], we let $M_{d}(n)$ denote the number of colored¹⁸¹⁸18We refer to [21, Section 2.1] for the precise definitions. triangulations of closed orientable $d$ -dimensional manifolds consisting of $n$ $d$ -simplices labeled from $1$ to $n$ . We assume $n$ to be even. By [21, Theorem 1.1] we have¹⁹¹⁹19Here “ $\preceq$ ” denotes a comparison where exponential factors are ignored: more precisely, $f(n)\preceq g(n)$ means that there exists some constant $K>0$ , such that for $n$ large enough, we have $f(n)\leqslant K^{n}g(n)$ .

\displaystyle n!\cdot n^{n/(2d)}\preceq M_{d}(n).

(5)

Ignoring the colors gives an uncolored triangulation, but any such $d$ -dimensional triangulation can be obtained from $(d+1)!$ colored triangulations, since the $d+1$ colors can always be permuted. Now, any $(d+1)$ -regular graph $G$ with $n$ vertices can be the dual graph of at most $d!^{n(d+1)/2}$ different $d$ -dimensional triangulations. Indeed, if $G$ is the dual graph of some $d$ -dimensional triangulation, then each of the $n(d+1)/2$ edges of $G$ corresponds to a face gluing, i.e., an identification of two $(d-1)$ -dimensional simplices via a simplicial isomorphism, of which there are $d!$ many.²⁰²⁰20This is because a simplicial isomorphism between two $(d-1)$ -simplices $\sigma$ and $\tau$ is determined by a perfect matching between the $d$ vertices of $\sigma$ and the $d$ vertices of $\tau$ . Hence by (5), for the number $\Gamma_{d}(n)$ of $(d+1)$ -regular graphs on $n$ labeled vertices that are dual graphs of some $d$ -dimensional triangulations, we have

\displaystyle\frac{n!\cdot n^{n/(2d)}}{(d+1)!\cdot d!^{n(d+1)/2}}\preceq\Gamma% _{d}(n).

(6)

As the left-hand side of (6) grows super-exponentially in $n$ , the next theorem directly follows.

Theorem 19.

For every $d\geqslant 3$ , the class of $(d+1)$ -regular graphs that are dual graphs of triangulations of $d$ -manifolds is not small. In particular, there are graphs with arbitrarily large twin-width in this class.

5.2 Complicated triangulations of the $\boldsymbol{d}$ -dimensional ball

In this section we show Theorem 3, according to which every piecewise-linear (PL) $d$ -manifold ( $d\geqslant 3$ ) admits triangulations with a dual graph of arbitrary large twin-width. To show the existence of such triangulations for every PL-manifold, we rely on the monotonicity of twin-width with respect to taking induced subtrigraphs (Proposition 5), the fact that the class of $d$ -subdivisions of $(d+1)$ -regular graphs is not small (Proposition 7) together with the following classical result from the theory of PL-manifolds. See [45] for an introduction.

Theorem 20 ([1, Corollary 1]).

Any triangulation of the boundary of a compact piecewise-linear (PL) manifold can be extended to a triangulation of the whole manifold.

We first show that already the $d$ -dimensional ball $\mathscr{B}^{d}=\{x\in\mathbb{R}^{d}:\|x\|\leqslant 1\}$ admits triangulations with dual graph of arbitrary large twin-width. More precisely, we prove:

Theorem 21.

For every $m\in\mathbb{N}$ there is a triangulation $\mathscr{T}_{m}$ of the $d$ -dimensional ball $\mathscr{B}^{d}$ , such that $\operatorname{tww}(\Gamma(\mathscr{T}_{m}))\geqslant m$ and $\partial\mathscr{T}_{m}=\partial\Delta^{d}$ , the boundary of the standard $d$ -simplex $\Delta^{d}$ .

Proof.

Let $G_{m}$ be a $d$ -subdivision of a $(d+1)$ -regular graph $G$ such that $\operatorname{tww}(G_{m})\geqslant m$ . The existence of such a graph is guaranteed by Proposition 7. Let $\mathscr{N}$ be a $d$ -manifold homeomorphic to a closed regular neighborhood of a straight-line embedding of $G$ in $\mathbb{R}^{d}$ . Informally, $\mathscr{N}$ can be seen as a $d$ -dimensional thickening of the graph $G$ .

Construct an abstract triangulation of $\mathscr{N}$ as follows. Take a $d$ -simplex $\sigma_{v}$ for each node $v$ of $G$ , and fix a one-to-one correspondence between the $d+1$ facets of $\sigma_{v}$ and the $d+1$ arcs incident to $v$ in $G$ . For every arc $\{u,v\}\in E(G)$ , take a simplicial $d$ -prism $P_{\{u,v\}}=\sigma_{\{u,v\}}\times[0,1]$ , where $\sigma_{\{u,v\}}$ is a $(d-1)$ -simplex, and attach $P_{\{u,v\}}$ to the simplices $\sigma_{u}$ and $\sigma_{v}$ by identifying $\sigma_{\{u,v\}}\times\{0\}$ (resp. $\sigma_{\{u,v\}}\times\{1\}$ ) with the facet of $\sigma_{u}$ (resp. $\sigma_{v}$ ) that corresponds to the arc $\{u,v\}$ . Now triangulate each prism $P_{\{u,v\}}$ with a minimal triangulation consisting of $d$ $d$ -simplices stacked onto each other, see [10, Appendix B].

Let $\mathscr{T}_{\mathscr{N}}$ denote the resulting triangulation of $\mathscr{N}$ .

Claim 22.

For the dual graph of the triangulation $\mathscr{T}_{\mathscr{N}}$ we have $\Gamma(\mathscr{T}_{\mathscr{N}})=G_{m}$ .

Proof.

The claim follows immediately from the facts that the dual graph of the constructed triangulation of the simplicial $d$ -prism is merely a path of length $d$ , and $G_{m}$ is the $d$ -subdivision of the $(d+1)$ -regular graph $G$ on which the triangulation $\mathscr{T}_{\mathscr{N}}$ is modeled. $\hfill\vartriangleleft$

Pick a sufficiently large $\ell\in\mathbb{N}$ such that the $\ell$ ^th iterated barycentric subdivision $\mathscr{T}_{\mathscr{N}}^{(\ell)}$ of $\mathscr{T}_{\mathscr{N}}$ embeds linearly in $\mathbb{R}^{d}$ and fix a simplex-wise linear embedding $\mathscr{E}\colon\|{\mathscr{T}_{\mathscr{N}}^{(\ell)}}\|\rightarrow\mathbb{R}% ^{d}$ . Consider a large geometric $d$ -simplex $\Sigma\subset\mathbb{R}^{d}$ that contains the image $\operatorname{im}(\mathscr{E})$ of $\mathscr{E}$ in its interior. Now $\Sigma_{\circ}=\Sigma\setminus\operatorname{int}(\operatorname{im}(\mathscr{E}))$ is a PL manifold²¹²¹21It is folklore that every codimension zero submanifold of a Euclidean space is a PL manifold, see, e.g., [34, p. 118] or [46, Remark 1.1.10]. with triangulated boundary, so by Theorem 20 this boundary triangulation can be extended to a triangulation $\mathscr{T}_{\Sigma_{\circ}}$ of the entire manifold $\Sigma_{\circ}$ . The boundary of $\mathscr{T}_{\Sigma_{\circ}}$ has two connected components: $\partial_{1}\mathscr{T}_{\Sigma_{\circ}}\cong\partial(\mathscr{T}_{\mathscr{N}% }^{(\ell)})$ and $\partial_{2}\mathscr{T}_{\Sigma_{\circ}}\cong\partial\Delta^{d}$ .

Let $\mathscr{Q}$ be a $d$ -manifold homeomorphic to $\partial\mathscr{T}_{\mathscr{N}}\times[0,1]$ . Take a triangulation $\mathscr{T}_{\mathscr{Q}}$ of $\mathscr{Q}$ , such that for the two boundary components we have $\partial_{1}\mathscr{T}_{\mathscr{Q}}\cong\partial\mathscr{T}_{\mathscr{N}}$ and $\partial_{2}\mathscr{T}_{\mathscr{Q}}\cong\partial(\mathscr{T}_{\mathscr{N}}^{% (\ell)})$ . One way to construct such a triangulation is as follows. First, consider the decomposition $\mathscr{P}_{\mathscr{Q}}$ of $\mathscr{Q}$ into simplicial $d$ -prisms induced by the product structure $\partial\mathscr{T}_{\mathscr{N}}\times[0,1]$ . That is, $\mathscr{P}_{\mathscr{Q}}$ consists of $d$ -prisms $P_{\sigma}\cong\sigma\times[0,1]$ , one for each $(d-1)$ -simplex $\sigma$ of $\partial\mathscr{T}_{\mathscr{N}}$ , glued together along their vertical boundary prisms the same way as the simplices of $\partial\mathscr{T}_{\mathscr{N}}$ . The boundary $\partial\mathscr{P}_{\mathscr{Q}}$ of $\mathscr{P}_{\mathscr{Q}}$ has two connected components: $\partial_{1}\mathscr{P}_{\mathscr{Q}}$ and $\partial_{2}\mathscr{P}_{\mathscr{Q}}$ , each combinatorially isomorphic to $\partial\mathscr{T}_{\mathscr{N}}$ . Next, pass to the $\ell$ ^th iterated barycentric subdivision of $\partial_{2}\mathscr{P}_{\mathscr{Q}}$ . This operation turns each prism $P_{\sigma}$ of $\mathscr{P}_{\mathscr{Q}}$ into a polyhedral cell $R_{\sigma}$ . These cells form a polyhedral decomposition $\mathscr{R}_{\mathscr{Q}}$ of $\mathscr{Q}$ , where $\partial_{1}\mathscr{R}_{\mathscr{Q}}\cong\partial\mathscr{T}_{\mathscr{N}}$ and $\partial_{2}\mathscr{R}_{\mathscr{Q}}\cong(\partial\mathscr{T}_{\mathscr{N}})^% {(\ell)}=\partial(\mathscr{T}_{\mathscr{N}}^{(\ell)})$ . Triangulate $R_{\sigma}$ as follows. Consider an order $c_{1}\prec c_{2}\prec\cdots$ of the vertical cells²²²²22These are precisely those cells that are not contained in the boundary of $\mathscr{R}_{\mathscr{Q}}$ . of $R_{\sigma}$ , where $c_{i}\prec c_{j}$ implies $\dim(c_{i})\leqslant\dim(c_{j})$ . Place a new vertex $v_{i}$ in the barycenter of $c_{i}$ and, iterating over the vertical cells in the above order, triangulate $c_{i}$ by coning from $v_{i}$ over its (already triangulated) boundary $\partial c_{i}$ . It is clear that the resulting triangulation of $R_{\sigma}$ is symmetric with respect to the symmetries of its base simplex $\sigma$ . Applying this procedure for each polyhedral cell $R_{\sigma}$ of $\mathscr{R}_{\mathscr{Q}}$ yields a triangulation $\mathscr{T}_{\mathscr{Q}}$ of $\mathscr{Q}$ with the desired properties.

Now the triangulation $\mathscr{T}_{m}$ of $\mathscr{B}^{d}$ is obtained by gluing together $\mathscr{T}_{\mathscr{N}}$ , $\mathscr{T}_{\mathscr{Q}}$ and $\mathscr{T}_{\Sigma_{\circ}}$ via the identity maps along the isomorphic boundary-pairs $\partial\mathscr{T}_{\mathscr{N}}\cong\partial_{1}\mathscr{T}_{\mathscr{Q}}$ and $\partial_{2}\mathscr{T}_{\mathscr{Q}}\cong\partial_{1}\mathscr{T}_{\Sigma_{% \circ}}$ .

To conclude, note that the $d$ -simplicies of $\mathscr{T}_{\mathscr{N}}$ triangulate a submanifold of $\|\mathscr{T}_{m}\|$ , hence by Proposition 13 the graph $\Gamma(\mathscr{T}_{\mathscr{N}})$ is an induced subgraph of $\Gamma(\mathscr{T}_{m})$ . By Claim 22, $\Gamma(\mathscr{T}_{\mathscr{N}})=G_{m}$ and by the initial assumption $\operatorname{tww}(G_{m})\geqslant m$ , hence by Proposition 5, $\Gamma(\mathscr{T}_{m})\geqslant m$ as well. $\hfill\blacktriangleleft$

Proof of Theorem 3.

Let $\mathscr{M}$ be an arbitrary PL-manifold possibly with non-empty boundary and $\mathscr{T}_{\circ}$ be a simplicial triangulation of $\mathscr{M}$ . Consider a triangulation $\mathscr{T}_{m}$ of the $d$ -ball with $\operatorname{tww}(\Gamma(\mathscr{T}_{m}))\geqslant m$ as in Theorem 21. Let $\Delta$ be a $d$ -simplex of $\mathscr{T}_{\circ}$ that is disjoint from $\partial\mathscr{M}$ (if $\mathscr{T}_{\circ}$ does not contain such a simplex, just replace $\mathscr{T}_{\circ}$ with its second barycentric subdivision). Since $\mathscr{T}_{\circ}$ is simplicial, $\Delta$ is embedded in $\mathscr{T}_{\circ}$ and is topologically a $d$ -ball. Now replace $\Delta$ with $\mathscr{T}_{m}$ by first removing $\Delta$ from $\mathscr{T}_{\circ}$ , thereby creating a boundary component isomorphic to $\partial\Delta$ , then gluing $\partial\mathscr{T}_{m}$ to this new boundary component via a simplicial isomorphism. (Note that this is possible since $\partial\mathscr{T}_{m}\cong\partial\Delta$ .) Let $\mathscr{T}$ denote the resulting triangulation of $\mathscr{M}$ . By Propositions 5 and 13, it follows that $\operatorname{tww}(\Gamma(\mathscr{T}))\geqslant\operatorname{tww}(\Gamma(% \mathscr{T}_{m}))\geqslant m$ . $\hfill\blacktriangleleft$

References

[1] M. A. Armstrong. Extending triangulations. Proc. Amer. Math. Soc., 18:701–704, 1967. doi:10.2307/2035442.
[2] B. Bagchi, B. A. Burton, B. Datta, N. Singh, and J. Spreer. Efficient algorithms to decide tightness. In 32nd Int. Symp. Comput. Geom. (SoCG 2016), volume 51 of LIPIcs. Leibniz Int. Proc. Inf., pages 12:1–12:15. Schloss Dagstuhl–Leibniz-Zent. Inf., 2016. doi:10.4230/LIPIcs.SoCG.2016.12.
[3] D. Bar-Natan. Fast Khovanov homology computations. J. Knot Theory Ramifications, 16(3):243–255, 2007. doi:10.1142/S0218216507005294.
[4] P. Bergé, É. Bonnet, H. Déprés, and R. Watrigant. Approximating highly inapproximable problems on graphs of bounded twin-width. In 40th Int. Symp. Theor. Aspects Comput. Sci. (STACS 2023), volume 254 of LIPIcs. Leibniz Int. Proc. Inform., pages 10:1–10:15. Schloss Dagstuhl. Leibniz-Zent. Inform., 2023. doi:10.4230/lipics.stacs.2023.10.
[5] J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken. Triangulating submanifolds: an elementary and quantified version of Whitney’s method. Discrete Comput. Geom., 66(1):386–434, 2021. doi:10.1007/s00454-020-00250-8.
[6] É. Bonnet. Twin-width and contraction sequences. Habilitation thesis, ENS de Lyon, April 2024. URL: https://perso.ens-lyon.fr/edouard.bonnet/text/hdr.pdf.
[7] É. Bonnet, D. Chakraborty, E. J. Kim, N. Köhler, R. Lopes, and S. Thomassé. Twin-width VIII: delineation and win-wins. In 17th Int. Symp. Parametr. Exact Comput. (IPEC 2022), volume 249 of LIPIcs. Leibniz Int. Proc. Inform., pages 9:1–9:18. Schloss Dagstuhl. Leibniz-Zent. Inform., 2022. doi:10.4230/LIPIcs.IPEC.2022.9.
[8] É. Bonnet, C. Geniet, E. J. Kim, S. Thomassé, and R. Watrigant. Twin-width III: max independent set, min dominating set, and coloring. In 48th Int. Colloq. Autom. Lang. Prog. (ICALP 2021), volume 198 of LIPIcs. Leibniz Int. Proc. Inform., pages 35:1–35:20. Schloss Dagstuhl. Leibniz-Zent. Inform., 2021. doi:10.4230/LIPIcs.ICALP.2021.35.
[9] É. Bonnet, C. Geniet, E. J. Kim, S. Thomassé, and R. Watrigant. Twin-width II: small classes. Comb. Theory, 2(2):Paper No. 10, 42, 2022. doi:10.5070/C62257876.
[10] É. Bonnet and K. Huszár. On the twin-width of smooth manifolds, 2024. arXiv:2407.10174.
[11] É. Bonnet, E. J. Kim, S. Thomassé, and R. Watrigant. Twin-width I: Tractable FO model checking. J. ACM, 69(1):Art. 3, 46, 2022. doi:10.1145/3486655.
[12] B. A. Burton. Computational topology with Regina: algorithms, heuristics and implementations. In Geometry and Topology Down Under, volume 597 of Contemp. Math., pages 195–224. Am. Math. Soc., Providence, RI, 2013. doi:10.1090/conm/597/11877.
[13] B. A. Burton. The HOMFLY-PT polynomial is fixed-parameter tractable. In 34th Int. Symp. Comput. Geom. (SoCG 2018), volume 99 of LIPIcs. Leibniz Int. Proc. Inform., pages 18:1–18:14. Schloss Dagstuhl–Leibniz-Zent. Inf., 2018. doi:10.4230/LIPIcs.SoCG.2018.18.
[14] B. A. Burton, R. Budney, W. Pettersson, et al. Regina: Software for low-dimensional topology, 1999–2023. Version 7.3. URL: https://regina-normal.github.io.
[15] B. A. Burton and R. G. Downey. Courcelle’s theorem for triangulations. J. Comb. Theory, Ser. A, 146:264–294, 2017. doi:10.1016/j.jcta.2016.10.001.
[16] B. A. Burton, H. Edelsbrunner, J. Erickson, and S. Tillmann, editors. Computational Geometric and Algebraic Topology, volume 12 of Oberwolfach Rep. EMS Publ. House, 2015. doi:10.4171/OWR/2015/45.
[17] B. A. Burton, T. Lewiner, J. Paixão, and J. Spreer. Parameterized complexity of discrete Morse theory. ACM Trans. Math. Softw., 42(1):6:1–6:24, 2016. doi:10.1145/2738034.
[18] B. A. Burton, C. Maria, and J. Spreer. Algorithms and complexity for Turaev–Viro invariants. J. Appl. Comput. Topol., 2(1–2):33–53, 2018. doi:10.1007/s41468-018-0016-2.
[19] B. A. Burton and W. Pettersson. Fixed parameter tractable algorithms in combinatorial topology. In Proc. 20th Int. Conf. Comput. Comb. (COCOON 2014), volume 8591 of Lect. Notes Comput. Sci., pages 300–311. Springer, 2014. doi:10.1007/978-3-319-08783-2_26.
[20] B. A. Burton and J. Spreer. The complexity of detecting taut angle structures on triangulations. In Proc. 24th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA 2013), pages 168–183, 2013. doi:10.1137/1.9781611973105.13.
[21] G. Chapuy and G. Perarnau. On the number of coloured triangulations of $d$ -manifolds. Discrete Comput. Geom., 65(3):601–617, 2021. doi:10.1007/s00454-020-00189-w.
[22] A. de Mesmay, J. Purcell, S. Schleimer, and E. Sedgwick. On the tree-width of knot diagrams. J. Comput. Geom., 10(1):164–180, 2019. doi:10.20382/jocg.v10i1a6.
[23] Z. Dvořák and S. Norine. Small graph classes and bounded expansion. J. Combin. Theory Ser. B, 100(2):171–175, 2010. doi:10.1016/j.jctb.2009.06.001.
[24] J. Gajarský, M. Pilipczuk, W. Przybyszewski, and Sz. Toruńczyk. Twin-width and types. In 49th Int. Conf. Autom. Lang. Prog. (ICALP 2022), volume 229 of LIPIcs. Leibniz Int. Proc. Inform., pages 123:1–123:21. Schloss Dagstuhl. Leibniz-Zent. Inform., 2022. doi:10.4230/lipics.icalp.2022.123.
[25] P. Hliněný and J. Jedelský. Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar. In 50th Int. Colloq. Autom. Lang. Prog. (ICALP 2023), volume 261 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 75, 18. Schloss Dagstuhl. Leibniz-Zent. Inform., 2023. doi:10.4230/lipics.icalp.2023.75.
[26] K. Huszár. Combinatorial width parameters for $3$ -dimensonal manifolds. PhD thesis, IST Austria, June 2020. doi:10.15479/AT:ISTA:8032.
[27] K. Huszár. On the pathwidth of hyperbolic 3-manifolds. Comput. Geom. Topol., 1(1):1–19, 2022. doi:10.57717/cgt.v1i1.4.
[28] K. Huszár and J. Spreer. 3-Manifold triangulations with small treewidth. In 35th Int. Symp. Comput. Geom. (SoCG 2019), volume 129 of LIPIcs. Leibniz Int. Proc. Inf., pages 44:1–44:20. Schloss Dagstuhl–Leibniz-Zent. Inf., 2019. doi:10.4230/LIPIcs.SoCG.2019.44.
[29] K. Huszár and J. Spreer. On the width of complicated JSJ decompositions. In 39th Int. Symp. Comput. Geom. (SoCG 2023), volume 258 of LIPIcs. Leibniz Int. Proc. Inf., pages 42:1–42:18. Schloss Dagstuhl–Leibniz-Zent. Inf., 2023. doi:10.4230/LIPIcs.SoCG.2023.42.
[30] K. Huszár, J. Spreer, and U. Wagner. On the treewidth of triangulated 3-manifolds. J. Comput. Geom., 10(2):70–98, 2019. doi:10.20382/jogc.v10i2a5.
[31] D. Kráľ and A. Lamaison. Planar graph with twin-width seven. Eur. J. Comb., page 103749, 2023. doi:10.1016/j.ejc.2023.103749.
[32] D. Kráľ, K. Pekárková, and K. Štorgel. Twin-Width of Graphs on Surfaces. In 49th Int. Symp. Math. Found. Comput. Sci. (MFCS 2024), volume 306 of LIPIcs. Leibniz Int. Proc. Inf., pages 66:1–66:15. Schloss Dagstuhl–Leibniz-Zent. Inf., 2024. doi:10.4230/LIPIcs.MFCS.2024.66.
[33] J. M. Lee. Introduction to smooth manifolds, volume 218 of Grad. Texts Math. Springer, New York, second edition, 2013. doi:10.1007/978-1-4419-9982-5.
[34] N. Levitt and A. Ranicki. Intrinsic transversality structures. Pacific J. Math., 129(1):85–144, 1987. doi:10.2140/pjm.1987.129.85.
[35] C. Lunel and A. de Mesmay. A Structural Approach to Tree Decompositions of Knots and Spatial Graphs. In 39th Int. Symp. Comput. Geom. (SoCG 2023), volume 258 of LIPIcs. Leibniz Int. Proc. Inf., pages 50:1–50:16. Schloss Dagstuhl–Leibniz-Zent. Inf., 2023. doi:10.4230/LIPIcs.SoCG.2023.50.
[36] J. A. Makowsky. Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Appl. Math., 145(2):276–290, 2005. doi:10.1016/j.dam.2004.01.016.
[37] J. A. Makowsky and J. P. Mariño. The parametrized complexity of knot polynomials. J. Comput. Syst. Sci., 67(4):742–756, 2003. Special issue on parameterized computation and complexity. doi:10.1016/S0022-0000(03)00080-1.
[38] C. Manolescu. Lectures on the triangulation conjecture. In Proc. 22nd Gökova Geom.-Topol. Conf. (GGT 2015), pages 1–38. Int. Press Boston, 2016. URL: https://gokovagt.org/proceedings/2015/manolescu.html.
[39] C. Maria. Parameterized complexity of quantum knot invariants. In 37th Int. Symp. Comput. Geom. (SoCG 2021), volume 189 of LIPIcs. Leibniz Int. Proc. Inf., pages 53:1–53:15. Schloss Dagstuhl–Leibniz-Zent. Inf., 2021. doi:10.4230/LIPIcs.SoCG.2021.53.
[40] C. Maria and J. Purcell. Treewidth, crushing and hyperbolic volume. Algebr. Geom. Topol., 19(5):2625–2652, 2019. doi:10.2140/agt.2019.19.2625.
[41] E. E. Moise. Affine structures in $3$ -manifolds. V. The triangulation theorem and Hauptvermutung. Ann. Math. (2), 56:96–114, 1952. doi:10.2307/1969769.
[42] M. Noy. Graphs. In Handbook of Enumerative Combinatorics, Discrete Math. Appl., pages 397–436. Chapman & Hall / CRC, 2015. doi:10.1201/b18255-12.
[43] V. V. Prasolov. Elements of combinatorial and differential topology, volume 74 of Grad. Stud. Math. Am. Math. Soc., Providence, RI, 2006. Translated from the 2004 Russian original by Olga Sipacheva. doi:10.1090/gsm/074.
[44] T. Radó. Über den Begriff der Riemannschen Fläche. Acta Sci. Math., 2(2):101–121, 1925.
[45] C. P. Rourke and B. J. Sanderson. Introduction to piecewise-linear topology. Springer Study Edition. Springer-Verlag, Berlin-New York, 1982. Reprint. doi:10.1007/978-3-642-81735-9.
[46] F. Waldhausen, B. Jahren, and J. Rognes. Spaces of PL manifolds and categories of simple maps, volume 186 of Annals Math. Stud. Princeton Univ. Press, Princeton, NJ, 2013. doi:10.1515/9781400846528.
[47] H. Whitney. The self-intersections of a smooth $n$ -manifold in $2n$ -space. Ann. of Math. (2), 45:220–246, 1944. doi:10.2307/1969265.
[48] H. Whitney. Geometric Integration Theory. Princeton Univ. Press, Princeton, NJ, 1957. doi:10.1515/9781400877577.

[bib.bib1] [1] M. A. Armstrong. Extending triangulations. Proc. Amer. Math. Soc., 18:701–704, 1967. doi:10.2307/2035442.

[bib.bib2] [2] B. Bagchi, B. A. Burton, B. Datta, N. Singh, and J. Spreer. Efficient algorithms to decide tightness. In 32nd Int. Symp. Comput. Geom. (SoCG 2016), volume 51 of LIPIcs. Leibniz Int. Proc. Inf., pages 12:1–12:15. Schloss Dagstuhl–Leibniz-Zent. Inf., 2016. doi:10.4230/LIPIcs.SoCG.2016.12.

[bib.bib3] [3] D. Bar-Natan. Fast Khovanov homology computations. J. Knot Theory Ramifications, 16(3):243–255, 2007. doi:10.1142/S0218216507005294.

[bib.bib4] [4] P. Bergé, É. Bonnet, H. Déprés, and R. Watrigant. Approximating highly inapproximable problems on graphs of bounded twin-width. In 40th Int. Symp. Theor. Aspects Comput. Sci. (STACS 2023), volume 254 of LIPIcs. Leibniz Int. Proc. Inform., pages 10:1–10:15. Schloss Dagstuhl. Leibniz-Zent. Inform., 2023. doi:10.4230/lipics.stacs.2023.10.

[bib.bib5] [5] J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken. Triangulating submanifolds: an elementary and quantified version of Whitney’s method. Discrete Comput. Geom., 66(1):386–434, 2021. doi:10.1007/s00454-020-00250-8.

[bib.bib6] [6] É. Bonnet. Twin-width and contraction sequences. Habilitation thesis, ENS de Lyon, April 2024. URL: https://perso.ens-lyon.fr/edouard.bonnet/text/hdr.pdf.

[bib.bib7] [7] É. Bonnet, D. Chakraborty, E. J. Kim, N. Köhler, R. Lopes, and S. Thomassé. Twin-width VIII: delineation and win-wins. In 17th Int. Symp. Parametr. Exact Comput. (IPEC 2022), volume 249 of LIPIcs. Leibniz Int. Proc. Inform., pages 9:1–9:18. Schloss Dagstuhl. Leibniz-Zent. Inform., 2022. doi:10.4230/LIPIcs.IPEC.2022.9.

[bib.bib8] [8] É. Bonnet, C. Geniet, E. J. Kim, S. Thomassé, and R. Watrigant. Twin-width III: max independent set, min dominating set, and coloring. In 48th Int. Colloq. Autom. Lang. Prog. (ICALP 2021), volume 198 of LIPIcs. Leibniz Int. Proc. Inform., pages 35:1–35:20. Schloss Dagstuhl. Leibniz-Zent. Inform., 2021. doi:10.4230/LIPIcs.ICALP.2021.35.

[bib.bib9] [9] É. Bonnet, C. Geniet, E. J. Kim, S. Thomassé, and R. Watrigant. Twin-width II: small classes. Comb. Theory, 2(2):Paper No. 10, 42, 2022. doi:10.5070/C62257876.

[bib.bib10] [10] É. Bonnet and K. Huszár. On the twin-width of smooth manifolds, 2024. arXiv:2407.10174.

[bib.bib11] [11] É. Bonnet, E. J. Kim, S. Thomassé, and R. Watrigant. Twin-width I: Tractable FO model checking. J. ACM, 69(1):Art. 3, 46, 2022. doi:10.1145/3486655.

[bib.bib12] [12] B. A. Burton. Computational topology with Regina: algorithms, heuristics and implementations. In Geometry and Topology Down Under, volume 597 of Contemp. Math., pages 195–224. Am. Math. Soc., Providence, RI, 2013. doi:10.1090/conm/597/11877.

[bib.bib13] [13] B. A. Burton. The HOMFLY-PT polynomial is fixed-parameter tractable. In 34th Int. Symp. Comput. Geom. (SoCG 2018), volume 99 of LIPIcs. Leibniz Int. Proc. Inform., pages 18:1–18:14. Schloss Dagstuhl–Leibniz-Zent. Inf., 2018. doi:10.4230/LIPIcs.SoCG.2018.18.

[bib.bib14] [14] B. A. Burton, R. Budney, W. Pettersson, et al. Regina: Software for low-dimensional topology, 1999–2023. Version 7.3. URL: https://regina-normal.github.io.

[bib.bib15] [15] B. A. Burton and R. G. Downey. Courcelle’s theorem for triangulations. J. Comb. Theory, Ser. A, 146:264–294, 2017. doi:10.1016/j.jcta.2016.10.001.

[bib.bib16] [16] B. A. Burton, H. Edelsbrunner, J. Erickson, and S. Tillmann, editors. Computational Geometric and Algebraic Topology, volume 12 of Oberwolfach Rep. EMS Publ. House, 2015. doi:10.4171/OWR/2015/45.

[bib.bib17] [17] B. A. Burton, T. Lewiner, J. Paixão, and J. Spreer. Parameterized complexity of discrete Morse theory. ACM Trans. Math. Softw., 42(1):6:1–6:24, 2016. doi:10.1145/2738034.

[bib.bib18] [18] B. A. Burton, C. Maria, and J. Spreer. Algorithms and complexity for Turaev–Viro invariants. J. Appl. Comput. Topol., 2(1–2):33–53, 2018. doi:10.1007/s41468-018-0016-2.

[bib.bib19] [19] B. A. Burton and W. Pettersson. Fixed parameter tractable algorithms in combinatorial topology. In Proc. 20th Int. Conf. Comput. Comb. (COCOON 2014), volume 8591 of Lect. Notes Comput. Sci., pages 300–311. Springer, 2014. doi:10.1007/978-3-319-08783-2_26.

[bib.bib20] [20] B. A. Burton and J. Spreer. The complexity of detecting taut angle structures on triangulations. In Proc. 24th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA 2013), pages 168–183, 2013. doi:10.1137/1.9781611973105.13.

[bib.bib21] [21] G. Chapuy and G. Perarnau. On the number of coloured triangulations of $d$ -manifolds. Discrete Comput. Geom., 65(3):601–617, 2021. doi:10.1007/s00454-020-00189-w.

[bib.bib22] [22] A. de Mesmay, J. Purcell, S. Schleimer, and E. Sedgwick. On the tree-width of knot diagrams. J. Comput. Geom., 10(1):164–180, 2019. doi:10.20382/jocg.v10i1a6.

[bib.bib23] [23] Z. Dvořák and S. Norine. Small graph classes and bounded expansion. J. Combin. Theory Ser. B, 100(2):171–175, 2010. doi:10.1016/j.jctb.2009.06.001.

[bib.bib24] [24] J. Gajarský, M. Pilipczuk, W. Przybyszewski, and Sz. Toruńczyk. Twin-width and types. In 49th Int. Conf. Autom. Lang. Prog. (ICALP 2022), volume 229 of LIPIcs. Leibniz Int. Proc. Inform., pages 123:1–123:21. Schloss Dagstuhl. Leibniz-Zent. Inform., 2022. doi:10.4230/lipics.icalp.2022.123.

[bib.bib25] [25] P. Hliněný and J. Jedelský. Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar. In 50th Int. Colloq. Autom. Lang. Prog. (ICALP 2023), volume 261 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 75, 18. Schloss Dagstuhl. Leibniz-Zent. Inform., 2023. doi:10.4230/lipics.icalp.2023.75.

[bib.bib26] [26] K. Huszár. Combinatorial width parameters for $3$ -dimensonal manifolds. PhD thesis, IST Austria, June 2020. doi:10.15479/AT:ISTA:8032.

[bib.bib27] [27] K. Huszár. On the pathwidth of hyperbolic 3-manifolds. Comput. Geom. Topol., 1(1):1–19, 2022. doi:10.57717/cgt.v1i1.4.

[bib.bib28] [28] K. Huszár and J. Spreer. 3-Manifold triangulations with small treewidth. In 35th Int. Symp. Comput. Geom. (SoCG 2019), volume 129 of LIPIcs. Leibniz Int. Proc. Inf., pages 44:1–44:20. Schloss Dagstuhl–Leibniz-Zent. Inf., 2019. doi:10.4230/LIPIcs.SoCG.2019.44.

[bib.bib29] [29] K. Huszár and J. Spreer. On the width of complicated JSJ decompositions. In 39th Int. Symp. Comput. Geom. (SoCG 2023), volume 258 of LIPIcs. Leibniz Int. Proc. Inf., pages 42:1–42:18. Schloss Dagstuhl–Leibniz-Zent. Inf., 2023. doi:10.4230/LIPIcs.SoCG.2023.42.

[bib.bib30] [30] K. Huszár, J. Spreer, and U. Wagner. On the treewidth of triangulated 3-manifolds. J. Comput. Geom., 10(2):70–98, 2019. doi:10.20382/jogc.v10i2a5.

[bib.bib31] [31] D. Kráľ and A. Lamaison. Planar graph with twin-width seven. Eur. J. Comb., page 103749, 2023. doi:10.1016/j.ejc.2023.103749.

[bib.bib32] [32] D. Kráľ, K. Pekárková, and K. Štorgel. Twin-Width of Graphs on Surfaces. In 49th Int. Symp. Math. Found. Comput. Sci. (MFCS 2024), volume 306 of LIPIcs. Leibniz Int. Proc. Inf., pages 66:1–66:15. Schloss Dagstuhl–Leibniz-Zent. Inf., 2024. doi:10.4230/LIPIcs.MFCS.2024.66.

[bib.bib33] [33] J. M. Lee. Introduction to smooth manifolds, volume 218 of Grad. Texts Math. Springer, New York, second edition, 2013. doi:10.1007/978-1-4419-9982-5.

[bib.bib34] [34] N. Levitt and A. Ranicki. Intrinsic transversality structures. Pacific J. Math., 129(1):85–144, 1987. doi:10.2140/pjm.1987.129.85.

[bib.bib35] [35] C. Lunel and A. de Mesmay. A Structural Approach to Tree Decompositions of Knots and Spatial Graphs. In 39th Int. Symp. Comput. Geom. (SoCG 2023), volume 258 of LIPIcs. Leibniz Int. Proc. Inf., pages 50:1–50:16. Schloss Dagstuhl–Leibniz-Zent. Inf., 2023. doi:10.4230/LIPIcs.SoCG.2023.50.

[bib.bib36] [36] J. A. Makowsky. Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Appl. Math., 145(2):276–290, 2005. doi:10.1016/j.dam.2004.01.016.

[bib.bib37] [37] J. A. Makowsky and J. P. Mariño. The parametrized complexity of knot polynomials. J. Comput. Syst. Sci., 67(4):742–756, 2003. Special issue on parameterized computation and complexity. doi:10.1016/S0022-0000(03)00080-1.

[bib.bib38] [38] C. Manolescu. Lectures on the triangulation conjecture. In Proc. 22nd Gökova Geom.-Topol. Conf. (GGT 2015), pages 1–38. Int. Press Boston, 2016. URL: https://gokovagt.org/proceedings/2015/manolescu.html.

[bib.bib39] [39] C. Maria. Parameterized complexity of quantum knot invariants. In 37th Int. Symp. Comput. Geom. (SoCG 2021), volume 189 of LIPIcs. Leibniz Int. Proc. Inf., pages 53:1–53:15. Schloss Dagstuhl–Leibniz-Zent. Inf., 2021. doi:10.4230/LIPIcs.SoCG.2021.53.

[bib.bib40] [40] C. Maria and J. Purcell. Treewidth, crushing and hyperbolic volume. Algebr. Geom. Topol., 19(5):2625–2652, 2019. doi:10.2140/agt.2019.19.2625.

[bib.bib41] [41] E. E. Moise. Affine structures in $3$ -manifolds. V. The triangulation theorem and Hauptvermutung. Ann. Math. (2), 56:96–114, 1952. doi:10.2307/1969769.

[bib.bib42] [42] M. Noy. Graphs. In Handbook of Enumerative Combinatorics, Discrete Math. Appl., pages 397–436. Chapman & Hall / CRC, 2015. doi:10.1201/b18255-12.

[bib.bib43] [43] V. V. Prasolov. Elements of combinatorial and differential topology, volume 74 of Grad. Stud. Math. Am. Math. Soc., Providence, RI, 2006. Translated from the 2004 Russian original by Olga Sipacheva. doi:10.1090/gsm/074.

[bib.bib44] [44] T. Radó. Über den Begriff der Riemannschen Fläche. Acta Sci. Math., 2(2):101–121, 1925.

[bib.bib45] [45] C. P. Rourke and B. J. Sanderson. Introduction to piecewise-linear topology. Springer Study Edition. Springer-Verlag, Berlin-New York, 1982. Reprint. doi:10.1007/978-3-642-81735-9.

[bib.bib46] [46] F. Waldhausen, B. Jahren, and J. Rognes. Spaces of PL manifolds and categories of simple maps, volume 186 of Annals Math. Stud. Princeton Univ. Press, Princeton, NJ, 2013. doi:10.1515/9781400846528.

[bib.bib47] [47] H. Whitney. The self-intersections of a smooth $n$ -manifold in $2n$ -space. Ann. of Math. (2), 45:220–246, 1944. doi:10.2307/1969265.

[bib.bib48] [48] H. Whitney. Geometric Integration Theory. Princeton Univ. Press, Princeton, NJ, 1957. doi:10.1515/9781400877577.

On the Twin-Width of Smooth Manifolds

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

Corollary 2.

Theorem 3.

▶ Remark 4.

Outline of the paper.

2 Preliminaries

Basic notation.

2.1 Trigraphs, contraction sequences and twin-width

Trigraphs.

Contraction sequences and twin-width.

Some properties of twin-width; grid graphs

Proposition 5.

Smallness.

Theorem 6 ([9, Theorem 2.5]).

Proposition 7.

Proof of Proposition 7.

Grid graphs.

Theorem 8 (Theorem 4 in [11]).

Theorem 9 (Lemma 4.4 in [11]).

2.2 Background in topology

2.2.1 Simplicial and cubical complexes

Abstract simplicial complexes.

Geometric realization of simplicial complexes.

Cubical complexes.

The hypercubic honeycomb.

Pure complexes and their dual graphs.

2.2.2 Barycentric subdivisions

Observation 10.

Observation 11.

Observation 12.

2.2.3 Manifolds and their triangulations

Smooth manifolds.

Triangulations.

Proposition 13.

3 Whitney’s method

Theorem 14 (strong Whitney embedding theorem [47, Theorem 5], cf. [33, Theorem 6.19]).

Theorem 15 (triangulation theorem [48, Chapter IV.B], cf. [5, Theorem 1.1]).

Triangulating smooth manifolds.

Proposition 16.

4 The proof of Theorem 1

Theorem 17.

Proof of Theorem 1.

Proof of Theorem 17.

Preparations.

The first epoch.

The second epoch.

Bounding the width of the first epoch.

Claim 18.

Proof of Claim 18.

5 Triangulations with dual graph of arbitrary large twin-width

5.1 The class of dual graphs of triangulations is not small

Theorem 19.

5.2 Complicated triangulations of the 𝒅-dimensional ball

Theorem 20 ([1, Corollary 1]).

Theorem 21.

Proof.

Claim 22.

Proof.

Proof of Theorem 3.

References

$\blacktriangleright$ Remark 4.

5.2 Complicated triangulations of the $\boldsymbol{d}$ -dimensional ball