Do you want to publish a course? Click here

Algorithmic canonical stratifications of simplicial complexes

84   0   0.0 ( 0 )
 Added by Jay Shah
 Publication date 2018
  fields
and research's language is English




Ask ChatGPT about the research

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.



rate research

Read More

202 - A. Costa , M. Farber 2015
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.
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.
In this paper, we study Formans discrete Morse theory in the context of weighted homology. We develop weight
93 - A. Costa , M. Farber 2015
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.
In many scientific and technological contexts we have only a poor understanding of the structure and details of appropriate mathematical models. We often, therefore, need to compare different models. With available data we can use formal statistical model selection to compare and contrast the ability of different mathematical models to describe such data. There is, however, a lack of rigorous methods to compare different models emph{a priori}. Here we develop and illustrate two such approaches that allow us to compare model structures in a systematic way {by representing models in terms of simplicial complexes}. Using well-developed concepts from simplicial algebraic topology, we define a distance between models based on their simplicial representations. Employing persistent homology with a flat filtration provides for alternative representations of the models as persistence intervals, which represent the structure of the models, from which we can also obtain the distances between models. We then expand on this measure of model distance to study the concept of model equivalence in order to determine the conceptual similarity of models. We apply our methodology for model comparison to demonstrate an equivalence between a positional-information model and a Turing-pattern model from developmental biology, constituting a novel observation for two classes of models that were previously regarded as unrelated.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا