Search

We prove amultiple coloured Tverberg theoremand abalanced coloured Tverberg theorem, applying different methods, tools and ideas. The proof of the first theorem uses a multiple chessboard complex (as configuration space) and the Eilenberg–Krasnoselskii theory of degrees of equivariant maps for non-free group actions. The proof of the second result relies on the high connectivity of the configuration space, established by using discrete Morse theory.

This article is an abstract of my presentation at RIMS, June, 2021. We show the relationship between the number of critical simplices, and Betti numbers with persistent pairs , which is an improvement to the discrete Morse inequalities. Furthermore, we prove that given two discrete Morse functions f₁, f₂ on a simple graph, the number of strongly connected number between f₁, f₂ is the Betti number. This result is also an necessary condition to the problem posed in [H. King, K. Knudson, N. M. Kostac, Birth and death in discrete Morse theory. Journal of Symbolic Computation 78 (2017), 41-60.] in case of graphs.

We generalize and extend the Conley-Morse-Forman theory for combinatorial multivector fields introduced in \cite{Mr2017}. The generalization consists in dropping the restrictive assumption in \cite{Mr2017} that every multivector has a unique maximal element. The extension is from the setting of Lefschetz complexes to the more general situation of finite topological spaces. We define isolated invariant sets, isolating neighbourhoods, Conley index and Morse decompositions. We also establish the additivity property of the Conley index and the Morse inequalities., Extended version

We focus on efficient computations of topological descriptors for voxel data. This type of data includes 2D greyscale images, 3D medical scans, but also higher-dimensional scalar fields arising from physical simulations. In recent years we have seen an increase in applications of topological methods for such data. However, computational issues remain an obstacle. We therefore propose a streaming scheme which simplifies large 3-dimensional voxel data - while provably retaining its persistent homology. We combine this scheme with an efficient boundary matrix reduction implementation, obtaining an end-to-end tool for persistent homology of large data. Computational experiments show its state-of-the-art performance. In particular, we are now able to robustly handle complex datasets with several billions voxels on a regular laptop. A software implementation called Cubicle is available as open-source: https://bitbucket.org/hubwag/cubicle., LIPIcs, Vol. 258, 39th International Symposium on Computational Geometry (SoCG 2023), pages 60:1-60:16

In this thesis, we develop algorithms in computational topology for working with regular CW-complexes and calculating associated homological invariants. We adapt the classical notion of broken surface diagrams for describing embeddings of surfaces in 4-dimensional space, and describe algorithms for constructing regular CW-complex structures on the complements of these embedded surfaces. In particular, we develop an algorithm for inputting a virtual knot/link diagram and returning a regular CW-structure on the complement in the 4-sphere of Satoh's Tube map of the virtual knot/link. We also develop algorithms that input classical knot/link diagrams and return regular CW-structures on the complements of the knot/link in the 3-sphere as well as algorithms that perform Dehn surgery on these complements to produce any closed, orientable 3-manifold. We use homological algebra to design isotopy invariants of codimension two embeddings and describe algorithms for computing these invariants. Key illustrations of the algorithms include: - A new method for distinguishing between the granny knot and the reef knot; these knot complements have isomorphic fundamental groups and homology groups. - Recovering a calculation of Faria Martins and Kauffman that distinguishes between the spun Hopf link and the Tube of the welded Hopf link. All algorithms in this thesis are implemented in the GAP computer algebra system and are publicly available as part of the GAP package HAP.

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.

Given a locally finite $$X \subseteq {{{\mathbb {R}}}}^d$$ X ⊆ R d and a radius $$r \ge 0$$ r ≥ 0 , the k-fold cover of X and r consists of all points in $${{{\mathbb {R}}}}^d$$ 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 $${{{\mathbb {R}}}}^{d+1}$$ 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.

