Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge Random Simplicial Complexes, III; The Critical Dimension
94
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we study the notion of critical dimension of random simplicial complexes in the general multi-parameter model described in our previous papers of this series. This model includes as special cases the Linial-Meshulam-Wallach model as well as the clique complexes of random graphs. We characterise the concept of critical dimension in terms of various geometric and topological properties of random simplicial complexes such as their Betti numbers, the fundamental group, the size of minimal cycles and the degrees of simplexes. We mention in the text a few interesting open questions.
rate research
Read More
In this paper we develop further the multi-parameter model of random simplicial complexes. Firstly, we give an intrinsic characterisation of the multi-parameter probability measure. Secondly, we show that in multi-parameter random simplicial complexes the links of simplexes and their intersections are also multi-parameter random simplicial complexes. Thirdly, we find conditions under which a multi-parameter random simplicial complex is connected and simply connected.
We provide a random simplicial complex by applying standard constructions to a Poisson point process in Euclidean space. It is gigantic in the sense that - up to homotopy equivalence - it almost surely contains infinitely many copies of every compact topological manifold, both in isolation and in percolation.
Given a simplicial complex K with weights on its simplices and a chain on it, the Optimal Homologous Chain Problem (OHCP) is to find a chain with minimal weight that is homologous (over the integers) to the given chain. The OHCP is NP-complete, but if the boundary matrix of K is totally unimodular (TU), it becomes solvable in polynomial time when modeled as a linear program (LP). We define a condition on the simplicial complex called non total-unimodularity neutralized, or NTU neutralized, which ensures that even when the boundary matrix is not TU, the OHCP LP must contain an integral optimal vertex for every input chain. This condition is a property of K, and is independent of the input chain and the weights on the simplices. This condition is strictly weaker than the boundary matrix being TU. More interestingly, the polytope of the OHCP LP may not be integral under this condition. Still, an integral optimal vertex exists for every right-hand side, i.e., for every input chain. Hence a much larger class of OHCP instances can be solved in polynomial time than previously considered possible. As a special case, we show that 2-complexes with trivial first homology group are guaranteed to be NTU neutralized.
We introduce a new algorithm for the structural analysis of finite abstract simplicial complexes based on local homology. Through an iterative and top-down procedure, our algorithm computes a stratification $pi$ of the poset $P$ of simplices of a simplicial complex $K$, such that for each strata $P_{pi=i} subset P$, $P_{pi=i}$ is maximal among all open subposets $U subset overline{P_{pi=i}}$ in its closure such that the restriction of the local $mathbb{Z}$-homology sheaf of $overline{P_{pi=i}}$ to $U$ is locally constant. Passage to the localization of $P$ dictated by $pi$ then attaches a canonical stratified homotopy type to $K$. Using $infty$-categorical methods, we first prove that the proposed algorithm correctly computes the canonical stratification of a simplicial complex; along the way, we prove a few general results about sheaves on posets and the homotopy types of links that may be of independent interest. We then present a pseudocode implementation of the algorithm, with special focus given to the case of dimension $leq 3$, and show that it runs in polynomial time. In particular, an $n$-dimensional simplicial complex with size $s$ and $nleq3$ can be processed in O($s^2$) time or O($s$) given one further assumption on the structure. Processing Delaunay triangulations of $2$-spheres and $3$-balls provides experimental confirmation of this linear running time.
Random abstract simplicial complex representation provides a mathematical description of wireless networks and their topology. In order to reduce the energy consumption in this type of network, we intend to reduce the number of network nodes without modifying neither the connectivity nor the coverage of the network. In this paper, we present a reduction algorithm that lower the number of points of an abstract simplicial complex in an optimal order while maintaining its topology. Then, we study the complexity of such an algorithm for a network simulated by a binomial point process and represented by a Vietoris-Rips complex.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
