Search

We prove that the Pommaret-Seiler resolution for quasi-stable ideals is cellular and give a cellular structure for it. This shows that this resolution is a generalization of the well known Eliahou–Kervaire resolution for stable ideals in a deeper sense. We also prove that the Pommaret-Seiler resolution can be reduced to the minimal one via Discrete Morse Theory and provide a constructive algorithm to perform this reduction. [ABSTRACT FROM AUTHOR]

This is the first of a series of papers that develop a systematic bridge between constructions in discrete mathematics and the corresponding continuous analogs. In this paper, we establish an equivalence between Forman's discrete Morse theory on a simplicial complex and the continuous Morse theory (in the sense of any known non-smooth Morse theory) on the associated order complex via the Lovász extension. Furthermore, we propose a new version of the Lusternik–Schnirelman category on abstract simplicial complexes to bridge the classical Lusternik–Schnirelman theorem and its discrete analog on finite complexes. More generally, we can suggest a discrete Morse theory on hypergraphs by employing piecewise-linear (PL) Morse theory and Lovász extension, hoping to provide new tools for exploring the structure of hypergraphs. [ABSTRACT FROM AUTHOR]

We introduce a novel combinatorial method to study Q^{**}-transformations of group presentations or, equivalently, 3-deformations of CW-complexes of dimension 2. Our procedure is based on a refinement of discrete Morse theory that gives a Whitehead simple homotopy equivalence from a regular CW-complex to the simplified Morse CW-complex, with an explicit description of the attaching maps and bounds on the dimension of the complexes involved in the deformation. We apply this technique to show that some known potential counterexamples to the Andrews–Curtis conjecture do satisfy the conjecture. [ABSTRACT FROM AUTHOR]

We introduce a theoretical and computational framework to use discrete Morse theory as an efficient preprocessing in order to compute zigzag persistent homology. From a zigzag filtration of complexes (X i) , we introduce a zigzag Morse filtration whose complexes (A i) are Morse reductions of the original complexes (X i) , and we prove that they both have same persistent homology. This zigzag Morse filtration generalizes the filtered Morse complex of Mischaikow and Nanda Mischaikow and Nanda (Discrete Comput Geom 50(2):330–353, 2013), defined for standard persistence. The maps in the zigzag Morse filtration are forward and backward inclusions, as is standard in zigzag persistence, as well as a new type of map inducing non trivial changes in the boundary operator of the Morse complex. We study in details this last map, and design algorithms to compute the update both at the complex level and at the homology matrix level when computing zigzag persistence. The key point of our construction is that it does not require any knowledge of past and future maps of the input filtration. We deduce an algorithm to compute the zigzag persistence of a filtration that depends mostly on the number of critical cells of the complexes, and show experimentally that it performs better in practice. [ABSTRACT FROM AUTHOR]

Discrete Morse theory, a cell complex-analog to smooth Morse theory allowing homotopic tools in the discrete realm, has been developed over the past few decades since its original formulation by Robin Forman in 1998. In particular, discrete gradient vector fields on simplicial complexes capture important topological features of the structure. We prove that the characteristic polynomials of the Laplacian matrices of a simplicial complex are generating functions for discrete gradient vector fields if the complex is a triangulation of an orientable manifold. Furthermore, we provide a full characterization of the correspondence between rooted forests in higher dimensions and discrete gradient vector fields. [ABSTRACT FROM AUTHOR]

We give a simple proof that the orbit space of the p-subgroup complex of a finite group is contractible using Brown-Forman discrete Morse theory. This result was originally conjectured by Webb [Proc. Sympos. Pure Math., vol. 47, Amer. Math. Soc., Providence, RI, 1987, pp. 349–365] and proved by Symonds [Comment. Math. Helv. 73 (1998), pp. 400–405]. [ABSTRACT FROM AUTHOR]

We construct cellular resolutions for monomial ideals via discrete Morse theory. In particular, we develop an algorithm to create homogeneous acyclic matchings and we call the cellular resolutions induced from these matchings Barile–Macchia resolutions. These resolutions are minimal for edge ideals of weighted oriented forests and (most) cycles. As a result, we provide recursive formulas for graded Betti numbers and projective dimension. Furthermore, we compare Barile–Macchia resolutions to those created by Batzies and Welker and some well-known simplicial resolutions. Under certain assumptions, whenever the above resolutions are minimal, so are Barile–Macchia resolutions. [ABSTRACT FROM AUTHOR]

