• Vitae
  Pedagogy with a view towards history
  
• Research Interests
  Topology Papers Project
  

 Research Papers

• Discrete Morse theory for open complexes (with Kevin P. Knudson)

  We develop a discrete Morse theory for open simplicial complexes K=X∖T where X is a simplicial complex and T a subcomplex of X. A discrete Morse function f on K gives rise to a discrete Morse function on the order complex SK of K, and the topology change determined by f on K can be understood by analyzing the the topology change determined by the discrete Morse function on SK. This topology change is given by a structure theorem on the level subcomplexes of SK. Finally, we show that the Borel-Moore homology of K, a homology theory for locally compact spaces, is isomorphic to the homology induced by a gradient vector field on K and deduce corresponding weak Morse inequalities.

• A Second Homotopy Group for Digital Imagess (with Gregory Lupton, Oleg Musin, P. Christopher Staecker, Jonathan Trevino-Marroquin)

  We define a second (higher) homotopy group for digital images. Namely, we construct a functor from digital images to abelian groups, which closely resembles the ordinary second homotopy group from algebraic topology. We illustrate that our approach can be effective by computing this (digital) second homotopy group for a digital 2-sphere.

• On cycles and merge trees (with Julian Bruggemann)

  In this paper, we extend the notion of a merge tree to that of a generalized merge tree, a merge tree that includes 1-dimensional cycle birth information. Given a discrete Morse function on a 1-dimensional regular CW complex, we construct the induced generalized merge tree. We give several notions of equivalence of discrete Morse functions based on the induced generalized merge tree and how these notions relate to one another. As a consequence, we obtain a complete solution to the inverse problem between discrete Morse functions on 1-dimensional regular CW complexes and generalized merge trees. After characterizing which generalized merge trees can be induced by a discrete Morse function on a simple graph, we give an algorithm based on the induced generalized merge tree of a discrete Morse function f:X→R that cancels the critical simplices of f and replaces it with an optimal discrete Morse function.

• The DOPE Distance is SIC: A Stable, Informative, and Computable Metric on Time Series And Ordered Merge Trees (with Christopher J. Tralie, Zachary Schlamowitz, Jose Arbelo, Antonio I. Delgado, Charley Kirk)

  Metrics for merge trees that are simultaneously stable, informative, and efficiently computable have so far eluded researchers. We show in this work that it is possible to devise such a metric when restricting merge trees to ordered domains such as the interval and the circle. We present the ``dynamic ordered persistence editing'' (DOPE) distance, which we prove is stable and informative while satisfying metric properties. We then devise a simple O(N2) dynamic programming algorithm to compute it on the interval and an O(N3) algorithm to compute it on the circle. Surprisingly, we accomplish this by ignoring all of the hierarchical information of the merge tree and simply focusing on a sequence of ordered critical points, which can be interpreted as a time series. Thus our algorithm is more similar to string edit distance and dynamic time warping than it is to more conventional merge tree comparison algorithms. In the context of time series with the interval as a domain, we show empirically on the UCR time series classification dataset that DOPE performs better than bottleneck/Wasserstein distances between persistence diagrams.

• Summation graphs and discrete Morse theory (with Dominic Klyve)

  We study a class of discrete Morse functions defined by a labeling of the vertex set on an infinite graph. In these summation graphs, we label the vertices with a set or multi-set of positive integers, and each edge with the sum of the two adjacent vertices. Such a function from a graph to the integers can be seen to be a discrete Morse function. In this paper, we characterize the homological sequences induced by several such summation graphs.
  

• The Closure Operation as the Foundation of Topology: A Mini-Primary Source Project for Topology Students

• Star clusters in the Matching, Morse, and Generalized Morse complex (with Connor Donovan)

  New York J. Math., 29 (2023) 1393–1412.

  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.
  