We study the restrictions, the strict fixed points, and the strict quotients of the partition complex $|\Pi_n|$, which is the $\Sigma_n$-space attached to the poset of proper nontrivial partitions of the set $\{1,\ldots,n\}$. We express the space of fixed points $|\Pi_n|^G$ in terms of subgroup posets for general $G\subset \Sigma_n$ and prove a formula for the restriction of $|\Pi_n|$ to Young subgroups $\Sigma_{n_1}\times \dots\times \Sigma_{n_k}$. Both results follow by applying a general method, proven with discrete Morse theory, for producing equivariant branching rules on lattices with group actions. We uncover surprising links between strict Young quotients of $|\Pi_n|$, commutative monoid spaces, and the cotangent fibre in derived algebraic geometry. These connections allow us to construct a cofibre sequence relating various strict quotients $|\Pi_n|^\diamond\wedge_{\Sigma_n} (S^\ell)^{\wedge n}$ and give a combinatorial proof of a splitting in derived algebraic geometry. Combining all our results, we decompose strict Young quotients of $|\Pi_n|$ in terms of "atoms" $|\Pi_d|^\diamond\wedge_{\Sigma_d} (S^\ell)^{\wedge d}$ for $\ell$ odd and compute their homology. We thereby also generalise Goerss' computation of the algebraic Andr\'e-Quillen homology of trivial square-zero extensions from $\mathbb{F}_2$ to $\mathbb{F}_p$ for $p$ an odd prime., Comment: Final version to appear in the Publications Math\'ematiques de l'IH\'ES. 79 pages, 15 figures

We prove that the symmetrized deleted join SymmDelJoin( $$\mathcal{K}$$ ) of a “balanced family” $$\mathcal{K}$$ = 〈Ki〉 =1 of collectively r-unavoidable subcomplexes of 2[m] is (m−r−1)-connected. As a consequence we obtain a Tverberg-Van Kampen-Flores type result which is more conceptual and more general than previously known results. Already the case r = 2 of this result seems to be new as an extension of the classical Van Kampen-Flores theorem. The main tool used in the paper is R. Forman’s discrete Morse theory.

We study the combinatorics of crystal graphs given by highest weight representations of types $A_{n}, B_{n}, C_{n}$, and $D_{n}$, uncovering new relations that exist among crystal operators. Much structure in these graphs has been revealed by local relations given by Stembridge and Sternberg. However, there exist relations among crystal operators that are not implied by Stembridge or Sternberg relations. Viewing crystal graphs as edge colored posets, we use poset topology to study them. Using the lexicographic discrete Morse functions of Babson and Hersh, we relate the M\"obius function of a given interval in a crystal poset of simply laced or doubly laced type to the types of relations that can occur among crystal operators within this interval. For a crystal of a highest weight representation of finite classical Cartan type, we show that whenever there exists an interval whose M\"obius function is not equal to -1, 0, or 1, there must be a relation among crystal operators within this interval not implied by Stembridge or Sternberg relations. As an example of an application, this yields relations among crystal operators in type $C_{n}$ that were not previously known. Additionally, by studying the structure of Sternberg relations in the doubly laced case, we prove that crystals of highest weight representations of types $B_{2}$ and $C_{2}$ are not lattices., Comment: 26 pages

With his landmark 1998 paper [7], Robin Forman launched the study of “Morse theory on cell complexes.” The subsequent two decades have seen a tremendous burst of related activity, leading to applic...

In the study of smooth functions on manifolds, min-max theory provides a mechanism for identifying critical values of a function. We introduce a discretized version of this theory associated to a discrete Morse function on a (regular) cell complex. As applications we prove a discrete version of the mountain pass lemma and give an alternate proof of a discrete Lusternik–Schnirelmann theorem.

We introduce a new notion of equivalence of discrete Morse functions on graphs called persistence equivalence. Two functions are considered persistence equivalent if and only if they induce the same persistence diagram. We compare this notion of equivalence to other notions of equivalent discrete Morse functions. Then we compute an upper bound for the number of persistence equivalent discrete Morse functions on a fixed graph and show that this upper bound is sharp in the case where our graph is a tree. This is a version of the “realization problem” of the persistence map. We conclude with an example illustrating our construction.

Шахматные комплексы и их обобщения, как объекты, и дискретная теория Морса, как инструмент, представлены в виде объединяющей темы, связывающая различные области геометрии, топологии, алгебры и комбинаторики. Теорема Эдмондса и Фулкерсона о бутылочном горлышке (минимаксе) реализуется и интерпретируется как результат о критической точке дискретной функции Морса на сфере Бира Bier(K) ассоциированного симплициального комплекса K. Мы проиллюстрируем использование «стандартных дискретных функций Морса» на обобщенных шахматных комплексах, доказав результат связности для шахматных комплексов с кратностями. Приложения включают новые результаты типа Тверберга-Ван Кампена-Флореса для разбиений симплекса без j-кратных пересечений.

Motivated by computational aspects of persistent homology for Vietoris–Rips filtrations, we generalize a result of Eliyahu Rips on the contractibility of Vietoris–Rips complexes of geodesic spaces for a suitable parameter depending on the hyperbolicity of the space. We consider the notion of geodesic defect to extend this result to general metric spaces in a way that is also compatible with the filtration. We further show that for finite tree metrics the Vietoris–Rips complexes collapse to their corresponding subforests. We relate our result to modern computational methods by showing that these collapses are induced by the apparent pairs gradient, which is used as an algorithmic optimization in Ripser, explaining its particularly strong performance on tree-like metric data., LIPIcs, Vol. 224, 38th International Symposium on Computational Geometry (SoCG 2022), pages 15:1-15:15

Persistent homology is a fundamental tool in topological data analysis used for the most diverse applications. Information captured by persistent homology is commonly visualized using scatter plots representations. Despite being widely adopted, such a visualization technique limits user understanding and is prone to misinterpretation. This article proposes a new approach for the efficient computation of persistence cycles, a geometric representation of the features captured by persistent homology. We illustrate the importance of rendering persistence cycles when analyzing scalar fields, and we discuss the advantages that our approach provides compared to other techniques in topology-based visualization. We provide an efficient implementation of our approach based on discrete Morse theory, as a new module for the Topology Toolkit. We show that our implementation has comparable performance with respect to state-of-the-art toolboxes while providing a better framework for visually analyzing persistent homology information.

The Manturov (2, 3)-group G32 is the group generated by three elements a, b, and c with defining relations a2 = b2 = c2 = (abc)2 = 1. We explicitly calculate the Anick chain complex for G32 by algebraic discrete Morse theory and evaluate the Hochschild cohomology groups of the group algebra $$\mathbb{k}G_3^2$$ with coefficients in all 1-dimensional bimodules over a field $$\mathbb{k}$$ of characteristic zero.

Using discrete Morse theory, we give an algorithm that prunes the excess of information in the Taylor resolution and constructs a new cellular free resolution for an arbitrary monomial ideal. The pruned resolution is not simplicial in general, but we can slightly modify our algorithm in order to obtain a simplicial resolution. We also show that the Lyubeznik resolution fits into our pruning strategy. We finally use our methods to give a different approach to the theory of splitting of monomial ideals., 16 pages. Final version, to appear in Journal of Algebra

We study the local homology of Artin groups using weighted discrete Morse theory. In all finite and affine cases, we are able to construct Morse matchings of a special type (we call them "precise matchings"). The existence of precise matchings implies that the homology has a square-free torsion. This property was known for Artin groups of finite type, but not in general for Artin groups of affine type. We also use the constructed matchings to compute the local homology in all exceptional cases, correcting some results in the literature.

In this paper we shall describe a combinatorial method related to Discrete Morse Theory, which allows us to calculate explicit homology cycles in polyhedral complexes. These cycles form a basis, in the case when the critical cells are in an isolated dimension. We illustrate the use of this technique by several examples from combinatorial topology, including the complexes of multihomomorphisms between complete graphs. Our method is optimal from the computational complexity point of view, requiring execution time which is linear in the number of d-cells.

