Goodness-of-fit via count statistics in dense random simplicial complexes

Tadas Temčinas; Vidit Nanda; Gesine Reinert

doi:10.3934/fods.2025013

Article Contents

2026, Volume 9: 88-136. Doi: 10.3934/fods.2025013

This volume Previous Article Convergence rates of non-stationary and deep Gaussian process regression Next Article Hamiltonian Monte Carlo methods for spectroscopy data analysis

Goodness-of-fit via count statistics in dense random simplicial complexes

1.
Department of Statistics, University of Oxford, United Kingdom
2.
Mathematical Institute, University of Oxford, United Kingdom

^*Corresponding author: Vidit Nanda
^*Corresponding author: Vidit Nanda

Received: February 2024

Revised: April 2025

Early access: August 4, 2025

Published online: August 4, 2025

Abstract / Introduction Full Text(HTML) Figure(4) / Table(3) Related Papers Cited by

Abstract

A key object of study in stochastic topology is a random simplicial complex. In this work we study a multi-parameter random simplicial complex model, where the probability of including a $ k $-simplex, given the lower dimensional structure, is fixed. This leads to a conditionally independent probabilistic structure. This model includes the Erdős–Rényi random graph, the random clique complex as well as the Linial-Meshulam complex as special cases. The model is studied from both probabilistic and statistical points of view. We prove multivariate central limit theorems with bounds and known limiting covariance structure for the subcomplex counts and the number of critical simplices under a lexicographical acyclic partial matching. We use the CLTs to develop a goodness-of-fit test for this random model and evaluate its empirical performance. In order for the test to be applicable in practice, we also prove that the MLE estimators are asymptotically unbiased, consistent, uncorrelated and normally distributed.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. Lexicographical matching given by the red arrows. Critical simplices are highlighted in blue

Download: Full-size image PowerPoint slide

Figure 2. Goodness of fit testing results of the tetrahedron model. The $ x $-axis corresponds to $ \Delta\epsilon : = \epsilon_2 - \epsilon_1 $

Download: Full-size image PowerPoint slide

Figure 3. Goodness of fit testing results of the triangle model. The $ x $-axis corresponds to $ \Delta\epsilon : = \epsilon_2 - \epsilon_1 $

Download: Full-size image PowerPoint slide

Figure 4. Goodness of fit testing results of the edge model. The $ x $-axis corresponds to $ \Delta\epsilon : = \epsilon_2 - \epsilon_1 $

Download: Full-size image PowerPoint slide

Table 1. Goodness of fit testing results of the tetrahedron model

$ \epsilon_1 $	$ \epsilon_2 $	centered triangles	triangles	critical
0.00818181818181818	0.462727272727272	96	100	99
0.0163636363636363	0.425454545454545	94	100	100
0.0245454545454545	0.388181818181818	88	100	100
0.0327272727272727	0.35090909090909	93	100	99
0.0409090909090909	0.313636363636363	94	100	100
0.049090909090909	0.276363636363636	96	100	99
0.0572727272727272	0.239090909090909	93	100	99
0.0654545454545454	0.201818181818181	95	100	100
0.0736363636363636	0.164545454545454	91	100	100
0.0818181818181818	0.127272727272727	95	100	81
0.0825619834710743	0.123884297520661	93	100	69
0.0833057851239669	0.120495867768595	91	100	67
0.0840495867768594	0.117107438016528	93	100	50
0.084793388429752	0.113719008264462	94	100	40
0.0855371900826446	0.110330578512396	93	100	29
0.0862809917355371	0.10694214876033	96	100	23
0.0870247933884297	0.103553719008264	92	100	18
0.0877685950413223	0.100165289256198	97	100	12
0.0885123966942148	0.0967768595041322	97	100	14
0.0892561983471074	0.0933884297520661	89	100	5
0.09	0.09	98	100	2

| Show Table

DownLoad: CSV

Table 2. Goodness of fit testing results of the triangle model

