DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2023.21

Finding Large Counterexamples by Selectively Exploring the Pachner Graph

Authors: Benjamin A. Burton and Alexander He

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

We often rely on censuses of triangulations to guide our intuition in 3-manifold topology. However, this can lead to misplaced faith in conjectures if the smallest counterexamples are too large to appear in our census. Since the number of triangulations increases super-exponentially with size, there is no way to expand a census beyond relatively small triangulations - the current census only goes up to 10 tetrahedra. Here, we show that it is feasible to search for large and hard-to-find counterexamples by using heuristics to selectively (rather than exhaustively) enumerate triangulations. We use this idea to find counterexamples to three conjectures which ask, for certain 3-manifolds, whether one-vertex triangulations always have a "distinctive" edge that would allow us to recognise the 3-manifold.

Cite as

Benjamin A. Burton and Alexander He. Finding Large Counterexamples by Selectively Exploring the Pachner Graph. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.SoCG.2023.21,
  author =	{Burton, Benjamin A. and He, Alexander},
  title =	{{Finding Large Counterexamples by Selectively Exploring the Pachner Graph}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.21},
  URN =		{urn:nbn:de:0030-drops-178712},
  doi =		{10.4230/LIPIcs.SoCG.2023.21},
  annote =	{Keywords: Computational topology, 3-manifolds, Triangulations, Counterexamples, Heuristics, Implementation, Pachner moves, Bistellar flips}
}

Search Results

Documents authored by He, Alexander

Finding Large Counterexamples by Selectively Exploring the Pachner Graph

Abstract

Cite as

Thanks for your feedback!

Could not send message