اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAlgorithms and complexity for Turaev-Viro invariants
146
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 in
variants 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 ex
istence 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 Reidemei
ster 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 parti
cipates 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