$ \epsilon_1 $	$ \epsilon_2 $	centered triangles	triangles	critical
0.00818181818181818	0.608181818181818	96	100	99
0.0163636363636363	0.556363636363636	95	100	98
0.0245454545454545	0.504545454545454	95	100	95
0.0327272727272727	0.452727272727272	92	100	100
0.0409090909090909	0.40090909090909	90	100	98
0.049090909090909	0.349090909090909	96	100	100
0.0572727272727272	0.297272727272727	97	100	98
0.0654545454545454	0.245454545454545	93	100	93
0.06681818182	0.2368181819	91	100	86
0.06818181818	0.2281818182	94	100	89
0.069545454545	0.21954545455	95	100	81
0.07090909091	0.2109090909	96	100	72
0.072272727275	0.20227272725	92	100	65
0.0736363636363636	0.193636363636363	98	100	67
0.0751239669421487	0.184214876033057	96	100	63
0.0766115702479338	0.174793388429752	95	100	55
0.078099173553719	0.165371900826446	98	100	53
0.0795867768595041	0.15595041322314	97	100	45
0.0810743801652892	0.146528925619834	94	100	38
0.0825619834710743	0.137107438016528	96	100	28
0.0840495867768594	0.127685950413223	95	100	15
0.0855371900826446	0.118264462809917	96	100	12
0.0870247933884297	0.108842975206611	87	100	11
0.09	0.0994214876033057	97	100	9

| Show Table

DownLoad: CSV

Table 3. Goodness of fit testing results of the edge model