We study the combinatorics of modular flats of oriented matroids and the topological consequences for their Salvetti complexes. We show that the natural map to the localized Salvetti complex at a modular flat of corank one is what we call a poset quasi-fibration – a notion derived from Quillen's fundamental Theorem B from algebraic K-theory. As a direct consequence, the Salvetti complex of an oriented matroid whose geometric lattice is supersolvable is a K(\pi,1)-space – a generalization of the classical result for supersolvable hyperplane arrangements due to Falk, Randell and Terao. Furthermore, the fundamental group of the Salvetti complex of a supersolvable oriented matroid is an iterated semidirect product of finitely generated free groups – analogous to the realizable case. Our main tools are discrete Morse theory, the shellability of certain subcomplexes of the covector complex of an oriented matroid, a nice combinatorial decomposition of poset fibers of the localization map, and an isomorphism of covector posets associated to modular elements. We provide a simple construction of supersolvable oriented matroids. This gives many non-realizable supersolvable oriented matroids and by our main result aspherical CW-complexes. [ABSTRACT FROM AUTHOR]

We provide a detailed study of topological and combinatorial properties of sectionable tournaments. This class forms an inductively constructed family of tournaments grounded over simply disconnected tournaments, those tournaments whose fundamental groups of acyclic complexes are non-trivial. When T is a sectionable tournament, we fully describe the cell-structure of its acyclic complex Acy(T) by using the adapted machinery of discrete Morse theory for acyclic complexes of tournaments. In the combinatorial side, we demonstrate that the dimension of the complex Acy(T) has a role to play. We prove that if T is a (2r + 1)-sectionable tournament and d is the dimension of Acy(T), then the (acyclic) chromatic number of T satisfies χ (T) ≤ 2 2 − 1 / (r + 1) log (d + 1) − 1 where the logarithm has two as its base. [ABSTRACT FROM AUTHOR]

Any watershed, when defined on a stack on a normal pseudomanifold of dimension d, is a pure (d - 1) -subcomplex that satisfies a drop-of-water principle. In this paper, we introduce Morse stacks, a class of functions that are equivalent to discrete Morse functions. We show that the watershed of a Morse stack on a normal pseudomanifold is uniquely defined and can be obtained with a linear-time algorithm relying on a sequence of collapses. Last, we prove that such a watershed is the cut of the unique minimum spanning forest, rooted in the minima of the Morse stack, of the facet graph of the pseudomanifold. [ABSTRACT FROM AUTHOR]

An h-tiling on a finite simplicial complex is a partition of its geometric realization by maximal simplices deprived of several codimension one faces together with possibly their remaining face of highest codimension. In this last case, the tiles are said to be critical. An h-tiling thus induces a partitioning of its face poset by closed or semi-open intervals. We prove the existence of h-tilings on every finite simplicial complex after finitely many stellar subdivisions at maximal simplices. These tilings are moreover shellable. We also prove that the number of tiles of each type used by a tiling, encoded by its h-vector, is determined by the number of critical tiles of each index it uses, encoded by its critical vector. In the case of closed triangulated manifolds, these vectors satisfy some palindromic property. We finally study the behavior of tilings under any stellar subdivision. [ABSTRACT FROM AUTHOR]

In this article, we prove that the neighborhood complex of the Kneser graph KG3,k is of the same homotopy type as that of a wedge of (k+1)(k+3)(k+4)(k+6)/4 + 1 spheres of dimension k. We construct a maximal subgraph S3,k of KG3,k, whose neighborhood complex deformation retracts onto the neighborhood complex of SG3,k. [ABSTRACT FROM AUTHOR]

Musiker and Reiner in [9] studied coefficients of cyclotomic polynomial in terms of topology of associated simplicial complexes. They determined homotopy type of associated complexes for all cyclotomic polynomials, except for cyclotomic polynomials whose degree is a product of three prime numbers. Using discrete Morse theory for simplicial complexes we partially answer a question posed by the two authors regarding homotopy type of the associated complexes when degree of the cyclotomic polynomial is a product of three prime numbers. [ABSTRACT FROM AUTHOR]

