BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Benjamin A. Burton

Benjamin A. Burton contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.GTComputational Geometrymath.COmath.OCComputational ComplexityData Structures and Algorithmsmath.ATMathematical Software

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
35works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

35 published item(s)

preprint2016arXiv

Finding non-orientable surfaces in 3-manifolds

We investigate the complexity of finding an embedded non-orientable surface of Euler genus $g$ in a triangulated $3$-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into $3$-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour

It is a major unsolved problem as to whether unknot recognition - that is, testing whether a given closed loop in R^3 can be untangled to form a plain circle - has a polynomial time algorithm. In practice, trivial knots (which can be untangled) are typically easy to identify using fast simplification techniques, whereas non-trivial knots (which cannot be untangled) are more resistant to being conclusively identified as such. Here we present the first unknot recognition algorithm which is always conclusive and, although exponential time in theory, exhibits a clear polynomial time behaviour under exhaustive experimentation even for non-trivial knots. The algorithm draws on techniques from both topology and integer / linear programming, and highlights the potential for new applications of techniques from mathematical programming to difficult problems in low-dimensional topology. The exhaustive experimentation covers all 2977 non-trivial prime knots with <= 12 crossings. We also adapt our techniques to the important topological problems of 3-sphere recognition and the prime decomposition of 3-manifolds.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A new approach to crushing 3-manifold triangulations

The crushing operation of Jaco and Rubinstein is a powerful technique in algorithmic 3-manifold topology: it enabled the first practical implementations of 3-sphere recognition and prime decomposition of orientable manifolds, and it plays a prominent role in state-of-the-art algorithms for unknot recognition and testing for essential surfaces. Although the crushing operation will always reduce the size of a triangulation, it might alter its topology, and so it requires a careful theoretical analysis for the settings in which it is used. The aim of this short paper is to make the crushing operation more accessible to practitioners, and easier to generalise to new settings. When the crushing operation was first introduced, the analysis was powerful but extremely complex. Here we give a new treatment that reduces the crushing process to a sequential combination of three &#34;atomic&#34; operations on a cell decomposition, all of which are simple to analyse. As an application, we generalise the crushing operation to the setting of non-orientable 3-manifolds, where we obtain a new practical and robust algorithm for non-orientable prime decomposition. We also apply our crushing techniques to the study of non-orientable minimal triangulations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Collection of abstracts of the Workshop on Triangulations in Geometry and Topology at CG Week 2014 in Kyoto

This workshop about triangulations of manifolds in computational geometry and topology was held at the 2014 CG-Week in Kyoto, Japan. It focussed on computational and combinatorial questions regarding triangulations, with the goal of bringing together researchers working on various aspects of triangulations and of fostering a closer collaboration within the computational geometry and topology community. Triangulations are highly suitable for computations due to their clear combinatorial structure. As a consequence, they have been successfully employed in discrete algorithms to solve purely theoretical problems in a broad variety of mathematical research areas (knot theory, polytope theory, 2- and 3-manifold topology, geometry, and others). However, due to the large variety of applications, requirements vary from field to field and thus different types of triangulations, different tools, and different frameworks are used in different areas of research. This is why today closely related research areas are sometimes largely disjoint leaving potential reciprocal benefits unused. To address these potentials a workshop on Triangulations was held at Oberwolfach Research Institute in 2012. Since then many new collaborations between researchers of different mathematical communities have been established. Regarding the computational geometry community, the theory of manifolds continues to contribute to advances in more applied areas of the field. Many researchers are interested in fundamental mathematical research about triangulations and thus will benefit from a broad set of knowledge about different research areas using different techniques. We hope that this workshop brought together researchers from many different fields of computational geometry to have fruitful discussions which will lead to new interdisciplinary collaborations and solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Courcelle&#39;s theorem for triangulations

In graph theory, Courcelle&#39;s theorem essentially states that, if an algorithmic problem can be formulated in monadic second-order logic, then it can be solved in linear time for graphs of bounded treewidth. We prove such a metatheorem for a general class of triangulations of arbitrary fixed dimension d, including all triangulated d-manifolds: if an algorithmic problem can be expressed in monadic second-order logic, then it can be solved in linear time for triangulations whose dual graphs have bounded treewidth. We apply our results to 3-manifold topology, a setting with many difficult computational problems but very few parameterised complexity results, and where treewidth has practical relevance as a parameter. Using our metatheorem, we recover and generalise earlier fixed-parameter tractability results on taut angle structures and discrete Morse theory respectively, and prove a new fixed-parameter tractability result for computing the powerful but complex Turaev-Viro invariants on 3-manifolds.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fixed parameter tractable algorithms in combinatorial topology

