{
  "id": "1011.4169",
  "version": "v2",
  "published": "2010-11-18T11:00:46.000Z",
  "updated": "2011-02-23T06:19:32.000Z",
  "title": "The Pachner graph and the simplification of 3-sphere triangulations",
  "authors": [
    "Benjamin A. Burton"
  ],
  "comment": "17 pages, 4 figures, 4 tables; v2: incorporate connectedness into Theorem 4, other minor revisions; to appear in SoCG 2011",
  "journal": "SCG '11: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp. 153-162",
  "doi": "10.1145/1998196.1998220",
  "categories": [
    "math.GT",
    "cs.CG",
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-02-23T06:19:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "F.2.2",
      "G.2.1",
      "G.2.2",
      "D.1.3"
    ],
    "keywords": [
      "triangulation",
      "simplification",
      "studying finite level sets",
      "infinite pachner graph",
      "polynomial-time computable signatures"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "ACM",
      "journal": "Commun. ACM"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1011.4169B"
    }
  }
}