ترغب بنشر مسار تعليمي؟ اضغط هنا

An edge-based framework for enumerating 3-manifold triangulations

126   0   0.0 ( 0 )
 نشر من قبل William Pettersson
 تاريخ النشر 2014
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

A typical census of 3-manifolds contains all manifolds (under various constraints) that can be triangulated with at most n tetrahedra. Al- though censuses are useful resources for mathematicians, constructing them is difficult: the best algorithms to date have not gone beyond n = 12. The underlying algorithms essentially (i) enumerate all relevant 4-regular multigraphs on n nodes, and then (ii) for each multigraph G they enumerate possible 3-manifold triangulations with G as their dual 1-skeleton, of which there could be exponentially many. In practice, a small number of multigraphs often dominate the running times of census algorithms: for example, in a typical census on 10 tetrahedra, almost half of the running time is spent on just 0.3% of the graphs. Here we present a new algorithm for stage (ii), which is the computational bottleneck in this process. The key idea is to build triangulations by recursively constructing neighbourhoods of edges, in contrast to traditional algorithms which recursively glue together pairs of tetrahedron faces. We implement this algorithm, and find experimentally that whilst the overall performance is mixed, the new algorithm runs significantly faster on those pathological multigraphs for which existing methods are extremely slow. In this way the old and new algorithms complement one another, and together can yield significant performance improvements over either method alone.



قيم البحث

اقرأ أيضاً

A key result in computational 3-manifold topology is that any two triangulations of the same 3-manifold are connected by a finite sequence of bistellar flips, also known as Pachner moves. One limitation of this result is that little is known about th e structure of this sequences; knowing more about the structure could help both proofs and algorithms. Motivated by this, we show that there must be a sequence that satisfies a rigid property that we call semi-monotonicity. We also study this result empirically: we implement an algorithm to find such semi-monotonic sequences, and compare their characteristics to less structured sequences, in order to better understand the practical and theoretical utility of this result.
In this paper, we explore minimal contact triangulations on contact 3-manifolds. We give many explicit examples of contact triangulations that are close to minimal ones. The main results of this article say that on any closed oriented 3-manifold the number of vertices for minimal contact triangulations for overtwisted contact structures grows at most linearly with respect to the relative $d^3$ invariant. We conjecture that this bound is optimal. We also discuss, in great details, contact triangulations for a certain family of overtwisted contact structures on 3-torus.
It is well known that a triangulation of a closed 2-manifold is tight with respect to a field of characteristic two if and only if it is neighbourly; and it is tight with respect to a field of odd characteristic if and only if it is neighbourly and o rientable. No such characterization of tightness was previously known for higher dimensional manifolds. In this paper, we prove that a triangulation of a closed 3-manifold is tight with respect to a field of odd characteristic if and only if it is neighbourly, orientable and stacked. In consequence, the K{u}hnel-Lutz conjecture is valid in dimension three for fields of odd characteristic. Next let $mathbb{F}$ be a field of characteristic two. It is known that, in this case, any neighbourly and stacked triangulation of a closed 3-manifold is $mathbb{F}$-tight. For triangulated closed 3-manifolds with at most 71 vertices or with first Betti number at most 188, we show that the converse is true. But the possibility of an $mathbb{F}$-tight non-stacked triangulation on a larger number of vertices remains open. We prove the following upper bound theorem on such triangulations. If an $mathbb{F}$-tight triangulation of a closed 3-manifold has $n$ vertices and first Betti number $beta_1$, then $(n-4)(617n- 3861) leq 15444beta_1$. Equality holds here if and only if all the vertex links of the triangulation are connected sums of boundary complexes of icosahedra.
165 - Marc Lackenby 2020
This survey focuses on the computational complexity of some of the fundamental decision problems in 3-manifold theory. The article discusses the wide variety of tools that are used to tackle these problems, including normal and almost surfaces, hiera rchies, homomorphisms to finite groups, and hyperbolic structures.
We prove foundational results about the set of homomorphisms from a finitely generated group to the collection of all fundamental groups of compact 3-manifolds and answer questions of Reid-Wang-Zhou and Agol-Liu.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا