Frontiers of sphere recognition in practice
Let \(K\) be a \(d\)-dimensional finite simplicial complex. The authors of the article present a multi-step heuristic for testing if \(K\) is a PL \(d\)-sphere. The first step involves verifying that \(K\) is a combinatorial \(d\)-manifold, and that its homology matches that of a \(d\)-sphere. In the second step, random discrete Morse functions in the style of \textit{B. Benedetti} and \textit{F. H. Lutz} [Exp. Math. 23, No. 1, 66--94 (2014; Zbl 1296.57018)] are generated, and are checked to see if they have single critical faces in dimensions \(0\) and \(d\) only. The third step is to modify \(K\) by applying bistellar flips (Pachner moves) and edge contractions, chosen randomly but with the goal of reducing the \(f\)-vector of \(K\). The resulting complex is checked if it is the boundary of a simplex. The last step involves computing the fundamental group of \(K\) and checking against the trivial group. If last step exits without a definitive result, the heuristic fails and no conclusion is drawn about \(K\). Numerical experiments performed indicate that the heuristic compares favorably, in terms of execution time and the ability to handle large complexes, with existing software programs. In addition, the authors introduce a class of contractible, but not collapsible, two-dimensional cell complexes which can be used to investigate the limits of sphere recognition algorithms.
- Heuristics for sphere recognition
- Extremal examples of collapsible complexes and random discrete Morse theory
- Simplicial Manifolds, Bistellar Flips and a 16-Vertex Triangulation of the Poincaré Homology 3-Sphere
- Simplifying triangulations of \(S^3\).
- scientific article; zbMATH DE number 7228935
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Sphere recognition lies in NP
- Optimal discrete Morse functions for 2-manifolds
- h-assignments of simplicial complexes and reverse search
- 15-vertex triangulations of an 8-manifold
- \textsc{Phat} -- persistent homology algorithms toolbox
- A new approach to crushing 3-manifold triangulations
- A potential smooth counterexample in dimension 4 to the Poincaré conjecture, the Schoenflies conjecture, and the Andrews-Curtis conjecture
- A structure theorem for pseudomanifolds
- A user's guide to discrete Morse theory
- Algorithms for tight spans and tropical linear spaces
- Cappell-Shaneson homotopy spheres are standard
- Cataloguing PL 4-manifolds by gem-complexity
- Combinatorial Properties of theK3 Surface: Simplicial Blowups and Slicings
- Combinatorial triangulations of homology spheres
- Computing convex hulls and counting integer points with \texttt{polymake}
- Computing Optimal Morse Matchings
- Decompositions of two-dimensional simplicial complexes
- Derived subdivisions make every PL sphere polytopal
- Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
- Extremal examples of collapsible complexes and random discrete Morse theory
- Generalized Poincaré's conjecture in dimensions greater than four
- GitHub
- Graph coloring manifolds
- Hardness of approximation for Morse matching
- Heuristics for sphere recognition
- scientific article; zbMATH DE number 4102053 (Why is no real title available?)
- scientific article; zbMATH DE number 1961543 (Why is no real title available?)
- scientific article; zbMATH DE number 849995 (Why is no real title available?)
- Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds
- Killing the Akbulut-Kirby 4-sphere, with relevance to the Andrews-Curtis and Schoenflies problems
- Knots in collapsible and non-collapsible balls
- Konstruktionsmethoden und das kombinatorische Homöomorphieproblem für Triangulationen kompakter semilinearer Mannigfaltigkeiten. (Methods of constructions and the combinatorical homeomorphism problem for triangulations of compact semilinear manifolds)
- Morse theory for cell complexes
- Morse theory for filtrations and efficient computation of persistent homology
- On discrete Morse functions and combinatorial decompositions
- On locally constructible spheres and balls
- On the dunce hat
- Optimal discrete Morse functions for 2-manifolds
- Polymake.jl: a new interface to \texttt{polymake}
- polymake: a framework for analyzing convex polytopes
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Random discrete Morse theory and a new library of triangulations
- Simplicial Manifolds, Bistellar Flips and a 16-Vertex Triangulation of the Poincaré Homology 3-Sphere
- Sphere recognition lies in NP
- Systems of distinct representatives and linear algebra
- The combinatorial structure of random polytopes
- The efficient certification of knottedness and Thurston norm
- The entropy formula for the Ricci flow and its geometric applications
- THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
- The simplex method. A probabilistic analysis
- The topology of four-dimensional manifolds
- Thin position and the recognition problem for \(S^ 3\)
- Triangulated manifolds with few vertices and vertex-transitive group actions
- Unrecognizability of manifolds
- Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix
- An algorithmic strategy for finding characteristic maps over wedged simplicial complexes
- Heuristics for sphere recognition
- Sphere recognition lies in NP
- scientific article; zbMATH DE number 2152058 (Why is no real title available?)
- Generalised cone complexes and tropical moduli in polymake
- Simplification strategies and extremal examples of simplicial complexes
- Random simple-homotopy theory
- Sampling Triangulations of Manifolds Using Monte Carlo Methods
- Small triangulations of 4-manifolds and the 4-manifold census
Uses Software
This page was built for publication: Frontiers of sphere recognition in practice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2098099)
