The focus of this proposal is homology of finite random simplicial complexes and Betti numbers of these complexes. Specifically, the investigator proposes methods based on combinatorial Hodge's theory to develop estimators for Betti numbers and other topological invariants (such as the Euler characteristic) of finite random complexes. As a direct outcome investigator expects to address questions in the theory of coverage processes, random sensor networks and the theory of random sets. An example of a problem the project will address is estimates for probability of complete coverage for finite coverage processes on closed Riemannian manifolds. This question has been precisely answered only in small number cases, such as the circle, the 2-sphere and very recently in the case of the sphere of arbitrary dimension. By studying a random nerve and Betti numbers associated to the random cover of a coverage process, the investigator seeks to provide insight into to this and related problems in the field. A long term goal of this project is development of a homology theory for (compact) random subsets of a metric space via an analog of a Cech construction adapted to the random setting. An advantage of this approach is reduction of a problem (of e.g. Betti number determination) to the finite probability space, where known numerical techniques can be used to estimate distributions of Betti numbers, and consequently address algorithmic questions involving complete coverage probability, distribution of number of clumps and other topological characteristics of random sets.
There are several practical outcomes expected of this project; one of them is novel coverage criteria for stochastic sensor networks. To elucidate, the reader should imagine that a swarm of cheap sensors is spread over a region in space. Sensors broadcast their unique IDs and have no capabilities to locate themselves (no GPS!) but only are able to determine if a different sensor or a "threat" appears in their neighborhood. The sensors communicate with a central processing node which reads their information via their IDs, the IDs of the neighboring nodes, and potential threats within the region to be secured. Additionally, we may assume that sensors and communication channels have stochastic features, that is, operate correctly only with a given probability or, for example, the sensors are mobile and appear and disappear from each other's sensing range. Under such constraints the methods developed in this project will provide new and effective criteria to determine the probability that the region is secure (i.e., covered by sensors). These criteria will be suitable for implementation in the central processing node as a threat detection algorithm. The further outcome of the proposed project will yield new qualitative approaches to probabilistic models of dust or powder particles, systems of water droplets and other similar processes, where one often is interested in features such as probability of cluster formation or connectivity, which are essential characteristics of these physical systems.