• The Digital Hopf Construction (with Greg Luon and John Oprea)

  Topology and its applications, 2023, 108405, ISSN 0166-8641, https://doi.org/10.1016/j.topol.2022.108405.

  Various concepts and constructions in homotopy theory have been defined in the digital setting. Although there have been several attempts at a definition of a fibration in the digital setting, robust examples of these digital fibrations are few and far between. In this paper, we develop a digital Hopf fibration within the category of tolerance spaces. By widening our category to that of tolerance spaces, we are able to give a construction of this digital Hopf fibration which mimics the smooth setting.
  

• Merge trees in discrete Morse theory (with Benjamin Johnson)

  Res Math Sci 9, 49 (2022). https://doi.org/10.1007/s40687-022-00347-x

  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.
  

• Fundamental Theorems of Morse theory on posets (with Desamparados Fernandez-Ternero, Enrique Macias-Virgos, David Mosquera-Lois, and Jose Antonio Vilches)

  AIMS Mathematics, 2022, Volume 7, Issue 8: 14922-14945. doi: 10.3934/math.2022818 

  We prove a version of the fundamental theorems of Morse Theory in the setting of finite spaces or partially ordered sets. By using these results we extend Forman's discrete Morse theory to more general cell complexes and derive the Morse-Pitcher inequalities in the context of finite spaces.
  

• On the homotopy and strong homotopy type of complexes of discrete Morse functions (with Connor Donovan and Maxwell Lin)

  Canadian Mathematical Bulletin, 1-19, 2022, doi:10.4153/S0008439522000121

  In this paper, we determine the homotopy type of the Morse complex of certain collections of simplicial complexes by studying dominating vertices or strong collapses. We show that if $K$ contains two leaves that share a common vertex, then the Morse complex is strongly collapsible and hence has the homotopy type of a point. We also show that the pure Morse complex of a tree is strongly collapsible, thereby recovering as a corollary a result of Ayala et al. In addition, we prove that the Morse complex of a disjoint union $K\sqcup L$ is the Morse complex of the join $K*L$. This result is used to compute the homotopy type of the Morse complex of some families of graphs, including Caterpillar graphs, as well as the automorphism group of a disjoint union for a large collection of disjoint complexes.
  

• Digital Fundamental Groups and Edge Groups of Clique Complexes (with Greg Lupton)

  Jounral of Applied and Computational topology,(2022). https://doi.org/10.1007/s41468-022-00095-5

  In previous work, we have defined---intrinsically, entirely within the digital setting---a fundamental group for digital images. Here, we show that this group is isomorphic to the edge group of the clique complex of the digital image considered as a graph. The clique complex is a simplicial complex and its edge group is well-known to be isomorphic to the ordinary (topological) fundamental group of its geometric realization. This identification of our intrinsic digital fundamental group with a topological fundamental group---extrinsic to the digital setting---means that many familiar facts about the ordinary fundamental group may be translated into their counterparts for the digital fundamental group: The digital fundamental group of any digital circle is Z; a version of the Seifert-van Kampen Theorem holds for our digital fundamental group; every finitely presented group occurs as the (digital) fundamental group of some digital image. We also show that the (digital) fundamental group of every 2D digital image is a free group.
  

• Higher connectivity of the Morse complex (with Matthew C.B. Zaremsky)

  Proceedings of the AMS Series B, 9 (2022), 135–149

  The Morse complex $\morse(\Delta)$ of a finite simplicial complex $\Delta$ is the complex of all gradient vector fields on $\Delta$. In particular $\morse(\Delta)$ encodes all possible discrete Morse functions (in the sense of Forman) on $\Delta$. In this paper we find sufficient conditions for $\morse(\Delta)$ to be connected or simply connected, in terms of certain measurements on $\Delta$. When $\Delta=\Gamma$ is a graph we get similar sufficient conditions for $\morse(\Gamma)$ to be $(m-1)$-connected. The main technique we use is Bestvina--Brady discrete Morse theory, applied to a ``generalized Morse complex'' that is easier to analyze.
  

• Subdivision of Maps of Digital Images (with Greg Lupton and John Oprea)

  Discrete and computational geometry, 67, 698–742 (2022). https://doi.org/10.1007/s00454-021-00350-z

  With a view towards providing tools for analyzing and understanding digitized images, various notions from algebraic topology have been introduced into the setting of digital topology. In the ordinary topological setting, invariants such as the fundamental group are invariants of homotopy type. In the digital setting, however, the usual notion of homotopy leads to a very rigid invariance that does not correspond well with the topological notion of homotopy invariance. In this paper, we establish fundamental results about subdivision of maps of digital images with 1- or 2-dimensional domains. Our results lay the groundwork for showing that the digital fundamental group is an invariant of a much less rigid equivalence relation on digital images, that is more akin to the topological notion of homotopy invariance. Our results also lay the groundwork for defining other invariants of digital images in a way that makes them invariants of this less rigid equivalence.
  

• Homotopy theory in digital topology (with Greg Lupton and John Oprea)

  Discrete and computational geometry, 67 (2022), no. 1, 112–165, doi.org/10.1007/s00454-021-00336-x, doi.org/10.1007/s00454-021-00336-x

  Digital topology is part of the ongoing endeavour to understand and analyze digitized images. With a view to supporting this endeavour, many notions from algebraic topology have been introduced into the setting of digital topology. But some of the most basic notions from homotopy theory remain largely absent from the digital topology literature. We embark on a development of homotopy theory in digital topology, and define such fundamental notions as function spaces, path spaces, and cofibrations in this setting. We establish digital analogues of basic homotopy-theoretic properties such as the homotopy extension property for cofibrations, and the homotopy lifting property for certain evaluation maps that correspond to path fibrations in the topological setting. We indicate that some depth may be achieved by using these homotopy-theoretic notions to give a preliminary treatment of Lusternik-Schnirelmann category in the digital topology setting. This topic provides a connection between digital topology and critical points of functions on manifolds, as well as other topics from topological dynamics.
  

• On the automorphism group of the Morse complex (with Maxwell Lin)

  Advances in Applied Mathematics, Volume 131, October 2021, 102250

  Let $K$ be a finite, connected, abstract simplicial complex. The Morse complex of $K$, first introduced by Chari and Joswig, is the simplicial complex constructed from all gradient vector fields on $K$. We show that if $K$ is neither the boundary of the $n$-simplex nor a cycle, then $\Aut(\mathcal{M}(K))\cong \Aut(K)$. In the case where $K= C_n$, a cycle of length $n$, we show that $\Aut(\mathcal{M}(C_n))\cong \Aut(C_{2n})$. In the case where $K=\pd^n$, we prove that $\Aut(\mathcal{M}(\partial\Delta^n))\cong \Aut(\partial\Delta^n)\times \mathbb{Z}_2$. These results are based on recent work of Capitelli and Minian.
  

• A Fundamental Group for Digital Images (with Greg Lupton and John Oprea)

  Journal of Applied and Computational Topology, 5 (2021), no. 2, 249–311.

  We define a fundamental group for digital images. Namely, we construct a functor from digital images to groups, which closely resembles the ordinary fundamental group from algebraic topology. Our construction differs in several basic ways from previously established versions of a fundamental group in the digital setting. Our development gives a prominent role to subdivision of digital images. We show that our fundamental group is preserved by subdivision.
  

• The realization problem for discrete Morse functions on trees (with Yuqing Liu)

  Algebra Colloquium 27 : 3 (2020) 455-468 DOI: 10.1142/S1005386720000371

  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. We then 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.
  

• Discrete Morse functions, vector fields, and homological sequences on trees (with Ian Rand)

  Involve, a Journal of Mathematics 13-2 (2020), 219--229. DOI 10.2140/involve.2020.13.219

  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.
  

• Topology from Analysis: A Mini-Primary Source Project for Topology Students

  Convergence (June 2020).

  Topology is often described as having no notion of distance, but a notion of nearness. How can such a thing be possible? Isn't this just a distinction without a difference? In this project, we will discover the notion of nearness without distance by studying the work of Georg Cantor and a problem he was investigating involving Fourier series. We will see that it is the relationship of points to each other, and not their distances per se, that is a proper view. We will see the roots of topology organically springing from analysis.
  

• Strong discrete Morse theory and simplicial L-S category: A discrete version of the Lusternik-Schnirelmann Theorem (with Desamparados Fernandez-Ternero, Enrique Macias-Virgos, and Jose Antonio Vilches)

  Discrete and Computational Geometry, 62, (2020), no. 3, 607-623.

  We prove a discrete version of the Lusternik-Schnirelmann theorem for discrete Morse functions and the recently introduced simplicial Lusternik-Schnirelmann 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 Lusternik-Schnirelmann category of $K$.
  

• Knots related by Knotoids (with Colin Adams, Kate Kearney, and Allison Henrich.)

  American Mathematical Monthly, Volume 126, 2019 - Issue 6, 483--490

  Turaev recently introduced the concept of a knotoid as a particular sort of knotted arc. There are several maps from knotoids to ordinary knots, or knotted circles. The two most natural ways of defining such maps give us an interesting relation between pairs of knots. In this paper, we explore this relation and ask the question: which pairs of knots are related to each other by a knotoid?
  

• Homologically equivalent discrete Morse functions (with Michael Agiorgousis, Brian Green, Alex Onderdonk, and Kim Rich)

  Toplogy Proceedings, Volume 54 (2019) 283--294

  A theory of homological equivalence of discrete Morse functions is developed in this paper, extending the work of Ayala et al. This is accomplished by defining the homological sequence associated with a discrete Morse function on any finite simplicial complex and developing its basic properties. These properties allow us to show that certain homological sequences may be viewed as lattice walks satisfying parameters. We count the number of discrete Morse functions up to homological equivalence on all collapsible $2$-dimensional complexes by constructing discrete Morse functions inducing the desired sequence. The paper concludes with an example to illustrate our construction.
  