We prove a discrete version of the Lusternik–Schnirelmann (L–S) theorem for discrete Morse functions and the recently introduced simplicial L–S category of a simplicial complex. To accomplish this, a new notion of critical object of a discrete Morse function is presented, which generalizes the usual concept of critical simplex (in the sense of R. Forman). We show that the non-existence of such critical objects guarantees the strong homotopy equivalence (in the Barmak and Minian’s sense) between the corresponding sublevel complexes. Finally, we establish that the number of critical objects of a discrete Morse function defined on K is an upper bound for the non-normalized simplicial L–S category of K.

Forman has developed a version of discrete Morse theory that can be understood in terms of arrow patterns on a (simplicial, polyhedral or cellular) complex without closed orbits, where each cell may either have no arrows, receive a single arrow from one of its facets, or conversely, send a single arrow into a cell of which it is a facet. By following arrows, one can then construct a natural Floer-type boundary operator. Here, we develop such a construction for arrow patterns where each cell may support several outgoing or incoming arrows (but not both), again in the absence of closed orbits. Our main technical achievement is the construction of a boundary operator that squares to 0 and therefore recovers the homology of the underlying complex.

In the 1980's Pierre Julg and Alain Valette, and also Tadeusz Pytlik and Ryszard Szwarc, constructed and studied a certain Fredholm operator associated to a simplicial tree. The operator can be defined in at least two ways: from a combinatorial flow on the tree, similar to the flows in Forman's discrete Morse theory, or from the theory of unitary operator-valued cocycles. There are applications of the theory surrounding the operator to C⁎-algebra K-theory, to the theory of completely bounded representations of groups that act on trees, and to the Selberg principle in the representation theory of p-adic groups. The main aim of this paper is to extend the constructions of Julg and Valette, and Pytlik and Szwarc, to CAT(0) cubical spaces. A secondary aim is to illustrate the utility of the extended construction by developing an application to operator K-theory and giving a new proof of K-amenability for groups that act properly on finite dimensional CAT(0)-cubical spaces.

We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp #P hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as graph embeddings, discrete Morse theory and graph clustering.

Fix a finite undirected graph $\Gamma$ and a vertex $v$ of $\Gamma$. Let $E$ be the set of edges of $\Gamma$. We call a subset $F$ of $E$ pandemic if each edge of $\Gamma$ has at least one endpoint that can be connected to $v$ by an $F$-path (i.e., a path using edges from $F$ only). In 1984, Elser showed that the sum of $\left(-1\right)^{\left| F\right|}$ over all pandemic subsets $F$ of $E$ is $0$ if $E\neq \varnothing$. We give a simple proof of this result via a sign-reversing involution, and discuss variants, generalizations and refinements, revealing connections to abstract convexity (the notion of an antimatroid) and discrete Morse theory., Comment: 25 pages. Final version (published in DMTCS, 2021). More detailed variants of the text can be found in version 8 (arXiv:2009.11527v8)

Given a locally finite set $$X \subseteq {{\mathbb {R}}}^d$$ X ⊆ R d and an integer $$k \ge 0$$ k ≥ 0 , we consider the function $${\mathbf{w}_{k}^{}} :{\mathrm{Del}_{k}{({X})}} \rightarrow {{\mathbb {R}}}$$ w k : Del k ( X ) → R on the dual of the order-k Voronoi tessellation, whose sublevel sets generalize the notion of alpha shapes from order-1 to order-k (Edelsbrunner et al. in IEEE Trans Inf Theory IT-29:551–559, 1983; Krasnoshchekov and Polishchuk in Inf Process Lett 114:76–83, 2014). While this function is not necessarily generalized discrete Morse, in the sense of Forman (Adv Math 134:90–145, 1998) and Freij (Discrete Math 309:3821–3829, 2009), we prove that it satisfies similar properties so that its increments can be meaningfully classified into critical and non-critical steps. This result extends to the case of weighted points and sheds light on k-fold covers with balls in Euclidean space.

Let $I$ be a square-free monomial ideal $I$ 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., Comment: To appear in Journal of Algebraic Combinatorics

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., 24 pages, 3 figures

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. 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 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., 14 pages, 4 figures