To enumerate 3-manifold triangulations with a given property, one typically begins with a set of potential face pairing graphs (also known as dual 1-skeletons), and then attempts to flesh each graph out into full triangulations using an exponential-time enumeration. However, asymptotically most graphs do not result in any 3-manifold triangulation, which leads to significant &#34;wasted time&#34; in topological enumeration algorithms. Here we give a new algorithm to determine whether a given face pairing graph supports any 3-manifold triangulation, and show this to be fixed parameter tractable in the treewidth of the graph. We extend this result to a &#34;meta-theorem&#34; by defining a broad class of properties of triangulations, each with a corresponding fixed parameter tractable existence algorithm. We explicitly implement this algorithm in the most generic setting, and we identify heuristics that in practice are seen to mitigate the large constants that so often occur in parameterised complexity, highlighting the practicality of our techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Complexity of Immersed Normal Surfaces

Normal surface theory, a tool to represent surfaces in a triangulated 3-manifold combinatorially, is ubiquitous in computational 3-manifold theory. In this paper, we investigate a relaxed notion of normal surfaces where we remove the quadrilateral conditions. This yields normal surfaces that are no longer embedded. We prove that it is NP-hard to decide whether such a surface is immersed. Our proof uses a reduction from Boolean constraint satisfaction problems where every variable appears in at most two clauses, using a classification theorem of Feder. We also investigate variants, and provide a polynomial-time algorithm to test for a local version of this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The cusped hyperbolic census is complete

From its creation in 1989 through subsequent extensions, the widely-used &#34;SnapPea census&#34; now aims to represent all cusped finite-volume hyperbolic 3-manifolds that can be obtained from <= 8 ideal tetrahedra. Its construction, however, has relied on inexact computations and some unproven (though reasonable) assumptions, and so its completeness was never guaranteed. For the first time, we prove here that the census meets its aim: we rigorously certify that every ideal 3-manifold triangulation with <= 8 tetrahedra is either (i) homeomorphic to one of the census manifolds, or (ii) non-hyperbolic. In addition, we extend the census to 9 tetrahedra, and likewise prove this to be complete. We also present the first list of all minimal triangulations of all census manifolds, including non-geometric as well as geometric triangulations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Computational topology with Regina: Algorithms, heuristics and implementations

Regina is a software package for studying 3-manifold triangulations and normal surfaces. It includes a graphical user interface and Python bindings, and also supports angle structures, census enumeration, combinatorial recognition of triangulations, and high-level functions such as 3-sphere recognition, unknot recognition and connected sum decomposition. This paper brings 3-manifold topologists up-to-date with Regina as it appears today, and documents for the first time in the literature some of the key algorithms, heuristics and implementations that are central to Regina&#39;s performance. These include the all-important simplification heuristics, key choices of data structures and algorithms to alleviate bottlenecks in normal surface enumeration, modern implementations of 3-sphere recognition and connected sum decomposition, and more. We also give some historical background for the project, including the key role played by Rubinstein in its genesis 15 years ago, and discuss current directions for future development.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Enumerating fundamental normal surfaces: Algorithms, experiments and invariants

Computational knot theory and 3-manifold topology have seen significant breakthroughs in recent years, despite the fact that many key algorithms have complexity bounds that are exponential or greater. In this setting, experimentation is essential for understanding the limits of practicality, as well as for gauging the relative merits of competing algorithms. In this paper we focus on normal surface theory, a key tool that appears throughout low-dimensional topology. Stepping beyond the well-studied problem of computing vertex normal surfaces (essentially extreme rays of a polyhedral cone), we turn our attention to the more complex task of computing fundamental normal surfaces (essentially an integral basis for such a cone). We develop, implement and experimentally compare a primal and a dual algorithm, both of which combine domain-specific techniques with classical Hilbert basis algorithms. Our experiments indicate that we can solve extremely large problems that were once though intractable. As a practical application of our techniques, we fill gaps from the KnotInfo database by computing 398 previously-unknown crosscap numbers of knots.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Locating regions in a sequence under density constraints