• The Cantor Set Before Cantor: A Mini-Primary Source Project for Analysis and Topology Students

  Convergence (May 2019)

  A special construction used in both analysis and topology today is known as the Cantor set. Cantor used this set in a paper in the 1880s. Yet it appeared as early as 1875 in a paper by the Irish mathematician Henry John Stephen Smith (1826 - 1883). Smith, who is best known for the Smith{normal form of a matrix, was a professor at Oxford who made great contributions in matrix theory and number theory. In this project, we will explore parts of a paper he wrote titled On the Integration of Discontinuous Functions.
  

• A Persistent Homological Analysis of Network Data Flow Malfunctions (with Karthik Yegnesh)

  Journal of Complex Networks, Issue 6, 1 December 2017, Pages 884-892, https://doi.org/10.1093/comnet/cnx038
  

  Persistent homology has recently emerged as a powerful technique in topological data analysis for analyzing the emergence and disappearance of topological features throughout a filtered space, shown via persistence diagrams. In this paper, we develop an application of ideas from the theory of persistent homology and persistence diagrams to the study of data flow malfunctions in networks with a certain hierarchical structure. In particular, we formulate an algorithmic construction of persistence diagrams that parametrize network data flow errors, thus enabling novel applications of statistical methods that are traditionally used to assess the stability of persistence diagrams corresponding to homological data to the study of data flow malfunctions. We conclude with an application to network packet delivery systems.
  

• Connecting Connectedness: A Mini-Primary Source Project for Topology Students

  Convergence (October 2017)

  Connectedness has become a fundamental concept in modern topology. The concept seems clear enough- a space is connected if it is a "single piece." Yet the definition of connectedness we use today was not what was originally written down. As we will see, connectedness is a classic example of a definition that took decades to arrive at. The first such definition of was given by Georg Cantor in an 1872 paper. After investigating his definition, we trace the evolution of the definition of connectedness through the work of Jordan, Schoenflies, and culminating with the modern definition given by Lennes.
  

• On the Lusternik-Schnirelmann category of a simplicial map (with Willie Swei)

  Topology and its applications, February 2017, Pages 116-128

  In this paper, we study the Lusternik--Schnirelmann category of a simplicial map between simplicial complexes, generalizing the simplicial category of a complex to that of a map. Several properties of this new invariant are shown, including its relevance to simplicial products and fibrations. We relate this category of a map to the classical Lusternik--Schnirelmann category of a map between finite topological spaces. Finally, we show how the simplicial category of a map may be used to define and study a simplicial version of the category weight of Y. Rudyak and J. Strom.
  

• Estimating the discrete Lusternik-Schnirelmann category (with Mimi Tsuruga and Brian Green)

  Topological Methods in Nonlinear Analysis, 45, No. 1 (2015), 103--116

  Let $K$ be a simplicial complex and suppose that $K$ collapses onto $L$. Dene $n$ to be $1$ minus the minimum number of collapsible sets it takes to cover $L$. Then the discrete Lusternik-Schnirelmann category of $K$ is the smallest $n$ taken over all such $L$. In this paper, we give an algorithm which yields an upper bound for the discrete category. We show our algorithm is correct and give several bounds for the discrete category of well-known simplicial complexes. We show that the discrete category of the dunce cap is $2$, implying that the dunce cap is ``further" from being collapsible than Bing's house.
  

• Graph Isomorphisms in Discrete Morse Theory (with Seth Aaronson, Marie Meyer, Mitchell T. Smith, and Laura M. Stibich)

  AKCE International Journal of Graphs and Combinatorics 11 (2014), no. 2, 163--176.

  A discrete Morse function $f$ on a graph $G$ induces a sequence of subgraphs of $G$. In a paper, the authors introduce a notion of equivalence between discrete Morse functions based on a sequence of homology groups induced by the subgraphs of $G$. In this paper, we use the homology sequence to study a new notion of equivalence between discrete Morse functions. This equivalence is based on the isomorphism type of the subgraphs of $G$. We count the number of equivalence classes on a particular collection of graphs, and deduce an upper bound for the number of equivalence classes for a large collection of graphs.
  

• Metric Structures for CW Complexes

  Topology Proceedings, Volume 44 (2014) 117-131

  We investigate the discrete Lusternik--Schnirelmann category of a $1$-dimensional simplicial complex $G$. In this case, the invariant is shown to be the minimum number of subtrees of $G$ whose union is equal to $G$. After some preliminary computations and bounds, we study the discrete category of the product of $1$-complexes. We prove a general upper bound, analogous to the classical upper bound for products in the smooth case, and prove a Ganea-like conjecture for some classes of spaces. We conclude by proposing a Ganea conjecture for all $1$-dimensional complexes.
  

• A Distributed Greedy Algorithm for Constructing Connected Dominating Sets in Wireless Sensor Networks(with Akshaye Dhawan and Michelle Tanco)

  3rd International Conference on Sensor Networks (SENSORNETS), Lisbon, Portugal, January, 2014

  A Connected Dominating Set (CDS) of the graph representing a Wireless Sensor Network can be used as a virtual backbone for routing in the network. Since sensor nodes are constrained by limited on-board batteries, it is desirable to have a small CDS for the network. However, constructing a minimum size CDS has been shown to be a NP-hard problem. In this paper we present a distributed greedy algorithm for constructing a CDS that we call Greedy Connect. Our algorithm operates in two phases, first constructing a dominating set and then connecting the nodes in this set. We evaluate our algorithm using simulations and compare it to the two-hop K2 algorithm in the literature. Depending on the network topology, our algorithm generally constructs a CDS that is up to 30% smaller in size than K2.
  

• Lusternik--Schnirelmann category for simplicial complexes (with Seth Aaronson)

  Illinois J. Math. 57 (2013), no. 3, 743--753.

  The discrete version of Morse theory due to Robin Forman is a powerful tool utilized in the study of topology, combinatorics, and mathematics involving the overlap of these fields. Inspired by the success of discrete Morse theory, we take the first steps in defining a discrete version of the Lusternik--Schnirelmann category suitable for simplicial complexes. This invariant is based on collapsibility as opposed to contractibility, and is defined in the spirit of the geometric category of a topological space. We prove some basic results of this theory, showing where it agrees and differs from that of the smooth case. Our work culminates in a discrete version of the Lusternik--Schnirelmann theorem relating the number of critical points of a discrete Morse function to its discrete category.
  

• Lusternik--Schnirelmann Category and the Connectivity of $X$

  Algebraic & Geometric Topology 12 (2012) 435-448

  In this paper we define and study a homotopy invariant called the connectivity weight to compute the weighted length between spaces $X$ and $Y$. This is an invariant based on the connectivity of $A_i$, where $A_i$ is a space attached in a mapping cone sequence from $X$ to $Y$. We use the Lusternik--Schnirelmann category to prove a theorem concerning the connectivity of all spaces attached in any decomposition from $X$ to $Y$. This theorem is used to prove that for any positive rational number $q$, there is a space $X$ such that $q=\mathrm{cl}^{\omega}(X)$, the connectivity weighted cone-length of $X$. We compute $\mathrm{cl}^{\omega}(X)$ and $\mathrm{kl}^{\omega}(X)$ for many spaces and give several examples.
  

• Georg Cantor at the Dawn of Point-Set Topology

  Loci (March 2012), DOI: 10.4169/loci003861

  A first course in point-set topology can be challenging for the student because of the abstract level of the material. In an attempt to mitigate this problem, we use the history of point-set topology to obtain natural motivation for the study of some key concepts. In this paper, we study an 1872 paper by Georg Cantor. We will look at what Cantor was attempting to accomplish and see how the now familiar concepts of a point-set and derived set are natural answers to his problem. We emphasize ways to utilize Cantor's methods in order to introduce point-set topology to the student.
  

• Mapping Cone Sequences and a Generalized Notion of Cone Length

  JP Journal of Geometry and Topology, Volume 11, Issue 3, November 2011, 209-233

  We introduce a weighted length between spaces. This is accomplished by using the numerical invariants of cone length and killing length as a framework and by considering other topological invariants to determine the complexity of spaces. This leads us to the definition of a weighted length between spaces. We estimate the weighted length amongst certain maps and spaces for pushouts, pullbacks, and fibrations. Examples of specific weights are given to show that hypotheses in theorems are necessary.
  

• Categorical Sequences (with Rob Nendorf and Jeff Strom)

  Algebraic & Geometric Topology 6 (2006) 809-838

  We define and study the categorical sequence of a space, which is a new formalism that streamlines the computation of the Lusternik-Schnirelmann category of a space $X$ by induction on its CW skeleta. The $k^{th}$ term in the categorical sequence of a CW complex $X$, $\sigma_X(k)$, is the least integer $n$ for which $\mathrm{cat}_X(X_n) = k$. We show that $\sigma_X$ is a well-defined homotopy invariant of $X$. We prove that $\sigma_X(k + l) = \sigma_X(k) + \sigma_X(l)$, which is one of three keys to the power of categorical sequences. In addition to this formula, we provide formulas relating the categorical sequences of spaces and some of their algebraic invariants, including their cohomology algebras and their rational models; we also find relations between the categorical sequences of the spaces in a fibration sequence and give a preliminary result on the categorical sequence of a product of two spaces in the rational case. We completely characterize the sequences which can arise as categorical sequences of formal rational spaces. The most important of the many examples that we offer is a simple proof of a theorem of Ghienne: if $X$ is a member of the Mislin genus of the Lie group $S_p(3), then $\mathrm{cat}_(X) = \mathrm{cat}(Sp(3)).$
  

• Homology of Boolean functions and the complexity of simplicial homology (with Erick Chastain)

  We study the topology of Boolean functions from the perspective of Simplicial Homology, and characterize Simplicial Homology in turn by using Monotone Boolean functions. In so doing, we analyze to what extent topological invariants of Boolean functions (for instance the Euler characteristic) change under binary operations over Boolean functions and other operations, such as permutations over the input variables. We apply these tools to proving the $\Delta^p_2$ -hardness of calculating the Euler characteristic of general Boolean functions (as defined by Kulkarni and Santha) and the co-NP-hardness of calculating the Euler characteristic for a simplicial complex of arbitrary dimension. We also show that calculating the Betti numbers for Simplicial Homology is co-NP hard.
  

Back to Scoville's homepage

---

Last modified on January 16, AD 2024