Understanding of neuronal circuitry at cellular resolution within the brain has relied on tract tracing methods which involve careful observation and interpretation by experienced neuroscientists. With recent developments in imaging and digitization, this approach is no longer feasible with the large scale (terabyte to petabyte range) images. Machine learning based techniques, using deep networks, provide an efficient alternative to the problem. However, these methods rely on very large volumes of annotated images for training and have error rates that are too high for scientific data analysis, and thus requires a significant volume of human-in-the-loop proofreading. Here we introduce a hybrid architecture combining prior structure in the form of topological data analysis methods, based on discrete Morse theory, with the best-in-class deep-net architectures for the neuronal connectivity analysis. We show significant performance gains using our hybrid architecture on detection of topological structure (e.g. connectivity of neuronal processes and local intensity maxima on axons corresponding to synaptic swellings) with precision/recall close to 90% compared with human observers. We have adapted our architecture to a high performance pipeline capable of semantic segmentation of light microscopic whole-brain image data into a hierarchy of neuronal compartments. We expect that the hybrid architecture incorporating discrete Morse techniques into deep nets will generalize to other data domains.

In this thesis we study the topology of quotients of posets. By the topology of a poset we mean the topology of its order complex called nerve in this thesis. An action of some group on a poset induces an action on its nerve. The posets we consider are partition lattices of finite sets. It is well-known that the nerve of a partition lattice is homotopy equivalent to a wedge of spheres of equal dimension. The symmetric group acts on a partition lattice in a natural way. We consider quotients of such a nerve by subgroups of the symmetric group. Especially we consider subgroups which fix at least one element. It turns out that quotients by such subgroups are also homotopy equivalent to wedges of spheres of equal dimension. Furthermore we consider sublattices of the partition lattice where certain block sizes are forbidden. For the proofs we use Discrete Morse Theory as well as Equivariant Discrete Morse Theory. We use the notion of an acyclic matching. We also develop new methods for Equivariant Discrete Morse Theory by adapting the Patchwork Theorem and poset maps with small fibers from Discrete Morse Theory. There exists an adaption of Discrete Morse Theory to free chain complexes. In this thesis we develop an adaption for the equivariant case.

In this paper, we give a combinatorial interpretation of the cardinality of the relative homology group H d − 1 ( F , R ) for any rooted forest ( F , R ) in a triangulated closed d-manifold M d , w...

Recently, discrete Morse vector fields have been shown to be useful in various applications. Analogous to the simplification of large meshes using edge contractions, one may want to simplify the cell complex K on which a discrete Morse vector field V(K) is defined. To this end, we define a gradient aware edge contraction operator for triangulated 2-manifolds with the following guarantee. If V(K) was generated by a specific persistence-based method, then the vector field that results from our contraction operator is exactly the same as the vector field produced by applying the same persistence-based method to the contracted complex. An implication of this result is that local operations on V(K) are sufficient to produce the persistence-based vector field on the contracted complex. Furthermore, our experiments show that the structure of the vector field is largely preserved by our operator. For example, 1-unstable manifolds remain largely unaffected by the contraction. This suggests that for some applications of discrete Morse theory, it is sufficient to use a contracted complex.

We show that an appropriate generalization of the oriented area function is a perfect Morse function on the space of three-dimensional configurations of an equilateral polygonal linkage with odd number of edges. Therefore cyclic equilateral polygons (which appear as Morse points) are interpreted as independent generators of the homology groups of the (decorated) configuration space.

We address the basic question in discrete Morse theory of combining discrete gradient fields that are partially defined on subsets of the given complex. This is a well-posed question when the discrete gradient field $V$ is generated using a fixed algorithm which has a local nature. One example is ProcessLowerStars, a widely used algorithm for computing persistent homology associated to a grey-scale image in 2D or 3D. While the algorithm for $V$ may be inherently local, being computed within stars of vertices and so embarrassingly parallelizable, in practical use it is natural to want to distribute the computation over patches $P_{i}$, apply the chosen algorithm to compute the fields $V_{i}$ associated to each patch, and then assemble the ambient field $V$ from these. Simply merging the fields from the patches, even when that makes sense, gives a wrong answer. We develop both very general merging procedures and leaner versions designed for specific, easy to arrange covering patterns., 18 pages, 3 figures