Several biological problems require the identification of regions in a sequence where some feature occurs within a target density range: examples including the location of GC-rich regions, identification of CpG islands, and sequence matching. Mathematically, this corresponds to searching a string of 0s and 1s for a substring whose relative proportion of 1s lies between given lower and upper bounds. We consider the algorithmic problem of locating the longest such substring, as well as other related problems (such as finding the shortest substring or a maximal set of disjoint substrings). For locating the longest such substring, we develop an algorithm that runs in O(n) time, improving upon the previous best-known O(n log n) result. For the related problems we develop O(n log log n) algorithms, again improving upon the best-known O(n log n) results. Practical testing verifies that our new algorithms enjoy significantly smaller time and memory footprints, and can process sequences that are orders of magnitude longer as a result.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Multi-objective integer programming: An improved recursive algorithm

This paper introduces an improved recursive algorithm to generate the set of all nondominated objective vectors for the Multi-Objective Integer Programming (MOIP) problem. We significantly improve the earlier recursive algorithm of Özlen and Azizoğlu by using the set of already solved subproblems and their solutions to avoid solving a large number of IPs. A numerical example is presented to explain the workings of the algorithm, and we conduct a series of computational experiments to show the savings that can be obtained. As our experiments show, the improvement becomes more significant as the problems grow larger in terms of the number of objectives.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A tree traversal algorithm for decision problems in knot theory and 3-manifold topology

In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a tree traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation. Experimental comparisons of running times are included.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Complementary vertices and adjacency testing in polytopes

Our main theoretical result is that, if a simple polytope has a pair of complementary vertices (i.e., two vertices with no facets in common), then it has at least two such pairs, which can be chosen to be disjoint. Using this result, we improve adjacency testing for vertices in both simple and non-simple polytopes: given a polytope in the standard form {x \in R^n | Ax = b and x \geq 0} and a list of its V vertices, we describe an O(n) test to identify whether any two given vertices are adjacent. For simple polytopes this test is perfect; for non-simple polytopes it may be indeterminate, and instead acts as a filter to identify non-adjacent pairs. Our test requires an O(n^2 V + n V^2) precomputation, which is acceptable in settings such as all-pairs adjacency testing. These results improve upon the more general O(nV) combinatorial and O(n^3) algebraic adjacency tests from the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Computing closed essential surfaces in knot complements

We present a new, practical algorithm to test whether a knot complement contains a closed essential surface. This property has important theoretical and algorithmic consequences; however, systematically testing it has until now been infeasibly slow, and current techniques only apply to specific families of knots. As a testament to its practicality, we run the algorithm over a comprehensive body of 2979 knots, including the two 20-crossing dodecahedral knots, yielding results that were not previously known. The algorithm derives from the original Jaco-Oertel framework, involves both enumeration and optimisation procedures, and combines several techniques from normal surface theory. This represents substantial progress in the practical implementation of normal surface theory, in that we can systematically solve a theoretically double exponential-time problem for significant inputs. Our methods are relevant for other difficult computational problems in 3-manifold theory, ranging from testing for Haken-ness to the recognition problem for knots, links and 3-manifolds.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Computing the crosscap number of a knot using integer programming and normal surfaces

The crosscap number of a knot is an invariant describing the non-orientable surface of smallest genus that the knot bounds. Unlike knot genus (its orientable counterpart), crosscap numbers are difficult to compute and no general algorithm is known. We present three methods for computing crosscap number that offer varying trade-offs between precision and speed: (i) an algorithm based on Hilbert basis enumeration and (ii) an algorithm based on exact integer programming, both of which either compute the solution precisely or reduce it to two possible values, and (iii) a fast but limited precision integer programming algorithm that bounds the solution from above. The first two algorithms advance the theoretical state of the art, but remain intractable for practical use. The third algorithm is fast and effective, which we show in a practical setting by making significant improvements to the current knowledge of crosscap numbers in knot tables. Our integer programming framework is general, with the potential for further applications in computational geometry and topology.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimising a nonlinear utility function in multi-objective integer programming

In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective integer programming problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations

Enumerating all 3-manifold triangulations of a given size is a difficult but increasingly important problem in computational topology. A key difficulty for enumeration algorithms is that most combinatorial triangulations must be discarded because they do not represent topological 3-manifolds. In this paper we show how to preempt bad triangulations by detecting genus in partially-constructed vertex links, allowing us to prune the enumeration tree substantially. The key idea is to manipulate the boundary edges surrounding partial vertex links using expected logarithmic time operations. Practical testing shows the resulting enumeration algorithm to be significantly faster, with up to 249x speed-ups even for small problems where comparisons are feasible. We also discuss parallelisation, and describe new data sets that have been obtained using high-performance computing facilities.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Simplification paths in the Pachner graphs of closed orientable 3-manifold triangulations

