Search

We develop a new method to compute the homology groups of Alexandroff topological spaces (or equivalently of partially ordered sets) by means of spectral sequences giving a complete and simple description of the corresponding differentials. Applying our tools, we obtain a generalization of a result of Minian in homological Morse theory for posets. [ABSTRACT FROM AUTHOR]

In graph theory, Courcelle's theorem essentially states that, if an algorithmic problem can be formulated in monadic second-order logic, then it can be solved in linear time for graphs of bounded treewidth. We prove such a metatheorem for a general class of triangulations of arbitrary fixed dimension d , including all triangulated d -manifolds: if an algorithmic problem can be expressed in monadic second-order logic, then it can be solved in linear time for triangulations whose dual graphs have bounded treewidth. We apply our results to 3-manifold topology, a setting with many difficult computational problems but very few parameterised complexity results, and where treewidth has practical relevance as a parameter. Using our metatheorem, we recover and generalise earlier fixed-parameter tractability results on taut angle structures and discrete Morse theory respectively, and prove a new fixed-parameter tractability result for computing the powerful but complex Turaev–Viro invariants on 3-manifolds. [ABSTRACT FROM AUTHOR]

In this paper, we prove that the Max Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch [1] . For D -dimensional simplicial complexes, we obtain a ( D + 1 ) ( D 2 + D + 1 ) -factor approximation ratio using a simple edge reorientation algorithm that removes cycles. For D ≥ 5 , we describe a 2 D -factor approximation algorithm for simplicial manifolds by processing the simplices in increasing order of dimension. This algorithm leads to 1 2 -factor approximation for 3-manifolds and 4 9 -factor approximation for 4-manifolds. This algorithm may also be applied to non-manifolds resulting in a 1 ( D + 1 ) -factor approximation ratio. One application of these algorithms is towards efficient homology computation of simplicial complexes. Experiments using a prototype implementation on several datasets indicate that the algorithm computes near optimal results. [ABSTRACT FROM AUTHOR]

Dorpalen-Barry et al. proved Elser's conjecture about signs of Elser's numbers by interpreting them as certain sums of reduced Euler characteristic of an abstract simplicial complex known as U -nucleus complex. We prove a conjecture posed by them regarding the homology of U -nucleus complex. [ABSTRACT FROM AUTHOR]

Homology groups are a prime tool for measuring the connectivity of a network, and their computation in a distributed and adaptive way is mandatory for their use in sensor networks. In this paper, we propose a solution based on the construction of an adaptive discrete vector field from where, thanks to the discrete Morse theory, the generators of the homology groups are extracted. The efficiency and the adaptability of our approach are tested against two applications: the detection and the localization of the holes in the coverage, and the selection of active sensors ensuring complete coverage.

Forman's discrete Morse theory appeared to be useful for providing filtration-preserving reductions of complexes in the study of persistent homology. So far, the algorithms computing discrete Morse matchings have only been used for one-dimensional filtrations. This paper is perhaps the first attempt in the direction of extending such algorithms to multidimensional filtrations. An initial framework related to Morse matchings for the multidimensional setting is proposed, and a matching algorithm given by King, Knudson, and Mramor is extended in this direction. The correctness of the algorithm is proved, and its complexity analyzed. The algorithm is used for establishing a reduction of a simplicial complex to a smaller but not necessarily optimal cellular complex. First experiments with filtrations of triangular meshes are presented. [ABSTRACT FROM AUTHOR]

Suppose M is a finite cell decomposition of a space X and that for 0 = t 0 < t 1 < ⋯ < t r = 1 we have a discrete Morse function F t i : M → R . In this paper, we study the births and deaths of critical cells for the functions F t i and present an algorithm for pairing the cells that occur in adjacent slices. We first study the case where the cell decomposition of X is the same for each t i , and then generalize to the case where they may differ. This has potential applications in topological data analysis, where one has function values at a sample of points in some region in space at several different times or at different levels in an object. [ABSTRACT FROM AUTHOR]

Topological methods are important tools for data analysis, and recently receiving more and more attention in vector field visualization. In this paper, we give an introductory description to some important topological methods in vector field visualization. Besides traditional methods of vector field topology, space-time method and finite-time Lyapunov exponent, we also include in this survey Hodge decomposition, combinatorial vector field topology, Morse decomposition, and robustness, etc. In addition to familiar numerical techniques, more and more combinatorial tools emerge in vector field visualization. The numerical methods often rely on error-prone interpolations and interpolations, while combinatorial techniques produce robust but coarse features. In this survey, we clarify the relevant concepts and hope to guide future topological research in vector field visualization. Graphical abstract: [ABSTRACT FROM AUTHOR]

In [18], a membrane parallel theoretical framework for computing (co)homology information of foreground or background of binary digital images is developed. Starting from this work, we progress here in two senses: (a) providing advanced topological information, such as (co)homology torsion and efficiently answering to any decision or classification problem for sum of k -xels related to be a (co)cycle or a (co)boundary; (b) optimizing the previous framework to be implemented in using GPGPU computing. Discrete Morse theory, Effective Homology Theory and parallel computing techniques are suitably combined for obtaining a homological encoding, called algebraic minimal model, of a Region-Of-Interest (seen as cubical complex) of a presegmented k -D digital image. [ABSTRACT FROM AUTHOR]

We generalize some homotopy calculation techniques such as splittings and matching trees that are introduced for the computations in the case of the independence complexes of graphs to arbitrary simplicial complexes. We then exemplify their efficiency on some simplicial complexes, the devoid complexes of graphs, $\mathcal {D}(G;\mathcal {F})$ whose faces are vertex subsets of G that induce $\mathcal {F}$ -free subgraphs, where G is a multigraph and $\mathcal {F}$ is a family of multigraphs. Additionally, we compute the homotopy type of dominance complexes of chordal graphs. [ABSTRACT FROM AUTHOR]

We consider the problem of segmenting triangle meshes endowed with a discrete scalar function f based on the critical points of f. The watershed transform induces a decomposition of the domain of function f into regions of influence of its minima, called catchment basins. The discrete Morse gradient induced by f allows recovering not only catchment basins but also a complete topological characterization of the function and of the shape on which it is defined through a Morse decomposition. Unfortunately, discrete Morse theory and related algorithms assume that the input scalar function has no flat areas, whereas such areas are common in real data and are easily handled by watershed algorithms. We propose here a new approach for building a discrete Morse gradient on a triangulated 3D shape endowed by a scalar function starting from the decomposition of the shape induced by the watershed transform. This allows for treating flat areas without adding noise to the data. Experimental results show that our approach has significant advantages over existing ones, which eliminate noise through perturbation: it is faster and always precise in extracting the correct number of critical elements. [ABSTRACT FROM AUTHOR]

Sheaves and sheaf cohomology are powerful tools in computational topology, greatly generalizing persistent homology. We develop an algorithm for simplifying the computation of cellular sheaf cohomology via (discrete) Morse theoretic techniques. As a consequence, we derive efficient techniques for distributed computation of (ordinary) cohomology of a cell complex. [ABSTRACT FROM AUTHOR]

Forman's combinatorial vector fields on simplicial complexes are a discrete analogue of classical flows generated by dynamical systems. Over the last decade, many notions from dynamical systems theory have found analogues in this combinatorial setting, such as for example discrete gradient flows and Forman's discrete Morse theory. So far, however, there is no formal tie between the two theories, and it is not immediately clear what the precise relation between the combinatorial and the classical setting is. The goal of the present paper is to establish such a formal tie on the level of the induced dynamics. Following Forman's paper [6], we work with possibly non-gradient combinatorial vector fields on finite simplicial complexes, and construct a flow-like upper semi-continuous acyclic-valued mapping on the underlying topological space whose dynamics is equivalent to the dynamics of Forman's combinatorial vector field on the level of isolated invariant sets and isolating blocks. [ABSTRACT FROM AUTHOR]

Optimal Morse matchings reveal essential structures of cell complexes that lead to powerful tools to study discrete geometrical objects, in particular, discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds through a reduction to the erasability problem. Here, we refine the study of the complexity of problems related to discrete Morse theory in terms of parameterized complexity. On the one hand, we prove that the erasability problem is W[P]-complete on the natural parameter. On the other hand, we propose an algorithm for computing optimal Morse matchings on triangulations of 3-manifolds, which is fixed-parameter tractable in the treewidth of the bipartite graph representing the adjacency of the 1- and 2-simplices. This algorithm also shows fixed-parameter tractability for problems such as erasability and maximum alternating cycle-free matching. We further show that these results are also true when the treewidth of the dual graph of the triangulated 3-manifold is bounded. Finally, we discuss the topological significance of the chosen parameters and investigate the respective treewidths of simplicial and generalized triangulations of 3-manifolds. [ABSTRACT FROM AUTHOR]

