Premium
Minimum spanning acycle and lifetime of persistent homology in the Linial–Meshulam process
Author(s) -
Hiraoka Yasuaki,
Shirai Tomoyuki
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20718
Subject(s) - spanning tree , mathematics , combinatorics , minimum spanning tree , limit (mathematics) , generalization , minimum weight , minimum degree spanning tree , persistent homology , discrete mathematics , algorithm , mathematical analysis
This paper studies a higher dimensional generalization of Frieze's ζ ( 3 ) ‐limit theorem on the d ‐Linial–Meshulam process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in Θ ( n d − 1 ) . © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 315–340, 2017