A polynomial-time algorithm to compute Turaev-Viro invariants TV₄,q of 3-manifolds with bounded first Betti number
Let \({\mathfrak T}\) be a generalized triangulation of a closed 3-manifold \(M\). That is, \(M\) is homeomorphic to a collection of \(n\) tetrahedra glued together along their triangular faces. For an integer \(r\), a coloring of \({\mathfrak T}\) assigns a non-negative integer or half-integer of at most \((r-2)/2\) to each edge. It is admissible if for any triangle, the sum of edge colors is an integer of at most \(r-2\), and each edge color is bounded by the sum of its opposite edge colors. Let \(\mathrm{Adm}({\mathfrak T},r)\) denote the set of all such colorings. For each positive integer \(q\), with \(q\leq 2r\) and relatively prime to \(r\), \textit{V. G. Turaev} and \textit{O. Y. Viro} [Topology 31, No. 4, 865--902 (1992; Zbl 0779.57009)] devised a way of assigning a weight \(|{\mathfrak T}|_\theta\) to a coloring \(\theta\), whose specific value depends on \(r\) and \(q\), such that the sum \(TV_{r,q}\doteq\sum_{\theta\in\mathrm{Adm}({\mathfrak T},r)}|{\mathfrak T}|_\theta\) is a topological invariant. The authors of the article provide an algorithm for computing \(TV_{4,q}\) under the assumption that \({\mathfrak T}\) has only a single vertex (any generalized triangulation can be modified to a single vertex one using a polynomial-time algorithm). In this case, a coloring \(\theta\in\mathrm{ Adm}({\mathfrak T},3)\) defines a unique class in the first cohomology group of \(M\) with coefficients in \({\mathbb Z}_2\), the field of two elements. In particular, the number of colorings in \(\mathrm{Adm}({\mathfrak T},3)\) is equal to \(2^{\beta_1}\), where \(\beta_1\) is the first \({\mathbb Z}_2\)-Betti number of \(M\). On the other hand, any coloring \(\hat\theta\in\mathrm{Adm}({\mathfrak T},4)\) induces a coloring \(\theta\in\mathrm{Adm}({\mathfrak T},3)\), and the authors provide a formula for the weight \(|{\mathfrak T}|_{\hat\theta}\) in terms of \(\theta\) and the combinatorics of \({\mathfrak T}\). The resulting algorithm computes \(TV_{4,q}\) in \(O(n^3\,2^{\beta_1})\) time.
- A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
- Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
- Algorithms and complexity for Turaev-Viro invariants
- Algorithms and complexity for Turaev-Viro invariants
- Ideal Turaev-Viro invariants
- 0-efficient triangulations of 3-manifolds
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A new approach to crushing 3-manifold triangulations
- A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
- Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
- Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization
- Algorithmic topology and classification of 3-manifolds
- Algorithms and complexity for Turaev-Viro invariants
- Complexity classes as mathematical axioms
- Complexity of Finding Embeddings in a k-Tree
- Computational topology. An introduction
- Computing Turaev-Viro invariants for 3-manifolds
- Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
- scientific article; zbMATH DE number 412172 (Why is no real title available?)
- scientific article; zbMATH DE number 3149985 (Why is no real title available?)
- scientific article; zbMATH DE number 4046702 (Why is no real title available?)
- scientific article; zbMATH DE number 4100181 (Why is no real title available?)
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- scientific article; zbMATH DE number 7236450 (Why is no real title available?)
- scientific article; zbMATH DE number 2227021 (Why is no real title available?)
- Mod two homology and cohomology
- On the tree-width of knot diagrams
- On the treewidth of triangulated 3-manifolds
- Proper minor-closed families are small
- Quantum invariants of knots and 3-manifolds
- State sum invariants of 3-manifolds and quantum \(6j\)-symbols
- STRUCTURES OF SMALL CLOSED NON-ORIENTABLE 3-MANIFOLD TRIANGULATIONS
- Symmetries, Isometries and Length Spectra of Closed Hyperbolic Three-Manifolds
- The Absolute Value of The Chern-Simons-Witten Invariants of Lens Spaces
- The geometrization conjecture
- THE QUANTUM CONTENT OF THE NORMAL SURFACES IN A THREE-MANIFOLD
- Treewidth, crushing and hyperbolic volume
- Which lens spaces are distinguished by Turaev-Viro invariants
- Algorithms and complexity for Turaev-Viro invariants
- Algorithms and complexity for Turaev-Viro invariants
- A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
- Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
- On the pathwidth of hyperbolic 3-manifolds
- Parameterized complexity of quantum knot invariants
- An algorithm for Tambara-Yamagami quantum invariants of 3-manifolds, parameterized by the first Betti number
- Hardness of computation of quantum invariants on 3-manifolds with restricted topology
- Hardness of computation of quantum invariants on 3-manifolds with restricted topology
This page was built for publication: A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216247)