The notion of the negative $q$-binomial was recently introduced by Fu, Reiner, Stanton and Thiem. Mirroring the negative $q$-binomial, we show the classical $q$ -Stirling numbers of the second kind can be expressed as a pair of statistics on a subset of restricted growth words. The resulting expressions are polynomials in $q$ and $(1+q)$. We extend this enumerative result via a decomposition of the Stirling poset, as well as a homological version of Stembridge’s $q=-1$ phenomenon. A parallel enumerative, poset theoretic and homological study for the $q$-Stirling numbers of the first kind is done beginning with de Médicis and Leroux’s rook placement formulation. Letting $t=1+q$ we give a bijective combinatorial argument à la Viennot showing the $(q; t)$-Stirling numbers of the first and second kind are orthogonal.

We first show that the braid group over a graph topologically containing no Θ-shape subgraph has a presentation related only by commutators. Then using discrete Morse theory and triple Massey products, we prove that a graph topologically contains none of four prescribed graphs if and only if its 4-braid groups is a right-angled Artin group. [ABSTRACT FROM AUTHOR]

We address the problem of simplifying Morse–Smale complexes computed on volume datasets based on discrete Morse theory. Two approaches have been proposed in the literature based on a graph representation of the Morse–Smale complex (explicit approach) and on the encoding of the discrete Morse gradient (implicit approach). It has been shown that this latter can generate topologically-inconsistent representations of the Morse–Smale complex with respect to those computed through the explicit approach. We propose a new simplification algorithm that creates topologically-consistent Morse–Smale complexes and works both with the explicit and the implicit representations. We prove the correctness of our simplification approach, implement it on volume data sets described as unstructured tetrahedral meshes and evaluate its simplification power with respect to the usual Morse simplification algorithm. [ABSTRACT FROM AUTHOR]

To solve the problem of generating segmentations of meaningful parts from scanned models with freeform surfaces, we explore a compact shape prior-based segmentation approach in this paper. Our approach is inspired by an observation that a variety of natural objects consist of meaningful components in the form of compact shape and these components with compact shape are usually separated with each other by salient features. The segmentation for multiregions is performed in two phases in our framework. First, the segmentation is taken in low-level with the help of discrete Morse complex enhanced by anisotropic filtering. Second, we extract components with compact shape by using agglomerative clustering to optimize the normalized cut metric, in which the affinities of boundary compatibility, 2D shape compactness and 3D shape compactness are incorporated. The practical functionality of our approach is proved by applying it to the application of customized dental treatment. [ABSTRACT FROM PUBLISHER]

We describe an algorithm for computing a finite, and typically small, presentation of the fundamental group of a finite regular CW-space. The algorithm is based on the construction of a discrete vector field on the $$3$$ -skeleton of the space. A variant yields the homomorphism of fundamental groups induced by a cellular map of spaces. We illustrate how the algorithm can be used to infer information about the fundamental group $$\pi _1(K)$$ of a metric space $$K$$ using only a finite point cloud $$X$$ sampled from the space. In the special case where $$K$$ is a $$d$$ -dimensional compact manifold $$K\subset \mathbb R^d$$ , we consider the closure of the complement of $$K$$ in the $$d$$ -sphere $$M_K=\overline{\mathbb S^d\!\setminus \!K}$$ . For a base-point $$x$$ in the boundary $$\partial M_K$$ of the manifold $$M_K$$ one can attempt to determine, from the point cloud $$X$$ , the induced homomorphism of fundamental groups $$\phi :\pi _1(\partial M_K,x)\rightarrow \pi _1(M_K,x)$$ in the category of finitely presented groups. We illustrate a computer implementation for $$K$$ a small closed tubular neighbourhood of a tame knot in $$\mathbb R^3$$ . In this case the homomorphism $$\phi $$ is known to be a complete ambient isotopy invariant of the knot. We observe that low-index subgroups of finitely presented groups provide useful invariants of $$\phi $$ . In particular, the first integral homology of subgroups $$G < \pi _1(M_K)$$ of index at most six suffices to distinguish between all prime knots with 11 or fewer crossings (ignoring chirality). We plan to provide formal time estimates for our algorithm and characteristics of a high performance C++ implementation in a subsequent paper. The prototype computer implementation of the present paper has been written in the interpreted gap programming language for computational algebra. [ABSTRACT FROM AUTHOR]

