Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlgorithms and complexity for Turaev-Viro invariants
145
0
0.0
(
0
)
Added by
Jonathan Spreer
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Turaev-Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. The invariants are parameterised by an integer $r geq 3$. We resolve the question of complexity for $r=3$ and $r=4$, giving simple proofs that computing Turaev-Viro invariants for $r=3$ is polynomial time, but for $r=4$ is #P-hard. Moreover, we give an explicit fixed-parameter tractable algorithm for arbitrary $r$, and show through concrete implementation and experimentation that this algorithm is practical---and indeed preferable---to the prior state of the art for real computation.
rate research
Read More
In this paper, we show that the Turaev-Viro invariant volume conjecture posed by Chen and Yang is preserved under gluings of toroidal boundary components for a family of $3$-manifolds. In particular, we show that the asymptotics of the Turaev-Viro invariants are additive under certain gluings of elementary pieces arising from a construction of hyperbolic cusped $3$-manifolds due to Agol. The gluings of the elementary pieces are known to be additive with respect to the simplicial volume. This allows us to construct families of manifolds with an arbitrary number of hyperbolic pieces such that the resultant manifolds satisfy an extended version of the Turaev-Viro invariant volume conjecture.
Goussarov, Polyak, and Viro proved that finite type invariants of knots are ``finitely multi-local, meaning that on a knot diagram, sums of quantities, defined by local information, determine the value of the knot invariant. The result implies the existence of Gauss diagram combinatorial formulas for finite type invariants. This article presents a simplified account of the original approach. The simplifications provide an easy generalization to the cases of pure tangles and pure braids. The associated problem on group algebras is introduced and used to prove the existence of ``multi-local word formulas for finite type invariants of pure braids.
The U(1) BF Quantum Field Theory is revisited in the light of Deligne-Beilinson Cohomology. We show how the U(1) Chern-Simons partition function is related to the BF one and how the latter on its turn coincides with an abelian Turaev-Viro invariant. Significant differences compared to the non-abelian case are highlighted.
We identify the leading order term of the asymptotic expansion of the Witten-Reshetikhin-Turaev invariants for finite order mapping tori with classical invariants for all simple and simply-connected compact Lie groups. The square root of the Reidemeister torsion is used as a density on the moduli space of flat connections and the leading order term is identified with the integral over this moduli space of this density weighted by a certain phase for each component of the moduli space. We also identify this phase in terms of classical invariants such as Chern-Simons invariants, eta invariants, spectral flow and the rho invariant. As a result, we show agreement with the semiclassical approximation as predicted by the method of stationary phase.
Consider a graph with a rotation system, namely, for every vertex, a circular ordering of the incident edges. Given such a graph, an angle cover maps every vertex to a pair of consecutive edges in the ordering -- an angle -- such that each edge participates in at least one such pair. We show that any graph of maximum degree 4 admits an angle cover, give a poly-time algorithm for deciding if a graph with no degree-3 vertices has an angle-cover, and prove that, given a graph of maximum degree 5, it is NP-hard to decide whether it admits an angle cover. We also consider extensions of the angle cover problem where every vertex selects a fixed number $a>1$ of angles or where an angle consists of more than two consecutive edges. We show an application of angle covers to the problem of deciding if the 2-blowup of a planar graph has isomorphic thickness 2.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