We study ν -Schroder paths, which are Schroder paths which stay weakly above a given lattice path ν . Some classical bijective and enumerative results are extended to the ν -setting, including the relationship between small and large Schroder paths. We introduce two posets of ν -Schroder objects, namely ν -Schroder paths and trees, and show that they are isomorphic to the face poset of the ν -associahedron A ν introduced by Ceballos, Padrol and Sarmiento. A consequence of our results is that the i -dimensional faces of A ν are indexed by ν -Schroder paths with i diagonal steps, and we obtain a closed-form expression for these Schroder numbers in the special case when ν is a ‘rational’ lattice path. Using our new description of the face poset of A ν , we apply discrete Morse theory to show that A ν is contractible. This yields one of two proofs presented for the fact that the Euler characteristic of A ν is one. A second proof of this is obtained via a formula for the ν -Narayana polynomial in terms of ν -Schroder numbers.

The celebrated asynchronous computability theorem provides a characterization of the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by writing and taking atomic snapshots of a shared memory. Several variations of the model have been proposed, all equivalent for wait-free solution of decision tasks, in spite of the fact that the protocol complexes that arise from the different models are structurally distinct. The topological and combinatorial properties of these snapshot protocol complexes have been studied in detail, providing explanations for why the asynchronous computability theorem holds in all the models. In reality concurrent systems do not provide processes with snapshot operations. Instead, snapshots are implemented (by a wait-free protocol) using operations that write and read individual shared memory locations. Thus, read/write protocols are also computationally equivalent to snapshot protocols. However, the structure of the read/write protocol complex has not been studied. In this paper we show that the read/write iterated protocol complex is collapsible, using discrete Morse theory. Furthermore, we show that a distributed protocol that wait-free implements atomic snapshots in effect is performing the collapses.

This paper proposes a class of dynamic P systems with constraint of discrete Morse function (DMDP systems). Membrane structure is extended on complex. Rules control activities of membranes. New classes of rules and mechanism to change types of rules by discrete gradient vector field are provided as well.DMDP system extends P systems both in structures and rules. Solving air quality evaluation problem in linear time verifies the effectiveness ofDMDP systems. Since air quality evaluation problem has significance in many areas. The new P systems provide an alternative for traditional membrane computing.

International audience; Discrete gradient vector fields are combinatorial structures that can be used for accelerating the homology computation of CW complexes, such as simplicial or cubical complexes, by reducing their number of cells. Consequently, they provide a bound for the Betti numbers (the most basic homological information). A discrete gradient vector field can eventually reduce the complex to its minimal form, having as many cells of each dimension as its corresponding Betti number, but this is not guaranteed. Moreover, finding an optimal discrete gradient vector field is an NP-hard problem. We describe here a generalization, which we call Homological Discrete Vector Field (HDVF), which can overcome these limitations by allowing cycles under a certain algebraic condition. In this work we define the HDVF and its associated reduction, we study how to efficiently compute a HDVF, we establish the relation between the HDVF and other concepts in computational homology and we estimate the average complexity of its computation. We also introduce five basic operations for modifying a HDVF, which can also be applied to discrete gradient vector fields.

Mapping every simplex in the Delaunay mosaic of a discrete point set to the radius of the smallest empty circumsphere gives a generalized discrete Morse function. Choosing the points from a Poisson point process in ℝn, we study the expected number of simplices in the Delaunay mosaic as well as the expected number of critical simplices and nonsingular intervals in the corresponding generalized discrete gradient. Observing connections with other probabilistic models, we obtain precise expressions for the expected numbers in low dimensions. In particular, we obtain the expected numbers of simplices in the Poisson–Delaunay mosaic in dimensionsn≤ 4.

We consider the problem of analyzing the topology of scalar fields defined on a triangulated shape by using a multi-scale approach, which allows reducing storage costs and computation times, and supports interactive inspection and classification of topological features. We define and implement a multi-scale model that we call a Hierarchical Forman Triangulation (HFT) , where a 3D shape or a terrain is discretized as a triangle mesh, and its topology is described by defining a discrete Morse gradient field based on function values given at the vertices of the mesh. We introduce a new edge contraction operator, which does not change the behavior of the gradient flow and does not create new critical points, and we apply it in combination with a topological simplification operator which eliminates critical elements in pair. By combining the two operators in a sequence, we generate the HFT . We discuss and implement a compact encoding for the HFT that has a lower storage cost with respect to the triangle mesh at full resolution. We show the effectiveness of this new hierarchical model by extracting representations of terrains and shapes endowed with a scalar field at different, uniform and variable, scales and by efficiently computing topological features and segmentations.

We introduce the van der Waerden complex vdW ( n , k ) defined as the simplicial complex whose facets correspond to arithmetic progressions of length k in the vertex set { 1 , 2 , … , n } . We show the van der Waerden complex vdW ( n , k ) is homotopy equivalent to a CW -complex whose cells asymptotically have dimension at most log ⁡ k / log ⁡ log ⁡ k . Furthermore, we give bounds on n and k which imply that the van der Waerden complex is contractible.

Piecewise-linear (PL) Morse theory and discrete Morse theory are used in shape analysis tasks to investigate the topological features of discretized spaces. In spite of their common origin in smooth Morse theory, various notions of critical points have been given in the literature for the discrete setting, making a clear understanding of the relationships occurring between them not obvious. This paper aims at providing equivalence results about critical points of the two discretized Morse theories. First of all, we prove the equivalence of the existing notions of PL critical points. Next, under an optimality condition called relative perfectness, we show a dimension agnostic correspondence between the set of PL critical points and that of discrete critical simplices of the combinatorial approach. Finally, we show how a relatively perfect discrete gradient vector field can be algorithmically built up to dimension 3. This way, we guarantee a formal and operative connection between critical sets in the PL and discrete theories., Comment: In this version, we have fixed some minor typos

We construct a discrete Morse function which induces both a specified gradient vector field and homological sequence on a given tree. After reviewing the basics of discrete Morse theory, we provide an algorithm to construct a discrete Morse function on a tree inducing a desired gradient vector field and homological sequence. We prove that our algorithm is correct, and conclude with an example to illustrate its use.

We call a continuous self-map that reveals itself through a discrete set of point-value pairs a sampled dynamical system. Capturing the available information with chain maps on Delaunay complexes, we use persistent homology to quantify the evidence of recurrent behavior. We establish a sampling theorem to recover the eigenspace of the endomorphism on homology induced by the self-map. Using a combinatorial gradient flow arising from the discrete Morse theory for \v{C}ech and Delaunay complexes, we construct a chain map to transform the problem from the natural but expensive \v{C}ech complexes to the computationally efficient Delaunay triangulations. The fast chain map algorithm has applications beyond dynamical systems., Comment: 22 pages, 8 figures

Discrete stratified Morse theory, first introduced by Knudson and Wang, works toward a discrete analogue of Goresky and MacPherson’s stratified Morse theory. It is inspired by the works of Forman on discrete Morse theory by generalizing stratified Morse theory to finite simplicial complexes. The class of discrete stratified Morse functions is much larger than that of discrete Morse functions. Any arbitrary real-valued function defined on a finite simplicial complex can be made into a discrete stratified Morse function with the proper stratification of the underlying complex. An algorithm is given by Knudson and Wang that constructs a discrete stratified Morse function on any finite simplicial complex equipped with an arbitrary real-valued function. Our media contribution is an open-sourced visualization tool that implements such an algorithm for 2-complexes embedded in the plane, and provides an interactive demo for users to explore the algorithmic process and to perform homotopy-preserving simplification of the resulting stratified complex., LIPIcs, Vol. 164, 36th International Symposium on Computational Geometry (SoCG 2020), pages 82:1-82:4