Motivated by the work of Panina and her coauthors on cyclopermutohedron we study a poset whose elements correspond to equivalence classes of partitions of the set { 1 , ⋯ , n + 1 } up to cyclic permutations and orientation reversion. This poset is the face poset of a regular CW complex which we call bi-cyclopermutohedron and denote it by QP n + 1 . The complex QP n + 1 contains subcomplexes homeomorphic to moduli space of certain planar polygons with n + 1 sides up to isometries. In this article we find an optimal discrete Morse function on QP n + 1 and use it to compute its homology with Z as well as Z 2 coefficients. [ABSTRACT FROM AUTHOR]

In this paper, we determine the homotopy type of the Morse complex and matching complex of multiple families of complexes by utilizing star cluster collapses and the Cluster Lemma. We compute the homotopy type of the Morse complex of an extended notion of a star graph, as well as the homotopy type of the matching complex of a Dutch windmill graph. Additionally, we provide alternate computations of the homotopy type of the Morse complex of paths, the homotopy type of the matching complex of paths, and the homotopy type of the matching complex of cycles. We then use this same method of computing homotopy types to investigate the relationship between the homotopy type of the matching complex and the generalized Morse complex. [ABSTRACT FROM AUTHOR]

Recently, Asao and Izumihara introduced CW-complexes whose homology groups are isomorphic to direct summands of the graph magnitude homology group. In this paper, we study the homotopy type of the CW-complexes in connection with the diagonality of magnitude homology groups. We prove that the Asao–Izumihara complex is homotopy equivalent to a wedge of spheres for pawful graphs introduced by Y. Gu. The result can be considered as a homotopy type version of Gu’s result. We also formulate a slight generalization of the notion of pawful graphs and find new non-pawful diagonal graphs of diameter 2. [ABSTRACT FROM AUTHOR]

For a tree T and a positive integer n, let B_nT denote the n-strand braid group on T. We use discrete Morse theory techniques to show that the cohomology ring H^*(B_nT) is encoded by an explicit abstract simplicial complex K_nT that measures n-local interactions among essential vertices of T. We show that, in many cases (for instance when T is a binary tree), H^*(B_nT) is the exterior face ring determined by K_nT. [ABSTRACT FROM AUTHOR]

The combination of persistent homology and discrete Morse theory has proven very effective in visualizing and analyzing big and heterogeneous data. Indeed, topology provides computable and coarse summaries of data independently from specific coordinate systems and does so robustly to noise. Moreover, the geometric content of a discrete gradient vector field is very useful for visualization purposes. The specific case of multivariate data still demands for further investigations, on the one hand, for computational reasons, it is important to reduce the necessary amount of data to be processed. On the other hand, for analysis reasons, the multivariate case requires the detection and interpretation of the possible interdepedance among data components. To this end, in this paper we introduce and study a notion of perfectness for discrete gradient vector fields with respect to multi-parameter persistent homology, called relative-perfectness. As a natural generalization of usual perfectness in Morse theory for homology, relative-perfectness entails having the least number of critical cells relevant for multi-parameter persistence. As a first contribution, we support our definition of relative-perfectness by generalizing Morse inequalities to the filtration structure where homology groups involved are relative with respect to subsequent sublevel sets. In order to allow for an interpretation of critical cells in 2-parameter persistence, our second contribution consists of two inequalities bounding Betti tables of persistence modules from above and below, via the number of critical cells. Our last result is the proof that existing algorithms based on local homotopy expansions allow for efficient computability over simplicial complexes up to dimension 2. [ABSTRACT FROM AUTHOR]

In this paper, we study merge trees induced by a discrete Morse function on a tree. Given a discrete Morse function, we provide a method to constructing an induced merge tree and define a new notion of equivalence of discrete Morse functions based on the induced merge tree. We then relate the matching number of a tree to a certain invariant of the induced merge tree. Finally, we count the number of merge trees that can be induced on a star graph and characterize the induced merge tree. [ABSTRACT FROM AUTHOR]

