Topologies of Random Geometric Complexes on Riemannian Manifolds in the Thermodynamic Limit
Abstract We investigate the topologies of random geometric complexes built over random points sampled on Riemannian manifolds in the so-called “thermodynamic” regime. We prove the existence of universal limit laws for the topologies; namely, the random normalized counting measure of connected components (counted according to homotopy type) is shown to converge in probability to a deterministic probability measure. Moreover, we show that the support of the deterministic limiting measure equals the set of all homotopy types for Euclidean connected geometric complexes of the same dimension as the manifold.
Authors:
; ;
Award ID(s):
Publication Date:
NSF-PAR ID:
10286247
Journal Name:
International Mathematics Research Notices
ISSN:
1073-7928
1. Suppose $F:=(f_1,\ldots,f_n)$ is a system of random $n$-variate polynomials with $f_i$ having degree $\leq\!d_i$ and the coefficient of $x^{a_1}_1\cdots x^{a_n}_n$ in $f_i$ being an independent complex Gaussian of mean $0$ and variance $\frac{d_i!}{a_1!\cdots a_n!\left(d_i-\sum^n_{j=1}a_j \right)!}$. Recent progress on Smale's 17$\thth$ Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, B\"{u}rgisser, and Cucker --- has resulted in a deterministic algorithm that finds a single (complex) approximate root of $F$ using just $N^{O(1)}$ arithmetic operations on average, where $N\!:=\!\sum^n_{i=1}\frac{(n+d_i)!}{n!d_i!}$ ($=n(n+\max_i d_i)^{O(\min\{n,\max_i d_i)\}}$) is the maximum possible total number of monomial terms for such an $F$. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when $F$ is instead a binomial system --- a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just $O(n^3\log^2(n\max_i d_i))$ arithmetic operations on average. Furthermore, our approach allows Gaussians with arbitrary variance. We also discuss briefly the obstructionsmore »
5. Abstract The objective of this study is to examine the asymptotic behavior of Betti numbers of Čech complexes treated as stochastic processes and formed from random points in the d -dimensional Euclidean space ${\mathbb{R}}^d$ . We consider the case where the points of the Čech complex are generated by a Poisson process with intensity nf for a probability density f . We look at the cases where the behavior of the connectivity radius of the Čech complex causes simplices of dimension greater than $k+1$ to vanish in probability, the so-called sparse regime, as well when the connectivity radius is of the order of $n^{-1/d}$ , the critical regime. We establish limit theorems in the aforementioned regimes: central limit theorems for the sparse and critical regimes, and a Poisson limit theorem for the sparse regime. When the connectivity radius of the Čech complex is $o(n^{-1/d})$ , i.e. the sparse regime, we can decompose the limiting processes into a time-changed Brownian motion or a time-changed homogeneous Poisson process respectively. In the critical regime, the limiting process is a centered Gaussian process but has a much more complicated representation, because the Čech complex becomes highly connected with many topological holes of any dimension.