Document Open Access Logo

Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations

Authors Ulrich Bauer , Fabian Roll

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.15.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Ulrich Bauer
  • Department of Mathematics and Munich Data Science Institute, Technische Universität München, Germany
  • www.ulrich-bauer.org
Fabian Roll
  • Department of Mathematics, Technische Universität München, Germany

Funding

This research has been supported by the DFG Collaborative Research Center SFB/TRR 109 Discretization in Geometry and Dynamics.

Acknowledgements

We thank Michael Bleher, Lukas Hahn, and Andreas Ott for stimulating discussions about applications of Vietoris-Rips complexes to the topological study of coronavirus evolution motivating our interest in the persistence of tree metrics, the organizers and participants of the AATRN Vietoris-Rips online seminar for sparking our interest in the Contractibility Lemma, and the anonymous reviewers for valuable feedback.

Cite AsGet BibTex

Ulrich Bauer and Fabian Roll. Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.15

Abstract

Motivated by computational aspects of persistent homology for Vietoris–Rips filtrations, we generalize a result of Eliyahu Rips on the contractibility of Vietoris–Rips complexes of geodesic spaces for a suitable parameter depending on the hyperbolicity of the space. We consider the notion of geodesic defect to extend this result to general metric spaces in a way that is also compatible with the filtration. We further show that for finite tree metrics the Vietoris–Rips complexes collapse to their corresponding subforests. We relate our result to modern computational methods by showing that these collapses are induced by the apparent pairs gradient, which is used as an algorithmic optimization in Ripser, explaining its particularly strong performance on tree-like metric data.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Geometric topology
  • Mathematics of computing → Trees
  • Theory of computation → Computational geometry
Keywords
  • Vietoris–Rips complexes
  • persistent homology
  • discrete Morse theory
  • apparent pairs
  • hyperbolicity
  • geodesic defect
  • Ripser

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Michał Adamaszek. Clique complexes and graph powers. Israel J. Math., 196(1):295-319, 2013. URL: https://doi.org/10.1007/s11856-012-0166-1.
  2. Michał Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier. On homotopy types of Vietoris-Rips complexes of metric gluings. J. Appl. Comput. Topol., 4(3):425-454, 2020. URL: https://doi.org/10.1007/s41468-020-00054-y.
  3. Dominique Attali, André Lieutier, and David Salinas. Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes. Comput. Geom., 46(4):448-465, 2013. URL: https://doi.org/10.1016/j.comgeo.2012.02.009.
  4. Dominique Attali, André Lieutier, and David Salinas. When convexity helps collapsing complexes. In 35th International Symposium on Computational Geometry, volume 129 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 11, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.11.
  5. Jonathan Ariel Barmak and Elias Gabriel Minian. Strong homotopy types, nerves and collapses. Discrete Comput. Geom., 47(2):301-328, 2012. URL: https://doi.org/10.1007/s00454-011-9357-5.
  6. Ulrich Bauer. Ripser: efficient computation of Vietoris-Rips persistence barcodes. J. Appl. Comput. Topol., 5(3):391-423, 2021. URL: https://doi.org/10.1007/s41468-021-00071-5.
  7. Ulrich Bauer and Herbert Edelsbrunner. The Morse theory of Čech and Delaunay complexes. Trans. Amer. Math. Soc., 369(5):3741-3762, 2017. URL: https://doi.org/10.1090/tran/6991.
  8. Michael Bleher, Lukas Hahn, Juan Angel Patino-Galindo, Mathieu Carriere, Ulrich Bauer, Raul Rabadan, and Andreas Ott. Topology identifies emerging adaptive mutations in SARS-CoV-2. Preprint, 2021. URL: http://arxiv.org/abs/2106.07292.
  9. Jean-Daniel Boissonnat and Siddharth Pritam. Edge collapse and persistence of flag complexes. In 36th International Symposium on Computational Geometry, volume 164 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 19, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.19.
  10. M. Bonk and O. Schramm. Embeddings of Gromov hyperbolic spaces. In Selected works of Oded Schramm. Volume 1, 2, Sel. Works Probab. Stat., pages 243-284. Springer, New York, 2011. With a correction by Bonk. URL: https://doi.org/10.1007/978-1-4419-9675-6_10.
  11. Joseph Minhow Chan, Gunnar Carlsson, and Raul Rabadan. Topology of viral evolution. Proceedings of the National Academy of Sciences, 110(46):18566-18571, 2013. URL: https://doi.org/10.1073/pnas.1313480110.
  12. R. Espínola and M. A. Khamsi. Introduction to hyperconvex spaces. In Handbook of metric fixed point theory, pages 391-435. Kluwer Acad. Publ., Dordrecht, 2001. URL: https://doi.org/10.1007/978-94-017-1748-9_13.
  13. Steven N. Evans. Probability and real trees, volume 1920 of Lecture Notes in Mathematics. Springer, Berlin, 2008. Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6-23, 2005. URL: https://doi.org/10.1007/978-3-540-74798-7.
  14. Robin Forman. Morse theory for cell complexes. Adv. Math., 134(1):90-145, 1998. URL: https://doi.org/10.1006/aima.1997.1650.
  15. Ragnar Freij. Equivariant discrete Morse theory. Discrete Math., 309(12):3821-3829, 2009. URL: https://doi.org/10.1016/j.disc.2008.10.029.
  16. M. Gromov. Hyperbolic groups. In Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. URL: https://doi.org/10.1007/978-1-4613-9586-7_3.
  17. Allen Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. Google Scholar
  18. Patricia Hersh. On optimizing discrete Morse functions. Adv. in Appl. Math., 35(3):294-322, 2005. URL: https://doi.org/10.1016/j.aam.2005.04.001.
  19. J. R. Isbell. Six theorems about injective metric spaces. Comment. Math. Helv., 39:65-76, 1964. URL: https://doi.org/10.1007/BF02566944.
  20. Jakob Jonsson. Simplicial complexes of graphs, volume 1928 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2008. URL: https://doi.org/10.1007/978-3-540-75859-4.
  21. Dmitry N. Kozlov. Organized collapse: an introduction to discrete Morse theory, volume 207 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2020. Google Scholar
  22. Urs Lang. Injective hulls of certain discrete metric spaces and groups. J. Topol. Anal., 5(3):297-331, 2013. URL: https://doi.org/10.1142/S1793525313500118.
  23. Janko Latschev. Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold. Arch. Math. (Basel), 77(6):522-528, 2001. URL: https://doi.org/10.1007/PL00000526.
  24. Michael Lesnick, Raúl Rabadán, and Daniel I. S. Rosenbloom. Quantifying genetic innovation: mathematical foundations for the topological study of reticulate evolution. SIAM J. Appl. Algebra Geom., 4(1):141-184, 2020. URL: https://doi.org/10.1137/18M118150X.
  25. Sunhyuk Lim, Facundo Memoli, and Osman Berat Okutan. Vietoris-Rips Persistent Homology, Injective Metric Spaces, and The Filling Radius. Preprint, 2020. URL: http://arxiv.org/abs/2001.07588.
  26. Vin de Silva and Gunnar Carlsson. Topological estimation using witness complexes. In Markus Gross, Hanspeter Pfister, Marc Alexa, and Szymon Rusinkiewicz, editors, SPBG'04 Symposium on Point - Based Graphics 2004. The Eurographics Association, 2004. URL: https://doi.org/10.2312/SPBG/SPBG04/157-166.
  27. Leopold Vietoris. Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen. Math. Ann., 97(1):454-472, 1927. URL: https://doi.org/10.1007/BF01447877.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact