Randomly Weighted $d-$complexes: Minimal Spanning Acycles and Persistence Diagrams
| Autor: | D. Yogeshwaran, Gugan Thoppe, Primoz Skraba |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Spanning tree
Applied Mathematics Dimension (graph theory) Probability (math.PR) 60C05 05E45 (Primary) 60G70 60B99 05C80 (Secondary) 0102 computer and information sciences 01 natural sciences Point process Theoretical Computer Science Combinatorics Simplicial complex Distribution (mathematics) Computational Theory and Mathematics 010201 computation theory & mathematics Poisson point process FOS: Mathematics Discrete Mathematics and Combinatorics Geometry and Topology Limit (mathematics) Equivalence (measure theory) Mathematics - Probability Mathematics |
| DOI: | 10.48550/arxiv.1701.00239 |
| Popis: | A weighted $d-$complex is a simplicial complex of dimension $d$ in which each face is assigned a real-valued weight. We derive three key results here concerning persistence diagrams and minimal spanning acycles (MSAs) of such complexes. First, we establish an equivalence between the MSA face-weights and \emph{death times} in the persistence diagram. Next, we show a novel stability result for the MSA face-weights which, due to our first result, also holds true for the death and birth times, separately. Our final result concerns a perturbation of a mean-field model of randomly weighted $d-$complexes. The $d-$face weights here are perturbation of some i.i.d. distribution while all the lower-dimensional faces have a weight of $0$. If the perturbations decay sufficiently quickly, we show that suitably scaled extremal nearest face-weights, face-weights of the $d-$MSA, and the associated death times converge to an inhomogeneous Poisson point process. This result completely characterizes the extremal points of persistence diagrams and MSAs. The point process convergence and the asymptotic equivalence of three point processes are new for any weighted random complex model, including even the non-perturbed case. Lastly, as a consequence of our stability result, we show that Frieze's $\zeta(3)$ limit for random minimal spanning trees and the recent extension to random MSAs by Hino and Kanazawa also hold in suitable noisy settings. Comment: 42 Pages, 1 Figure. Streamlined introduction, modified Section 3 significantly |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|