In this paper, we propose a bio-inspired membrane computational framework for constructing discrete Morse complexes for binary digital images. Our approach is based on the discrete Morse theory and we work with cubical complexes. As example, a parallel algorithm for computing homology groups of binary 3D digital images is designed. [ABSTRACT FROM AUTHOR]

We prove that the complement of a toric arrangement has the homotopy type of a minimal CW-complex. As a corollary we deduce that the integer cohomology of these spaces is torsionfree. We apply discrete Morse theory to the toric Salvetti complex, providing a sequence of cellular collapses that leads to a minimal complex. [ABSTRACT FROM AUTHOR]

We study for a finite simplicial complex $$K$$ and a CW-pair $$(X,A)$$ the associated CW-complex $${\mathcal Z}_K(X,A)$$ , known as the polyhedral product or generalized moment angle-complex. We apply discrete Morse theory to a particular CW-structure on the $$n$$ -sphere moment-angle complexes $${\mathcal Z}_K(D^{n}, S^{n-1})$$ . For the class of simplicial complexes with vertex-decomposable duals, we show that the associated $$n$$ -sphere moment-angle complexes have the homotopy type of wedges of spheres. As a corollary we show that a sufficiently high suspension of any restriction of a simplicial complex with the vertex-decomposable dual is homotopy equivalent to a wedge of spheres. [ABSTRACT FROM AUTHOR]

In this paper, we relate combinatorial conditions for polarizations of powers of the graded maximal ideal with rank conditions on submodules generated by collections of Young tableaux. We apply discrete Morse theory to the hypersimplex resolution introduced by Batzies–Welker to show that the L -complex of Buchsbaum and Eisenbud for powers of the graded maximal ideal is supported on a CW-complex. We then translate the "spanning tree condition" of Almousa–Fløystad–Lohne characterizing polarizations of powers of the graded maximal ideal into a condition about which sets of hook tableaux span a certain Schur module. As an application, we give a complete combinatorial characterization of polarizations of so-called "restricted powers" of the graded maximal ideal. [ABSTRACT FROM AUTHOR]

We prove that the complement of a complexified toric arrangement has the homotopy type of a minimal CW-complex, and thus its homology is torsion-free. To this end, we consider the toric Salvetti complex, a combinatorial model for the arrangement's complement. Using diagrams of acyclic categories we obtain a stratification of this combinatorial model that explicitly associates generators in homology to the "local no-broken-circuit sets'' defined in terms of the incidence relations of the arrangement. Then we apply a suitably generalized form of Discrete Morse Theory to describe a sequence of elementary collapses leading from the full model to a minimal complex.

In his PhD thesis [1] , Abrams proved that, for a natural number n and a graph G with at least n vertices, the n -strand configuration space of G , denoted C n ( G ) , deformation retracts to a compact subspace, the discretized n -strand configuration space, provided G satisfies two conditions: each path between distinct essential vertices (vertices of degree not equal to 2) is of length at least n + 1 edges, and each path from a vertex to itself which is not nullhomotopic is of length at least n + 1 edges. Using Forman's discrete Morse theory for CW-complexes, we show the first condition can be relaxed to require only that each path between distinct essential vertices is of length at least n − 1 . [ABSTRACT FROM AUTHOR]

We provide explicit and efficient reduction algorithms based on discrete Morse theory to simplify homology computation for a very general class of complexes. A set-valued map of top-dimensional cells between such complexes is a natural discrete approximation of an underlying (and possibly unknown) continuous function, especially when the evaluation of that function is subject to measurement errors. We introduce a new Morse theoretic preprocessing framework for deriving chain maps from such set-valued maps, and hence provide an effective scheme for computing the morphism induced on homology by the approximated continuous function. [ABSTRACT FROM AUTHOR]