Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants

DOI10.4230/LIPICS.ESA.2016.64zbMATH Open1397.68205arXiv1512.04648MaRDI QIDQ4606336FDOQ4606336

Jonathan Spreer, Clément Maria

Publication date: 2 March 2018

Abstract: Turaev Viro invariants are amongst the most powerful tools to distinguish 3-manifolds: They are implemented in mathematical software, and allow practical computations. The invariants can be computed purely combinatorially by enumerating colourings on the edges of a triangulation T. These edge colourings can be interpreted as embeddings of surfaces in T. We give a characterisation of how these embedded surfaces intersect with the tetrahedra of T. This is done by characterising isotopy classes of simple closed loops in the 3-punctured disk. As a direct result we obtain a new system of coordinates for edge colourings which allows for simpler definitions of the tetrahedron weights incorporated in the Turaev-Viro invariants. Moreover, building on a detailed analysis of the colourings, as well as classical work due to Kirby and Melvin, Matveev, and others, we show that considering a much smaller set of colourings suffices to compute Turaev-Viro invariants in certain significant cases. This results in a substantial improvement of running times to compute the invariants, reducing the number of colourings to consider by a factor of $2^n$. In addition, we present an algorithm to compute Turaev-Viro invariants of degree four -- a problem known to be #P-hard -- which capitalises on the combinatorial structure of the input. The improved algorithms are shown to be optimal in the following sense: There exist triangulations admitting all colourings the algorithms consider. Furthermore, we demonstrate that our new algorithms to compute Turaev-Viro invariants are able to distinguish the majority of $mathbbZ$-homology spheres with complexity up to $11$ in $O(2^n)$ operations in $mathbbQ$.

Full work available at URL: https://arxiv.org/abs/1512.04648

Recommendations

• Algorithms and complexity for Turaev-Viro invariants
• Algorithms and complexity for Turaev-Viro invariants
• A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
• On Colored Turaev-Viro Invariants for Links in Arbitrary 3-Manifolds
• A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number

zbMATH Keywords

low-dimensional topologycombinatorial algorithmsTuraev-Viro invariantscohomology theorytriangulations of 3-manifolds

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Triangulating manifolds (57Q15)

Cited In (2)

• A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
• Period collapse in Ehrhart quasi-polynomials of \(\{1,3\}\)-graphs

Uses Software

• Regina

This page was built for publication: Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606336)