On the pathwidth of hyperbolic 3-manifolds

Sur la largeur arborescente linéaire des 3-variétés hyperboliques

Kristóf Huszár (1)

1 DATASHAPE - Understanding the Shape of Data

According to Mostow's celebrated rigidity theorem, the geometry of closed hyperbolic 3-manifolds is already determined by their topology. In particular, the volume of such manifolds is a topological invariant and, as such, has been investigated for half a century. Motivated by the algorithmic study of 3-manifolds, Maria and Purcell have recently shown that every closed hyperbolic 3-manifold M with volume vol(M) admits a triangulation with dual graph of treewidth at most C vol(M), for some universal constant C. Here we improve on this result by showing that the volume provides a linear upper bound even on the pathwidth of the dual graph of some triangulation, which can potentially be much larger than the treewidth. Our proof relies on a synthesis of tools from 3-manifold theory: generalized Heegaard splittings, amalgamations, and the thick-thin decomposition of hyperbolic 3-manifolds. We provide an illustrated exposition of this toolbox and also discuss the algorithmic consequences of the result.

Selon le célèbre théorème de rigidité de Mostow, la géométrie des 3-variétés hyperboliques fermées est entièrement déterminée par leur topologie. En particulier, le volume de ces variétés est un invariant topologique et, en tant que tel, a été étudié pendant un demi-siècle. Motivés par l'étude algorithmique des 3-variétés, Maria et Purcell ont récemment montré que toute 3-variété hyperbolique fermée M avec un volume vol(M) admet une triangulation avec un graphe dual de largeur arborescente au plus C vol(M), pour une certaine constante universelle C. Ici, nous améliorons ce résultat en montrant qu'une fonction linéaire du volume fournit une borne supérieure à la largeur arborescente linéaire du graphe dual d'une certaine triangulation, qui peut potentiellement être beaucoup plus grande que la largeur arborescente (non-linéaire). Notre preuve s'appuie sur une synthèse d'outils issus de la théorie des 3-variétés : les divisions de Heegaard généralisées, les amalgames et la décomposition épaisse-fine des 3-variétés hyperboliques. Nous fournissons une exposition illustrée de cette boîte à outils et discutons également des conséquences algorithmiques de ce résultat.

Mots clés: thick-thin decomposition; volume; computational 3-manifold topology; fixed-parameter tractability; generalized Heegaard splittings; pathwidth; treewidth; hyperbolic 3-manifolds

Mots clés: topologie algorithmique des 3-variétés; complexité paramétrée; solubilité à paramètre fixé; divisions de Heegaard généralisées; largeur arborescente linéaire; largeur arborescente; 3-variétés hyperboliques; décomposition épaisse-fine; volume

Domaines: Topologie géométrique [math.GT]; Géométrie algorithmique [cs.CG]

Kristóf Huszár. On the pathwidth of hyperbolic 3-manifolds. Computing in Geometry and Topology, 2022, 1 (1), pp.1:1-1:19. ⟨10.57717/cgt.v1i1.4⟩. ⟨hal-03373577⟩