×

Random geometric complexes. (English) Zbl 1219.05175

In this paper the expected topological properties are investigated for Čech and Vietoris-Rips complexes built on random points in \(\mathbb R^d\). In particular are identified intervals of vanishing and non-vanishing for each homology group, and asymptotic formulas for the expected rank of homology are determined when this is non-vanishing. There is also a close connection to geometric probability, and in particular to the theory of geometric random graphs. The main technical contribution of the article is the application of discrete Morse theory in geometric probability. Several motivations and comments are also provided in the interesting introductory section

MSC:

05C80 Random graphs (graph-theoretic aspects)
05E18 Group actions on combinatorial structures
60D05 Geometric probability and stochastic geometry
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Alon, N., Spencer, J.H.: The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization, 3rd edn. Wiley, Hoboken (2008). With an appendix on the life and work of Paul Erdős · Zbl 1148.05001
[2] Babson, E.; Hoffman, C.; Kahle, M., The fundamental group of random 2-complexes, J. Am. Math. Soc., 24, 1-28, (2011) · Zbl 1270.20042
[3] Barishnokov, Y.: Quantum foam, August 2009. (Talk given at AIM Workshop on “Topological complexity of random sets”)
[4] Björner, A., Topological methods, No. 2, 1819-1872, (1995), Amsterdam · Zbl 0851.52016
[5] Bollobás, B.; Riordan, O., Clique percolation, Random Struct. Algorithms, 35, 294-322, (2009) · Zbl 1205.60165
[6] Bubenik, P.; Carlson, G.; Kim, P. T.; Luo, Z. M., Statistical topology via Morse theory, persistence and nonparametric estimation, Algebr. Methods Stat. Probab. II, 516, 75, (2010) · Zbl 1196.62041
[7] Bubenik, P.; Kim, P. T., A statistical approach to persistent homology, Homology Homotopy Appl., 9, 337-362, (2007) · Zbl 1136.55004
[8] Carlsson, G., Topology and data, Bull. Am. Math. Soc. (N.S.), 46, 255-308, (2009) · Zbl 1172.62002
[9] Chambers, E. W.; Silva, V.; Erickson, J.; Ghrist, R., Vietoris-Rips complexes of planar point sets, Discrete Comput. Geom., 44, 75-90, (2010) · Zbl 1231.05306
[10] Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Stability of persistence diagrams, Discrete Comput. Geom., 37, 103-120, (2007) · Zbl 1117.54027
[11] Diaconis, P.: Application of topology. Quicktime video, September 2006. (Talk given at MSRI Workshop on “Application of topology in science and engineering,” Quicktime video available on MSRI webpage)
[12] Edelsbrunner, H.; Harer, J., Persistent homology—a survey, No. 453, 257-282, (2008), Providence · Zbl 1145.55007
[13] Forman, R., A user’s guide to discrete Morse theory, Sémin. Lothar. Comb., 48, (2002) · Zbl 1048.57015
[14] Gromov, M., Hyperbolic groups, No. 8, 75-263, (1987), New York · Zbl 0634.20015
[15] Gromov, M., Random walk in random groups, Geom. Funct. Anal., 13, 73-146, (2003) · Zbl 1122.20021
[16] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002) · Zbl 1044.55001
[17] Hausmann, J.-C., On the Vietoris-Rips complexes and a cohomology theory for metric spaces, Princeton, NJ, 1994, Princeton · Zbl 0928.55003
[18] Kahle, M., The neighborhood complex of a random graph, J. Comb. Theory, Ser. A, 114, 380-387, (2007) · Zbl 1110.05090
[19] Kahle, M., Topology of random clique complexes, Discrete Math., 309, 1658-1671, (2009) · Zbl 1215.05163
[20] Kahle, M., Meckes, E.: Limit theorems for Betti numbers of random simplicial complexes. Submitted, arXiv:1009.4130 (2010) · Zbl 1268.05180
[21] Linial, N.; Meshulam, R., Homological connectivity of random 2-complexes, Combinatorica, 26, 475-487, (2006) · Zbl 1121.55013
[22] Linial, N.; Novik, I., How neighborly can a centrally symmetric polytope be, Discrete Comput. Geom., 36, 273-281, (2006) · Zbl 1127.52011
[23] Meshulam, R.; Wallach, N., Homological connectivity of random \(k\)-dimensional complexes, Random Struct. Algorithms, 34, 408-417, (2009) · Zbl 1177.55011
[24] Niyogi, P.; Smale, S.; Weinberger, S., Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom., 39, 419-441, (2008) · Zbl 1148.68048
[25] Niyogi, P., Smale, S., Weinberger, S.: A topological view of unsupervised learning from noisy data (2010, to appear) · Zbl 1230.62085
[26] Penrose, M.: Random Geometric Graphs. Oxford Studies in Probability, vol. 5. Oxford University Press, Oxford (2003) · Zbl 1029.60007
[27] Pippenger, N.; Schleich, K., Topological characteristics of random triangulated surfaces, Random Struct. Algorithms, 28, 247-288, (2006) · Zbl 1145.52009
[28] Vietoris, L.: Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen. Math. Ann. 97(1), 454-472 (1927) · JFM 53.0552.01
[29] Zomorodian, A.; Carlsson, G., Computing persistent homology, Discrete Comput. Geom., 33, 249-274, (2005) · Zbl 1069.55003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.