We study the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. We first show inapproximability of Min-Morse Matching within a factor of 2 log (1 − ϵ) ⁡ n. Our second result shows that Min-Morse Matching is W [ P ] -hard with respect to the standard parameter. Next, we show that Min-Morse Matching with standard parameterization has no FPT approximation algorithm for any approximation factor ρ. The above hardness results are applicable to complexes of dimension ≥2. On the positive side, we provide a factor O (n log ⁡ n) approximation algorithm for Min-Morse Matching on 2-complexes, noting that no such algorithm is known for higher dimensional complexes. Finally, we devise discrete gradients with very few critical simplices for typical instances drawn from a fairly wide range of parameter values of the Costa–Farber model of random complexes. [ABSTRACT FROM AUTHOR]

Given two discrete Morse functions on a simplicial complex, we introduce the connectedness homomorphism between the corresponding discrete Morse complexes. This concept leads to a novel framework for studying the connectedness in discrete Morse theory at the chain complex level. In particular, we apply it to describe a discrete analogy to 'cusp-degeneration' of Morse complexes. A precise comparison between smooth case and our discrete cases is also given. [ABSTRACT FROM AUTHOR]

In this article, we consider the bipartite graphs K 2 × K n. We prove that the connectedness of the complex Hom (K 2 × K n , K m) is m − n − 1 if m ≥ n and m − 3 in all the other cases. Therefore, we show that for this class of graphs, Hom (G , K m) is exactly (m − d − 2) -connected, m ≥ n , where d is the maximal degree of the graph G. [ABSTRACT FROM AUTHOR]

We recently introduced a notion of tilings of geometric realizations of finite relative simplicial complexes and related those tilings to the discrete Morse theory of R. Forman, especially when they have the property of being shellable, a property shared by the classical shellable complexes. We now observe that every such tiling supports a quiver which is acyclic precisely when the tiling is shellable and then, that every shelling induces two spectral sequences which converge to the relative (co)homology of the complex. Their first pages are free modules over the critical tiles of the tiling. [ABSTRACT FROM AUTHOR]

How hard is it to fill a loop in a Cayley graph with an unoriented surface? Following a comment of Gromov in "Asymptotic invariants of infinite groups", we define homological filling functions of groups with coefficients in a group R. Our main theorem is that the coefficients make a difference. That is, for every n ≥ 1 and every pair of coefficient groups A, B ∈ {ℤ,ℚ} ∪ {ℤ/pℤ: p prime}, there is a group whose filling functions for n-cycles with coefficients in A and B have different asymptotic behavior. [ABSTRACT FROM AUTHOR]

Inspired by the works of Forman on discrete Morse theory, which is a combinatorial adaptation to cell complexes of classical Morse theory on manifolds, we introduce a discrete analogue of the stratified Morse theory of Goresky and MacPherson. We describe the basics of this theory and prove fundamental theorems relating the topology of a general simplicial complex with the critical simplices of a discrete stratified Morse function on the complex. We also provide an algorithm that constructs a discrete stratified Morse function out of an arbitrary function defined on a finite simplicial complex; this is different from simply constructing a discrete Morse function on such a complex. We then give simple examples to convey the utility of our theory. Finally, we relate our theory with the classical stratified Morse theory in terms of triangulated Whitney stratified spaces. [ABSTRACT FROM AUTHOR]

Let I be a square-free monomial ideal of projective dimension one. Starting with the Taylor complex on the generators of I r , we use discrete Morse theory to describe a CW complex that supports a minimal free resolution of I r . To do so, we concretely describe the acyclic matching on the faces of the Taylor complex. [ABSTRACT FROM AUTHOR]

The Morse complex M(Δ) of a finite simplicial complex \Delta is the complex of all gradient vector fields on Δ. In this paper we study higher connectivity properties of M(Δ). For example, we prove that M(Δ) gets arbitrarily highly connected as the maximum degree of a vertex of Δ goes to ∞, and for Δ a graph additionally as the number of edges goes to ∞. We also classify precisely when M(Δ) is connected or simply connected. Our main tool is Bestvina–Brady Morse theory, applied to a "generalized Morse complex." [ABSTRACT FROM AUTHOR]