$ \epsilon_1 $	$ \epsilon_2 $	centered triangles	triangles	critical
0	1.732050808	100	100	100
0.02344631004	1.673018508	99	100	99
0.04689262009	1.613986208	90	100	100
0.07033893013	1.554953908	97	100	99
0.09378524018	1.495921608	96	100	99
0.1172315502	1.436889308	97	100	99
0.1406778603	1.377857009	94	100	100
0.1641241703	1.318824709	96	100	100
0.1875704804	1.259792409	99	100	100
0.2110167904	1.200760109	91	100	100
0.2344631004	1.141727809	95	100	99
0.2579094105	1.082695509	77	100	97
0.2813557205	1.023663209	43	100	98
0.2857519	1.01259465	39	100	99
0.29014809	1.0015261	26	100	97
0.29454427	0.99045754	17	100	93
0.29894045	0.97938898	12	100	88
0.30333664	0.96832043	5	100	75
0.3048020306	0.9646309096	0	100	73
0.30773282	0.95725187	1	100	81
0.312129	0.94618332	0	98	62
0.31652519	0.93511476	0	96	51
0.32092137	0.9240462	0	90	33
0.32531755	0.91297765	0	75	29
0.3282483406	0.9055986098	3	74	12
0.32971373	0.90190909	0	53	9
0.33410992	0.89084053	0	33	4
0.3385061	0.87977198	0	16	3
0.34290228	0.86870342	0	4	1
0.34729847	0.85763487	0	3	1
0.3516946507	0.84656631	0	3	0
0.3751409607	0.7875340101	0	0	0
0.3985872707	0.7285017103	0	0	0
0.4220335808	0.6694694104	0	0	0
0.4454798908	0.6104371106	0	0	0
0.4689262009	0.5514048108	0	0	0
0.4923725109	0.4923725109	0	0	0

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Ababneh and M. Kahle, Maximal persistence in random clique complexes, Journal of Applied and Computational Topology, 8 (2014), 1449-1463.
[2]	K. A. Adiprasito, B. Benedetti and F. H. Lutz, Extremal examples of collapsible complexes and random discrete Morse theory, Discrete & Computational Geometry, 57 (2017), 824-853.
[3]	A. D. Barbour, L. Holst and S. Janson, Poisson Approximation, Oxford Stud. Probab., 2, Oxford Sci. Publ., The Clarendon Press, Oxford University Press, New York, 1992.
[4]	A. D. Barbour, M. Karoński and A. Ruciński, A central limit theorem for decomposable random variables with applications to random graphs, Journal of Combinatorial Theory, Series B, 47 (1989), 125-145. doi: 10.1016/0095-8956(89)90014-2.
[5]	M. Barthelemy, Class of models for random hypergraphs, Physical Review E, 106 (2022), Paper No. 064310, 10 pp. doi: 10.1103/PhysRevE.106.064310.
[6]	U. Bauer, Ripser: efficient computation of Vietoris–Rips persistence barcodes, Journal of Applied and Computational Topology, 5 (2021), 391-423. doi: 10.1007/s41468-021-00071-5.
[7]	U. Bauer and A. Rathod, Parameterized inapproximability of Morse matching, Comput. Geom., 126 (2025), Paper No. 102148, 35 pp.
[8]	G. Bianconi, Higher-Order Networks, Cambridge University Press, 2021.
[9]	C. Bick, E. Gross, H. A. Harrington and M. T. Schaub, What are higher-order networks?, SIAM Review, 65 (2023), 686-731. doi: 10.1137/21M1414024.
[10]	C. A. N. Biscio, N. Chenavier, C. Hirsch and A. M. Svane, Testing goodness of fit for point processes via topological data analysis, Electronic Journal of Statistics, 14 (2020), 1024-1074. doi: 10.1214/20-EJS1683.
[11]	O. Bobrowski and M. Kahle, Topology of random geometric complexes: A survey, Journal of Applied and Computational Topology, 1 (2018), 331-364. doi: 10.1007/s41468-017-0010-0.
[12]	O. Bobrowski and D. Krioukov, Random simplicial complexes: Models and phenomena, in Higher-Order Systems, Springer, Cham, 2022, 59-96. doi: 10.1007/978-3-030-91374-8_2.
[13]	S. Bubeck, J. Ding, R. Eldan and M. Z. Rácz, Testing for high-dimensional geometry in random graphs, Random Structures & Algorithms, 49 (2016), 503-532.
[14]	A. Cipriani, C. Hirsch and M. Vittorietti, Topology-based goodness-of-fit tests for sliced spatial data, Computational Statistics & Data Analysis, 179 (2023), 107655.
[15]	A. Costa and M. Farber, Large random simplicial complexes, Ⅰ, Journal of Topology and Analysis, 8 (2016), 399-429. doi: 10.1142/S179352531650014X.
[16]	A. Costa and M. Farber, Large random simplicial complexes, iii the critical dimension, Journal of Knot Theory and Its Ramifications, 26 (2017), 1740010, 26pp. doi: 10.1142/S0218216517400107.
[17]	J. Curry, R. Ghrist and V. Nanda, Discrete Morse theory for computing cellular sheaf cohomology, Foundations of Computational Mathematics, 16 (2016), 875-897. doi: 10.1007/s10208-015-9266-8.
[18]	P. de Jong, A central limit theorem with applications to random hypergraphs, Random Structures & Algorithms, 8 (1996), 105-120.
[19]	P. Eichelsbacher, B. Rednoß, C. Thäle and G. Zheng, A simplified second-order gaussian poincaré inequality in discrete setting with applications, in Annales de l'Institut Henri Poincare (B) Probabilites et Statistiques, Institut Henri Poincaré, 59 (2023), 271-302. doi: 10.1214/22-AIHP1247.
[20]	M. Farber and L. Mead, Random simplicial complexes in the medial regime, Topology and its Applications, 272 (2020), 107065, 22pp. doi: 10.1016/j.topol.2020.107065.
[21]	R. Forman, A user's guide to discrete morse theory, Séminaire Lotharingien de Combinatoire, 48 (2002), B48c, 35pp.
[22]	S. Harker, K. Mischaikow, M. Mrozek and V. Nanda, Discrete Morse theoretic algorithms for computing homology of complexes and maps, Foundations of Computational Mathematics, 14 (2014), 151-184. doi: 10.1007/s10208-013-9145-0.
[23]	S. Janson, Poisson approximation for large deviations, Random Structures & Algorithms, 1 (1990), 221-229.
[24]	S. Janson, Gaussian Hilbert Spaces, Cambridge Tracts in Math., 129, Cambridge University Press, Cambridge, 1997.
[25]	S. Janson, Large deviations for sums of partly dependent random variables, Random Structures & Algorithms, 24 (2004), 234-248.
[26]	S. Janson and K. Nowicki, The asymptotic distributions of generalized u-statistics with applications to random graphs, Probability Theory and Related Fields, 90 (1991), 341-375. doi: 10.1007/BF01193750.
[27]	M. Joswig and M. E. Pfetsch, Computing optimal discrete Morse functions, SIAM J. Discrete Math., 20 (2006), 11-25. doi: 10.1137/S0895480104445885.
[28]	M. Kahle, Topology of random clique complexes, Discrete Mathematics, 309 (2009), 1658-1671. doi: 10.1016/j.disc.2008.02.037.
[29]	M. Kahle, Random geometric complexes, Discrete & Computational Geometry, 45 (2011), 553-573.
[30]	M. Kahle, Sharp vanishing thresholds for cohomology of random flag complexes, Annals of Mathematics, 179 (2014), 1085-1107.
[31]	M. Kahle, Topology of random simplicial complexes: A survey, AMS Contemp. Math, 620 (2014), 201-222. doi: 10.1090/conm/620/12367.
[32]	M. Kahle and E. Meckes, Limit theorems for betti numbers of random simplicial complexes, Homology, Homotopy and Applications, 15 (2013), 343-374. doi: 10.4310/HHA.2013.v15.n1.a17.
[33]	G. Kaur and A. Röllin, Higher-order fluctuations in dense random graph models, Electronic Journal of Probability, 26 (2021), 1-36. doi: 10.1214/21-EJP708.
[34]	J. Krebs and C. Hirsch, Functional central limit theorems for persistent betti numbers on cylindrical networks, Scandinavian Journal of Statistics, 49 (2022), 427-454. doi: 10.1111/sjos.12524.
[35]	J. Lei, A goodness-of-fit test for stochastic block models, The Annals of Statistics, 44 (2016), 401-424. doi: 10.1214/15-AOS1370.
[36]	C. Ley, G. Reinert and Y. Swan, Stein's method for comparison of univariate distributions, Probability Surveys, 14 (2017), 1-52. doi: 10.1214/16-PS278.
[37]	N. Linial and R. Meshulam, Homological connectivity of random 2-complexes, Combinatorica, 26 (2006), 475-487. doi: 10.1007/s00493-006-0027-9.
[38]	N. Linial and Y. Peled, On the phase transition in random simplicial complexes, Annals of Mathematics, 184 (2016), 745-773. doi: 10.4007/annals.2016.184.3.3.
[39]	S. Liu and M. Z. Rácz, Phase transition in noisy high-dimensional random geometric graphs, Electron. J. Stat., 17 (2023), 3512-3574.
[40]	W. McGinley and R. Sibson, Dissociated random variables, in Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge University Press, 77 (1975), 185-188. doi: 10.1017/S0305004100049513.
[41]	K. Mischaikow and V. Nanda, Morse theory for filtrations and efficient computation of persistent homology, Discrete and Computational Geometry, 50 (2013), 330-353. doi: 10.1007/s00454-013-9529-6.
[42]	A. Newman, One-sided sharp thresholds for homology of random flag complexes, J. Lond. Math. Soc. (2), 109 (2024), Paper No. e12872, 26 pp.
[43]	M. Newman, Networks, Oxford University Press, Oxford, 2018.
[44]	S. Ouadah, S. Robin and P. Latouche, Degree-based goodness-of-fit tests for heterogeneous random graph models: Independent and exchangeable cases, Scandinavian Journal of Statistics, 47 (2020), 156-181. doi: 10.1111/sjos.12410.
[45]	T. Owada, G. Samorodnitsky and G. Thoppe, Limit theorems for topological invariants of the dynamic multi-parameter simplicial complex, Stochastic Processes and their Applications, 138 (2021), 56-95. doi: 10.1016/j.spa.2021.04.008.
[46]	A. Roy and D. Yogeshwaran, Random clique complex process inside the critical window, arXiv preprint, arXiv: 2303.17535.
[47]	A. Ruciński, When are small subgraphs of a random graph normally distributed?, Probability Theory and Related Fields, 78 (1988), 1-10. doi: 10.1007/BF00718031.
[48]	G. Samorodnitsky and T. Owada, Large deviations for subcomplex counts and betti numbers in multiparameter simplicial complexes, Random Structures Algorithms, 63 (2023), 533-556.
[49]	J. Schulz, The Optimal Berry-Esseen Constant in the Binomial Case, PhD thesis, University of Trier, 2016.
[50]	E. Spanier, Algebraic Topology, McGraw-Hill Book Co., New York-Toronto-London, 1966. doi: 10.1007/978-1-4684-9322-1_5.
[51]	T. Temčinas, V. Nanda and G. Reinert, Multivariate central limit theorems for random clique complexes, Journal of Applied and Computational Topology, 8 (2024), 1837-1880.
[52]	N. Yerolemou and V. Nanda, Morse theory for complexes of groups, J. Pure Appl. Algebra, 228 (2024), Paper No. 107606, 31 pp.
[53]	Z.-S. Zhang, Berry–esseen bounds for generalized u-statistics, Electronic Journal of Probability, 27 (2022), 1-36. doi: 10.1214/22-EJP860.
[54]	K. Zuev, O. Eisenberg and D. Krioukov, Exponential random simplicial complexes, Journal of Physics A: Mathematical and Theoretical, 48 (2015), 465002, 25pp. doi: 10.1088/1751-8113/48/46/465002.