It is important to have effective methods for simplifying 3-manifold triangulations without losing any topological information. In theory this is difficult: we might need to make a triangulation super-exponentially more complex before we can make it smaller than its original size. Here we present experimental work that suggests the reality is far different: for an exhaustive census of 81,800,394 one-vertex triangulations that span 1,901 distinct closed orientable 3-manifolds, we never need to add more than two extra tetrahedra, we never need more than a handful of Pachner moves (or bistellar flips), and the average number of Pachner moves decreases as the number of tetrahedra grows. If they generalise, these extremely surprising results would have significant implications for decision algorithms and the study of triangulations in 3-manifold topology. Key techniques include polynomial-time computable signatures that identify triangulations up to isomorphism, the isomorph-free generation of non-minimal triangulations, theoretical operations to reduce sequences of Pachner moves, and parallel algorithms for studying finite level sets in the infinite Pachner graph.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Pachner graph and the simplification of 3-sphere triangulations

It is important to have fast and effective methods for simplifying 3-manifold triangulations without losing any topological information. In theory this is difficult: we might need to make a triangulation super-exponentially more complex before we can make it smaller than its original size. Here we present experimental work suggesting that for 3-sphere triangulations the reality is far different: we never need to add more than two tetrahedra, and we never need more than a handful of local modifications. If true in general, these extremely surprising results would have significant implications for decision algorithms and the study of triangulations in 3-manifold topology. The algorithms behind these experiments are interesting in their own right. Key techniques include the isomorph-free generation of all 3-manifold triangulations of a given size, polynomial-time computable signatures that identify triangulations uniquely up to isomorphism, and parallel algorithms for studying finite level sets in the infinite Pachner graph.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Maximal admissible faces and asymptotic bounds for the normal surface solution space

The enumeration of normal surfaces is a key bottleneck in computational three-dimensional topology. The underlying procedure is the enumeration of admissible vertices of a high-dimensional polytope, where admissibility is a powerful but non-linear and non-convex constraint. The main results of this paper are significant improvements upon the best known asymptotic bounds on the number of admissible vertices, using polytopes in both the standard normal surface coordinate system and the streamlined quadrilateral coordinate system. To achieve these results we examine the layout of admissible points within these polytopes. We show that these points correspond to well-behaved substructures of the face lattice, and we study properties of the corresponding &#34;admissible faces&#34;. Key lemmata include upper bounds on the number of maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the two coordinate systems mentioned above.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Projective geometry and the outer approximation algorithm for multiobjective linear programming

A key problem in multiobjective linear programming is to find the set of all efficient extreme points in objective space. In this paper we introduce oriented projective geometry as an efficient and effective framework for solving this problem. The key advantage of oriented projective geometry is that we can work with an &#34;optimally simple&#34; but unbounded efficiency-equivalent polyhedron, yet apply to it the familiar theory and algorithms that are traditionally restricted to bounded polytopes. We apply these techniques to Benson&#39;s outer approximation algorithm, using oriented projective geometry to remove an exponentially large complexity from the algorithm and thereby remove a significant burden from the running time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Searching a bitstream in linear time for the longest substring of any given density

Given an arbitrary bitstream, we consider the problem of finding the longest substring whose ratio of ones to zeroes equals a given value. The central result of this paper is an algorithm that solves this problem in linear time. The method involves (i) reformulating the problem as a constrained walk through a sparse matrix, and then (ii) developing a data structure for this sparse matrix that allows us to perform each step of the walk in amortised constant time. We also give a linear time algorithm to find the longest substring whose ratio of ones to zeroes is bounded below by a given value. Both problems have practical relevance to cryptography and bioinformatics.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The complexity of the normal surface solution space

Normal surface theory is a central tool in algorithmic three-dimensional topology, and the enumeration of vertex normal surfaces is the computational bottleneck in many important algorithms. However, it is not well understood how the number of such surfaces grows in relation to the size of the underlying triangulation. Here we address this problem in both theory and practice. In theory, we tighten the exponential upper bound substantially; furthermore, we construct pathological triangulations that prove an exponential bound to be unavoidable. In practice, we undertake a comprehensive analysis of millions of triangulations and find that in general the number of vertex normal surfaces is remarkably small, with strong evidence that our pathological triangulations may in fact be the worst case scenarios. This analysis is the first of its kind, and the striking behaviour that we observe has important implications for the feasibility of topological algorithms in three dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Weber-Seifert dodecahedral space is non-Haken