Using the ordered analogue of Farley–Sabalka's discrete gradient field on the configuration space of a graph, we unravel a levelwise behavior of the generators of the pure braid group on a tree. This allows us to generalize Farber's equivariant description of the homotopy type of the configuration space on a tree on two particles. The results are applied to the calculation of all the higher topological complexities of ordered configuration spaces on trees on any number of particles. [ABSTRACT FROM AUTHOR]

Combinatorial vector fields on simplicial complexes introduced by Robin Forman constitute a combinatorial analogue of classical flows. They have found numerous and varied applications in recent years. Yet, their formal relationship to classical dynamical systems has been less clear. In this paper we prove that for every combinatorial vector field on a finite simplicial complex X one can construct a semiflow on the underlying polytope X which exhibits the same dynamics. The equivalence of the dynamical behavior is established in the sense of Conley-Morse graphs and uses a tiling of the topological space X which makes it possible to directly construct isolating blocks for all involved isolated invariant sets based purely on the combinatorial information. [ABSTRACT FROM AUTHOR]

We show how the classical notions of cohomology with local coefficients, CW-complex, covering space, homeomorphism equivalence, simple homotopy equivalence, tubular neighbourhood, and spinning can be encoded on a computer and used to calculate ambient isotopy invariants of continuous embeddings N ↪ M of one topological manifold into another. More specifically, we describe an algorithm for computing the homology H n (X , A) and cohomology H n (X , A) of a finite connected CW-complex X with local coefficients in a Z π 1 X -module A when A is finitely generated over Z. It can be used, in particular, to compute the integral cohomology H n ( X ˜ H , Z) and induced homomorphism H n (X , Z) → H n ( X ˜ H , Z) for the covering map p : X ˜ H → X associated to a finite index subgroup H < π 1 X , as well as the corresponding homology homomorphism. We illustrate an open-source implementation of the algorithm by using it to show that: (i) the degree 2 homology group H 2 ( X ˜ H , Z) distinguishes between the homotopy types of the complements X ⊂ R 4 of the spun Hopf link and Satoh's tube map of the welded Hopf link (these two complements having isomorphic fundamental groups and integral homology); (ii) the degree 1 homology homomorphism H 1 (p − 1 (B) , Z) → H 1 ( X ˜ H , Z) distinguishes between the homeomorphism types of the complements X ⊂ R 3 of the granny knot and the reef knot, where B ⊂ X is the knot boundary (these two complements again having isomorphic fundamental groups and integral homology). Our open source implementation allows the user to experiment with further examples of knots, knotted surfaces, and other embeddings of spaces. We conclude the paper with an explanation of how the cohomology algorithm also provides an approach to computing the set [ W , X ] ϕ of based homotopy classes of maps f : W → X of finite CW-complexes over a fixed group homomorphism π 1 f = ϕ in the case where dim ⁡ W = n , π 1 X is finite and π i X = 0 for 2 ≤ i ≤ n − 1. [ABSTRACT FROM AUTHOR]

Denoising noisy datasets is a crucial task in this data-driven world. In this paper, we develop a persistence-guided discrete Morse theoretic denoising framework. We use our method to denoise point-clouds and to extract surfaces from noisy volumes. In addition, we show that our method generally outperforms standard methods. Our paper is a synergy of classical noise removal techniques and topological data analysis. [ABSTRACT FROM AUTHOR]

The question we address in this paper is: which monomial ideals have minimal cellular resolutions, that is, minimal resolutions obtained from homogenizing the chain maps of CW-complexes? Velasco gave families of examples of monomial ideals that do not have minimal cellular resolutions, but those examples have large minimal generating sets. In this paper, we show that if a monomial ideal has at most four generators, then the ideal and its (monomial) Artinian reductions have minimal cellular resolutions. When the ideal is generated by two monomials, we can give a precise description of the CW-complex supporting minimal free resolution of the ideal and its Artinian reduction. Also, in this case, we compute the multigraded Betti numbers, Cohen-Macaulay type and determine when the corresponding algebra is a level algebra. [ABSTRACT FROM AUTHOR]

Given a locally finite X ⊆ R d and a radius r ≥ 0 , the k-fold cover of X and r consists of all points in R d that have k or more points of X within distance r. We consider two filtrations—one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k—and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in R d + 1 whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module of Delaunay mosaics that is isomorphic to the persistence module of the multi-covers. [ABSTRACT FROM AUTHOR]