In this paper we settle Thurston&#39;s old question of whether the Weber-Seifert dodecahedral space is non-Haken, a problem that has been a benchmark for progress in computational 3-manifold topology over recent decades. We resolve this question by combining recent significant advances in normal surface enumeration, new heuristic pruning techniques, and a new theoretical test that extends the seminal work of Jaco and Oertel.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Converting between quadrilateral and standard solution sets in normal surface theory

The enumeration of normal surfaces is a crucial but very slow operation in algorithmic 3-manifold topology. At the heart of this operation is a polytope vertex enumeration in a high-dimensional space (standard coordinates). Tollefson&#39;s Q-theory speeds up this operation by using a much smaller space (quadrilateral coordinates), at the cost of a reduced solution set that might not always be sufficient for our needs. In this paper we present algorithms for converting between solution sets in quadrilateral and standard coordinates. As a consequence we obtain a new algorithm for enumerating all standard vertex normal surfaces, yielding both the speed of quadrilateral coordinates and the wider applicability of standard coordinates. Experimentation with the software package Regina shows this new algorithm to be extremely fast in practice, improving speed for large cases by factors from thousands up to millions.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Optimizing the double description method for normal surface enumeration

Many key algorithms in 3-manifold topology involve the enumeration of normal surfaces, which is based upon the double description method for finding the vertices of a convex polytope. Typically we are only interested in a small subset of these vertices, thus opening the way for substantial optimization. Here we give an account of the vertex enumeration problem as it applies to normal surfaces, and present new optimizations that yield strong improvements in both running time and memory consumption. The resulting algorithms are tested using the freely available software package Regina.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Quadrilateral-octagon coordinates for almost normal surfaces

Normal and almost normal surfaces are essential tools for algorithmic 3-manifold topology, but to use them requires exponentially slow enumeration algorithms in a high-dimensional vector space. The quadrilateral coordinates of Tollefson alleviate this problem considerably for normal surfaces, by reducing the dimension of this vector space from 7n to 3n (where n is the complexity of the underlying triangulation). Here we develop an analogous theory for octagonal almost normal surfaces, using quadrilateral and octagon coordinates to reduce this dimension from 10n to 6n. As an application, we show that quadrilateral-octagon coordinates can be used exclusively in the streamlined 3-sphere recognition algorithm of Jaco, Rubinstein and Thompson, reducing experimental running times by factors of thousands. We also introduce joint coordinates, a system with only 3n dimensions for octagonal almost normal surfaces that has appealing geometric properties.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Enumeration of non-orientable 3-manifolds using face pairing graphs and union-find

Drawing together techniques from combinatorics and computer science, we improve the census algorithm for enumerating closed minimal P^2-irreducible 3-manifold triangulations. In particular, new constraints are proven for face pairing graphs, and pruning techniques are improved using a modification of the union-find algorithm. Using these results we catalogue all 136 closed non-orientable P^2-irreducible 3-manifolds that can be formed from at most ten tetrahedra.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Observations from the 8-tetrahedron non-orientable census

Through computer enumeration with the aid of topological results, we catalogue all 18 closed non-orientable P^2-irreducible 3-manifolds that can be formed from at most eight tetrahedra. In addition we give an overview as to how the 100 resulting minimal triangulations are constructed. Observations and conjectures are drawn from the census data, and future potential for the non-orientable census is discussed. Some preliminary nine-tetrahedron results are also included.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Structures of small closed non-orientable 3-manifold triangulations

A census is presented of all closed non-orientable 3-manifold triangulations formed from at most seven tetrahedra satisfying the additional constraints of minimality and P^2-irreducibility. The eight different 3-manifolds represented by these 41 different triangulations are identified and described in detail, with particular attention paid to the recurring combinatorial structures that are shared amongst the different triangulations. Using these recurring structures, the resulting triangulations are generalised to infinite families that allow similar triangulations of additional 3-manifolds to be formed. Algorithms and techniques used in constructing the census are included.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

Face pairing graphs and 3-manifold enumeration

The face pairing graph of a 3-manifold triangulation is a 4-valent graph denoting which tetrahedron faces are identified with which others. We present a series of properties that must be satisfied by the face pairing graph of a closed minimal P^2-irreducible triangulation. In addition we present constraints upon the combinatorial structure of such a triangulation that can be deduced from its face pairing graph. These results are then applied to the enumeration of closed minimal P^2-irreducible 3-manifold triangulations, leading to a significant improvement in the performance of the enumeration algorithm. Results are offered for both orientable and non-orientable triangulations.

0 citations0 reviewsNo code linkedOpen access