HYPERGRAPHS AND THEIR HOMOLOGY By Christopher Potvin A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of Mathematicsβ€”Doctor of Philosophy 2023 ABSTRACT It is commonplace today for scientists to study networks where interactions among the participants happen at higher orders, where any number of participants can be related at once. Graphs, the typical mathematical model for networks, can only display pairwise relationships, and are sometimes inadequate in these situations. The combinatorial structures that have been used to model higher order networks and generalize graphs, and which will play a major role in this thesis, are hypergraphs and simplicial complexes. Hypergraphs have grown in popularity over the past decades, and are becoming standard combinatorial objects used in network representations. They differ from graphs only in that an edge in a hypergraph can have any number of vertices, not just two. Simplicial complexes, another generalization of graphs, have become ubiquitous in algebraic topology. In part, this is because the homology of simplicial complexes is standard. Homology is a tool for studying properties of the shape of topological spaces, and has proven to be useful in topology for classifying spaces as it is a topological invariant. In data science, researchers study the homology of simplicial complexes that change with the data. Keeping track of the simplicial complexes over time allows them to ascertain when changes in the homology are caused by meaningful changes in the data. Hypergraphs are also generalizations of simplicial complexes, however, the homology of hy- pergraphs is currently a problematic gap in the theory. No universal theory of homology for hypergraphs has been established, and the definition of homology for simplicial complexes does not extend obviously. Nonetheless, there has been research done into the homology of hyper- graphs. The two homology theories for hypergraphs studied in this thesis are called the restricted barycentric homology and the relative barycentric homology. We present novel combinatorial definitions, topological and classification results, and methods for computation. This thesis aids in the development of theory, interpretability, and data science of topological hypergraph analytics. Copyright by CHRISTOPHER POTVIN 2023 ACKNOWLEDGEMENTS I would like to begin by thanking my wife Cassie, my parents, sister, in-laws, and extended family for their patience and support while I was a graduate student. They always gave me the time and space I needed when I was studying, reading, or writing. I am also grateful for my friends, both among fellow graduate students at MSU and outside of school, who have helped to keep me sane-ish. My advisor, Dr. Liz Munch, was incredibly helpful for the past three years. She was willing to take on a new mentee as the pandemic started and allowed me to choose a research area not directly related to her own. She always reminded me of the big picture, and had time for me when I needed it. I appreciate everyone whom I have met through MunchLab’s weekly meetings, which have always served to motivate me. I was fortunate to do an internship at Pacific Northwest National Laboratory (PNNL), which was a great opportunity and experience for me. I would like to thank everyone I met there for including me as one of their own; the authors of [22] form a nonexhaustive list. Dr. Emilie Purvine, in particular, served on my graduate committee, encouraged me to apply for the internship, and mentored me while I was interning. Throughout this thesis, the symbol † will be used to denote a result that I worked on during my time at PNNL. iv TABLE OF CONTENTS LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi CHAPTER 1: INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 CHAPTER 2: BACKGROUND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1: Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2: Simplicial Complexes and their Homology . . . . . . . . . . . . . . . . . . . . 14 2.3: Hypergraph Homology Theories . . . . . . . . . . . . . . . . . . . . . . . . . 26 CHAPTER 3: RESULTS ON THE RESTRICTED BARYCENTRIC HOMOLOGY . . 35 3.1: Restricted Barycentric Subdivision . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2: Restricted Barycentric Homology . . . . . . . . . . . . . . . . . . . . . . . . . 37 CHAPTER 4: RESULTS ON THE RELATIVE BARYCENTRIC HOMOLOGY . . . . 43 4.1: Two Versions of a Mayer-Vietoris Sequence . . . . . . . . . . . . . . . . . . . 44 4.2: Results on Maximum Edge Hypergraphs . . . . . . . . . . . . . . . . . . . . . 52 4.3: Results on General Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . 63 CHAPTER 5: BRIDGING THE THEORIES AND COMPUTATION . . . . . . . . . . 77 5.1: Results Bridging the Relative and Restricted Barycentric Homologies . . . . . 77 5.2: Computation of the Restricted and Relative Barycentric Homologies . . . . . . 80 CHAPTER 6: DYNAMIC HYPERGRAPHS . . . . . . . . . . . . . . . . . . . . . . . 87 6.1: Adding an Edge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.2: Adding a Vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 CHAPTER 7: CONCLUSIONS AND FUTURE WORK . . . . . . . . . . . . . . . . . 102 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 v LIST OF FIGURES Figure 2.1 A hypergraph H and a reduced hypergraph H β€². . . . . . . . . . . . . . . . . . 7 Figure 2.2 A hypergraph H and its line graph 𝐿(H ). . . . . . . . . . . . . . . . . . . . . 8 Figure 2.3 A hypergraph H and its complement Comp(H ). . . . . . . . . . . . . . . . . . 9 Figure 2.4 A hypergraph H , its complement Comp(H ), and its supplement Supp(H ). . . 10 Figure 2.5 Of these two hypergraphs, H and 𝐾, only 𝐾 is a simplicial complex. . . . . . . 15 Figure 2.6 A simplicial complex 𝐾, its barycentric subdivision 𝑇, and a generated sub- complex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Figure 2.7 Comparing a hypergraph and simplicial model of a biological system. . . . . . . 27 Figure 2.8 A hypergraph H and its barycentric subdivision 𝑇 with the restricted barycen- tric subdivision highlighted. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Figure 2.9 A hypergraph H and its barycentric subdivision 𝑇 with the missing subcom- plex highlighted. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Figure 3.1 Hypergraphs with different fence components than connected components. . . . 41 Figure 3.2 Hypergraphs used as examples of Theorem 3.2.6. . . . . . . . . . . . . . . . . 42 Figure 4.1 A hypergraph H with computation of 𝐻 π‘Ÿπ‘’π‘™ (H ). . . . . . . . . . . . . . . . . . 55 Figure 4.2 A hypergraph H used as an example for Theorem 4.2.7. . . . . . . . . . . . . . 58 Figure 4.3 Hypergraphs used as examples for Theorem 4.2.9. . . . . . . . . . . . . . . . . 60 Figure 4.4 A hypergraph H used as an example for Theorem 4.2.10. . . . . . . . . . . . . 63 Figure 4.5 A hypergraph H with multiple connected components. . . . . . . . . . . . . . 64 Figure 4.6 A non maximum edge hypergraph H with contractible 𝐾. . . . . . . . . . . . . 65 Figure 4.7 A non maximum edge hypergraph H with contractible 𝑆. . . . . . . . . . . . . 68 Figure 4.8 A hypergraph for which the map 𝐻1 (𝑆) β†’ 𝐻1 (𝐾) is not zero. . . . . . . . . . . 69 Γ‰ Figure 4.9 A hypergraph for which π»π‘›π‘Ÿπ‘’π‘™ (H ) = 𝐻𝑛 (𝐾) π»π‘›βˆ’1 (𝑆). . . . . . . . . . . . . . 70 Figure 4.10 Three different hypergraphs with the same toplexes. . . . . . . . . . . . . . . . 75 Figure 5.1 A hypergraph H used as an example for Theorem 5.1.2. . . . . . . . . . . . . . 79 vi Figure 5.2 A hypergraph H and its missing subcomplex and restricted barycentric sub- division. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Figure 6.1 Three hypergraphs used as examples for Proposition 6.1.1. . . . . . . . . . . . . 89 Figure 6.2 A hypergraph where adding the edge 𝐢𝐷 merged two simplicial components. . 91 Figure 6.3 A hypergraph where adding the edge 𝐴 reduced π›½π‘Ÿπ‘’π‘  0 (H ) . . . . . . . . . . . . 95 Figure 6.4 A hypergraph used as an example for Theorem 6.2.1. . . . . . . . . . . . . . . 99 Figure 6.5 A hypergraph used as an example for Theorem 6.2.2. . . . . . . . . . . . . . . 101 vii CHAPTER 1 INTRODUCTION Studying mathematics and analyzing data with network representations is a concept as old as particular trip of Euler through KΓΆnigsberg, and a generic traveling salesperson looking for the shortest path to travel to all of the cities on their itinerary. Traditionally, those networks have been modeled using graphs. However, over the course of the 20th century, graphs have occasionally been found lacking because, by default, they only encode pairwise interactions. It is commonplace today for scientists to study networks where interactions among the participants happen at higher orders. For example, researchers in biology have found evidence of a three way symbiotic relationship where no two of the organisms would be able to survive without the third [23]. They discovered this network while studying a plant that was surviving in warmer soil than it would typically be able to live. Originally, they found a fungus on the plant and thought the fungus and the plant were in a symbiotic relationship, but later, they found a virus using the fungus as a host. Researchers isolated and removed the virus, and the fungus and the plant died. The fungus and the virus could not live without the plant, and the virus and the plant died without the fungus. If data scientists wanted to use a combinatorial object to model this data, a graph would be insufficient because there is a three way relationship without any of the two way subsets that would need to be displayed in a graph. The combinatorial structures that have been used to generalize graphs, and which will play a major role in this thesis, are hypergraphs and simplicial complexes. Surveys of historical and current methods of studying higher order networks can be found in the following: [3, 4, 6, 31]. Hypergraphs have grown in popularity over the past decades, and are becoming standard combinatorial objects used in network representations [5, 8]. Similar to graphs, hypergraphs can be studied via notions of their path components [17, 1, 21], or via ideas of acyclicity [15, 10]. Some fields where researchers have studied hypergraphs include biology for gene identification [16], urban traffic networks [17], and the domain name system [20]. Simplicial complexes, another generalization of graphs to higher order networks, have become ubiquitous in algebraic topology. In part, this is because the homology of simplicial complexes is 1 standard [18, 24]. Homology is a tool for studying properties of the shape of topological spaces. Given a topological space, the homology of that space is represented by a group in every integer dimension greater than or equal to zero. The ranks of these groups are called the Betti numbers. In dimension zero, the Betti number is the number of connected components of the space. In dimension one, it is the number of loops, or one dimensional holes. This increases with the dimension, so in dimension two, the Betti number represents the number of hollow voids in the space, and so on. Homology has proven to be useful in topology for classifying spaces as it is a topological invariant. In data science, researchers track the homology of simplicial complexes that change with the data. Keeping track of the simplicial complexes over time allows them to ascertain when changes in the data cause changes in the homology. This process, called persistent homology, is one of the major successes of the field of topological data analysis. Topological data analysis is the name given to the science of using topological methods to model and analyze data, an umbrella under which this thesis also falls. Hypergraphs can also be viewed as generalizations of simplicial complexes, however, the lack of a notion of homology of hypergraphs is currently a problematic gap in the theory. No universal theory of homology for hypergraphs has been established, and the definition of homology for simplicial complexes does not extend obviously. Nonetheless, there has been research done into defining a homology of hypergraphs. First, researchers embedded hypergraphs into a particular simplicial complex and found the homology of that complex [26, 25]. However, many different hypergraphs will have the same simplicial complex. One group of researchers studying hypergraph homology defined the embedded homology [7], which fits a hypergraph to the closest chain complex (the algebraic structure needed for homology). They have also expanded that theory with typical homology results like relative homology, a Mayer-Vietoris sequence, and a KΓΌnneth formula [7, 33, 29, 30]. One drawback of the embedded homology is that it abstractifies the original hypergraph to an unrecognizable state, making it difficult to glean information about the original hypergraph from this homology theory. Other theories on the homology of hypergraphs have crept up as well, includin algebraic theories on rings and ideals associated to hypergraphs [14] and 1-dimensional 2 homology on oriented hypergraphs [12]. There are two additional homology theories for hypergraphs that rely on the barycentric sub- division of the associated simplicial complex [28], which are the focus of this thesis. The first of these constructions, the restricted barycentric homology, only considers the subset of simplices of the barycentric subdivision which are included as edges in the hypergraph. The second is the relative barycentric homology for hypergraphs, where given the same barycentric subdivision, the homology is computed relative to the subcomplex of the simplices that are not edges in the hyper- graph. This latter definition of homology does a good job of accounting for the missing subedges, thus discriminating between different hypergraphs with the same associated simplicial complex. This thesis contributes to the study of hypergraph homology by developing the theory of the restricted and relative barycentric homology. We accomplish this simultaneously in three directions: combinatorics, topology, and data science. We start by manipulating standard results from algebraic topology like the Mayer-Vietoris sequence and the long exact sequence of a pair to make it easier to calculate the homology of complicated hypergraphs. These tools allow us to completely classify the relative barycentric homology in several dimensions of a specific type of hypergraph called a maximum edge hypergraph. In order to interpret these results, we also needed novel combinatorial definitions not found in the hypergraph literature. These new concepts include the ideas of the supplement of a hypergraph, and its fence components, an alternative to the traditional idea of connected components. Lastly, we made advancements towards using these methods in data science by finding techniques to simplify the computation and developing results that account for changes in the hypergraph. The computations discussed in this thesis were implemented in HyperNetX, an open source python package for hypergraph analytics [27]. We have studied how the changes in a hypergraph over a filtration will affect the relative and restricted barycentric homology. We will conclude the introduction with an outline of the contents of the paper. The next chapter contains background information: Section 2.1 on hypergraphs and Section 2.2 on simplicial complexes and their homology. Section 2.3 gives the definitions of the restricted and relative 3 barycentric homology for hypergraphs. Chapter 3 contains development of the restricted barycentric homology. The chapter on the relative barycentric homology, Chapter 4, is split into three sections: Section 4.1 on Mayer-Vietoris theorems for hypergraphs, Section 4.2 on results for maximum edge hypergraphs, and Section 4.3, which contains results on the relative barycentric homology that apply to general hypergraphs, and not just maximum edge hypergraphs. Chapter 5 discusses some results that bridge the relative and restricted versions of the theory, and also contains Section 5.2, which is about computation. Dynamic hypergraphs are studied in Chapter 6. This thesis finishes with some concluding remarks and discussions of potential directions for future research in Chapter 7. 4 CHAPTER 2 BACKGROUND In this chapter, we will introduce the main objects of study, and the primary techniques used to study them. First up will be an introduction to hypergraphs, including several novel definitions. Then, we will introduce simplicial complexes, objects that are both combinatorial and topological in nature. One major advantage of simplicial complexes is that they have a well studied homology theory [24, 18], which is not true for hypergraphs. We will define simplicial homology and give a few traditional results that we will analogize to hypergraphs later in this thesis. The last thing in this chapter will be the definitions of the restricted and relative barycentric homology of hypergraphs. These definitions were originally given by Emilie Purvine and collaborators [28]. The bulk of this thesis will be developing the homology theory further for these two definitions. 2.1 Hypergraphs A hypergraph is a combinatorial object that generalizes vertex-edge graphs. Informally, hyper- graphs are graphs where an edge can have any number of vertices, not just two. Hypergraphs are becoming increasingly utilized because of their ability to represent multirelational network data. Two standard references for hypergraphs are [5, 8]. This section will be split into two parts. The first contains standard hypergraph definitions. Versions of these definitions can be found in [8] unless otherwise noted. The second part consists of new definitions and set-theoretic results on hypergraphs. 2.1.1 Standard Hypergraph Definitions We will begin with the definition of a hypergraph. Similarly to a graph, a hypergraph consists of vertices and edges, with the difference being that an edge can have any number of vertices. Definition 2.1.1 (Hypergraph). A hypergraph H consists of two sets: a set of vertices 𝑉 = {𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑛 } and a set of edges, each of which is a nonempty subset of the vertex set, 𝐸 = {𝑒 1 , 𝑒 2 , . . . , 𝑒 π‘š | 𝑒𝑖 βŠ‚ 𝑉 }. 5 We will assume in perpetuity that neither 𝑉 nor 𝐸 is empty and that every vertex is in some edge, i.e. that there are no isolated vertices [8]. Because of this property, a hypergraph is well-defined given only the edge set. Henceforth, we will use the notation 𝑒 ∈ H in place of 𝑒 ∈ 𝐸 to mean that 𝑒 is an edge in the hypergraph H , and will not consider the hypergraph any different from its edge set. We will occasionally specify the edge set 𝐸 or the vertex set 𝑉 when it is convenient. The next definition comes from [27], where it is used to simplify hypergraphs that have repeated edges. Definition 2.1.2 (Edge-Collapsed Hypergraph). A hypergraph is said to be edge-collapsed if for all 𝑖 β‰  𝑗, 𝑒𝑖 β‰  𝑒 𝑗 . All hypergraphs are henceforth assumed to be edge-collapsed, so there will not be any hyper- graphs that have more than one copy of the same edge. This is analogous to avoiding multigraphs when studying graph theory. A hypergraph that is a subset of another hypergraph will be called a subhypergraph. Throughout this thesis, it will often be important whether or not an edge is contained in another edge. We will use the terminology subedge [11] to describe an edge that is a subset of another edge, and toplex [28] to describe an edge that is not a subset of another edge. Definition 2.1.3 (Subedge). Let H be a hypergraph and 𝑒𝑖 , 𝑒 𝑗 ∈ H such that 𝑒𝑖 βŠ‚ 𝑒 𝑗 . Then 𝑒𝑖 is called a subedge in H and in particular it is a subedge of 𝑒 𝑗 . Definition 2.1.4 (Toplex). Let H be a hypergraph and 𝑒𝑖 ∈ 𝐸 such that βˆ€π‘’ ∈ 𝐸, 𝑒𝑖 βŠ„ 𝑒. Then 𝑒𝑖 is called a toplex of H . Since an edge is either a subset of some other edge or a subset of no other edges, every edge in a hypergraph is a subedge or a toplex. Hypergraphs that have no subedges will also play an important role, particularly in Theorems 3.2.2 and 4.3.9. Definition 2.1.5 (Reduced Hypergraph). Let H be a hypergraph. It will be called a reduced hypergraph if it does not have any subedges, or equivalently, if every edge is a toplex. A reduced hypergraph is also called a simple hypergraph in [8] and other places. A reduced hypergraph H β€² that has the same toplexes as a hypergraph H will be called its reduction. Figure 6 Figure 2.1 A hypergraph H and a reduced hypergraph H β€². 2.1 gives our first two examples of a hypergraph, H and H β€². Notice that both hypergraphs have the same vertex set, {𝐴, 𝐡, 𝐢, 𝐷}, but there are different edge sets, H = {𝐴𝐡𝐢, 𝐡𝐢𝐷, 𝐡, 𝐢} and H β€² = {𝐴𝐡𝐢, 𝐡𝐢𝐷}. Here, H β€² does not have any edges that are subedges, and so it is a reduced hypergraph, and since H has the same toplexes, H β€² is the reduction of H . There are multiple ways of turning a hypergraph back into a graph. One can turn a hypergraph into a bipartite graph by using 𝑉 and 𝐸 as the vertex sets of the bipartite graph, with graph edges from 𝑣 ∈ 𝑉 to 𝑒 ∈ 𝐸 if 𝑣 ∈ 𝑒 in the hypergraph [21]. Another method is the two-section [8] of a hypergraph, which is a graph on the same vertex set 𝑉, with graph edges between two vertices that share an edge in the hypergraph. Most useful for us will be the line graph, defined next. In [8], the line graph is also called the intersection graph or representative graph. Definition 2.1.6 (Line Graph). Let H be a hypergraph with edge set 𝐸. The line graph of H , denoted 𝐿(H ), is a graph built as follows: 1. The vertex set of the line graph is the edge set of the hypergraph, 𝑉𝐿 B 𝐸 2. There is an edge between 𝑒𝑖 and 𝑒 𝑗 in the line graph if 𝑒𝑖 ∩ 𝑒 𝑗 β‰  βˆ… in H . For an example of a line graph, see Figure 2.2. The hypergraph H in the figure has edge set 𝐸 = {𝐴𝐡𝐢, 𝐡𝐢𝐷, 𝐡, 𝐢}, which are the vertices of the line graph 𝐿(𝐻). Notice that there is not a graph edge between 𝐡 and 𝐢 in 𝐿 (H ) because 𝐡 ∩ 𝐢 = βˆ…, but all other pairs of edges in H intersect nontrivially, and that is represented by a graph edge in 𝐿(H ). 7 Figure 2.2 A hypergraph H and its line graph 𝐿 (H ). The next definition is that of a complement hypergraph. Like with graphs, the complement hypergraph consists of all of the edges that were not in the original hypergraph, retaining the same vertex set. Definition 2.1.7 (Complement of a Hypergraph). Let H = {𝑉, 𝐸 } be a hypergraph. The comple- ment of H is all subsets of the vertex set that are not edges in H , and is denoted Comp(H ). Hence, if P (𝑉) denotes the power set of 𝑉, Comp(H ) = P (𝑉) \ 𝐸. This set theoretic standard notion of the complement serves as the building block for several results herein, as well as the inspiration for Definition 2.1.11 in the novel definitions section below. See Figure 2.3 for an example. Another definition brought over from graph theory is the definition of a walk along a hypergraph. Below is the definition of 1-walk along a hypergraph from [21], herein just referred to as a walk. Definition 2.1.8 (Hypergraph Edge Walk). Let H be a hypergraph with edge set 𝐸. A walk is a sequence of edges 𝑒𝑖1 , 𝑒𝑖2 , . . . , 𝑒𝑖 π‘˜ , where 𝑒𝑖 𝑗 ∩ 𝑒𝑖 𝑗+1 β‰  βˆ… and 𝑒𝑖 𝑗 β‰  𝑒𝑖 𝑗+1 . Note that there is not a standard definition of walk in the hypergraph literature. In [8], a walk lists both edges and vertices that are in their intersection, and is called a path. In [21], a path is a specific type of walk. The idea of an 𝑠-walk, as defined in [21], leverages the more general nature of hypergraphs by stipulating that each pair of consecutive edges in the walk must intersect in at least 𝑠 different vertices. There would also be a natural notion of walk where only the vertices are 8 Figure 2.3 A hypergraph H and its complement Comp(H ). listed and adjacent vertices in the walk must share an edge. We will use the given definition of walks to define connected components in hypergraphs. Definition 2.1.9 (Connected Components of a Hypergraph). Let H be a hypergraph with edge set 𝐸. Define an equivalence relation on 𝐸: 𝑒𝑖 ∼ 𝑒 𝑗 if there is a walk from 𝑒𝑖 to 𝑒 𝑗 . The equivalence classes of this relation are the connected components of the hypergraph. If walks were defined here in terms of vertices then the definition above could also be reworked to give connected components in terms of vertices, as done in [8]. 2.1.2 New Definitions and Results Next we will include some novel definitions and some set-theoretic results on the complement and supplement hypergraphs. The first definition is that of a maximum edge hypergraph. This definition was necessitated and motivated by the results of Section 4.2. Definition 2.1.10 (Maximum Edge Hypergraph). Let H = {𝑉, 𝐸 } be a hypergraph. It will be called a maximum edge hypergraph if there is some edge 𝑒 such that 𝑒 = 𝑉. Oftentimes, 𝑒 will be referred to as the maximum edge of H . An important property of maximum edge hypergraphs is that if 𝑒 is the maximum edge, 𝑒𝑖 βŠ‚ 𝑒 βˆ€ 𝑒𝑖 ∈ 𝐸. In words, every other edge of H is a subedge of the maximum edge 𝑒. It will become apparent later (as soon as Section 2.3) that a special subset of the complement hypergraph is particularly important. This subset consists of the edges that are subsets of edges that 9 Figure 2.4 A hypergraph H , its complement Comp(H ), and its supplement Supp(H ). are in the hypergraph, and will be called the supplement hypergraph. (The † is used throughout this thesis to indicate work partially supported by PNNL.) Definition 2.1.11 (Supplement Hypergraph† ). Let H be a hypergraph with edge set 𝐸 and vertex set 𝑉. Consider the set E of all subsets of edges in 𝐸. Define 𝐺 B E \ 𝐸. Here, 𝐺 is the set of all subedges of edges in H that are not themselves edges, i.e. 𝐺 = {𝑒′ βŠ‚ 𝑒 for some 𝑒 ∈ 𝐸 | 𝑒′ β‰  𝑒 for any 𝑒 ∈ 𝐸 }. The hypergraph with edge set 𝐺 is called the supplement hypergraph and denoted Supp(H ). Figure 2.4 gives an example of a hypergraph with both its complement and supplement. Here, the hypergraph H has the vertices {𝐴, 𝐡, 𝐢}, but 𝐴𝐡𝐢 is not an edge, and so 𝐴𝐡𝐢 is an edge in Comp(H ). However, 𝐴𝐡𝐢 is not a subset of any existing edge in H , and is thus not an edge in Supp(H ). The complement Comp(H ) is a maximum edge hypergraph, and the other two hypergraphs are not. Note that the vertex set of Supp(H ) may not be the same as the vertex set of H , as in Figure 2.4. Supp(H ) inherits only the vertices in edges in 𝐺. Since the complement includes all subsets of 𝑉 that are not edges in H , Supp(H ) βŠ‚ Comp(H ). Furthermore, for maximum edge hypergraphs, the supplement and the complement agree, as shown next. Proposition 2.1.1. † Let H be a maximum edge hypergraph. Then Comp(H ) = Supp(H ). 10 Proof. Let 𝑒 be the maximum edge of H , and 𝑉 the vertex set of H . Since H is a maximum edge hypergraph, 𝑒 = {𝑉 }. By definition, Supp(H ) βŠ‚ Comp(H ). Let 𝑓 ∈ Comp(H ). By the definition of complement, 𝑓 is not an edge in H , and 𝑓 βŠ‚ 𝑉. However, 𝑒 = {𝑉 }, so 𝑓 βŠ‚ 𝑒. Therefore, 𝑓 is not an edge in H , but is a subset of an edge in H . Thus, 𝑓 ∈ Supp(H ). So, Comp(H ) βŠ‚ Supp(H ), and by double inclusion, the two are equal, proving the proposition. β–‘ Maximum edge hypergraphs will turn out to be quite important, so we will want ways to generate them even when starting with a hypergraph that is not maximum edge. One such way is to take the complement. The next result says that for H that is not maximum edge, its complement is maximum edge. Lemma 2.1.2. Suppose H is not a maximum edge hypergraph. Then its complement, Comp(H ), is a maximum edge hypergraph. Proof. Since H is not a maximum edge hypergraph, there is no edge containing all of its vertices 𝑉. Therefore, by definition of the complement, 𝑒 = 𝑉 is an edge in the complement hypergraph. Since all other edge in the complement will be subsets of 𝑒 = 𝑉, the complement hypergraph is a maximum edge hypergraph. β–‘ The following corollary combines the previous results with the law of double complements to write any hypergraph that is not maximum edge as a supplement of a maximum edge hypergraph. Hence, every hypergraph is either a maximum edge hypergraph or the supplement of one. Corollary 2.1.3. Suppose H is not a maximum edge hypergraph. Then H is the supplement of its complement, H = Supp(Comp(H )). Proof. This corollary follows from the previous results. Recall the law of double complements H = Comp(Comp(H )). Since Comp(H ) is a maximum edge hypergraph by Lemma 2.1.2, its complement is equal to its supplement by Proposition 2.1.1. Thus we get the following string of equalities that prove the corollary: H = Comp(CompH )) = Supp(Comp(H )). β–‘ 11 The next few definitions of this section are moving towards an alternative to the definition of connected components in hypergraphs (Definition 2.1.9), which are called fence components. Instead of being based off of intersections, fence components will be based off of inclusions of subedges. These will come up often, particularly in Chapter 3. The preliminary definition will be that of a hypergraph fence, which is a specific type of walk (Definition 2.1.8). Definition 2.1.12 (Hypergraph Fence). Let H be a hypergraph. A fence in H is a hypergraph walk 𝑒𝑖1 , 𝑒𝑖2 , . . . , 𝑒𝑖 π‘˜ such that for all 𝑒𝑖 𝑗 either: 1. 𝑒𝑖 𝑗 βˆ’1 βŠ‚ 𝑒𝑖 𝑗 βŠƒ 𝑒𝑖 𝑗+1 , or 2. 𝑒𝑖 𝑗 βˆ’1 βŠƒ 𝑒𝑖 𝑗 βŠ‚ 𝑒𝑖 𝑗+1 . A fence is more restrictive than a walk because for a fence, each consecutive pair of edges needs to have an inclusion relation instead of only a nontrivial intersection. The definition for connected components in Definition 2.1.9 uses the notion of walks to form an equivalence relation and partition the edge set. The next definition does an analogous thing with fences instead of walks. Definition 2.1.13 (Fence Components). Let H be a hypergraph with edge set 𝐸. Define a relation ∼ on 𝐸 with 𝑒𝑖 ∼ 𝑒 𝑗 if there is a fence from 𝑒𝑖 to 𝑒 𝑗 . The equivalence classes of this relation are called the fence components of H , and the number of fence components of a hypergraph will be denoted Ξ“(H ). A good example of the difference between fence components and connected components can be found in Figure 2.1. Both hypergraphs H and H β€² have one connected component, as the two toplexes intersect in both hypergraphs. In H , 𝐴𝐡𝐢 βŠƒ 𝐡 βŠ‚ 𝐡𝐢𝐷 is a fence between 𝐴𝐡𝐢 and 𝐡𝐢𝐷, and 𝐢 βŠ‚ 𝐴𝐡𝐢, so all edges are in the same fence component. In H β€², though, there is no fence between 𝐴𝐡𝐢 and 𝐡𝐢𝐷, since they do not have a mutual subedge. Therefore H β€² has two fence components whilst having one connected component. Inclusion of edges in a hypergraph gives a partial order on H . The below definition comes from [22], where it is called the edge containment partial order. This poset will be used later 12 on, especially in Section 5.2. The name face poset was inspired by the face poset of a simplicial complex from [32]. Definition 2.1.14 (Face Poset of a Hypergraph). Let H be a hypergraph. Define a relation on the edges of H by 𝑒𝑖 < 𝑒 𝑗 if 𝑒𝑖 βŠ‚ 𝑒 𝑗 . This is a partial order, and it forms what is called the face poset of H , 𝐹𝑃(H ). Recalling Definition 2.1.6, the line graph is a graph on the edge set of H that displays information about the intersection of edges. The next definition is another graph called the edge inclusion graph and it is analogous to the line graph, but displays information about the inclusion relations among edges in H . That difference is comparable to the difference between the connected components of a hypergraph and its fence components, as discussed in the previous example. Definition 2.1.15 (Edge Inclusion Graph). Let H be a hypergraph. The edge inclusion graph is a graph 𝐸 𝐼𝐺 (H ) constructed as follows: 1. The vertex set of 𝐸 𝐼𝐺 (H ) is the edge set of the hypergraph, 𝑉𝐸 𝐼𝐺 = {𝑣 𝑒 | 𝑒 ∈ H }. 2. There is an edge in 𝐸 𝐼𝐺 (H ) between 𝑣 𝑒𝑖 and 𝑣 𝑒 𝑗 if 𝑒𝑖 βŠ‚ 𝑒 𝑗 or 𝑒𝑖 βŠƒ 𝑒 𝑗 in H . The final definition on hypergraphs is reserved for a special type of connected component (Definition 2.1.9), called a simplicial component, which will prepare our transition to talking about simplicial complexes. Definition 2.1.16 (Simplicial Components). Let H be a hypergraph. Suppose there is a connected component C βŠ‚ H that is closed under taking subsets, i.e. βˆ€ 𝑒 ∈ C, 𝑒′ βŠ‚ 𝑒 ∈ C =β‡’ 𝑒′ ∈ C. Then C is called a simplicial component. Another way of phrasing the subset closure property is that there is a connected component that contains all possible subedges of its toplexes. A hypergraph for which every component is a simplicial component is a simplicial complex, as we will see in the next section. 13 2.2 Simplicial Complexes and their Homology Like hypergraphs, simplicial complexes are combinatorial objects that generalize graphs. In fact, all graphs are 1-dimensional simplicial complexes. Moreover, simplicial complexes could be considered as a special class of hypergraphs. They are hypergraphs for which every component is a simplicial component (Definition 2.1.16), i.e. a hypergraph for which all possible subedges are present in the hypergraph. They are commonly used in algebraic topology. One nice property that simplicial complexes have that general hypergraphs do not have is a well-defined, standard homology theory. Abstract simplicial complexes were originally defined in [34] in the late 1930s and many of the definitions below appear in some form there. Unless another source is cited, versions of the definitions in this section can be found in [18] and/or [24]. 2.2.1 Simplicial Complexes We will begin with the definition of an abstract simplex (plural - simplices). Informally, an abstract simplex is a set of distinct vertices, just like an edge in a hypergraph. Definition 2.2.1 (Simplex). An abstract simplex 𝜎 is a set of vertices 𝜎 = {𝑣 0 , 𝑣 1 , ..., 𝑣 𝑛 } such that 𝑣 𝑖 β‰  𝑣 𝑗 for any 𝑖 β‰  𝑗, i.e. a set without any repeated elements. The dimension of the simplex 𝜎 is 𝑛, one less than the number of vertices it has. In this thesis we will consider abstract simplices, but simplices have geometric realizations as well. Suppose the 𝑛 + 1 vertices of an 𝑛-simplex 𝜎 lie in R𝑛 such that {𝑣 1 βˆ’ 𝑣 0 , . . . , 𝑣 𝑛 βˆ’ 𝑣 0 } is a linearly independent set. Then the geometric realization of 𝜎 is the convex hull of its vertices in R𝑛 [24]. Henceforth, all simplices will be abstract simplices (the word abstract will be omitted), and figures will show a geometric realization. Simplices are the building blocks for simplicial complexes. An abstract simplicial complex is a set of distinct simplices that is closed under taking subsets of its elements. Simplicial complexes also have geometric realizations, as the union of the geometric realization of their simplices, and similarly, outside of figures, all simplicial complexes will be abstract simplicial complexes. Definition 2.2.2 (Simplicial Complex). A (finite) simplicial complex 𝐾 is a collection of simplices 14 Figure 2.5 Of these two hypergraphs, H and 𝐾, only 𝐾 is a simplicial complex. 𝐾 = {𝜎1 , 𝜎2 , ..., πœŽπ‘š } such that: 1. πœŽπ‘– β‰  𝜎 𝑗 for any 𝑖 β‰  𝑗 and 2. for all πœŽπ‘– ∈ 𝐾, if 𝜏 βŠ‚ πœŽπ‘– , then 𝜏 ∈ 𝐾. The dimension of a simplicial complex is the maximum dimension over all of its simplices. All simplicial complexes considered will be assumed to be finite in both the number of simplices and their dimensions. Hypergraphs were defined after simplicial complexes, historically, and are generalizations of simplicial complexes. Every simplicial complex is a hypergraph, but the converse is not true. The following lemma relates to Definition 2.1.16 of simplicial components in a hypergraph. It says that a hypergraph with all of its possible subedges is a simplicial complex. Lemma 2.2.1 (Hypergraphs that are Simplicial Complexes). Let H be a hypergraph. If for all 𝑒 ∈ H , 𝑒′ βŠ‚ 𝑒 =β‡’ 𝑒′ ∈ H , then H is a simplicial complex. Proof. Since all hypergraphs are assumed to be edge-collapsed (Definition 2.1.2), any hypergraph satisfies the first condition of Definition 2.2.2. The second condition of Definition 2.2.2 is exactly the assumption made in the lemma, proving that a hypergraph with subedge closure is a simplicial complex. β–‘ A first example of viewing a hypergraph as a simplicial complex is in Figure 2.5. The hypergraph H is missing some subedges, like 𝐴𝐢, and so is not a simplicial complex. However, the hypergraph 15 𝐾 is closed under taking subedges, and is thus a simplicial complex. The rightmost image in the figure shows the geometric realization of 𝐾 as a shaded triangle. Both the second hypergraph and the triangle represent the exact same set of sets, 𝐾, which is the minimal simplicial complex containing H . It might be important to consider only a part of a simplicial complex and the first definition about simplicial complexes is that of a special subset of a simplicial complex, called a subcomplex. Definition 2.2.3 (Subcomplex of a Simplicial Complex). A subset of a simplicial complex that is itself a simplicial complex is called a subcomplex. Here is one important type of subcomplex: Definition 2.2.4 (Generated Subcomplex). Given a simplicial complex 𝐾, let 𝑉 β€² βŠ‚ 𝑉 be a subset of the vertex set of 𝐾. Then, the subcomplex generated by 𝑉 β€² is the set of simplices in 𝐾 whose vertices are contained in 𝑉 β€², i.e. 𝐾𝑉 β€² = {𝜎 ∈ 𝐾 | 𝜎 βŠ† 𝑉 β€² }. The next special type of subcomplex is the 𝑛-skeleton associated with a simplicial complex. Definition 2.2.5 (Skeleta of a Simplicial Complex and Underlying Graph). The 𝑛-skeleton of a simplicial complex is the subcomplex consisting of all of the simplices that are at most dimension 𝑛. The 1-skeleton of a simplicial complex is a graph, called the underlying graph in [2]. Many important results in algebraic topology rely on the idea of refining a simplicial complex (see, for example, the Simplicial Approximation Theorem in [24]). One standard way of doing so is called the barycentric subdivision, defined below. As the names restricted and relative barycentric homology suggest, both of the main homology theories developed herein utilize the barycentric subdivision. Definition 2.2.6 (Barycentric Subdvision). Given a simplicial complex 𝐾, its barycentric subdivi- sion 𝑇 is a simplicial complex such that the vertex set of 𝑇 is the set of simplices of 𝐾, i.e. 𝑉𝑇 = {𝑣 πœŽπ‘– | πœŽπ‘– ∈ 𝐾 } 16 Figure 2.6 A simplicial complex 𝐾, its barycentric subdivision 𝑇, and a generated subcomplex. and the simplices of 𝑇 are given by the face relations on 𝐾. That is, 𝑇 B {Ξ© = {𝑣 𝜎1 , . . . , 𝑣 πœŽπ‘š } βŠ‚ 𝐾 | upto reordering of vertices in Ξ©, 𝜎1 βŠ‚ 𝜎2 βŠ‚ . . . βŠ‚ πœŽπ‘š ∈ 𝐾 }. Figure 2.6 gives an example of both a barycentric subdivision and a generated subcomplex (Definition 2.2.4). It starts with the simplicial complex 𝐾, given by the triangle 𝐴𝐡𝐢 and all of its subsets, 𝐾 = {𝐴𝐡𝐢, 𝐴𝐡, 𝐴𝐢, 𝐡𝐢, 𝐴, 𝐡, 𝐢}. Each of these becomes a vertex in 𝑇, the barycentric subdivision. Notice, for example, that there is an edge between the vertices 𝐴 and 𝐴𝐡 in 𝑇. This is because in 𝐾, 𝐴 βŠ‚ 𝐴𝐡. Similarly, there is a triangle on the vertices 𝐢, 𝐴𝐢, 𝐴𝐡𝐢 in 𝑇 because in 𝐾, 𝐢 βŠ‚ 𝐴𝐢 βŠ‚ 𝐴𝐡𝐢. The rightmost picture highlights the subcomplex in 𝑇 generated by the vertices {𝐴, 𝐡, 𝐴𝐢, 𝐡𝐢}, which includes all simplices in 𝑇 only consisting of those vertices. Recall that in graph theory, clique is the term for a complete subgraph. If a set of π‘š vertices of a graph is a clique, then all smaller subsets of those same vertices will also be a clique. Thus, it might be advantageous to turn the cliques of a graph into simplices of a simplicial complex. This construction is called a clique complex. Definition 2.2.7 (Clique Complex). Let 𝐺 be a graph. Cliques in 𝐺 are complete subgraphs, i.e. sets of vertices in which every two vertices are joined by an edge. Form a simplicial complex 𝑋 (𝐺) by letting every clique in 𝐺 be a simplex in 𝑋 (𝐺). Then 𝑋 (𝐺) is called the clique complex of 𝐺. If 𝐾 is a simplicial complex, it is called a clique complex (or flag complex) if it is the clique complex of its 1-skeleton. 17 The last sentence of that definition is equivalent to the condition that every set of vertices that are pairwise connected by 1-simplices are mutually contained in a single simplex [2]. In hypergraphs, this condition is called conformality [2, 8]. As an example, the barycentric subdivision is always a clique complex. This is because, for a set of simplices in a simplicial complex, if they are pairwise related to each other, then there is a total order on that set. This can be seen in Figure 2.6. The vertices {𝐢, 𝐴𝐢, 𝐴𝐡𝐢} in 𝑇 are each pairwise connected by an edge since 𝐢 βŠ‚ 𝐴𝐢, 𝐢 βŠ‚ 𝐴𝐡𝐢, and 𝐴𝐢 βŠ‚ 𝐴𝐡𝐢 in 𝐾. These can be rearranged into a single chain, 𝐢 βŠ‚ 𝐴𝐢 βŠ‚ 𝐴𝐡𝐢 in 𝐾, and so the corresponding triangle in 𝑇 is shaded. Recall the face poset 𝐹𝑃 from Definition 2.1.14. Since simplicial complexes are hypergraphs, it also makes sense to use this definition for the face poset of a simplicial complex. There is also a natural way to generate a simplicial complex given a poset. This is called the order complex [32]. It uses chains of relations in the poset as simplices for the simplicial complex. Definition 2.2.8 (Order Complex). Let (𝑃, <) be a poset. The order complex of 𝑃, denoted Ξ”(𝑃), is the simplicial complex whose vertices are the elements of 𝑃, and whose simplices are chains of the relation on 𝑃. In other words, {𝑣 0 , 𝑣 1 , . . . , 𝑣 π‘˜ } is a simplex in Ξ”(𝑃) exactly when 𝑣 0 < 𝑣 1 < . . . < 𝑣 π‘˜ is a linearly ordered set in 𝑃. One result that uses the order complex is that the order complex of the face poset of a simplicial complex is the same as the barycentric subdivision of that simplicial complex [32]. This gives an alternative definition of the barycentric subdivision. Proposition 2.2.2 (Alternative Definition of Barycentric Subdivision). Let 𝐾 be a simplicial com- plex, and let 𝐹𝑃(𝐾) be its face poset. The order complex Ξ”(𝐹𝑃(𝐾)) is the same simplicial complex as the barycentric subdivision, i.e. Ξ”(𝐹𝑃(𝐾)) = 𝑇𝐾 . Proof. By Definition 2.2.6 of the barycentric subdivision, the vertex set of 𝑇𝐾 is 𝑉𝑇𝐾 = {𝑣 𝜎 | 𝜎 ∈ 𝐾 } 18 and the simplices in 𝑇𝐾 are given by chains of face relations in 𝐾, Ξ© = {𝑣 𝜎1 , 𝑣 𝜎2 . . . , 𝑣 πœŽπ‘š } ∈ 𝑇𝐾 if and only if, for some reordering of the πœŽπ‘– , 𝜎1 βŠ‚ 𝜎2 βŠ‚ . . . βŠ‚ πœŽπ‘š ∈ 𝐾. The elements of the face poset of 𝐾 are the simplices in 𝐾, with πœŽπ‘– < 𝜎 𝑗 in 𝐹𝑃(𝐾) if and only if πœŽπ‘– βŠ‚ 𝜎 𝑗 in 𝐾. The order complex Ξ”(𝐹𝑃(𝐾)) has as vertices the elements of 𝐹𝑃(𝐾), which are the simplices in 𝐾. Therefore, Ξ”(𝐹𝑃(𝐾)) and 𝑇𝐾 have the same vertices. The simplices in Ξ”(𝐹𝑃(𝐾)) are given by chains of relations in 𝐹𝑃(𝐾). Since in 𝐹𝑃(𝐾), 𝜎1 < 𝜎2 < . . . < πœŽπ‘š if and only if 𝜎1 βŠ‚ 𝜎2 βŠ‚ . . . βŠ‚ πœŽπ‘š ∈ 𝐾, the simplices of Ξ”(𝐹𝑃(𝐾)) are the same as the simplices of 𝑇𝐾 , and thus they are the same simplicial complex. β–‘ The last definitions on simplicial complexes before we get into their homology are that of the star and link. The star and link are important for many results on simplicial complexes that are of a topological nature, as they essentially analogize the concepts of an open neighborhood and its boundary to the combinatorial objects of simplicial complexes. Definition 2.2.9 (Stars and Links of Simplices). Let 𝐾 be a simplicial complex, and 𝜎 ∈ 𝐾 be a simplex. The (open) star of 𝜎, denoted St(𝜎), is defined as the set of simplices having 𝜎 as a face: St(𝜎) = {𝜏 ∈ 𝐾 | 𝜎 βŠ† 𝜏}. Let 𝐿 = {𝜎1 , 𝜎2 , . . . , πœŽπ‘› } be a subset of simplices in 𝐾, not necessarily a subcomplex. The star of 𝐿 is the union of the stars of its simplices: Γ˜π‘› St(𝐿) = St(πœŽπ‘˜ ). π‘˜=1 19 The closed star of 𝐿, St(𝐿), is the smallest subcomplex of 𝐾 containing St(𝐿). The link of 𝐿, Lk(𝐿), is the set of simplices in the closed star that are not in the star. This is the boundary of the star, given by Lk(𝐿) = St(𝐿) \ St(𝐿). 2.2.2 Simplicial Homology Next we will move into defining the homology of simplicial complexes. Earlier, we mentioned that the presence of a standard homology theory was a feature that set simplicial complexes apart from hypergraphs. Recall that the difference between general hypergraphs and simplicial complexes is that simplicial complexes contain all of their subsets. This property makes a critical difference when it comes to defining homology. In short, simplices have natural boundaries while general hypergraph edges do not. Consider a 2-simplex with three vertices; its geometric realization is a triangle. Assuming it is in a simplicial complex, the three sides of the triangle (one dimensional simplices) are also guaranteed to be geometric realizations of simplices, and they make up the boundary of the simplex. On the other hand, in a general hypergraph, there might be an edge with three vertices, but not all (or possibly even none) of the two vertex subsets of that edge might be edges themselves. This property plays an important role in the boundary map, a requirement for homology. In particular we will define a group for each dimension of simplices, and then the boundary map descends in dimension by one, as in the triangle to edges example above. This sequence of groups and maps forms the underlying structure required for a homology theory. Let 𝐾 be a simplicial complex. Define the 𝑛th chain group of 𝐾 as the group of finite formal sums of 𝑛-dimensional simplices: nβˆ‘οΈ o 𝐢𝑛 (𝐾) B π‘Žπ‘– πœŽπ‘– | πœŽπ‘– is an 𝑛-dimensional simplex ∈ 𝐾 . The π‘Žπ‘– are coefficients from a specified group; in this thesis the coefficient group is always assumed Z to be 2Z . Henceforth, when there is no ambiguity the 𝐾 will be dropped, and the chain groups will 20 be denoted by 𝐢𝑛 . There is a map πœ•π‘› : 𝐢𝑛 β†’ πΆπ‘›βˆ’1 called the boundary map defined as follows. If 𝜎 = {𝑣 0 , ..., 𝑣 𝑛 } is an 𝑛-simplex in 𝐾, then 𝑝 βˆ‘οΈ πœ•π‘ (𝜎) B (βˆ’1) 𝑖 [𝑣 0 , 𝑣 1 , Β· Β· Β· , 𝑣ˆ𝑖 , Β· Β· Β· , 𝑣 𝑛 ] 𝑖=0 Z where the hat indicates removal of that vertex. The (βˆ’1) 𝑖 is not necessary when working with 2Z coefficients, but is included in the general definition of the boundary map for any coefficient group. The map πœ•π‘› is then extended linearly to the chains of 𝐢𝑛 . Importantly, πœ•π‘›βˆ’1 β—¦ πœ•π‘› = 0. So there is a sequence of groups and maps: πœ• πœ• πœ• πœ• ... 𝐢𝑛 πΆπ‘›βˆ’1 Β·Β·Β· 𝐢0 0. A sequence of groups and maps of this form where πœ• 2 = 0 is called a chain complex. If πΎπ‘’π‘Ÿ (πœ•π‘› )  πΌπ‘š(πœ•π‘›+1 ), then the chain complex is said to be exact at 𝑛, and if the sequence is exact at every step, it is called an exact sequence. While 𝐢𝑛 is not necessarily exact at 𝑛, we can measure its failure to be exact using homology. Definition 2.2.10 (Simplicial Homology). Given a simplicial complex 𝐾, form the chain complex 𝐢 (𝐾) of its chain groups and boundary maps as above. Then, the 𝑛th homology group of 𝐾, 𝐻𝑛 (𝐾), is defined as πΎπ‘’π‘Ÿ (πœ•π‘› ) 𝐻𝑛 (𝐾) B . πΌπ‘š(πœ•π‘›+1 ) The rank of this group is called the 𝑛-th Betti number of 𝐾, denoted 𝛽𝑛 (𝐾). Viewing a single vertex 𝑣 as a 0-dimensional simplicial complex, we can compute that 𝛽0 (𝑣) = 1, while all other Betti numbers are 0. In some sense, homology generalizes the concept of finding, counting, and listing cycles in a graph. Since every graph is a 1-dimensional simplicial complex, it makes sense to talk about the simplicial homoloy of a graph. Let 𝐺 be a graph. Then, it turns out that 𝛽0 (𝐺) is equal to the number of connected components of the graph, and 𝛽1 (𝐺) is equal to the number of linearly independent cycles in the graph. 21 In higher dimensional simplicial complexes, however, some of those graph cycles might be filled in with two dimensional simplices. Perhaps there is even a two dimensional analogue of a cycle, this could look like an enclosed void in the geometric realization. Such a void would show up as a class in 𝐻2 (𝐾), the second dimensional homology group. This generalizes up to the dimension of the simplicial complex, above which the homology groups are guaranteed to be zero, since there are no simplices in those dimensions. Instead of 𝛽0 = 1 for a single point, it would perhaps be more intuitive for a point to have no homology whatsoever. This is the case in the theory of reduced homology (see, e.g. [18]), which we will define next. Reduced homology is occasionally used when a result relies on it, for example in the proof of Theorem 4.2.9. This could occur when it will be convenient to say that, for a vertex 𝑣, 𝛽𝑖 (𝑣) = 0 for all 𝑖. Definition 2.2.11 (Reduced Homology). Given a simplicial complex 𝐾 with chain groups 𝐢𝑛 , the Z reduced chain complex is the usual chain complex with 2Z augmented after 𝐢0 , i.e. πœ•π‘›+1 πœ•π‘› πœ•π‘›βˆ’1 πœ•1 πœ– Z ... 𝐢𝑛 πΆπ‘›βˆ’1 Β·Β·Β· 𝐢0 2Z 0 where πœ– maps a 0-chain to the sum of its coefficients. Then, the reduced homology of 𝐾 is the homology of the reduced chain complex, denoted 𝐻 e(𝐾), with reduced Betti numbers 𝛽(𝐾). e The main property we need from reduced homology is that 𝛽e0 (𝐾) = 𝛽0 (𝐾) βˆ’ 1, and for 𝑖 β‰  0, 𝐻e𝑖 (𝐾)  𝐻𝑖 (𝐾). Reduced homology in dimension zero does not represent the number of connected components. It instead represents gaps between connected components; 𝛽e0 (𝐾) is the number of 1-dimensional simplices that would need to be added to 𝐾 to have a conneced simplicial complex. Another useful property of simplicial complexes is that the barycentric subdivision operator preserves homology, creating a refinement of a simplicial complex with the same topological properties, as shown in [18, 24]. 22 Lemma 2.2.3 (Homology of Barycentric Subdivision). Let 𝐾 be a simplicial complex, with 𝑇 its barycentric subdivision. Then, 𝐻𝑛 (𝑇)  𝐻𝑛 (𝐾) for all 𝑛. Simplicial complexes that have the same topological properties as a point play an important role, and are given the name contractible. Definition 2.2.12 (Contractible Simplicial Complex). A simplicial complex 𝐾 is said to be con- tractible if it is homotopy equivalent to a single point. We will not define homotopy equivalence here (see [18], but this definition implies (among other things) that for reduced homology, 𝐻 e𝑛 (𝐾) = 0 for all 𝑛. For the regular simplicial homology of a contractible simplicial complex, ο£±  Z when 𝑛 = 0   ο£² 2Z  𝐻𝑛 (𝐾) =   0  else. ο£³ In this thesis, the simplicity of the homology groups of a contractible simplicial complex will be often used to ease calculation of homology groups of more complicated complexes. The last homological definition we will require is the relative homology of a pair 𝑆 βŠ† 𝐾, where 𝐾 is a simplicial complex, and 𝑆 is a subcomplex. Geometrically, this gives the homology of a simplicial complex, after collapsing the subcomplex 𝑆 to a point. Unfortunately, the quotient space 𝐾/𝑆 is not generally a simplicial complex, so it does not make sense to talk about the simplicial homology of 𝐾/𝑆. Let 𝐢 (𝐾) and 𝐢 (𝑆) be the chain groups of 𝐾 and 𝑆, as defined above for the definition of simplicial homology. Then 𝐢𝑛 (𝑆) βŠ‚ 𝐢𝑛 (𝐾), and in particular, 𝐢𝑛 (𝐾)/𝐢𝑛 (𝑆) is a well defined quotient group in all dimensions. This sequence of groups, with the inherited boundary maps, still forms a chain complex [18]. This chain complex is denoted 𝐢 (𝐾, 𝑆) and is called the relative chain complex. Since it is a chain complex, the homology can be computed, and that is the definition of relative homology. 23 Definition 2.2.13 (Relative Homology). Let 𝐾 be a simplicial complex, with 𝑆 a subcomplex. Then, the homology of 𝐾 relative to 𝑆, denoted 𝐻 (𝐾, 𝑆), is defined as the homology of the chain complex 𝐢 (𝐾, 𝑆) defined above. Relative homology can be difficult to calculate. Some of the results in the next section will give additional ways to calculate it. 2.2.3 Simplicial Homology Theorems There are some important theorems of simplicial homology that we will analogize to hyper- graphs in this thesis. The first of these is the Mayer-Vietoris Theorem, which relates the homology of a space to the homology of two of its subsets that cover it, as well as their intersection. This theorem can be found in [18, 24]. Theorem 2.2.4 (Mayer-Vietoris Theorem). Let 𝐾 be a simplicial complex, and 𝐿 1 , 𝐿 2 be subcom- plexes such that 𝐿 1 βˆͺ 𝐿 2 = 𝐾. Then the sequence of homology groups . . . β†’ 𝐻𝑛 (𝐿 1 ∩ 𝐿 2 ) β†’ 𝐻𝑛 (𝐿 1 ) βŠ• 𝐻𝑛 (𝐿 2 ) β†’ 𝐻𝑛 (𝐾) β†’ π»π‘›βˆ’1 (𝐿 1 ∩ 𝐿 2 ) β†’ . . . where the first two maps are induced by inclusions, and the third map is derived through techniques of homological algebra, is exact. This long exact sequence is often called the Mayer-Vietoris sequence. It is commonly used in algebraic topology to calculate the homology of complicated spaces when the homology of a cover of them is known. It can be used with regular homology or reduced homology. A first application of the Mayer-Vietoris sequence is to find the homology of the spheres, 𝑆 𝑛 , via induction, assuming that the homology of 𝑆 1 has been computed as the base case. Recall that ο£±  Z 𝑖 = 0, 1   ο£² 2Z  𝐻𝑖 (𝑆 1 ) =   0  else ο£³ Z For the inductive step, assume that 𝐻𝑖 (𝑆𝑖 ) = 2Z and consider 𝑆𝑖+1 . Note that 𝑆𝑖+1 can be split into slightly overlapping northern and southern hemisphere, which are both 𝑖 + 1 dimensional disks, 24 𝐷 𝑖+1 , so 𝑆𝑖+1 = 𝐷 𝑖+1 βˆͺ 𝐷 𝑖+1 . Each disk is homologically trivial, and they intersect in an equator of the sphere, 𝐷 𝑖+1 ∩ 𝐷 𝑖+1 = 𝑆𝑖 . Each of these pieces can now be plugged into the Mayer Vietoris sequence, giving . . . β†’ 𝐻𝑖+1 (𝑆𝑖 ) β†’ 𝐻𝑖+1 (𝐷 𝑖+1 )βŠ•π»π‘–+1 (𝐷 𝑖+1 ) β†’ 𝐻𝑖+1 (𝑆𝑖+1 ) β†’ 𝐻𝑖 (𝑆𝑖 ) β†’ 𝐻𝑖 (𝐷 𝑖+1 )βŠ•π»π‘– (𝐷 𝑖+1 ) β†’ . . . Since disks are homologically trivial, it follows from the exactness of the sequence that 𝐻𝑖+1 (𝑆𝑖+1 ) β†’ 𝐻𝑖 (𝑆𝑖 ) is an isomorphism, and thus, Z 𝐻𝑖+1 (𝑆𝑖+1 )  . 2Z The rest of the Mayer-Vietoris sequence yields the expected result, and can be applied in the same way. We will discuss another application of the Mayer-Vietoris sequence in Theorem 6.2.1. However, there is also a version of the Mayer-Vietoris sequence that uses relative homology, and that is the version we will be analogizing to hypergraphs in Theorem 4.1.1. Theorem 2.2.5 (Relative Mayer-Vietoris Theorem). Let 𝐾 be a simplicial complex with subcom- plexes 𝐿 1 , 𝐿 2 , 𝑆 βŠ‚ 𝐾 such that 𝐿 1 βˆͺ 𝐿 2 = 𝐾. Further assume we have subcomplexes 𝑅1 βŠ‚ 𝐿 1 ∩ 𝑆, and 𝑅2 βŠ‚ 𝐿 2 ∩ 𝑆 such that 𝑅1 βˆͺ 𝑅2 = 𝑆. Then the sequence . . . β†’ 𝐻𝑛 (𝐿 1 ∩𝐿 2 , 𝑅1 βˆ©π‘…2 ) β†’ 𝐻𝑛 (𝐿 1 , 𝑅1 )βŠ•π»π‘› (𝐿 2 , 𝑅2 ) β†’ 𝐻𝑛 (𝐾, 𝑆) β†’ π»π‘›βˆ’1 (𝐿 1 ∩𝐿 2 , 𝑅1 βˆ©π‘…2 ) β†’ . . . is exact. Next up is the main result of relative homology. This is another long exact sequence, one that relates the relative homology 𝐻 (𝐾, 𝑆) to 𝐻 (𝐾) and 𝐻 (𝑆). This sequence will play a major role in Chapters 4 and 5. 25 Theorem 2.2.6 (Long Exact Sequence of a Pair). Given a simplicial complex 𝐾 and a subcomplex 𝑆, the following is a long exact sequence of homology groups: . . . β†’ 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝐾) β†’ 𝐻𝑛 (𝐾, 𝑆) β†’ π»π‘›βˆ’1 (𝑆) β†’ π»π‘›βˆ’1 (𝐾) β†’ . . . The exactness of this sequence implies that in order to compute the homology 𝐻 (𝐾, 𝑆), we only need 𝐻 (𝐾), 𝐻 (𝑆), and knowledge of the linear maps between them. Computationally, leveraging this sequence will be vital as an alternative to taking the relative homology directly, since 𝐾/𝑆 is in general not a simplicial complex. The final result of this section is a way to remove simplices from simplicial complexes without changing their homology, called a collapse. This will be analogized to hypergraphs in Theorem 3.2.6 and also used in Proposition 4.3.10. Theorem 2.2.7 (Simplicial Collapse). Assume 𝜎 < 𝜏 are simplices in a simplicial complex 𝐾 such that: 1. 𝜏 is a maximal face of 𝐾, and 2. 𝜏 is the only maximal coface of 𝜎. Then, if 𝐾 := 𝐾 \ {πœ” | 𝜎 ≀ πœ” ≀ 𝜏}, 𝐾 ∼ 𝐾 are homotopy equivalent. Simplicial complexes that collapse to a single vertex are called collapsible. Collapsible simpli- cial complexes are always contractible, but the converse is not true. 2.3 Hypergraph Homology Theories We are now ready to merge the topics of the prior two sections - hypergraphs, simplicial complexes, and simplicial homology. Hypergraphs are more general than simplicial complexes. The lack of the subset closure requirement means that more data can be modeled and that some data can be modeled more accurately with hypergraphs than simplicial complexes or graphs [1, 3, 4, 6, 16, 17, 19, 21, 20, 22, 28, 31]. 26 Figure 2.7 Comparing a hypergraph and simplicial model of a biological system. Here is an example from biology [23]. Researchers found a species of panic grass that was surviving in hostile conditions that it would not typically have been able to survive. Originally, they located a fungus on the plant that was in a symbiotic relationship with the plant. After more research, though, they also found a virus that was on the fungus that was a part of this symbiosis. Researchers isolated and removed the virus, and both the fungus and the plant died. Researchers isolated and removed the fungus, and both the virus and the plant died. Researchers killed the plant, and both the fungus and virus died. No pair of them could survive without the third, in what appears to be a three-way symbiotic relationship. This is much easier to represent with a hypergraph than a graph or simplicial complex. If attempting to represent this with a graph, all three (the virus, fungus, and plant) would need to be connected somehow, but each edge in the graph can only connect two of them, which might mislead the reader into thinking that two of them connected by an edge could survive. As a simplicial complex, there would be a 2-dimensional simplex that represents the three way relationship, but this simplex would also necessarily contain all of its subsets, including all of the two-way edges. As a hypergraph, there only needs to be a three vertex edge and no possibly misleading subedges. This can be seen in Figure 2.7. Homology has a history of being a useful tool for mathematicians. In topology, it is an important invariant for classifying spaces. In topological data analysis, researchers use persistent homology to measure how their data is changing over a parameter. This is done by taking the homology of simplicial complexes built at critical points in the parameter’s range. Being able to define a 27 homology theory for hypergraphs will allow researchers to use these results to classify and study hypergraphs, and analyze data that is better modeled using a hypergraph. It is when we reach the point of defining a homology theory on hypergraphs that their generality becomes a double-edged sword. Because of the lack of the downward closure property that simpli- cial complexes have, hypergraphs can be used to model data in ways that sometimes better reflects its internal structure. However, the lack of that property also means there is not a natural boundary map on hypergraph edges that immediately analogizes the definition of simplicial homology. From the example in Figure 2.7, in order to more accurately represent the data the hypergraph does not contain the pairwise edges between the vertices. The lack of those edges means that there is not a natural boundary map for the edge that is present, and so it does not fit into our understood framework for a homology theory. The main complication, therefore, in defining a hypergraph homology theory is finding a chain complex and boundary map that adequately and accurately represent the hypergraph. The bulk of my thesis consists of development of the theory for two related definitions of hypergraph homology, as originally defined by Emilie Purvine and collaborators [28]. These are the restricted barycentric homology and the relative barycentric homology. There also exist other homology and cohomology theories for hypergraphs, like the embedded homology [7, 29, 30, 33], and others [9, 12, 14, 25, 26]. Since we want to use simplicial homology, we will first start by taking a hypergraph, and mapping it into a simplicial complex. One natural way of turning a hypergraph into a simplicial complex is called the associated simplicial complex of the hypergraph [21, 25]. Definition 2.3.1 (Associated Simplicial Complex). Let H be a hypergraph. The associated sim- plicial complex of H , denoted 𝐾, is the simplicial complex constructed as follows: 𝐾 = {𝜎 βŠ‚ 𝑉 | 𝜎 βŠ‚ 𝑒 for some 𝑒 ∈ 𝐸 }. The associated simplicial complex is the smallest simplicial complex that contains the hyper- graph H . The toplexes (Definition 2.1.4) of H are the maximal faces of 𝐾. An initial approach 28 to hypergraph homology, then, may be to define the homology of a hypergraph as the homology of its associated simplicial complex, as done in [26, 25]. However, many distinct hypergraphs can have the same associated simplicial complex, as we will explain. Because of the downward closure property, a simplicial complex is completely characterized by its maximal faces. Thus, the toplexes of a hypergraph determine its associated simplicial complex. Take, for example, a hypergraph whose only toplex is the edge 𝐴𝐡𝐢. There are six possible subedges: 𝐴, 𝐡, 𝐢, 𝐴𝐡, 𝐴𝐢, 𝐡𝐢. This means that there are 26 = 64 different hypergraphs that have that identical associated simplicial complex, even with such a small example. The set of hypergraphs with the same toplexes, and hence, associated simplicial complex, is called a hyperblock [21]. In order to distinguish between different hypergraphs with the same associated simplicial complex, a more nuanced homology definition is needed. The associated simplicial complex is the simplicial complex attained by forcing the hypergraph to be closed under taking subedges. Essentially, we are adding all of the missing subedges to the hypergraph to get the associated simplicial complex. Each edge 𝑒 ∈ H has a corresponding simplex πœŽπ‘’ ∈ 𝐾. Typically, 𝑒 ∈ 𝐾 will be used to indicate a simplex in 𝐾 that represents an edge 𝑒 in the hypergraph. However, if that 𝑒 was also used in close proximity to talk about the hypergraph edge, we will use πœŽπ‘’ ∈ 𝐾 when talking about the simplex in 𝐾. Another notation will come up when talking about the barycentric subdivision 𝑇 of 𝐾. Edges in the hypergraph are simplices in the associated simplicial complex, and hence, vertices in its barycentric subdivision. When there is no risk of confusion, 𝑒 ∈ 𝑇 will be used to denote a vertex in the barycentric subdivision that represents an edge in the hypergraph. In a situation where that might seem ambiguous, 𝑣 𝑒 or 𝑣 πœŽπ‘’ ∈ 𝑇 will denote that a vertex in the barycentric subdivision represents an edge in the hypergraph. Similarly, 𝑣 𝜎 ∈ 𝑇 will be used when a vertex in the barycentric subdivision represents the simplex 𝜎 in 𝐾. Both homology theories we will develop herein utilize the associated simplicial complex of the hypergraph and its barycentric subdivision. We will start by defining the restricted barycentric homology. These homology theories were originally defined by Emilie Purvine and collaborators [28]. The notation and formal statements of the definitions are original to this thesis. 29 2.3.1 Restricted Barycentric Homology The idea behind the restricted barycentric homology is that we should restrict our study to only the simplices that represent edges in the hypergraph. If one were to attempt to restrict the associated simplicial complex 𝐾 to the simplices 𝑒 representing edges in H , the resulting set is not necessarily a simplicial complex, as it is the hypergraph H exactly. Thus it is ill-defined to discuss its simplicial homology. The definition of restricted barycentric homology works around this pitfall by first passing to the barycentric subdivision 𝑇. Each edge 𝑒 ∈ H is represented by a vertex 𝑣 𝑒 ∈ 𝑇. Build the subcomplex generated by those vertices as in Definition 2.2.4. This subcomplex contains only simplices whose vertices all represent edges in the hypergraph and so, better reflects the structure of the hypergraph. During the results section in Chapter 3, it will become apparent that the restricted barycentric homology does well quantifying information about inclusion relations among edges that are present in the hypergraph. Definition 2.3.2 (Restricted Barycentric Subdivision). Let H be a hypergraph. Let 𝐾 be its associated simplicial complex, and let 𝑇 be the barycentric subdivision of 𝐾. The restricted barycentric subdivision 𝑅 of H is a subcomplex 𝑅 βŠ‚ 𝑇 constructed as follows: 𝑅 = {Ξ© ∈ 𝑇 | βˆ€ 𝑣 ∈ Ξ©, 𝑣 = 𝑣 𝑒 for some 𝑒 ∈ H }. Each simplex in 𝑅 consists of vertices that represent edges in H . The next result says that if a set of vertices 𝑣 𝑒𝑖 ∈ 𝑅 forms a simplex in 𝑅, those edges 𝑒𝑖 ∈ H are totally ordered by inclusion in the hypergraph. This is useful to help get some intuition about what the restricted barycentric subdivision can tell us about the hypergraph. It will also be utilized later when discussing alternate ways of constructing 𝑅, for example in 3.1.1. Proposition 2.3.1. Let H be a hypergraph, and let Ξ© = {𝑣 𝑒1 , 𝑣 𝑒2 , . . . , 𝑣 𝑒 π‘˜ } be a simplex in 𝑅, its restricted barycentric subdivision. Then for some ordering of the 𝑒𝑖 , 𝑒 1 βŠ‚ 𝑒 2 βŠ‚ . . . βŠ‚ 𝑒 π‘˜ as edges in H . Proof. By Definition 2.3.2 of the restricted barycentric subdivision, each vertex 𝑣 𝑒𝑖 in Ξ© is an edge 𝑒𝑖 in H , and a simplex πœŽπ‘’π‘– ∈ 𝐾. By Definition 2.2.6, simplices in the barycentric subdivision are 30 Figure 2.8 A hypergraph H and its barycentric subdivision 𝑇 with the restricted barycentric subdivision highlighted. given by chains of face relations in 𝐾. Thus for some ordering, πœŽπ‘’1 βŠ‚ πœŽπ‘’2 βŠ‚ . . . βŠ‚ πœŽπ‘’ π‘˜ as simplices in 𝐾. However, the simplices πœŽπ‘’π‘– are set theoretically the same in 𝐾 and as edges 𝑒𝑖 in H , so 𝑒 1 βŠ‚ 𝑒 2 βŠ‚ . . . βŠ‚ 𝑒 π‘˜ as edges in H as well, proving the proposition. β–‘ We will now define the restricted barycentric homology for hypergraphs. By first defining the restricted barycentric subdivision 𝑅, we have done most of the leg work. The restricted barycentric homology is defined as the simplicial homology of 𝑅. Definition 2.3.3 (Restricted Barycentric Homology). Let H be a hypergraph, and 𝑅 its restricted barycentric subdivision as constructed above. The restricted barycentric homology of H , denoted 𝐻 π‘Ÿπ‘’π‘  (H ) is defined to be the simplicial homology of 𝑅, i.e. π»π‘›π‘Ÿπ‘’π‘  (H ) B 𝐻𝑛 (𝑅). The rank of π»π‘›π‘Ÿπ‘’π‘  (H ) will be denoted π›½π‘Ÿπ‘’π‘  𝑛 (H ) and called the 𝑛th restricted Betti number of the hypergraph. We will go through an example of the restricted barycentric homology with the hypergraph in Figure 2.8. This hypergraph has two toplexes, 𝐴𝐡𝐢 and 𝐡𝐢𝐷, so its associated simplicial complex (not shown) is the triangles 𝐴𝐡𝐢 and 𝐡𝐢𝐷, glued along their shared edge 𝐡𝐢. Shown in the picture is the barycentric subdivision 𝑇 of that associated simplicial complex. The restricted barycentric subdivision 𝑅 is highlighted. Here, 𝑅 is generated by the four vertices in 𝑇 that represent the 31 four edges in H : 𝐴𝐡𝐢, 𝐡𝐢𝐷, 𝐡, 𝐢. Since 𝐡 βŠ‚ 𝐴𝐡𝐢, there is an edge in 𝑅 between 𝐡 and 𝐴𝐡𝐢, and similarly for the other highlighted edges. This creates a hollow diamond shape, which has simplicial homology ο£±  Z when𝑛 = 0, 1   ο£² 2Z  𝐻𝑛 (𝑅) =   0  else. ο£³ Therefore, the restricted barycentric homology of H is ο£±  Z when 𝑛 = 0, 1   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘  (H ) =   0  else. ο£³ 2.3.2 Relative Barycentric Homology Whereas the restricted barycentric homology theory accounted for the subedges that were missing in the hypergraph by simply omitting them, the relative barycentric homology takes a different approach. The process begins the same way, by taking the associated simplicial complex 𝐾 of a hypergraph H , and then moving to the barycentric subdivision 𝑇. Once again, we take a particular subcomplex of 𝑇, which we call the missing subcomplex, defined below. The missing subcomplex is defined in almost the same way as the restricted barycentric subdivision, as a generated subcomplex on a vertex set. The difference is that the vertex set of the missing subcomplex consists of the vertices 𝑣 ∈ 𝑇 that do not represent edges in H . It is the subcomplex in 𝑇 built by vertices representing all of the missing subedges of edges in H . Definition 2.3.4 (Missing Subcomplex). Let H be a hypergraph. Let 𝐾 be its associated simplicial complex, and let 𝑇 be the barycentric subdivision of 𝐾. The missing subcomplex 𝑆 of H is a subcomplex 𝑆 βŠ‚ 𝑇 constructed as follows: 𝑆 = {Ξ© ∈ 𝑇 | βˆ€π‘£ ∈ Ξ©, 𝑣 β‰  𝑣 𝑒 for any 𝑒 ∈ H }. Similarly to the restricted case, defining the missing subcomplex was most of the work towards defining the relative barycentric simplicial homology. The next definition is purely for notational convenience while discussing examples. 32 Definition 2.3.5. Let H be a hypergraph, with 𝑇 the barycentric subdivision of its associated simplicial complex 𝐾. Let 𝑆 be the missing subcomplex as defined above. Then the relative barycentric subdivision (𝑇, 𝑆) of H will be defined as the geometric realization of the barycentric subdivision 𝑇 with the missing subcomplex 𝑆 labeled. Now we are ready to define the relative barycentric homology of a hypergraph H . It is defined as the homology of the barycentric subdivision 𝑇 relative to the missing subcomplex 𝑆, using relative homology from Definition 2.2.13. In Chapter 4, it will become apparent that one of the strengths of the relative barycentric homology is to quantify information about the subedges of H , and in particular the relationship between the subedges that are present and the possible subedges that are missing from H . Definition 2.3.6 (Relative Barycentric Homology). Let H be a hypergraph with barycentric sub- division 𝑇, and missing subcomplex 𝑆 as above. Then the relative barycentric homology of H , denoted 𝐻 π‘Ÿπ‘’π‘™ (H ), is defined as the homology of 𝑇 relative to 𝑆: π»π‘›π‘Ÿπ‘’π‘™ (H ) B 𝐻𝑛 (𝑇, 𝑆) The rank of π»π‘›π‘Ÿπ‘’π‘™ (H ) will be denoted π›½π‘Ÿπ‘’π‘™π‘› (H ) and called the 𝑛-th relative Betti number of the hypergraph. For a first example of the relative barycentric homology, see Figure 2.9. The hypergraph H has a single edge 𝐴𝐡𝐢. Its associated simplicial complex is the two-simplex 𝐴𝐡𝐢 and its subsets. Notice that this is, topologically, a 2-dimensional disk. The barycentric subdivision 𝑇 is shown. The missing subcomplex is generated by all of the missing subsets of 𝐴𝐡𝐢 in H , which is all of its proper subsets {𝐴𝐡, 𝐴𝐢, 𝐡𝐢, 𝐴, 𝐡, 𝐢}. These are connected to form the missing subcomplex, highlighted in the figure. The missing subcomplex 𝑆 in this case forms the entire boundary of 𝑇. Now the relative barycentric homology π»π‘›π‘Ÿπ‘’π‘™ (H ) = 𝐻𝑛 (𝑇, 𝑆). A disk relative to its boundary is the sphere of the same dimension [18], so here 𝐻𝑛 (𝑇, 𝑆) = 𝐻 f𝑛 (S2 ), where S2 is the 2-dimensional 33 Figure 2.9 A hypergraph H and its barycentric subdivision 𝑇 with the missing subcomplex highlighted. sphere. Recalling the homology groups of spheres from algebraic topology texts such as [18, 24] yields that ο£±  Z when 𝑛 = 2   ο£² 2Z  f𝑛 (S2 ) = π»π‘›π‘Ÿπ‘’π‘™ (H ) = 𝐻𝑛 (𝑇, 𝑆) = 𝐻   0  else. ο£³ The rest of this thesis contains new results, almost all of which utilize either the restricted barycentric homology or the relative barycentric homology of hypergraphs. We start with the restricted barycentric homology in the next chapter. 34 CHAPTER 3 RESULTS ON THE RESTRICTED BARYCENTRIC HOMOLOGY We will begin the results portion of this thesis with the restricted barycentric homology. Throughout this chapter, 𝑅 will be used to denote the restricted barycentric subdivision (Definition 2.3.2) of a hypergraph H . 3.1 Restricted Barycentric Subdivision We begin this section with results on the combinatorial structure of the restricted barycentric subdivisiOn 𝑅 itself before moving into results on the homology. A main component of this thesis, discussed in Section 5.2, is the computation of these homology theories. In general, computing the barycentric subdivision of a simplicial complex is expensive, as the number of simplices grows very quickly. Sepcifically, the barycentric subdivision of an 𝑛-dimensional simplex has (𝑛 + 1)! 𝑛-dimensional simplices. Therefore, where possible, we will use alternate constructions that do not require a full barycentric subdivision. To that end, the first two results of this section are alternative constructions of the restricted barycentric subdivision 𝑅. The following proposition is used as the definition of the restricted barycentric subdivision in [22]. It says that 𝑅 is the order complex (Definition 2.2.8) of the face poset (Definition 2.1.14) of the hypergraph. Proposition 3.1.1 (Poset Construction of 𝑅). The restricted barycentric subdivisIon 𝑅 of a hyper- graph H is the same simplicial complex as the order complex of the face poset of H , 𝑅 = Ξ”(𝐹𝑃(H )). Proof. Let H be a hypergraph. Denote its restricted barycentric subdivision by 𝑅. From H , form the poset 𝐹𝑃 and its order complex Ξ”(𝐹𝑃). Let Ξ© be a simplex in 𝑅. Then, after a relabelling if necessary, Ξ© = {𝑣 𝑒1 , 𝑣 𝑒2 , . . . , 𝑣 𝑒 π‘˜ } where 𝑒𝑖 βŠ‚ 𝑒 𝑗 in H for all 𝑖 < 𝑗. Note 𝑒 1 βŠ‚ 𝑒 2 βŠ‚ 𝑒 3 . . . βŠ‚ 𝑒 π‘˜ in H 35 by Proposition 2.3.1. Thus, in 𝐹𝑃(H ), 𝑒 1 < 𝑒 2 < ... < 𝑒 π‘˜ , which implies 𝜎 is a simplex in Ξ”(𝐹𝑃) as well. Therefore 𝑅 βŠ‚ Ξ”(𝐹𝑃). Let 𝜎 = {𝑒 1 , 𝑒 2 , . . . , 𝑒 π‘˜ } be a simplex in Ξ”(𝐹𝑃(H )). By definition, a simplex in the order complex of a poset represents a chain of inclusions in the poset, 𝑒 1 < 𝑒 2 < . . . < 𝑒 π‘˜ in 𝐹𝑃(H ). The relation on the poset 𝐹𝑃(H ) was given to be edge inclusion in H , so this means 𝑒 1 βŠ‚ 𝑒 2 βŠ‚ . . . βŠ‚ 𝑒 π‘˜ 𝑑𝑒π‘₯𝑑𝑖𝑛H . Therefore, 𝜎 = {𝑣 𝑒1 , 𝑣 𝑒2 , . . . , 𝑣 𝑒 π‘˜ } is also a simplex in 𝑅 by Proposition 2.3.1, and Ξ”(𝐹𝑃) βŠ‚ 𝑅, so Ξ”(𝐹𝑃) = 𝑅. β–‘ Recall the edge inclusion graph 𝐸 𝐼𝐺 (Definition 2.1.15) of a hypergraph. The second result is that its clique complex (Definition 2.2.7) is also equal to 𝑅. This is the construction that will be used later for computation, since it does not require the entire barycentric subdivision. Theorem 3.1.2 (Clique Construction of 𝑅). The restricted barycentric subdivision of a hypergraph H is the same simplicial complex as the clique complex (Definition 2.2.7) of the edge inclusion graph (Definition 2.1.15) of H that is 𝑅 = 𝑋 (𝐸 𝐼𝐺). Proof. Let H be a hypergraph. Denote its restricted barycentric subdivision with 𝑅. Build the edge inclusion graph, 𝐸 𝐼𝐺. The vertices of 𝐸 𝐼𝐺 are edges in H so let π‘˜ vertices, 𝑣 𝑒1 , ..., 𝑣 𝑒 π‘˜ , be a clique in 𝐸 𝐼𝐺. This yields a (π‘˜ βˆ’ 1)-simplex in 𝑋 (𝐸 𝐼𝐺). Inclusion is a partial order, and these π‘˜ vertices represent edges 𝑒 1 , ..., 𝑒 π‘˜ that are each pairwise comparable since it is a clique. Thus there is a linear order (potentially after reordering), 𝑒 1 βŠ‚ 𝑒 2 βŠ‚ . . . βŠ‚ 𝑒 π‘˜βˆ’1 βŠ‚ 𝑒 π‘˜ in H . This chain of edge inclusions gives rise to a matching (π‘˜ βˆ’ 1)-simplex in 𝑅, so 𝑋 (𝐸 𝐼𝐺) βŠ‚ 𝑅. 36 Let 𝜎 be a π‘˜ simplex in 𝑅. This corresponds to a chain of π‘˜ + 1 edges, 𝑒 1 βŠ‚ 𝑒 2 βŠ‚ . . . βŠ‚ 𝑒 π‘˜ βŠ‚ 𝑒 π‘˜+1 in H . Each of these edges is a vertex in the edge inclusion graph, and since subset is a transitive relation, each of those edges has a pairwise inclusion relation with every other, forming a (π‘˜ + 1)-clique in the graph, which corresponds to a π‘˜ simplex in is clique complex 𝑋 (𝐸 𝐼𝐺), so 𝑅 βŠ‚ 𝑋 (𝐸 𝐼𝐺). Therefore, 𝑅 = 𝑋 (𝐸 𝐼𝐺). β–‘ When starting with the associated simplicial complex and barycentric subdivision, all of the possible subedges are needed as vertices, not just the subedges that are present in the hypergraph. Even worse, information about all possible chains of inclusion among all the possible edges is needed. In this construction, only the edges of H are stored as vertices, and only their possible inclusion relations need to be checked. 3.2 Restricted Barycentric Homology Now we will develop the theory of the restricted barycentric homology. The first result is a plausibility check. If H is a hypergraph that also happens to be a simplicial complex, its restricted barycentric homology is the same as the simplicial homology. We first note a minor technicality: as a result of the downward closure property, a simplicial complex will always contain the empty set, and by Definition 2.1.1, a hypergraph never will. So, we say that a hypergraph is the same as its associated simplicial complex when their set of nonempty elements are the same. Proposition 3.2.1. Let H be a hypergraph that is the same as its associated simplicial complex, 𝐾. Then for all 𝑛, π»π‘›π‘Ÿπ‘’π‘  (H )  𝐻𝑛 (𝐾). Proof. Since H is already a simplicial complex, there are no missing subedges to add to obtain the associated simplicial complex 𝐾 (Definition 2.3.1), and thus H = 𝐾 \ {βˆ…}. Let 𝑇 be the barycentric subdivision of 𝐾 as in Definition 2.2.6. 37 Let Ξ© be a simplex in 𝑇. Then Ξ© = {𝑣 𝜎1 , 𝑣 𝜎2 , . . . , 𝑣 πœŽπ‘˜ }, where each πœŽπ‘– is a simplex in 𝐾. However, 𝐾 \ {βˆ…} = H , and so each 𝑣 πœŽπ‘– = 𝑣 𝑒𝑖 represents an edge 𝑒𝑖 in H . Thus by the definition of the restricted barycentric subdivision (Definition 2.3.2), Ξ© ∈ 𝑅, and hence 𝑇 βŠ‚ 𝑅. Since by definition 𝑅 βŠ‚ 𝑇, 𝑅 = 𝑇. We now have the following equalities and isomorphism: 𝐻 π‘Ÿπ‘’π‘  (H ) = 𝐻 (𝑅) = 𝐻 (𝑇)  𝐻 (𝐾). The first equality comes from Definition 2.3.3 of the restricted barycentric homology. The second equality comes from the set theoretic result 𝑅 = 𝑇, proved above, and the isomorphism 𝐻 (𝑇)  𝐻 (𝐾) was given as Lemma 2.2.3. This proves the proposition. β–‘ In words, when H is a simplicial complex, the restricted barycentric subdivision is equal to the barycentric subdivision because all of the possible edges are actually present in the hypergraph. In the next result, let 𝐻 π‘Ÿπ‘’π‘  (𝑒𝑖 ) denote the restricted barycentric homology of the hypergraph with only one edge, 𝑒𝑖 . Recall the definition of a reduced hypergraph from Definition 2.1.5 as a hypergraph with no subedges. Since the restricted barycentric homology is concerned primarily with inclusion relations, and a reduced hypergraph has no inclusion relations, a reduced hypergraph has a fairly simple, characterizable restricted barycentric homology. This characterization is given in the next theorem. Theorem 3.2.2 (Restricted Homology of Reduced Hypergraphs† ). Let H be a reduced hypergraph. 0 (H ) = |H | and 𝛽𝑖 (H ) = 0 for 𝑖 > 0. Then π›½π‘Ÿπ‘’π‘  π‘Ÿπ‘’π‘  Proof. Recall the restricted barycentric subdivision (Definition 2.3.2) is a simplicial complex with a vertex for each edge in the hypergraph, and simplices based on chains of inclusions of edges. In a reduced hypergraph, no edges are subedges, so each vertex is isolated and the restricted barycentric subdivision is a disjoint union of vertices, each representing one of the 𝑒𝑖 . Since the homology of 38 disjoint topological spaces is equal to the direct sum of the homology of each of their components Γ‰π‘š π‘Ÿπ‘’π‘  [18], this gives that 𝐻 π‘Ÿπ‘’π‘  (H ) = 𝑖=1 𝐻 (𝑒𝑖 ), where π‘š is the number of edges in the hypergraph. Since the hypergraph with only the edge 𝑒𝑖 is a maximum edge hypergraph, we can apply Theorem 3.2.3 to find its restricted Betti numbers, π›½π‘Ÿπ‘’π‘  0 (𝑒𝑖 ) = 1 and 𝛽𝑛 (𝑒𝑖 ) = 0 for 𝑛 > 0. Thus π‘Ÿπ‘’π‘  each vertex of 𝑅 contributes a rank one subgroup to the zeroth dimensional homology of the 0 (H ) = |H | and 𝛽𝑛 (H ) = 0 for 𝑛 > 0, as was to be simplicial complex. This means that π›½π‘Ÿπ‘’π‘  π‘Ÿπ‘’π‘  shown. β–‘ In a reduced hypergraph, every edge is a toplex and there are no subedges. The next result is about maximum edge hypergraphs (Definition 2.1.10), in which there is only one toplex. The restricted barycentric homology has useful implications for the inclusion relationships between toplexes and their subedges. In a maximum edge hypergraph, all of the edges are subedges of the single toplex. This leads to a classification of the restricted barycentric homology of maximum edge hypergraphs with nontrivial homology in only dimension zero. Theorem 3.2.3 (Restricted Homology of Maximum Edge Hypergraphs). Let H be a maximum edge hypergraph. Then the restricted barycentric homology π»π‘›π‘Ÿπ‘’π‘  (H ) is as follows: ο£±  Z if 𝑛 = 0   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘  (H ) =    0 else.  ο£³ Proof. Let H be a maximum edge hypergraph, with maximum edge 𝑒. Construct 𝑅, the restricted barycentric subdivision (Definition 2.3.2) of H . Note that 𝑒 is a vertex in 𝑅, since it is an edge in the hypergraph and a simplex in 𝐾. Because all other edges are included in 𝑒, 𝑣 𝑒 is connected via an edge in 𝑅 to all other vertices in 𝑅. If there are any higher dimensional simplices Ξ© with vertices in 𝑅 \ 𝑣 𝑒 , representing inclusions among subedges of 𝑒 in the hypergraph, all of those edges are still contained in 𝑒, so Ξ© βˆͺ 𝑣 𝑒 is a simplex in 𝑅. Thus, 𝑅 is a cone with apex 𝑣 𝑒 , and hence contractible ([18]), proving the lemma. β–‘ A maximum edge hypergraph has a single fence component (Definition 2.1.12). The next theorem says that this knowledge is enough to know the zeroth dimensional restricted barycentric 39 homology of the hypergraph. It turns out that the number of fence components of the hypergraph is equal to the rank of the zeroth dimensional homology group, as shown next. Theorem 3.2.4 (Zeroth Dimensional Restricted Homology† ). The rank of the zeroth dimensional restricted barycentric homology group, π›½π‘Ÿπ‘’π‘  0 (H ), is equal to the number of fence components, Ξ“(H ), of the hypergraph. Proof. Recall that π›½π‘Ÿπ‘’π‘  0 (H ) = 𝛽0 (𝑅) is the number of path components of 𝑅 where 𝑅 is the restricted barycentric subdivision of H (Definition 2.3.3). Suppose two vertices of 𝑅, 𝑣 𝑒 and 𝑣 𝑓 , are in the same path component of 𝑅. This means that there is a sequence of vertices 𝑣 𝑒 , 𝑣 𝑒1 , 𝑣 𝑒2 , ..., 𝑣 𝑓 such that there is an inclusion relationship between the hyperedges representing each pair of adjacent vertices in the sequence. In other words, in the hypergraph there is a sequence of edges 𝑒, 𝑒 1 , 𝑒 2 , ..., 𝑓 where each pair of adjacent edges has an inclusion relationship in either direction. This is the definition of 𝑒 and 𝑓 being in the same fence component of H . Reversing that line of thought yields the inverse statement, and so two vertices in 𝑅 are in the same path component of 𝑅 if and only if their corresponding edges are in the same fence component of H . Since there is a bΔ³ection between vertices of 𝑅 and edges of H , there will be the same number of path components of 𝑅 and fence components of H . Thus π›½π‘Ÿπ‘’π‘  0 (H ) = Ξ“(H ), proving the theorem. β–‘ In the above proof, a bΔ³ection is found between fence components of the hypergraph and path components of 𝑅. Each fence component of the hypergraph gives rise to a path component of 𝑅. Since the homology of a simplicial complex is the direct sum of the homologies of its path components [18], we get the following corollary. Corollary 3.2.5. Let H be a hypergraph, with fence components H1 , H2 , . . . , Hπ‘˜ . Then Ê π‘˜ π»π‘›π‘Ÿπ‘’π‘  (H ) = π»π‘›π‘Ÿπ‘’π‘  (H𝑖 ). 𝑖=1 40 Figure 3.1 Hypergraphs with different fence components than connected components. As an application of Theorem 3.2.4, see the hypergraphs in Figure 3.1. The difference between H and H β€² is the edge 𝐡, which is only in H β€². This edge does not change the number of connected components as per Definition 2.1.9, but does change the number of fence components. In H , there is no fence between the edge 𝐴𝐡 and 𝐡𝐢, because they do not share a mutual subedge or toplex. However, in H , 𝐴𝐡, 𝐡, 𝐡𝐢 is a fence. Thus π›½π‘Ÿπ‘’π‘  β€² 0 (H ) = 2 and 𝛽0 (H ) = 1. π‘Ÿπ‘’π‘  The last theorem in this section uses the idea of a simplicial collapse (Theorem 2.2.7). It gives conditions on which edges can be removed from a hypergraph without changing the restricted barycentric homology. Theorem 3.2.6. † Let H be a hypergraph with an edge 𝑒 such that there is exactly one edge 𝑓 with 𝑒 βŠ‚ 𝑓 or 𝑓 βŠ‚ 𝑒. Denote by H β€² the hypergraph H \ {𝑒}. Then βˆ€ 𝑛, π»π‘›π‘Ÿπ‘’π‘  (H )  π»π‘›π‘Ÿπ‘’π‘  (H β€²). Proof. Let 𝑅, 𝑅′ be the restricted barycentric subdivisions of H , H β€² respectively. Note that 𝑅 = 𝑅′ βˆͺ {𝑒 𝑓 , 𝑒}. In 𝑅, 𝑒 𝑓 is a maximal simplex. If 𝑒 𝑓 was not maximal, then it would be a face of 𝑒 𝑓 𝑔 for some edge 𝑔 ∈ 𝐸. This would imply that 𝑒𝑔 is a simplex in 𝑅, which would imply that either 𝑒 βŠ‚ 𝑔 or 𝑔 βŠ‚ 𝑒, which cannot be true as 𝑒 was assumed to only be related by inclusion to 𝑓 . Since 𝑒 𝑓 is the only maximal simplex that 𝑒 is a face of, 𝑅 can be simplicially collapsed along 𝑒 and 𝑒 𝑓 by Theorem 2.2.7. Removing 𝑒 𝑓 and 𝑒 from 𝑅 leaves the same simplicial complex as 𝑅′. Therefore, 𝑅 simplicially collapses to, and is thus homotopy equivalent to, 𝑅′, proving the theorem. β–‘ 41 Figure 3.2 Hypergraphs used as examples of Theorem 3.2.6. The two hypergraphs in Figure 3.2 have the same restricted barycentric homology because the edge 𝐢𝐷 in H only has 𝐢 as a subedge, and thus can be removed by the theorem. We will further discuss the computation of the restricted barycentric homology in Section 5.2. As part of the conclusion, we will share some ideas for future research on the restricted barycentric homology of hypergraphs. For now, we are ready to move on to the results on the second definition of hypergraph homology studied in this thesis, the relative barycentric homology. 42 CHAPTER 4 RESULTS ON THE RELATIVE BARYCENTRIC HOMOLOGY In this chapter, we will discuss some results in the development of the theory of the relative barycen- tric homology for hypergraphs. Throughout, 𝑆 will denote the missing subcomplex (Definition 2.3.4), and 𝑇 will denote the barycentric subdivision (Definition 2.2.6) of the associated simplicial complex 𝐾 (Definition 2.3.1) of the hypergraph. This chapter has three sections. The first section contains two analogues of the Mayer-Vietoris sequence from Theorem 2.2.4. These allow for breaking large and complex hypergraphs down and taking the relative barycentric homology of subhypergraphs, before gluing them back together with the Mayer-Vietoris sequences. The first version is at the level of the hypergraph edges. It allows for computing the relative barycentric homology of a hypergraph by knowing the homology of two subhypergraphs and of the hypergraph whose edges are their intersection. The second method applies at the simplicial complex level, using the relative Mayer-Vietoris Theorem to compute the homology after taking the barycentric subdivision and finding the missing subcomplex. Therefore, the second Mayer-Vietoris Theorem of this section will be called the simplicial version. The drawback of the second method is that there is not a nice way to frame this theorem using edges of the original hypergraph, but it has the advantage of requiring one fewer condition. We will give an example of a hypergraph where the first version cannot be used to compute its relative barycentric homology, but the simplicial version can be used to show why both results are useful. The last topic of this section will be some implications of the hypergraph versions of the Mayer-Vietoris Theorem. The second section, then, is useful for studying the subhypergraphs. Maximum edge hyper- graphs (Definition 2.1.10) have a relative barycentric homology that is simpler to study than general hypergraphs. This is due to their associated simplicial complex 𝐾 being contractible. We will uti- lize that fact and the long exact sequence of a pair of spaces from Theorem 2.2.6 as shortcuts to computing the relative barycentric homology of maximum edge hypergraphs. We will see that the relative barycentric homology 𝐻 π‘Ÿπ‘’π‘™ (H ) for a maximum edge hypergraph H depends heavily on 43 the homology of its missing subcomplex 𝐻 (𝑆). After showing that in generality, we move on to some results that help interpret what information the relative barycentric homology relates about the maximum edge hypergraph. This is done in dimensions 0, 1, π‘š βˆ’ 2, and π‘š βˆ’ 1, where π‘š is the number of vertices in the hypergraph. Lastly, a condition is presented that would cause a maximum edge hypergraph to have no relative barycentric homology at all. The third section gives results on the relative barycentric homology for general hypergraphs. These include an overall classification of the relative barycentric homology of reduced hypergraphs in all dimensions and of any hypergraph in dimension zero, comparable to Theorems 3.2.4 and 3.2.2 for the restricted barycentric homology. In dimension zero, the relative barycentric homology turns out to be entirely dependent on the simplicial components (Definition 2.1.16) of the hypergraph. There are more results about manipulating the long exact sequence of the pair (𝑇, 𝑆), which maintains usefulness even when H is not a maximum edge hypergraph. The last result of this chapter gives a condition on which simplicial collapses can be applied during relative barycentric homology computations. 4.1 Two Versions of a Mayer-Vietoris Sequence We will begin the results for the relative barycentric homology with two versions of the Mayer- Vietoris Theorem. Since this is a relative homology theory, both versions are built off of Theorem 2.2.5. In algebraic topology, the Mayer-Vietoris Theorem is very useful for finding the homology of a space when it can be decomposed into the union of two subspaces whose homology is already known, and the intersection of those two subspaces also has a known homology. Recall the 𝑛- dimensional sphere from the earlier example when we defined the Mayer-Vietoris sequence. It is the union of two hemispheres, which are 𝑛-dimensional disks. The intersection of the hemispheres is the equator, which is an (𝑛 βˆ’ 1)-dimensional sphere. The Mayer-Vietoris theorem can thus inductively be used to prove the homology groups of the spheres. Ð The first version allows for the hypergraph H to be written as H = H1 H2 , and these H1 and H2 form the analogous constructions to the subspaces in the regular Mayer-Vietoris sequence (Theorem 2.2.4). This is helpful because it can be used to break down hypergraphs into smaller 44 components for relative barycentric homology computations. Alternatively, it can be used to glue together hypergraphs along some intersecting edges and compute the homology of the new hypergraph. Theorem 4.1.1 (Mayer-Vietoris Theorem for Hypergraphs). Fix a hypergraph H = {𝑉, 𝐸 }. Let H1 = {𝑉1 , 𝐸 1 } and H2 = {𝑉2 , 𝐸 2 } be subhypergraphs, chosen such that 1. 𝐸 1 , 𝐸 2 βŠ‚ 𝐸 with 𝐸 1 βˆͺ 𝐸 2 = 𝐸. 2. Let π‘˜ ∈ {1, 2}. For any 𝑒𝑖 ∈ H and 𝑒 𝑗 ∈ 𝐸 π‘˜ with 𝑒𝑖 βŠ‚ 𝑒 𝑗 , we have that 𝑒𝑖 ∈ 𝐸 π‘˜ . 3. Let 𝐸 β€² B 𝐸 1 ∩ 𝐸 2 and call the hypergraph it induces H β€². For all 𝑒 1 ∈ 𝐸 1 and 𝑒 2 ∈ 𝐸 2 , βˆƒ 𝑒′ ∈ 𝐸 β€² s.t. 𝑒 1 ∩ 𝑒 2 βŠ‚ 𝑒′. Then the following is a long exact sequence on the relative barycentric homology of hypergraphs: . . . β†’ π»π‘›π‘Ÿπ‘’π‘™ (H β€²) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H1 ) βŠ• π»π‘›π‘Ÿπ‘’π‘™ (H2 ) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 π‘Ÿπ‘’π‘™ (H β€²) β†’ . . . . Proof. The main objective of the proof is to show that the barycentric subdivisions and missing subcomplexes of H , H1 , H2 and H β€² satisfy the requirements of Theorem 2.2.5. Note that because we have inclusions on hypergraphs, H1 Hβ€² H H2 we have inclusions on the associated simplicial complexes, 𝐾1 𝐾′ 𝐾. 𝐾2 Define pairs (𝑇, 𝑆), (𝑇 β€², 𝑆′), (𝑇1 , 𝑆1 ), and (𝑇2 , 𝑆2 ) as in Definition 2.3.5 for H , H β€², H1 , and H2 respectively. In each case, 𝑇 is the barycentric subdivision of the relevant associated simplicial 45 complex 𝐾, and 𝑆 is the missing subcomplex of 𝑇 induced by the relevant hypergraph. For example, 𝑆′ and 𝑇 β€² are defined as 𝑇 β€² = {Ξ© = {𝑣 𝜎1 , Β· Β· Β· , 𝑣 πœŽπ‘› } | 𝜎1 βŠ‚ 𝜎2 βŠ‚ . . . βŠ‚ πœŽπ‘› βŠ‚ 𝐾 β€² }, and 𝑆′ = {Ξ© ∈ 𝑇 | βˆ€ 𝑣 πœŽπ‘– ∈ Ξ©, πœŽπ‘– does not represent an edge in H β€² }. With this notation in place, the long exact sequence becomes . . . β†’ 𝐻𝑛 (𝑇 β€², 𝑆′) β†’ 𝐻𝑛 (𝑇1 , 𝑆1 ) βŠ• 𝐻𝑛 (𝑇2 , 𝑆2 ) β†’ 𝐻𝑛 (𝑇, 𝑆) β†’ π»π‘›βˆ’1 (𝑇 β€², 𝑆′) β†’ . . . We will show that our setting fits the setup of the relative Mayer-Vietoris sequence from Definition 2.2.5, which will give the theorem. In particular, we need to show four things: (i) 𝑇 = 𝑇1 βˆͺ 𝑇2 ; (ii) 𝑆 = 𝑆1 βˆͺ 𝑆2 ; (iii) 𝑇 β€² = 𝑇1 ∩ 𝑇2 ; and (iv) 𝑆′ = 𝑆1 ∩ 𝑆2 . This will be done in order. First, we will show 𝑇 = 𝑇1 βˆͺ 𝑇2 . If Ξ© = {𝑣 𝜎1 , 𝑣 𝜎2 , . . . , 𝑣 πœŽπ‘˜ } is a simplex in 𝑇, then for some ordering of those vertices, 𝜎1 βŠ‚ 𝜎2 βŠ‚ . . . βŠ‚ πœŽπ‘˜ ∈ 𝐾. Further, πœŽπ‘˜ represents a subedge of an edge 𝑒 in H , in which all of the other πœŽπ‘– represented by vertices in Ξ© must also be contained. For the rest of this proof, the 𝑣 πœŽπ‘˜ that represents the simplex in 𝐾 containing all other vertices of a simplex Ξ© in 𝑇 will be called the maximal vertex of Ξ©. This edge 𝑒 must then be in 𝐸 1 or 𝐸 2 , hence πœŽπ‘– for all 𝑖 ∈ {1, 2, . . . , π‘˜ } is in 𝐾1 or 𝐾2 , which implies then that Ξ© is a simplex in 𝑇1 or 𝑇2 , i.e. Ξ© ∈ 𝑇1 βˆͺ 𝑇2 . Similarly, a simplex Ξ¦ in 𝑇1 or 𝑇2 has a maximal vertex 𝑣 𝜏 corresponding to a simplex 𝜏 in 𝐾1 or 𝐾2 , such that 𝜎 βŠ‚ 𝜏 for all 𝑣 𝜎 ∈ Ξ¦. This simplex 𝜏 represents a subedge of an edge 𝑒′ in 𝐸 1 or 𝐸 2 . Both 𝐸 1 and 𝐸 2 are subsets of 𝐸, so 𝑒′ ∈ 𝐸. Thus 𝜏 ∈ 𝐾, and, hence, Ξ¦ ∈ 𝑇. Therefore, any simplex in 𝑇1 or 𝑇2 must also be in 𝑇. So, 𝑇1 βˆͺ 𝑇2 = 𝑇. Next, it is necessary to show 𝑆 = 𝑆1 βˆͺ 𝑆2 . Recall that 𝑆 is the subcomplex of 𝑇 generated by the vertices 𝑣 𝜎 that correspond to the simplices 𝜎 in 𝐾 that are missing as subedges in H . Suppose Ξ© is a simplex in 𝑆. Then every vertex comprising Ξ© corresponds to a simplex in 𝐾 that is a missing subedge in H . In particular, the maximal vertex of Ξ¦ corresponds to a subedge of an edge 𝑒 in 𝐸. Now, 𝑒 must be in 𝐸 1 or 𝐸 2 . Thus, Ξ¦ is in 𝑆1 or 𝑆2 , so 𝑆 βŠ† 𝑆1 βˆͺ 𝑆2 . 46 Now let Ξ¦ be in 𝑆1 βˆͺ 𝑆2 , say WLOG Ξ¦ ∈ 𝑆1 . Then every vertex in Ξ¦ represents a missing subedge of an edge in H1 . By assumption two of the theorem for the construction of 𝐸 1 and 𝐸 2 , all of those vertices represent edges that are missing in 𝐸 as well, thus Ξ¦ is also in 𝑆. Therefore, 𝑆 = 𝑆1 βˆͺ 𝑆2 . The third step is to show that 𝑇 β€² = 𝑇1 ∩ 𝑇2 . Let Ξ© ∈ 𝑇 β€². Then all of the vertices in Ξ© represent simplices in 𝐾 β€² contained in the simplex representing the maximal vertex of Ξ©, meaning they are all subedges of the edge 𝑒′ in 𝐸 β€² corresponding to that simplex. Since 𝐸 β€² = 𝐸 1 ∩ 𝐸 2 , 𝑒′ is in 𝐸 1 and 𝐸 2 , so all of its subedges are represented in 𝐾1 and 𝐾2 . Therefore Ξ© ∈ 𝑇1 ∩ 𝑇2 , and hence 𝑇 β€² βŠ† 𝑇1 ∩ 𝑇2 . Similarly, a simplex Ξ¦ in both 𝑇1 and 𝑇2 has the same maximum edge in 𝐸 1 and 𝐸 2 , so that edge is in their intersection 𝐸 β€², and thus Ξ¦ is in 𝑇 β€². Therefore, 𝑇 β€² = 𝑇1 ∩ 𝑇2 . Lastly, it is necessary to verify that 𝑆′ = 𝑆1 ∩ 𝑆2 . Let Ξ¦ be a simplex in 𝑆′, then every vertex in Ξ¦ represents a missing subedge of an edge in 𝐸 β€², hence a missing subedge of an edge in both 𝐸 1 and 𝐸 2 . Again by the second condition in the theorem on 𝐸 1 and 𝐸 2 ,Ξ¦ is necessarily a simplex in both 𝑆1 and 𝑆2 . If Ξ© is a simplex in 𝑆1 βˆ©π‘†2 , then every vertex in Ξ© represents a missing subedge of a hyperedge in 𝐸 1 ∩ 𝐸 2 = 𝐸 β€², and so Ξ© ∈ 𝑆′. Thus, 𝑆′ = 𝑆1 ∩ 𝑆2 . Therefore the complexes satisfy the requirements of Definition 2.2.5, and so we have that the long exact sequence . . . β†’ π»π‘›π‘Ÿπ‘’π‘™ (H β€²) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H1 ) βŠ• π»π‘›π‘Ÿπ‘’π‘™ (H2 ) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 π‘Ÿπ‘’π‘™ (H β€²) β†’ . . . . is exact as required. β–‘ Condition 3 seems, and is, restrictive, but it is a necessary condition. Recall that the condition states that for any 𝑒 1 in 𝐸 1 and 𝑒 2 in 𝐸 2 , there is an edge 𝑒′ in 𝐸 1 ∩ 𝐸 2 such that 𝑒 1 ∩ 𝑒 2 βŠ‚ 𝑒′. In words, this means that every pairwise intersection of edges in 𝐸 1 and 𝐸 2 is contained in an edge in both. Consider the following hypergraph, which can be seen in Figure 2.1: H = {𝐴𝐡𝐢, 𝐡𝐢𝐷, 𝐡, 𝐢}. 47 A natural choice for a partition of this hypergraph is to separate the 3-vertex edges, and then in order to satisfy condition 2 of the theorem, 𝐸 1 = {𝐴𝐡𝐢, 𝐡, 𝐢} and 𝐸 2 = {𝐡𝐢𝐷, 𝐡, 𝐢}. This partition, however, does not satisfy condition 3. The edges 𝐴𝐡𝐢 ∈ 𝐸 1 and 𝐡𝐢𝐷 ∈ 𝐸 2 intersect in 𝐡𝐢, which is not an edge of 𝐸 β€² or a subset therein. The vertices generating 𝑇 β€² = 𝑇1 ∩ 𝑇2 are {𝐡𝐢, 𝐡, 𝐢}, but since 𝐡, 𝐢 ∈ 𝐸, the only vertex generating 𝑆′ = 𝑆1 ∩ 𝑆2 is {𝐡𝐢}. If there was an β€œintersection hypergraph" that would allow us to use the Mayer-Vietoris theorem for hypergraphs here, it would have to contain 𝐡𝐢 as both a missing subedge and a maximal edge. Of course, an edge can’t be both a maximal edge and a missing subedge, so this is impossible. Thus, for this H and the most natural partition, there is not a hypergraph whose relative barycentric division is (𝑇 β€², 𝑆′), and it will therefore be impossible to write the Mayer-Vietoris sequence where the intersection term is the relative barycentric homology of any hypergraph. The following lemma gives this result in generality. Lemma 4.1.2. Suppose 𝐸 1 , 𝐸 2 form a partition of a hypergraph and satisfy condition two of the Mayer-Vietoris Theorem for hypergraphs, but do not satisfy condition three. Then, (𝑇 β€², 𝑆′) is not the relative barycentric subdivision of any hypergraph. Proof. Let 𝑒 1 ∈ 𝐸 1 , 𝑒 2 ∈ 𝐸 2 be such that 𝑒 1 βˆ©π‘’ 2 is not a subset of any edge in 𝐸 1 ∩𝐸 2 ; in other words 𝑒 1 and 𝑒 2 are edges that contradict condition three. It suffices to assume that 𝑒 1 ∩ 𝑒 2 is maximal among intersections of edges in 𝐸 1 and 𝐸 2 . This is because if an intersection is not maximal, then a maximal intersection that it is contained in would also contradict the third condition. Since 𝑒 1 ∩ 𝑒 2 is maximal among intersections {𝑒𝑖 ∩ 𝑒 𝑗 | 𝑒𝑖 ∈ 𝐸 1 , 𝑒 𝑗 ∈ 𝐸 2 }, πœŽπ‘’1 βˆ©π‘’2 is a maximal simplex in 𝐾 β€² = 𝐾1 ∩ 𝐾2 . There is thus also a corresponding vertex 𝑣 πœŽπ‘’1 βˆ©π‘’2 of 𝑇 β€² = 𝑇1 ∩ 𝑇2 . Since 𝑒 1 ∩ 𝑒 2 is not a subedge of any edge in 𝐸 1 ∩ 𝐸 2 , by condition two 𝑣 𝑒1 ∩ 𝑣 𝑒2 is a vertex in 𝑇 β€² that is part of the generating set for 𝑆′. It will form part of the missing subcomplex. Suppose there was a hypergraph such that 𝐾 β€² was its associated simplicial complex, with (𝑇 β€², 𝑆′) being its relative barycentric subdivision. By the preceding sentences, 𝑒 1 ∩ 𝑒 2 is both a maximal edge and a missing subedge of that hypergraph, which is a contradiction. Therefore, no hypergraph with relative barycentric subdivision (𝑇 β€², 𝑆′) can exist, proving the lemma. β–‘ 48 All hope is not lost for a useful Mayer-Vietoris sequence on hypergraphs, though. If we pass through to the level of the relative barycentric subdivision, the relative version of the Mayer-Vietoris sequence (Theorem 2.2.5) will still hold and be useful to compute the homology of a hypergraph in terms of a direct sum of two of its subgraphs. In this case, simply defining 𝑇 β€² as 𝑇1 ∩ 𝑇2 and 𝑆′ as 𝑆1 ∩ 𝑆2 still ensures . . . β†’ 𝐻𝑛 (𝑇 β€², 𝑆′) β†’ 𝐻𝑛 (𝑇1 , 𝑆1 ) βŠ• 𝐻𝑛 (𝑇2 , 𝑆2 ) β†’ 𝐻𝑛 (𝑇, 𝑆) β†’ π»π‘›βˆ’1 (𝑇 β€², 𝑆′) β†’ . . . is an exact sequence. The difference here is that π»βˆ— (𝑇 β€², 𝑆′) is not the relative barycentric homology of the hypergraph H𝐸1 ∩𝐸2 , which is the hypergraph whose edgeset is 𝐸 1 ∩ 𝐸 2 . The simplicial complex 𝑇 β€² still can be given a physical interpretation in terms of the hypergraph, though. A simplex in 𝑇 β€² is a simplex in 𝑇1 ∩ 𝑇2 and the simplices in 𝑇𝑖 are the simplices in 𝑇 that only contain the representations of subsets of edges in 𝐸𝑖 as their vertices. Thus 𝑇 β€² is generated by (as in Definition 2.2.4) the subsets 𝑉 𝑗 = {𝑣 𝜎0 , ...., 𝑣 πœŽπ‘˜ | βˆ€ 𝑖, πœŽπ‘– βŠ‚ 𝑒 1 ∈ 𝐸 1 , and πœŽπ‘– βŠ‚ 𝑒 2 ∈ 𝐸 2 }. Physically, then, 𝑇 β€² is still the simplicial complex whose vertices are subedges of edges in 𝐸 1 and 𝐸 2 and whose simplices are all the simplices in 𝑇 containing just some subset of those vertices. The caveat is just that if the toplexes of 𝑇 β€² are not hyperedges, then there is no hypergraph interpretation of 𝑇 β€², as the toplexes that are not hyperedges cannot be phrased as β€œmissing subedges". In our example above from Figure 2.1, 𝐡𝐢 was a toplex in 𝑇 β€², but was not an edge of H . The missing subcomplex 𝑆′ is still generated by any vertex of 𝑇 β€² that isn’t a hyperedge, but there may be a vertex in 𝑆′ whose corresponding simplex in 𝐾 is not a subset of any edge in 𝐸 β€² = 𝐸 1 ∩ 𝐸 2 . We get the following theorem: Theorem 4.1.3 (Mayer-Vietoris Theorem - Simplicial Version). Let H = {𝑉, 𝐸 } be a hypergraph. If H1 = {𝑉1 , 𝐸 1 } and H2 = {𝑉2 , 𝐸 2 } are subhypergraphs chosen such that 1. 𝐸 1 , 𝐸 2 βŠ‚ 𝐸 with 𝐸 1 βˆͺ 𝐸 2 = 𝐸, and 2. if 𝑒𝑖 βŠ‚ 𝑒 𝑗 , and 𝑒 𝑗 ∈ 𝐸 1 (wlog), then 𝑒𝑖 ∈ 𝐸 1 . 49 If 𝑇 β€² = 𝑇1 βˆ©π‘‡2 and 𝑆′ = 𝑆1 βˆ©π‘†2 , where π‘‡π‘˜ , 𝑆 π‘˜ are the barycentric subdvision and missing subcomplex of Hπ‘˜ , then the following is a long exact sequence using both the relative barycentric homology of hypergraphs and the relative homology of simplicial complexes: . . . β†’ 𝐻𝑛 (𝑇 β€², 𝑆′) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H1 ) βŠ• π»π‘›π‘Ÿπ‘’π‘™ (H2 ) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑇 β€², 𝑆′) β†’ . . . Using this simplicial version of the theorem, the homology of the hypergraph in the example above from Figure 2.1 can be computed. Recall that 𝐸 1 = {𝐴𝐡𝐢, 𝐡, 𝐢} and 𝐸 2 = {𝐡𝐢𝐷, 𝐡, 𝐢}. We will see in the next section that ο£±  Z 𝑛=1   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘™ (H1 )  π»π‘›π‘Ÿπ‘’π‘™ (H2 ) =   0  else. ο£³ The associated simplicial complex of H is two triangles joined together at an edge, so H is not going to have any relative barycentric homology in dimensions higher than 2. Note that 𝑇1 and 𝑇2 are each barycentric subdivisions of triangles, with intersection 𝑇 β€² = {{𝐡𝐢, 𝐡}, {𝐡𝐢, 𝐢}, 𝐡𝐢, 𝐡, 𝐢}. Of these, only 𝐡𝐢 ∈ 𝑆′, as 𝐡 and 𝐢 are both edges in the hypergraph. Therefore, (𝑇 β€², 𝑆′) is homotopic to a line segment, which is contractible and so 𝐻𝑛 (𝑇 β€², 𝑆′) = 𝐻 f𝑛 (𝑇 β€²) = 0 for all 𝑛. Since every third term in the long exact sequence of Theorem 4.1.3 is 0, there is an isomorphism, π»π‘›π‘Ÿπ‘’π‘™ (H1 ) βŠ• π»π‘›π‘Ÿπ‘’π‘™ (H2 )  π»π‘›π‘Ÿπ‘’π‘™ (H ). Therefore, ο£±  Z Z βŠ• 𝑛=1   ο£² 2Z  2Z π»π‘›π‘Ÿπ‘’π‘™ (H ) =   0  else. ο£³ Applications of both Theorem 4.1.1 for hypergraphs and the simplicial version in Theorem 4.1.3 follow. If 𝐸 1 and 𝐸 2 can be chosen as disjoint sets (including if, for example, the hypergraph has multiple connected components), then the Mayer-Vietoris sequence from Theorem 4.1.1 reduces to π»π‘›π‘Ÿπ‘’π‘™ (H1 ) βŠ• π»π‘›π‘Ÿπ‘’π‘™ (H2 )  π»π‘›π‘Ÿπ‘’π‘™ (H β€²) βˆ€π‘›. This is displayed in the second hypergraph in Figure 2.1. Here, 𝐸 1 = {𝐴𝐡𝐢} and 𝐸 2 = {𝐡𝐢𝐷}. Their intersection is empty, so the homology of the hypergraph is the direct sum of their homologies. 50 In Figure 2.9, we computed that ο£±  Z when 𝑛 = 2   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘™ (H1 ) = π»π‘›π‘Ÿπ‘’π‘™ (H2 ) =   0  else, ο£³ and so ο£±  Z Z βŠ• when 𝑛 = 2   ο£² 2Z  2Z π»π‘›π‘Ÿπ‘’π‘™ (H β€²) =   0  else. ο£³ The second condition of Theorem 4.1.3 which says that the sets of edges chosen to partition H must be closed under taking subedges in the hypergraph, means choosing 𝐸 1 , 𝐸 2 to be disjoint is not always possible. For example, if H is a maximum edge hypergraph, then the Mayer-Vietoris sequence will not be useful, as whichever subhypergraph contains the maximum edge must contain all of the edges in H . If 𝐸 1 and 𝐸 2 are not disjoint, but the space (𝑇 β€², 𝑆′) is contractible (whether or not condition 3 holds), then very nearly the same thing can be said. This was the case in our previous example from Figure 2.1, where condition 3 does not hold. After passing through to the relative barycentric subdi- vision level of the Mayer-Vietoris sequence, (𝑇 β€², 𝑆′) being contractible implies that 𝐻𝑛 (𝑇 β€², 𝑆′) = 0 when 𝑛 > 0, so the isomorphism π»π‘›π‘Ÿπ‘’π‘™ (H1 ) βŠ• π»π‘›π‘Ÿπ‘’π‘™ (H2 )  π»π‘›π‘Ÿπ‘’π‘™ (H ) holds for all 𝑛 > 1, with a still exact sequence 0 β†’ 𝐻1π‘Ÿπ‘’π‘™ (H1 ) βŠ• 𝐻1π‘Ÿπ‘’π‘™ (H2 ) β†’ 𝐻1π‘Ÿπ‘’π‘™ (H ) β†’ 𝐻0 (𝑇 β€², 𝑆′) β†’ 𝐻0π‘Ÿπ‘’π‘™ (H1 ) βŠ• 𝐻0π‘Ÿπ‘’π‘™ (H2 ) β†’ 𝐻0π‘Ÿπ‘’π‘™ (H ) β†’ 0. The Mayer-Vietoris sequence can reduce any hypegraph to a collection of maximum edge hypergraphs and their intersections, by letting the subhypergraphs be induced by the toplexes. It is easier to find the homology of those subhypergraphs and their intersections, and then the Mayer- Vietoris sequence will help splice them together. In fact, the next section will focus on computing the homology of hypergraphs with maximum edges. 51 4.2 Results on Maximum Edge Hypergraphs Maximum edge hypergraphs have many nice properties in the relative barycentric homology, running contrary to Theorem 3.2.3 which says the restricted barycentric homology does not dis- tinguish any maximum edge hypergraph from any other. For the duration of this section, let H be a maximum edge hypergraph as per Definition 2.1.10. Let 𝑒 be the maximum edge, and |𝑒| = π‘š be the number of vertices in the hypergraph. In this section, we will begin by leveraging the long exact sequence of a pair, Theorem 2.2.6, as a computational tool for the relative barycentric homology. This will lead into Theorem 4.2.3 and Corollary 4.2.4 which give computational aides in high and low dimensions, respectively. Using those results, this section will conclude with several interpretability results that glean information about the hypergraph edge structure based on its relative barycentric homology, with examples along the way. 4.2.1 Leveraging the Long Exact Sequence of a Pair As the relative barycentric homology of a hypergraph H is a relative homology, it is a good idea to try to fit it into the long exact sequence of a pair of spaces from Theorem 2.2.6. The missing subcomplex 𝑆 is a subcomplex of the barycentric subdivision 𝑇. Since the definition of the relative barycentric homology in Definition 2.3.5 is π»π‘›π‘Ÿπ‘’π‘™ (H ) = 𝐻𝑛 (𝑇, 𝑆), there is always a long exact sequence: . . . β†’ 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) β†’ . . . In the case of a maximum edge hypergraph, this sequence becomes a lot simpler, which the results at the beginning of this section show. Specifically, the first lemma of this section fully details the associated simplicial complex 𝐾 of a maximum edge hypergraph H . Lemma 4.2.1. The associated simplicial complex 𝐾 of a maximum edge hypergraph H is the standard (π‘š βˆ’ 1)-simplex. Proof. Recall from Definition 2.3.1 that 𝐾 is obtained from H by adding all of the subedges of edges in H . However, all of the subedges of a maximum edge hypergraph are the subedges of 𝑒, its maximum edge. The simplex associated to 𝑒 is of dimension π‘š βˆ’ 1 since 𝑒 has π‘š vertices. The 52 only other simplices in 𝐾 are the faces of 𝑒, so 𝐾 is an (π‘š βˆ’ 1)-simplex, consisting of πœŽπ‘’ and its subsets. β–‘ Since the homology of the standard (π‘š βˆ’ 1)-simplex is well documented [18], we have the following corollary based on Lemma 2.2.3, which says that the barycentric subdivision 𝑇 has the same homology as the associated simplicial complex 𝐾. Corollary 4.2.2. Let H be a maximum edge hypergraph, with associated simplicial complex 𝐾 and barycentric subdivision 𝑇. The homology of 𝐾, and hence of 𝑇 is ο£±  Z when 𝑛 = 0   ο£² 2Z  𝐻𝑛 (𝐾) = 𝐻𝑛 (𝑇) = (4.1)   0  else. ο£³ We will substitute the preceding corollary into the long exact sequence to get the following theorem that relates the relative barycentric homology of the hypergraph H to the homology of its missing subcomplex 𝑆. In high dimensions, this is an isomorphism. Theorem 4.2.3. In high dimensions (𝑛 β‰₯ 2), the relative barycentric homology of a maximum edge hypergraph H depends only on the (𝑛 βˆ’ 1)-dimensional homology of the missing subcomplex 𝑆: βˆ€π‘› β‰₯ 2, π»π‘›π‘Ÿπ‘’π‘™ (H )  π»π‘›βˆ’1 (𝑆). Proof. This theorem follows from the long exact sequence: ... 𝐻𝑛 (𝑇) π»π‘›π‘Ÿπ‘’π‘™ (H ) π»π‘›βˆ’1 (𝑆) π»π‘›βˆ’1 (𝑇) ... 0 0 According to Corollary 4.2.2, this part of the long exact sequence can be written with zeros for 𝐻𝑛 (𝑇) and π»π‘›βˆ’1 (𝑇), since 𝑛 β‰₯ 2. This makes the sequence 0 β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) β†’ 0, which implies, by exactness, that π»π‘›π‘Ÿπ‘’π‘™ (H )  π»π‘›βˆ’1 (𝑆). β–‘ 53 Although there is not as nice of a theorem in low dimensions, substituting Corollary 4.2.2 into the long exact sequence can still be fruitful. This next corollary yields an exact sequence that will aid in studying the relative barycentric homology in dimensions 0 and 1. Corollary 4.2.4. If H is a maximum edge hypergraph, then the following is an exact sequence: 𝐻1 (𝑇) 𝐻1π‘Ÿπ‘’π‘™ (H ) 𝐻0 (𝑆) 𝐻0 (𝑇) 𝐻0π‘Ÿπ‘’π‘™ (H ) 0. Z 0 2Z Z Proof. The first 0 and the 2Z come from substituting Corollary 4.2.2 into the long exact sequence, which already terminates in a 0 after 𝐻0π‘Ÿπ‘’π‘™ (H ). β–‘ Next, we will go through a few examples utilizing Theorem 4.2.3 and Corollary 4.2.4. We have already done the first example, which is of the hypergraph H = {𝐴𝐡𝐢}. A picture of H , 𝑇, and 𝑆 can be found in Figure 2.9. Here, 𝑆 is homotopic to a 1-sphere, and so ο£±  Z 𝑛 = 0, 1   ο£² 2Z  𝐻𝑛 (𝑆) =   0  else. ο£³ Z Theorem 4.2.3 then gives that 𝐻2π‘Ÿπ‘’π‘™ (H )  𝐻1 (𝑆) = 2Z , and Corollary 4.2.4 is now 𝐻1 (𝑇) 𝐻1π‘Ÿπ‘’π‘™ (H ) 𝐻0 (𝑆) 𝐻0 (𝑇) 𝐻0π‘Ÿπ‘’π‘™ (H ) 0. Z Z 0 2Z 2Z Z Z Since the map 2Z β†’ 2Z is induced by 𝑆 βŠ‚ 𝑇, it is the identity map, leaving (by exactness) 𝐻1π‘Ÿπ‘’π‘™ (H )  𝐻0π‘Ÿπ‘’π‘™ (H ) = 0. Therefore, ο£±  Z 𝑛=2   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘™ (H ) =   0  else. ο£³ Another example is given in Figure 4.1. This hypergraph is H = {𝐴𝐡𝐢, 𝐴𝐡, 𝐢}. Its barycentric subdivision 𝑇 is shown on the right and the missing subcomplex 𝑆 is highlighted. Notice that 𝑆 54 Figure 4.1 A hypergraph H with computation of 𝐻 π‘Ÿπ‘’π‘™ (H ). Z Z is two line segments and so 𝐻0 (𝑆) = 2Z βŠ• 2Z , and it has no homology in other dimensions. By Theorem 4.2.3, π»π‘›π‘Ÿπ‘’π‘™ (H ) = 0 for all 𝑛 β‰₯ 2. In this case, the exact sequence from Corollary 4.2.4 reads as follows: 𝐻1 (𝑇) 𝐻1π‘Ÿπ‘’π‘™ (H ) 𝐻0 (𝑆) 𝐻0 (𝑇) 𝐻0π‘Ÿπ‘’π‘™ (H ) 0. Z Z Z 0 2Z βŠ• 2Z 2Z Z Both path components of 𝑆 (each represented by a 2Z ) lie in the same path component of 𝑇, and Z Z Z Z so the map 2Z βŠ• 2Z β†’ 2Z is surjective with a rank one kernel. By exactness then, 𝐻1π‘Ÿπ‘’π‘™ (H ) = 2Z and 𝐻0π‘Ÿπ‘’π‘™ (H ) = 0. Thus, ο£±  Z 𝑛=1   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘™ (H ) =   0  else. ο£³ 4.2.2 Interpretations For the remainder of this section, we will give interpretative results on the relative barycentric homology. These results will allow us to utilize relative barycentric homology to glean information about the structure of the hypergraph itself, thus making these tools potentially useful for data analysis. There are interpretative results in dimensions 0, 1, π‘š βˆ’ 2 and π‘š βˆ’ 1, where π‘š is the cardinality of the maximum edge (and hence also the vertex set). A condition is also given that 55 causes a hypergraph to have no relative barycentric homology in any dimension. The first result, however, classifies the relative barycentric homology of a hypergraph that only has one edge. Theorem 4.2.5. Let H be a hypergraph with one edge, 𝑒. Let |𝑒| = π‘š. Then ο£±  Z when 𝑛 = π‘š βˆ’ 1   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘™ (H ) =   0  else. ο£³ Proof. Since a one edge hypergraph is a maximum edge hypergraph, it follows from Lemma 4.2.1 that 𝑇 is homotopic to an (π‘š βˆ’ 1)-disk. Let us construct 𝑆. It is the subcomplex of 𝑇 given by all simplices whose vertices do not represent edges in the hypergraph H . Since the only edge in H is 𝑒, 𝑆 = 𝑇 \ 𝑆𝑑 (𝑣 πœŽπ‘’ ), where 𝑆𝑑 (𝑣 πœŽπ‘’ ) is the star of the vertex 𝑣 πœŽπ‘’ in 𝑇 (Definition 2.2.9). Since πœŽπ‘’ is the only (π‘š βˆ’ 1)-simplex in 𝐾, any of the (π‘š βˆ’ 1)-simplices of 𝑇 must contain the vertex 𝑣 πœŽπ‘’ , and so 𝑆 is constrained to simplices of dimension at most π‘š βˆ’ 2 that do not contain 𝑣 πœŽπ‘’ . Thus, as can be seen for π‘š = 3 in Figure 2.9, 𝑆 is the boundary of 𝑇. The boundary of an (π‘š βˆ’ 1)-disk is an (π‘š βˆ’ 2)-sphere, and, therefore, (𝑇, 𝑆) is homotopic to an (π‘š βˆ’ 1)-sphere. Recall π»π‘›π‘Ÿπ‘’π‘™ (H ) = 𝐻𝑛 (𝑇, 𝑆) by definition, and from the reduced homology of the (π‘š βˆ’1)-sphere [18]. ο£±  Z when 𝑛 = π‘š βˆ’ 1   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘™ (H ) =   0  else. ο£³ β–‘ For an example of this theorem, see Figure 2.9, where we computed the relative barycentric homology of H = {𝐴𝐡𝐢}, a one edge hypergraph. The next theorem says that the only way for a maximum edge hypergraph to have 𝐻0π‘Ÿπ‘’π‘™ (H ) β‰  0 is if that hypergraph is a simplicial complex, combining with Corollary 4.2.2 for a sufficient and necessary condition to get a nontrivial 𝐻0π‘Ÿπ‘’π‘™ (H ). Theorem 4.2.6. A maximum edge hypergraph H has nontrivial homology in dimension zero if and only if it is a simplicial complex, i.e. there are no missing subedges and 𝑆 is empty. In this case, Z 𝐻0π‘Ÿπ‘’π‘™ (H ) = 2Z . 56 Proof. Suppose that there are no missing subedges in the hypergraph H . This means 𝑆 is empty and thus, 𝐻0 (𝑆) = 0. Substitute that into Corollary 4.2.4 to get the following exact sequence: Z 0β†’ β†’ 𝐻0π‘Ÿπ‘’π‘™ (H ) β†’ 0. 2Z Z This implies that 𝐻0π‘Ÿπ‘’π‘™ (H ) = 2Z as required. Next suppose the hypergraph H is not a simplicial complex. Then there are some missing Z subedges and so 𝑆 is not empty. The map from 𝐻0 (𝑆) β†’ 2Z from Corollary 4.2.4 is surjective then, since any representative in 𝐻0 (𝑆) of a path component in 𝑆 will also represent the path component Z of 𝑇, and thus be in 𝐻0 (𝑇). Since the generator of 2Z is in the image of the map 𝐻0 (𝑆) β†’ 𝐻0 (𝑇), Z it is in the kernel of the map 2Z β†’ 𝐻0π‘Ÿπ‘’π‘™ (H ). That map then factors through 0, leaving an exact sequence 0 β†’ 𝐻0π‘Ÿπ‘’π‘™ (H ) β†’ 0, proving that H not simplicial implies 𝐻0π‘Ÿπ‘’π‘™ (H ) = 0. β–‘ Because a maximum edge hypergraph that has a nontrivial 𝐻0π‘Ÿπ‘’π‘™ must be a simplicial complex, Corollary 4.2.2 says that it will have no other nontrivial homology groups. Therefore, a maximum edge hypergraph cannot have both a 0-dimensional homology cycle and a homology cycle in any higher dimension. The next result heavily utilizes Corollary 4.2.4 and relates π›½π‘Ÿπ‘’π‘™ 1 (H ), the rank of the first dimensional relative barycentric homology group, to the number of path components of the missing subcomplex 𝑆. Theorem 4.2.7. Let H be a maximum edge hypergraph with missing subcomplex 𝑆. If H is a simplicial complex, 𝐻1π‘Ÿπ‘’π‘™ (H ) = 0. If H is not a simplicial complex, then π›½π‘Ÿπ‘’π‘™ 1 (H ) = 𝛽0 (𝑆) βˆ’ 1 = 𝛽e0 (𝑆) Proof. Suppose that the hypergraph H is a simplicial complex. This means 𝑆 is empty, and so 𝐻0 (𝑆) = 0. Substitute that into Corollary 4.2.4 to get the exact sequence 0 β†’ 𝐻1π‘Ÿπ‘’π‘™ (H ) β†’ 0, implying that 𝐻1π‘Ÿπ‘’π‘™ (H ) = 0. Z Next, assume 𝑆 is nontrivial. Then the map 𝐻0 (𝑆) β†’ 2Z from Corollary 4.2.4 relates the path components of 𝑆 to the single path component of 𝑇 and is surjective. This means that the kernel has rank 𝛽0 (𝑆) βˆ’ 1, by rank-nullity. Since 0 β†’ 𝐻1π‘Ÿπ‘’π‘™ (H ) β†’ 𝐻0 (𝑆) is exact, 𝐻1π‘Ÿπ‘’π‘™ (H ) β†’ 𝐻0 (𝑆) 57 Figure 4.2 A hypergraph H used as an example for Theorem 4.2.7. Z is injective. So the rank of 𝐻1π‘Ÿπ‘’π‘™ (H ) is equal to the rank of the kernel of the map 𝐻0 (𝑆) β†’ 2Z . 1 (H ) = 𝛽0 (𝑆) βˆ’ 1, proving the theorem. Therefore, π›½π‘Ÿπ‘’π‘™ β–‘ We have already computed two examples of the relative barycentric homology in dimension 1. In the one edge hypergraph of Figure 2.9, 𝑆 only has one path component, and hence, π›½π‘Ÿπ‘’π‘™ 1 (H ) = 0. The hypergraph in Figure 4.1 has a missing subcomplex 𝑆 with two path components, making 1 (H ) = 1. In Figure 4.2, 𝑆 has three path components, which leads to 𝛽1 (H ) = 2. π›½π‘Ÿπ‘’π‘™ π‘Ÿπ‘’π‘™ Moving towards higher dimensions now, recall that the relative barycentric homology of the single edge hypergraph is concentrated in dimension π‘š βˆ’ 1 (Theorem 4.2.5). This is actually an if and only if statement, of which the next theorem proves the other half. The only way for a maximum edge hypergraph with π‘š vertices in the maximum edge to have homology in dimension π‘š βˆ’ 1 is if the maximum edge is the only edge in the hypergraph. Theorem 4.2.8. Given a maximum edge hypergraph H , ο£±  |H | = 1  ο£²1   π›½π‘Ÿπ‘’π‘™ π‘šβˆ’1 (H ) =   0  else. ο£³ Proof. The |H | = 1 part of the statement follows from Theorem 4.2.5. Now let |H | β‰₯ 2, and let 𝑓 be an edge that is not the maximum edge. Recall from Theorem 4.2.3 that π›½π‘Ÿπ‘’π‘™ π‘šβˆ’1 (H ) = π›½π‘šβˆ’2 (𝑆). 58 Recall from the proof of Theorem 4.2.5 that 𝑆 is a subspace of the boundary of 𝑇. This boundary is an (π‘š βˆ’ 2)-sphere. However, since 𝑓 is an edge in the hypergraph, any simplices containing the vertex representing 𝑓 are not part of 𝑆. Since 𝑆 is not the entire (π‘š βˆ’ 2)-sphere, there cannot be any (π‘š βˆ’ 2)-homology. Thus π›½π‘Ÿπ‘’π‘™ π‘šβˆ’1 (H ) = π›½π‘šβˆ’2 (𝑆) = 0, as was to be shown. β–‘ A hypergraph can have relative barycentric homology in dimension zero if and only if it is a simplicial complex, and in dimension π‘šβˆ’1 if and only if it is only a single edge. This way of relating the 0th dimensional homology and the (π‘š βˆ’ 1)-dimensional homology of an (π‘š βˆ’ 1)-dimensional simplicial complex is reminiscent of some of the duality theorems from algebraic topology like Poincare, Lefschetz, or Alexander Duality (see [24, 18]). The next theorem is another indicator that there may be a duality at work, because it gives a way of relating the (π‘š βˆ’ 2)-dimensional homology to the homology in dimension 1. The pairing of dimensions that add up to the dimension of the simplicial complex is a staple of the aforementioned duality theories. Recall from Theorem 4.2.7 that the relative barycentric homology in dimension 1 of a maximum edge hypergraph was related to the number of path components in the missing subcomplex. The next result relates the relative barycentric homology in dimension π‘š βˆ’ 2 to the number of path components in the subcomplex of 𝑇 generated by the subedges that are present in the hypergraph, which is a complementary notion to the missing subcomplex. Theorem 4.2.9. Given a maximal edge hypergraph, H , with π‘š > 3, let H β€² = H \ {𝑒} be the hypergraph after removing the maximum edge. Recall from Definition 2.1.12 that Ξ“(H β€²) is the number of fence components of H β€². Then ο£± H β€² is empty,   ο£²0   π›½π‘Ÿπ‘’π‘™ π‘šβˆ’2 (H ) =  Ξ“(H β€²) βˆ’ 1    else. ο£³ Proof. From Theorem 4.2.8, π»π‘šβˆ’2 (𝑆) = 0 as long as there are any present subedges in the β€² π‘šβˆ’2 (H ) = Ξ“(H ) = 0 by Corollary 4.2.5, taking care of the hypergraph. If there are not, then π›½π‘Ÿπ‘’π‘™ first case. Now, we can assume that H β€² is not empty for the remainder of the proof. 59 Figure 4.3 Hypergraphs used as examples for Theorem 4.2.9. Since H is a maximum edge hypergraph, its associated simplicial complex 𝐾 is the standard (π‘š βˆ’ 1)-simplex (Lemma 4.2.1). Recall from Theorem 4.2.3 that π»π‘šβˆ’2 π‘Ÿπ‘’π‘™ (H )  𝐻 π‘šβˆ’3 (𝑆), where 𝑆 is the missing subcomplex (Definition 2.3.4). Note that, geometrically, 𝑆 is entirely contained in the boundary of the barycentric subdivision 𝑇 (since the only interior point represents the maximal edge), and this boundary is homeomorphic to Sπ‘šβˆ’2 , the (π‘š βˆ’ 2) dimensional sphere. In particular, an application of the long exact sequence of the pair (πœ•π‘‡, 𝑆) of topological spaces leads to the following exact sequence: π»π‘šβˆ’2 (𝑆) π»π‘šβˆ’2 (πœ•π‘‡) π»π‘šβˆ’2 (πœ•π‘‡, 𝑆) π»π‘šβˆ’3 (𝑆) π»π‘šβˆ’3 (πœ•π‘‡) 0 π»π‘šβˆ’2 (Sπ‘šβˆ’2 ) π»π‘šβˆ’3 (𝑆 π‘šβˆ’2 ) Z 2Z 0 Because H β€² is not empty, π»π‘šβˆ’2 (𝑆) = 0. Thus, π›½π‘šβˆ’2 (πœ•π‘‡, 𝑆) βˆ’ 1 = π›½π‘šβˆ’3 (𝑆) by the exactness of the above sequence. Furthermore, π›½π‘šβˆ’3 (𝑆) = π›½π‘Ÿπ‘’π‘™ π‘šβˆ’2 (H ) by Theorem 4.2.3. Thus we get the following string of equalities: π›½π‘šβˆ’2 (πœ•π‘‡, 𝑆) βˆ’ 1 = π›½π‘šβˆ’3 (𝑆) = π›½π‘Ÿπ‘’π‘™ π‘šβˆ’2 (H ). So, to prove the theorem, we need to show that that π›½π‘šβˆ’2 (πœ•π‘‡, 𝑆) is the number of fence components of H β€², Ξ“(H β€²) which was already seen (Theorem 3.2.4) to be the number of path components in the restricted barycentric subdivision 𝑅′. Recall from Definition 2.3.2 that the vertices in 𝑅′ are 𝑣 πœŽπ‘’β€² , where 𝑒′ is a proper subedge in H (and hence an edge in H β€²). This means 𝑅′ will be entirely 60 contained in πœ•π‘‡. We prove π›½π‘šβˆ’2 (πœ•π‘‡, 𝑆) = Ξ“(H β€²) = 𝛽0 (𝑅′) by showing that each path component of 𝑅′ gives rise to an (π‘š βˆ’ 2)-dimensional homology class in π»π‘šβˆ’2 (πœ•π‘‡, 𝑆). We start by showing the (π‘š βˆ’ 2)-faces of the star (Definition 2.2.9) of a path component of 𝑅′ comprise an (π‘š βˆ’ 2)-cycle in πΆπ‘šβˆ’2 (πœ•π‘‡, 𝑆), the chain group. To see this, it needs to be shown that its boundary is contained in 𝑆. However, the boundary of the star is the link, and the link must be entirely contained in 𝑆, as shown next. If there was a vertex in the link that was not in 𝑆, then that vertex would have to represent an existing subedge from the hypergraph, but then it would be part of the path component in question, as it would be connected to the path component via the star. So, the link, and hence boundary, of a path component in 𝑅′ is in 𝑆. Thus, any fence component of the hypergraph H β€² gives rise to an (π‘š βˆ’ 2)-cycle in πΆπ‘šβˆ’2 (πœ•π‘‡, 𝑆), i.e. is in the kernel of πΆπ‘šβˆ’2 (πœ•π‘‡, 𝑆). Since there are no (π‘š βˆ’ 1)-simplices in πœ•π‘‡, the image of πΆπ‘šβˆ’1 (πœ•π‘‡, 𝑆) via πœ•π‘šβˆ’1 is empty. Thus, by the definition of homology, any fence component of the hypergraph H β€² gives rise to an (π‘š βˆ’ 2)-cycle in π»π‘šβˆ’2 (πœ•π‘‡, 𝑆). Therefore, the number of fence components of H is equal to π›½π‘šβˆ’2 (πœ•π‘‡, 𝑆), which is equal to π›½π‘šβˆ’3 (𝑆) + 1, which is equal to π›½π‘Ÿπ‘’π‘™π‘šβˆ’2 (H ) + 1, proving the theorem. β–‘ For two examples of the π‘š = 4 case, see Figure 4.3. Each of these hypergraphs has π›½π‘Ÿπ‘’π‘™ 2 = 1 since they have two fence components after removing the maximum edge. Theorem 4.2.9 is useful because it is giving information about the edges that are actually present in the hypergraph, while the result in dimension 1 is giving information about the missing subedges. This complementary relationship between the results in dimension 1 and π‘šβˆ’2 suggests a duality in the relative barycentric homology. For a maximum edge hypergraph with π‘š > 3, combining Theorem 4.2.3 and Theorem 4.2.9 creates an easy way to study the subedges of the hypergraph by building only 𝑆, and taking its (π‘š βˆ’ 3)-dimensional homology, like in the proof of the latter theorem. Table 4.1 displays π›½π‘Ÿπ‘’π‘™ (H ) for the different dimensions and types of maximum edge hypergraphs that have been discussed thus far. In this table, π‘š is the number of vertices in the hypergraph, Ξ“ is the number of fence components, Supp(H ) is the supplement of H (Definition 2.1.11), and H β€² is as in the previous theorem. The final theorem in this section gives a condition on maximum edge 61 Dimension H Simplicial H One Edge H Other 0 (H ) π›½π‘Ÿπ‘’π‘™ 1 0 0 1 (H ) π›½π‘Ÿπ‘’π‘™ 0 0 Ξ“(Supp(H )) βˆ’ 1 π‘šβˆ’2 (H ) π›½π‘Ÿπ‘’π‘™ 0 0 Ξ“(H β€²) βˆ’ 1 π‘šβˆ’1 (H ) π›½π‘Ÿπ‘’π‘™ 0 1 0 Table 4.1 with π›½π‘Ÿπ‘’π‘™ (H ) for Maximum Edge Hypergraphs, π‘š is the number of vertices in the hypergraph, Ξ“ is its number of fence components. hypergraphs that would cause H to have no nontrivial relative barycentric homology groups. This will happen when the missing subcomplex 𝑆 turns out to be contractible (Definition 2.2.12). Theorem 4.2.10. Let H be a maximum edge hypergraph such that 𝑆 is nonempty and contractible. 𝑛 (H ) = 0 for all 𝑛. Then π›½π‘Ÿπ‘’π‘™ Proof. Since 𝑆 is contractible, ο£±  Z when 𝑛 = 0   ο£² 2Z  𝐻𝑛 (𝑆) =    0 else.  ο£³ Z Theorem 4.2.3 gives that π›½π‘Ÿπ‘’π‘™ 𝑛 (H ) = 0 for all 𝑛 β‰₯ 2. Now, plug in 𝐻0 (𝑆) = 2Z to the exact sequence from Corollary 4.2.4 to get 𝐻1 (𝑇) 𝐻1π‘Ÿπ‘’π‘™ (H ) 𝐻0 (𝑆) 𝐻0 (𝑇) 𝐻0π‘Ÿπ‘’π‘™ (H ) 0. Z Z 0 2Z 2Z Z Z The map 2Z β†’ 2Z is the identity isomorphism since the path component of 𝑆 is included into the path component of 𝑇. Therefore, 𝐻1π‘Ÿπ‘’π‘™ (H ) = 0 = 𝐻0π‘Ÿπ‘’π‘™ (H ). 𝑛 (H ) = 0. Thus, for all 𝑛, π›½π‘Ÿπ‘’π‘™ β–‘ Figure 4.4 gives an example of a hypergraph that has a contractible 𝑆. This hypergraph is H = {𝐴𝐡𝐢, 𝐴𝐡, 𝐴}. In the figure, we can see that 𝑆 is one connected line segment, and so it is contractible. Therefore, by Theorem 4.2.10, π»π‘›π‘Ÿπ‘’π‘™ (H ) = 0 for all 𝑛. Even if H is not a maximum edge hypergraph, the condition of contractibility of 𝑆 eases the computation of the 62 Figure 4.4 A hypergraph H used as an example for Theorem 4.2.10. relative barycentric homology, which is the result of Theorem 4.3.4 in the next section. That theorem, and the rest of the results therein, generalizes the results on the relative barycentric homology of maximum edge hypergraphs of this section to hypergraphs that are not necessarily maximum edge. 4.3 Results on General Hypergraphs One of the first results we did for the restricted barycentric homology was Proposition 3.2.1, saying that the restricted barycentric homology of a hypergraph that happens to be a simplicial complex agrees with its simplicial homology. This is true for the relative baryencetric homology as well, as stated in the first result of this section. This is largely due to the fact that the missing subcomplex, 𝑆, will be empty in this case. Proposition 4.3.1. Let H be a hypergraph that is the same as 𝐾, its associated simplicial complex. Then for all 𝑛, π»π‘›π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝐾). Proof. Since H = 𝐾 as sets, there are no missing subedges of H , and 𝑆, the missing subcomplex, is empty. Recall that π»π‘›π‘Ÿπ‘’π‘™ (H ) was defined as 𝐻𝑛 (𝑇, 𝑆). Since 𝑆 is empty, 𝐻𝑛 (𝑇, 𝑆)  𝐻𝑛 (𝑇) for all 𝑛. By definition of barycentric subdivision, 𝐻𝑛 (𝑇)  𝐻𝑛 (𝐾) for all 𝑛. Thus for all 𝑛, π»π‘›π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝐾). β–‘ A standard result of simplicial homology is that different path components do not interact during 63 Figure 4.5 A hypergraph H with multiple connected components. the homology computation, and so the simplicial homology of a simplicial complex with multiple path components is the direct sum of the simplicial homology of its path components. This turns out to be true for the relative barycentric homology as well. Compare this to Corollary 3.2.5, which wrote the restricted barycentric homology as the direct sum of the homology of its fence components. For the relative barycentric homology, we will go back to the standard definition of hypergraph connected components from Definition 2.1.9. Proposition 4.3.2. Let H be a hypergraph, with connected components H1 , H2 , . . . , Hπ‘˜ . Then Ê π‘˜ π»π‘›π‘Ÿπ‘’π‘™ (H ) = π»π‘›π‘Ÿπ‘’π‘™ (H𝑖 ). 𝑖=1 Proof. Let 𝑇𝑖 and 𝑆𝑖 be the barycentric subdivision and missing subcomplex corresponding to each component H𝑖 . Let βŠ” be used to denote the disjoint union of two spaces. The proof is the following string of isomorphisms: Ê π‘˜ ΓŠπ‘˜ π‘˜ π‘˜ π»π‘›π‘Ÿπ‘’π‘™ (H𝑖 )  𝐻𝑛 (𝑇𝑖 , 𝑆𝑖 )  𝐻𝑛 (βŠ”π‘–=1 𝑇𝑖 , βŠ”π‘–=1 𝑆𝑖 )  𝐻𝑛 (𝑇, 𝑆)  π»π‘›π‘Ÿπ‘’π‘™ (H ). 𝑖=1 𝑖=1 Here the first and last isomorphisms are the definition of the relative barycentric homology from Definition 2.2.13, and the middle two isomorphisms are drawn from the fact that the result holds for simplicial homology, which can be found in [18]. β–‘ Although the proof above uses properties of simplicial homology, one could also have ap- proached that proof with the Mayer-Vietoris sequence from Theorem 4.1.1 and inducted on the number of path components, since distinct path components have empty intersections. 64 Figure 4.6 A non maximum edge hypergraph H with contractible 𝐾. The hypergraph in Figure 4.5 has two connected components. By the theorem, it would suffice to compute the relative barycentric homology of each and then the relative barycentric homoloy of H would be the direct sum. Each component is a maximum edge hypergraph, so we could use the results of the last section to do this computation more easily than if we started with the barycentric subdivision of all of H at once. 4.3.1 Manipulating the Long Exact Sequence of a Pair In the last section, we manipulated the long exact sequence of homology groups of a pair of topological spaces as in Definition 2.2.6. As we noted there, in the case of the relative barycentric homology of hypergraphs, it is as follows: . . . β†’ 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) β†’ . . . This sequence was used in the last section in the case where H was a maximum edge hypergraph, which meant 𝑇 was homotopic to a disk. Since the homology of a disk is well known, this allowed us to easily study the relative barycentric homology of a maximum edge hypergraph, as in Theorem 4.2.3 and Corollary 4.2.4. Theorem 4.2.10 gave a condition where, if 𝑆 is contractible and H is a maximum edge hypergraph, 𝐻 π‘Ÿπ‘’π‘™ (H ) = 0 for all 𝑛. However, the long exact sequence above is useful in more cases besides just when H is a maximum edge hypergraph. The next few results give more situations where the long exact sequence is useful for studying the relative barycentric homology. Corollary 4.2.2 gave us the homology for the barycentric subdivision of a maximum edge 65 hypergraph, and that allowed us to utilize the long exact sequence, as in Theorem 4.2.3 and other results. Any hypergraph whose barycentric subdivision has the same homology groups as a disk, i.e. is contractible, will allow us to do the same thing. See, for example, Figure 4.6 where the hypergraph H has a contractible associated simplicial complex 𝐾 even though it is not a maximum edge hypergraph. Since the homology groups have not changed, we also have not fundamentally changed the result (see Theorem 4.2.3 and Corollary 4.2.4), just extended it to a wider class of hypergraphs. The following theorem now holds for any hypergraph whose associated simplicial complex is contractible. Theorem 4.3.3. Let H be a hypergraph such that its associated simplicial complex 𝐾 is contractible. Then βˆ€π‘› β‰₯ 2, π»π‘›π‘Ÿπ‘’π‘™ (H )  π»π‘›βˆ’1 (𝑆), and the following is an exact sequence: 𝐻1 (𝑇) 𝐻1π‘Ÿπ‘’π‘™ (H ) 𝐻0 (𝑆) 𝐻0 (𝑇) 𝐻0π‘Ÿπ‘’π‘™ (H ) 0 Z 0 2Z Proof. This result (and proof) is identical to the one in Theorem 4.2.3 and Corollary 4.2.4. Since 𝐾 is contractible, 𝑇 is also contractible, and so (by Definition 2.2.12) they have homology groups ο£±  Z when 𝑛 = 0   ο£² 2Z  𝐻𝑛 (𝐾)  𝐻𝑛 (𝑇)  (4.2)    0 else.  ο£³ Plugging these groups into the long exact sequence of the pair (𝑇, 𝑆) gives the result. β–‘ Even if H is not a maximum edge hypergraph as in Theorem 4.2.10, using the long exact sequence when 𝑆 is contractible can simplify the calculation of the relative barycentric homology. The case where 𝑆 is contractible is even more enlightening than when 𝐾 is contractible, as it was above. 66 Theorem 4.3.4. Let H be a hypergraph such that its missing subcomplex, 𝑆, is contractible. Then βˆ€π‘› β‰₯ 1, π»π‘›π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝑇)  𝐻𝑛 (𝐾), and π›½π‘Ÿπ‘’π‘™ 0 (H ) = 𝛽0 (𝑇) βˆ’ 1 = 𝛽0 (𝐾) βˆ’ 1. Proof. Since 𝑆 is contractible, its homology groups are as follows: ο£±  Z when 𝑛 = 0   ο£² 2Z  𝐻𝑛 (𝑆)  (4.3)    0 else.  ο£³ Plug these into the long exact sequence of a pair . . . β†’ 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) β†’ π»π‘›βˆ’1 (𝑇) β†’ . . . to get an exact sequence 𝐻𝑛 (𝑆) 𝐻𝑛 (𝑇) π»π‘›π‘Ÿπ‘’π‘™ (H ) π»π‘›βˆ’1 (𝑆) 0 0 for dimensions 𝑛 β‰₯ 2. This shows that for 𝑛 β‰₯ 2, π»π‘›π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝑇). We must consider low Z dimensions separately since 𝐻0 (𝑆) = 2Z . The end of the exact sequence then reads Z 0 β†’ 𝐻1 (𝑇) β†’ 𝐻1π‘Ÿπ‘’π‘™ (H ) β†’ β†’ 𝐻0 (𝑇) β†’ 𝐻0π‘Ÿπ‘’π‘™ (H ) β†’ 0. 2Z Z The map 2Z β†’ 𝐻0 (𝑇) is rank one since the representative of the path componenent in 𝑆 is also a Z representative of the path component in 𝑇. Thus by exactness, the map 𝐻1π‘Ÿπ‘’π‘™ (H ) β†’ 2Z is the zero map. So, by exactness, 𝐻1 (𝑇)  𝐻1π‘Ÿπ‘’π‘™ (H ) and 𝛽0 (𝑇) βˆ’ 1 = π›½π‘Ÿπ‘’π‘™ 0 (H ), as was to be shown. The last equality in each part of the theorem are given by the equivalence of the simplicial homology of 𝑇 and 𝐾, from Lemma 2.2.3. β–‘ Figure 4.7 shows a hypergraph H where the last theorem can be applied to compute the relative barycentric homology. The missing subcomplex 𝑆 is highlighted; note that it is contractible. Therefore by the theorem, π›½π‘Ÿπ‘’π‘™ 1 (H ) = 1 since 𝛽1 (𝑇) = 1, and 𝛽0 (H ) = 0 because 𝛽0 (𝑇) = 1. π‘Ÿπ‘’π‘™ 67 Figure 4.7 A non maximum edge hypergraph H with contractible 𝑆. It is also possible to factor long exact sequences via maps, and not just groups. One example of this is when the map 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) is zero for all 𝑛 > 0. Since, as topological spaces, 𝑆 βŠ‚ 𝑇, the map 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) could only be zero in dimension 0 if 𝑆 is empty, but there is a rather large class of hypergraphs that satisfy this condition for 𝑛 > 0. We will describe what this condition says about the hypergraph, its missing subedges and its associated simplicial complex. What the expression 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) = 0 means is that none of the (higher than 0-dimensional) homology in 𝑆 survives the inclusion into 𝑇, i.e. that any homology cycle in 𝑆 is a boundary in 𝑇. Figure 4.8 has an example of a hypergraph that does not satisfy this condition. The chain of 1-simplices {𝐸, 𝐢𝐸, 𝐢, 𝐡𝐢, 𝐡, 𝐡𝐸 } is a homology generator in both 𝑆 and 𝑇, so the map 𝐻1 (𝑆) β†’ 𝐻1 (𝑇) is not the zero map. Hypergraphs that do satisfy this condition can decompose their relative barycentric homology as a direct sum of the homology of 𝑇 and the homology of 𝑆, in the following way. Theorem 4.3.5. Suppose that H is a hypergraph such that the map on homology, 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇), induced by the inclusion 𝑆 β†’ 𝑇, is the zero map for all 𝑛 > 0. Then, for all 𝑛 β‰₯ 2, Ê π»π‘›π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝑇) π»π‘›βˆ’1 (𝑆). Proof. Since the map 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) is the zero map for all 𝑛 > 0, the long exact sequence factors into short exact sequences that can be split up between the 𝑆 and 𝑇 step: 0 β†’ 𝐻𝑛 (𝑇) β†’ 𝐻 π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) β†’ 0 68 Figure 4.8 A hypergraph for which the map 𝐻1 (𝑆) β†’ 𝐻1 (𝐾) is not zero. Z is exact when 𝑛 β‰₯ 2. Because the homology groups in question are vector spaces over the field 2Z , the sequence splits, and for all 𝑛 β‰₯ 2, Ê π»π‘›π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝑇) π»π‘›βˆ’1 (𝑆), completing the proof. β–‘ Often, the sequence will split even if the coefficient group is not a field. This will be true, if, for example, the group π»π‘›βˆ’1 (𝑆) is a free module. A slight modification of the hypergraph in Figure 4.8 is shown in Figure 4.9. Notice the difference is that now, 𝐸 is an edge in the hypergraph, and so the map 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝐾) is zero for all 𝑛 β‰  0. Even though there still is a nontrivial homology class in 𝐻1 (𝑆), it is homologically trivial when included into 𝑇, because it is the boundary of the 2-simplices it surrounds. Thus the thereom applies, and π›½π‘Ÿπ‘’π‘™2 (H ) = 𝛽1 (𝑆) + 𝛽2 (𝐾) = 1. This theorem is useful because instead of having a relative homology, we now have the direct sum of two nonrelative homologies that are easier to compute than the relative homology. Moreover, there is a large class of hypergraphs for which this decomposition holds. One type of hypergraph to which Theorem 4.3.5 always applies, and for which we would not even need to construct 𝑆 to check the condition, is classified in the next theorem. 69 Γ‰ Figure 4.9 A hypergraph for which π»π‘›π‘Ÿπ‘’π‘™ (H ) = 𝐻𝑛 (𝐾) π»π‘›βˆ’1 (𝑆). Theorem 4.3.6. Let H be a hypergraph such that its associated simplicial complex 𝐾 satisfies the following condition: π‘˜ βˆ‘οΈ For all 𝑛, for any πœŽπ‘– generating a class in 𝐻𝑛 (𝐾), 𝑖=1 βˆƒ 𝑗 ∈ {1, 2, . . . , π‘˜ } such that 𝜎 𝑗 is a toplex in 𝐾. Then for H , 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) is 0 for all 𝑛 > 0, and the previous theorem applies to H . Proof. Suppose H is a hypergraph with 𝐾 satisfying the condition given in the theorem statement. We will approach the proof by contradiction: suppose that for some 𝑛 > 0, 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) is not Γπ‘˜ Í π‘˜  the zero map. Let 𝑖=1 πœŽπ‘– be in the image of the map from 𝐢𝑛 (𝑆) β†’ 𝐢𝑛 (𝑇) such that 𝑖=1 πœŽπ‘– is not homologous to 0 in 𝐻𝑛 (𝑇). Since the map 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) is generated by the inclusion map Γπ‘˜ Γπ‘˜ 𝑆 β†’ 𝑇, the preimage of 𝑖=1 πœŽπ‘– in 𝑇 is 𝑖=1 πœŽπ‘– in 𝑆. Therefore, each of the πœŽπ‘– represents a missing subedge in H . However, according to the condition given in the theorem statement, at least one of the πœŽπ‘– is a toplex in 𝐾. Toplexes in 𝐾 are exactly the same as toplexes in H , by definition of the associated simplicial complex (Definition 2.3.1). Thus, for some 𝑖, πœŽπ‘– is both a missing subedge of H and a present toplex in H . This is a contradiction. Thus, 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) = 0 for all 𝑛 > 0, and Theorem 4.3.5 can be applied to H . β–‘ At least for this section, we are finished manipulating the long exact sequence of a pair. This idea, and especially the map 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) will play a major role in computing the relative barycentric 70 homology in Section 5.2. We will use the long exact sequence to avoid computing a relative homology, instead using the linear algebra of the maps of the exact sequence for computation. 4.3.2 Classification of Relative Barycentric Homology for General Hypergraphs We will continue developing the relative barycentric homology with some classification theo- rems. The next theorem is the analog of Theorem 3.2.4 for relative barycentric homology. It relates the zeroth dimensional relative barycentric homology to the simplicial components (Definition 2.1.16). Theorem 4.3.7 (Zeroth Dimensional Relative Homology† ). Let H be a hypergraph. Then π›½π‘Ÿπ‘’π‘™ 0 equals the number of simplicial components of H . The proof will be given by induction on the number of connected components (Definition 2.1.9). The base case (H is connected) is written as a separate lemma, and was already proven for maximum edge hypergraphs in Theorem 4.2.6. Note that not every connected hypergraph is maximum edge, but the proofs are similar. † Let H be a connected hypergraph. Then π›½π‘Ÿπ‘’π‘™ Lemma 4.3.8. 0 ≀ 1, and 𝛽0 = 1 if and only if H π‘Ÿπ‘’π‘™ is a simplicial complex. Proof. First, note that since H is connected, its associated simplicial complex 𝐾 and barycentric subdivision 𝑇 are also connected. Since π»βˆ— (H ) B π»βˆ— (𝑇, 𝑆), recall the tail end of the long exact exact sequence of a pair of topological spaces: . . . β†’ 𝐻1 (𝑇, 𝑆) β†’ 𝐻0 (𝑆) β†’ 𝐻0 (𝑇) β†’ 𝐻0 (𝑇, 𝑆) β†’ 0. Z Because 𝑇 is connected, 𝐻0 (𝑇)) = 2Z . Noting that 𝐻0 (𝑇, 𝑆) maps to 0 in the exact sequence, everything (if anything) in 𝐻0 (𝑇, 𝑆) must be in its kernel. Thus by exactness, rk(𝐻0 (𝑇, 𝑆)) ≀ 1. Now let’s consider the exactness at the 𝐻0 (𝑇) step. Recall that rk(𝐻0 (𝑇) = 1, and so if the kernel of the map 𝐻0 (𝑇) β†’ 𝐻0 (𝑇, 𝑆) is rank 1, then 𝐻0 (𝑇, 𝑆) = 0 by exactness. That will happen exactly when the map 𝐻0 (𝑆) β†’ 𝐻0 (𝑇) has rank 1. 71 That map is the map on homology induced by the inclusion 𝑆 β†’ 𝑇. If 𝑆 is not empty, then 𝑆 includes nontrivially into 𝑇, and so the map on homology cannot be trivial. Thus as long as 𝑆 is nonempty, 𝐻0 (𝑆) β†’ 𝐻0 (𝑇) has rank 1, and therefore 𝐻0 (𝑇, 𝑆) = 0. Recall that with respect to the hypergraph, 𝑆 is the missing subcomplex, i.e. the subcomplex of 𝑇 generated by the simplices in 𝐾 that are not edges of H . So 𝑆 will be empty only when there are no missing subedges in H . A hypergraph with no missing subedges is a simplicial complex, completing the proof. β–‘ Proof of Theorem 4.3.7. The lemma will serve as the base case for the proof of the theorem. Next, suppose that the theorem is true for hypergraphs with π‘˜ βˆ’ 1 connected components. Let H be a hypergraph with π‘˜ connected components. WLOG, choose a connected component of H and call it H1 and its edge set 𝐸 1 . Let the rest of the hypergraph be H2 with edge set 𝐸 2 = 𝐸 \ 𝐸 1 . Since 𝐸 1 ∩ 𝐸 2 = βˆ…, the Mayer-Vietoris theorem for hypergraphs (Theorem 4.1.1) applies in this situation, and every term corresponding to the intersection is 0. This yields an isomorphism 𝐻0 (H1 ) βŠ• 𝐻0 (H2 )  𝐻0 (H ). By the induction hypothesis and the base case, each of the terms on the left has rank equal to its number of simplicial components. Since the map giving the isomorphism is induced by the inclusions of H1 and H2 into H , and will be the identity on homology generators (which are representatives of those simplicial components), 𝛽0 (H ) = 𝛽0 (H1 ) + 𝛽0 (H2 ) will be the number of simplicial components, finishing the proof. β–‘ As an example, consider again the hypergraph in Figure 4.5. This hypergraph has two connected components. The component with the edge 𝐴𝐡𝐢 is not simplicial, but the component with the edge 𝐷𝐸 𝐹 is simplicial. Therefore π›½π‘Ÿπ‘’π‘™0 (H ) = 1. Throughout the next theorem, we will use 𝐻 (𝑒𝑖 ) π‘Ÿπ‘’π‘™ to denote the relative barycentric homology of the hypergraph with only one edge, 𝑒𝑖 , which was given in Theorem 4.2.5. The next result classifies the relative barycentric homology for reduced 72 hypergraphs (Definition 2.1.5). This result compares to Theorem 3.2.2 for the restricted barycentric homology. Theorem 4.3.9 (Relative Homology of Reduced Hypergraphs† ). Let H be a reduced hypergraph, with edge set 𝐸 = {𝑒 1 , ..., 𝑒 π‘š }. Let 𝐸 π‘˜ denote the set of edges with exactly π‘˜ vertices, i.e. 𝐸 π‘˜ B {𝑒 ∈ 𝐸 | |𝑒| = π‘˜ }. Γ‰π‘š Then 𝐻 π‘Ÿπ‘’π‘™ (H ) = π‘˜βˆ’1 (H ) = |𝐸 |. 𝐻 π‘Ÿπ‘’π‘™ (𝑒𝑖 ), and π›½π‘Ÿπ‘’π‘™ π‘˜ 𝑖=1 Proof. The proof is by induction on the number of edges in the hypergraph. Base Case: Suppose π‘š = 1, then since 𝑒 1 is the only edge in the hypergraph, 𝐻 π‘Ÿπ‘’π‘™ (H ) = 𝐻 π‘Ÿπ‘’π‘™ (𝑒 1 ). Let |𝑒 1 | = π‘˜. Recall the homology of the single edge hypergraph (Theorem 4.2.5): ο£±  Z when 𝑛 = π‘˜ βˆ’ 1   ο£² 2Z  π»π‘›π‘Ÿπ‘’π‘™ (H ) =    0 else.  ο£³ Since |𝐸 | = 1, and |𝐸 | = 0 for 𝑗 β‰  π‘˜, the base case is proved. π‘˜ 𝑗 Induction Hypothesis: Assume that the theorem holds for a reduced hypergraph with π‘š βˆ’ 1 edges. Induction Step: Let H be a reduced hypergraph with π‘š edges. Let 𝐾 be the associated simplicial complex of H and 𝑇 its barycentric subdivision. Let 𝑆 denote the missing subcomplex. Partition 𝐸 into 𝐸 1 and 𝐸 2 with 𝐸 1 = {𝑒 1 } and 𝐸 2 = 𝐸 \ {𝑒 1 }. Let H1 and H2 be the hypergraphs with edge sets 𝐸 1 and 𝐸 2 , respectively. Let 𝐾1 , 𝐾2 , 𝑇1 , and 𝑇2 be the corresponding associated simplicial complexes and barycentric subdivisions. Let 𝑆1 and 𝑆2 be the corresponding missing subcomplexes. Then recall the simplicial version of the Mayer-Vietoris sequence (Theorem 4.1.3). Let 𝑇 β€² = 𝑇1 ∩ 𝑇2 and 𝑆′ = 𝑆1 ∩ 𝑆2 . Then there is an exact sequence: . . . β†’ 𝐻𝑛 (𝑇 β€², 𝑆′) β†’ 𝐻𝑛 (𝑇1 , 𝑆1 ) βŠ• 𝐻𝑛 (𝑇2 , 𝑆2 ) β†’ 𝐻𝑛 (𝑇, 𝑆) β†’ π»π‘›βˆ’1 (𝑇 β€², 𝑆′) β†’ . . . 73 Apply the definition of the relative barycentric homology to see that 𝐻𝑛 (𝑇, 𝑆) = π»π‘›π‘Ÿπ‘’π‘™ (H ), Γ‰π‘š π‘Ÿπ‘’π‘™ 𝐻𝑛 (𝑇1 , 𝑆1 ) = π»π‘›π‘Ÿπ‘’π‘™ (H1 ) = π»π‘›π‘Ÿπ‘’π‘™ (𝑒 1 ) by the base case, and 𝐻𝑛 (𝑇2 , 𝑆2 ) = π»π‘›π‘Ÿπ‘’π‘™ (H2 ) = 𝑖=2 𝐻𝑛 (𝑒𝑖 ) by the induction hypothesis. Next, we will show 𝐻𝑛 (𝑇 β€², 𝑆′) = 0 for all 𝑛. This is done by showing that 𝑆′ = 𝑇 β€². By definition, 𝑆′ βŠ‚ 𝑇 β€², since 𝑆1 βŠ‚ 𝑇1 , and 𝑆2 βŠ‚ 𝑇2 . Suppose Ξ© ∈ 𝑇 β€². Then, Ξ© ∈ 𝑇1 and 𝑇2 . Recall that simplices in the barycentric subdivision represent chains of inclusions of simplices in the original simplicial complex, so Ξ© = {𝑣 𝜎0 βŠ‚ 𝑣 𝜎1 βŠ‚ . . . βŠ‚ 𝑣 πœŽπ‘Ÿ } for π‘Ÿ = dim Ξ© + 1 and every πœŽπ‘– is a subset of an edge in 𝐸 1 and and edge in 𝐸 2 . Remember that 𝐸 1 = {𝑒 1 } and 𝑒 1 βˆ‰ 𝐸 2 . Since the hypergraph is reduced, any subset of 𝑒 1 that is also a subset of an edge in 𝐸 2 cannot be present as an edge in the hypergraph, as it would be a proper subedge. Therefore, Ξ© is built on the vertices 𝜎 that are all missing subedges of the hypergraph, and thus Ξ© ∈ 𝑆′. Since Ξ© was an arbitrary simplex in 𝑇 β€², 𝑇 β€² βŠ‚ 𝑆′, and thus, 𝑇 β€² = 𝑆′. Therefore 𝐻𝑛 (𝑇 β€², 𝑆′) = 0 for all 𝑛. We get the following exact sequence: 𝐻𝑛 (𝑇 β€², 𝑆′) 𝐻𝑛 (𝑇1 , 𝑆1 ) βŠ• 𝐻𝑛 (𝑇2 , 𝑆2 ) 𝐻𝑛 (𝑇, 𝑆) π»π‘›βˆ’1 (𝑇 β€², 𝑆′) Γ‰π‘š 0 π»π‘›π‘Ÿπ‘’π‘™ (𝑒 1 ) βŠ• ( π»π‘›π‘Ÿπ‘’π‘™ (𝑒𝑖 )) π»π‘›π‘Ÿπ‘’π‘™ (H ) 0 𝑖=2 which yields the following isomorphism of homology: ΓŠπ‘š π»π‘›π‘Ÿπ‘’π‘™ (𝑒 1 ) βŠ• ( π»π‘›π‘Ÿπ‘’π‘™ (𝑒𝑖 ))  π»π‘›π‘Ÿπ‘’π‘™ (H ). 𝑖=2 This proves the first part of the theorem. The second part of the theorem about π›½π‘Ÿπ‘’π‘™ follows from the base case and induction hypothesis, with π›½π‘Ÿπ‘’π‘™ 𝑛 (H ) = 𝛽𝑛 (H2 ) for all 𝑛 β‰  |𝑒 1 |, and π‘Ÿπ‘’π‘™ π›½π‘Ÿπ‘’π‘™ |𝑒 1 | (H ) = π›½π‘Ÿπ‘’π‘™|𝑒 1 | (H2 ) + 1. β–‘ For this theorem, it does not matter whether the reduced hypergraph has a high degree of intersection, or is made up of many connected components. It only considers that there are no subedges present in the hypergraph. This seems to imply that the relative barycentric homology is giving information primarily about the subedge structure of the hypergraph, and not the structure 74 Figure 4.10 Three different hypergraphs with the same toplexes. and intersectionality of its toplexes. For example, the three hypergraphs in Figure 4.10 all have the same relative barycentric homology. Recall the definition of a simplicial collapse from Theorem 2.2.7. Simplicial collapses make computing the homology of a simplicial complex easier by shrinking the complex without changing its homology. Unfortunately, not every allowable collapse can be applied to the barycentric subdivision 𝑇 of a hypergraph H without changing its relative barycentric homology. In the barycentric subdivision 𝑇 of Figure 4.4, the edge {𝐴𝐢, 𝐢} can be simplicially collapsed with the triangle {𝐴𝐡𝐢, 𝐴𝐢, 𝐢}. However, this would split the missing subcomplex 𝑆, highlighted in the image, into two path components, thereby changing 𝐻1π‘Ÿπ‘’π‘™ (H ). This theorem gives a condition on the simplices of the barycentric subdivision 𝑇 allowing collapses depending on whether or not the collapsed simplices lie in the missing subcomplex 𝑆. Proposition 4.3.10. Let H be a hypergraph, with barycentric subdivision 𝑇 and missing subcom- plex 𝑆. Let Ξ¦ < Ξ© be two simplices in 𝑇 that meet the requirements for a simplicial collapse. Suppose either 1. All of the vertices of Ξ¦ and Ξ© are in 𝑆, or 2. All of the vertices of Ξ¦ and Ξ© are not in 𝑆. Then the collapse can be made at the simplicial level without changing the relative barycentric homology of the hypergraph. Proof. Recall the definition of the relative barycentric homology as π»π‘›π‘Ÿπ‘’π‘™ (H ) = 𝐻𝑛 (𝑇, 𝑆). Let 𝑇 β€² denote 𝑇 \ {Ξ¦, Ξ©} and 𝑆′ denote the analogous construction for 𝑆. In the second case, 𝑆′ = 𝑆. 75 Since simplicial collapses preserve homology, 𝐻𝑛 (𝑇)  𝐻𝑛 (𝑇 β€²) for all 𝑛, and 𝐻𝑛 (𝑆)  𝐻𝑛 (𝑆′). Using the long exact sequences of the pairs (𝑇, 𝑆) and (𝑇 β€², 𝑆′) and maps on homology generated by inclusions, we get the following commutative diagram: 𝐻𝑛 (𝑆′) 𝐻𝑛 (𝑇 β€²) 𝐻𝑛 (𝑇 β€², 𝑆′) π»π‘›βˆ’1 (𝑆′) π»π‘›βˆ’1 (𝑇 β€²) ... 𝐻𝑛 (𝑆) 𝐻𝑛 (𝑇) 𝐻𝑛 (𝑇, 𝑆) π»π‘›βˆ’1 (𝑆) π»π‘›βˆ’1 (𝑇) ... The four outside vertical maps are all isomorphisms, thus the middle map is an isomorphism as well. Therefore, for all 𝑛, π»π‘›π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝑇, 𝑆)  𝐻𝑛 (𝑇 β€², 𝑆′), proving the theorem. β–‘ Initial collapses can only use case 2 of not in 𝑆, but subsequent collapses might use the in 𝑆 case. An example of a hypergraph H and corresponding barycentric subdivision where Proposition 4.3.10 does apply can be found in Figure 4.1. The edge { 𝐴𝐢, 𝐢} can be collapsed with the triangle {𝐴𝐡𝐢, 𝐴𝐢, 𝐢}. After that collapse, {𝐴𝐡𝐢, 𝐴𝐢, 𝐴} is the only maximal simplex that {𝐴𝐡𝐢, 𝐴𝐢} is a face of, and so they can be collapsed. Then, finally, the only maximal simplex that 𝐴𝐢 is a face of is { 𝐴𝐢, 𝐴}, and they are both simplices in 𝑆. The pair (𝑇 β€², 𝑆′) after these collapses has the same relative homology. In this section, we gave some results helping to compute and interpret the relative barycentric homology for hypergraphs. Several of these results, like Theorem 4.3.3 and Theorem 4.3.5, leveraged the ideas of the long exact sequence of a pair. Because of the exactness of the sequence . . . β†’ 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) β†’ π»π‘›βˆ’1 (𝑇) β†’ . . . every homology class in π»π‘›π‘Ÿπ‘’π‘™ (H ) either comes from 𝐻𝑛 (𝑇) or maps into π»π‘›βˆ’1 (𝑆). This concept will form the backbone for computing the relative barycentric homology at the end of the next chapter in Section 5.2. First, however, we will state some results that help to form a bridge between the restricted and relative barycentric homology theories, allowing us to connect the two. 76 CHAPTER 5 BRIDGING THE THEORIES AND COMPUTATION This chapter has two main objectives, which both serve the purpose of uniting the relative and restricted barycentric homology theories. The second goal will be to discuss the computation of the relative and restricted barycentric homology. During my internship with PNNL, I wrote code in Python for computing the Betti numbers for both the restricted barycentric homology and the relative barycentric homology. That code, and an accompanying tutorial, will soon be avilable on HyperNetX, a PNNL developed Python package for studying hypergraphs [27]. In this thesis, we will not spend much time discussing the code and its efficiency. Instead, in Section 5.2, we will look to show the theory behind why the algorithm returns the correct answer. This is necessary because the computations are not done using the definitions given in Section 2.3. In particular, a main goal when writing the code was to avoid building the entire barycentric subdivision since this is computationally expensive, and we will discuss how this goal was accomplished. Before we discuss computation however, we will give some theoretical results merging the two homology theories. These are mainly set-theoretic results on the supplement and complement of hypergraphs and how the definition of supplement from Definition 2.1.11 interacts with the definition of the missing subcomplex from Definition 2.3.4. Recall Lemma 2.1.2 which says that for every hypergraph, either it is a maximum edge hypergraph or its complement is maximum edge (sometimes both). Since the relative barycentric homology of maximum edge hypergraphs is easier to study, benefits of the results in this section include ways of relating the homology of a complement or supplement hypergraph to the homology of the original hypergraph. 5.1 Results Bridging the Relative and Restricted Barycentric Homologies For this section, recall the definition of the complement (Definition 2.1.7) and supplement (Definition 2.1.11) of a hypergraph. Briefly, given a hypergraph, its complement is all of the subsets of the vertex set that are not edges in the hypergraph, while the supplement is all subsets of existing edges that are not themselves edges. The first lemma says that given a hypergraph, its missing subcomplex (Definition 2.3.4) is the restricted barycentric subdivision (Definition 2.3.2) 77 of its supplement. Lemma 5.1.1. † Let H be a hypergraph and Supp(H ) be its supplement. The restricted barycentric subdivison 𝑅 of Supp(H ) is the same as the missing subcomplex 𝑆 of H . Proof. Let 𝑅 be the restricted barycentric subdivision of Supp(H ). Then the vertices in 𝑅 are the edges of Supp(H ) and the simplices of 𝑅 are given by their inclusion relations in Supp(H ). By definition of the supplement, the edges in Supp(H ) are the missing subedges of edges in H . Let 𝑆 be the missing subcomplex of the relative barycentric subdivision of H . The vertices of 𝑆 are the missing subedges of edges in H , with simplices given by the chains of inclusions in the associated simplicial complex H . Thus, these simplicial complexes 𝑅 and 𝑆 have the same vertex set with simplices constructed in the same way, and are therefore the same simplicial complex. β–‘ This means that given a hypergraph H , we can alter the long exact sequence for the relative barycentric homology . . . β†’ 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) β†’ . . . by replacing 𝐻𝑛 (𝑆) at all steps with 𝐻 π‘Ÿπ‘’π‘  Supp(H ), as in the following theorem, which is based off of Theorem 4.2.3 and Corollary 4.2.4 and holds when H is a maximum edge hypergraph. Theorem 5.1.2. † Let H be a maximum edge hypergraph, and G be its supplement. Then π‘Ÿπ‘’π‘™ 𝐻𝑛+1 (H )  π»π‘›π‘Ÿπ‘’π‘  (G) when 𝑛 > 1, and there is a long exact sequence Z 0 β†’ 𝐻1π‘Ÿπ‘’π‘™ (H ) β†’ 𝐻0π‘Ÿπ‘’π‘  (G) β†’ β†’ 𝐻0π‘Ÿπ‘’π‘™ (H ) β†’ 0. 2Z Proof. Since H is a maximum edge hypergraph, we have the following results for its relative homology from Theorem 4.2.3 and Corollary 4.2.4. π‘Ÿπ‘’π‘™ 𝐻𝑛+1 (H )  𝐻𝑛 (𝑆) 78 Figure 5.1 A hypergraph H used as an example for Theorem 5.1.2. when 𝑛 > 1 and an exact sequence 0 β†’ 𝐻1π‘Ÿπ‘’π‘™ (H ) β†’ 𝐻0 (𝑆) β†’ Z β†’ 𝐻0π‘Ÿπ‘’π‘™ (H ) β†’ 0. However, by the lemma, we can substitute 𝑅 in for 𝑆. Moreover, since 𝑅 is the restricted barycentric subdivision of Supp(G), 𝐻𝑛 (𝑅)  π»π‘›π‘Ÿπ‘’π‘  (Supp(H )) βˆ€ 𝑛, so in the above expressions, 𝐻𝑛 (𝑆) can be replaced by π»π‘›π‘Ÿπ‘’π‘  (Supp(G)). This proves the theorem. β–‘ The prior theorem relates the relative barycentric homology of a maximum edge hypergraph to the restricted barycentric homology of its supplement. Figure 5.1 shows a hypergraph H and its supplement Supp(H ). Notice that the missing subcomplex of H , highlighted in 𝑇, is the same as the restricted barycentric subdivision of Supp(H ). The following corollary, which uses Corollary 2.1.3 to rephrase Theorem 5.1.2, relates the restricted barycentric homology of a hypergraph that is not maximum edge to the relative barycentric homology of its complement. Corollary 5.1.3. † Let H be a hypergraph that is not maximum edge, and let Comp(H ) be its complement. Then π‘Ÿπ‘’π‘™ 𝐻𝑛+1 (Comp(H ))  π»π‘›π‘Ÿπ‘’π‘  (H ) when 𝑛 > 1, and there is a long exact sequence 0 β†’ 𝐻1π‘Ÿπ‘’π‘™ (Comp(H )) β†’ 𝐻0π‘Ÿπ‘’π‘  (H ) β†’ Z β†’ 𝐻0π‘Ÿπ‘’π‘™ (Comp(H )) β†’ 0. Proof. This corollary is a result of Corollary 2.1.3, which says that H is the supplement of Comp(H ), and so the previous theorem can be applied to yield the corollary. β–‘ 79 Figure 5.2 A hypergraph H and its missing subcomplex and restricted barycentric subdivision. This sheds some light on why it makes sense to talk about the restricted and relative barycentric homologies as complementary theories. The restricted barycentric subdivision (Definition 2.3.2) is built from the barycentric subdivision using the vertices that represent edges in the hypergraph. The missing subcomplex of Definition 2.3.4 is built from the barycentric subdivision using the vertices that do not represent edges in the hypergraph. A vertex in the barycentric subdivision either represents an edge in the hypergraph or it does not. Therefore, the restricted barycentric subdivision and the missing subcomplex partition the vertex set of the barycentric subdivision. However, the same cannot be said for the higher dimensional simplices. Simplices that have some vertices representing edges in the hypergraph and others that do not will not be in either the restricted barycentric subdivision or the missing subcomplex. Figure 5.2 illustrates this interesting concept. The missing subcomplex 𝑆 is highlighted in red and the restricted barycentric subdivision 𝑅 is highlighted in blue. These partition the vertex set of the barycentric subdivision 𝑇. In the next section, which discusses computation, the connection between the restricted and relative barycentric homologies will become even more apparent. During computation, there are many parallels between the theories, and some of the shortcuts that can be taken to reduce computation complexity work for both versions of the homology, as we will see next. 5.2 Computation of the Restricted and Relative Barycentric Homologies This section† contains a discussion of the computation of the restricted and relative barycentric homology theories. There are two main success stories of this section. First, for both the restricted 80 and relative barycentric homology, the computation is made without taking the barycentric sub- division. Avoiding this computationally unwieldy construction saves both space and time. The second contribution, exclusively pertaining to the relative barycentric homology, is that the com- putation happens without needing to take the quotient space or a relative homology at all. This is shown in Theorem 5.2.3. The code, and an accompanying tutorial, which was written during my internship with PNNL, will soon be included in the python package HyperNetX [27]. Finding the asscoiated simplicial complex of a hypergraph was already implemented in HyperNetX, and taking the homology of a simplicial complex is done using the standard Smith Normal Form [13], so my contribution besides the two successes outlined above is building the specific simplicial complexes needed for the computations. We will begin with the computation of the restricted barycentric homology. 5.2.1 Computation of Restricted Barycentric Homology The restricted barycentric subdivision is built in the code as follows: the edges of the hypergraph are used as vertices of a graph. Each pair of edges is checked for an inclusion, and an edge is added to the graph if there is an inclusion relation. The restricted barycentric subdivision is the clique complex of this graph, as demonstrated in Theorem 3.1.2, and the chain complex of that is what is used in the computation. The main advantage of this approach is that it does not require taking all subsets of the edges, as is necessary for finding the full barycentric subdivision. There is still a bottleneck in having to take all maximal cliques of a graph. This construction follows closely the understanding of the restricted barycentric subdivision as the order complex of the edge containment poset, as in Proposition 3.1.1. Each element of the poset is an edge in the hypergraph, and the relations in the poset are inclusions of edges. After building the restricted barycentric subdivision, one builds the chain complex, boundary matrices, and takes the homology as implemented in HyperNetX. Before we move on to the relative barycentric homology, we will follow along with the algorithm to compute the homology of the hypergraph in Figure 2.8. This hypergraph has four edges: H = { 𝐴𝐡𝐢, 𝐡𝐢𝐷, 𝐡, 𝐢}. First, the algorithm will build a graph with those as its vertices. Then, 81 𝐡 will be connected to 𝐴𝐡𝐢 and 𝐡𝐢𝐷 because it is a subset of them, but 𝐡 will not be connected to 𝐢, because there is not an inclusion relation in either direction between 𝐡 and 𝐢. Next, 𝐢 will be connected via an edge to 𝐴𝐡𝐢 and 𝐡𝐢𝐷 since it is a subset of both of them. Then 𝐴𝐡𝐢 and 𝐡𝐢𝐷 will not be connected. This gives the restricted barycentric subdivision 𝑅, as highlighted in the figure, but without having to construct 𝑇. HyperNetX will build the chain complex to 𝑅 and take its homology using Smith Normal Form, returning [1, 1] to indicate that π›½π‘Ÿπ‘’π‘  0 (H ) = 1 and 1 (H ) = 1. Since there are no simplices in higher dimension, it does not return any higher Betti π›½π‘Ÿπ‘’π‘  numbers, which are all zero. 5.2.2 Computation of Relative Barycentric Homology The first step in taking the relative barycentric homology is to use the native HyperNetX functions to find the chain complex, boundary matrices, and homology of the associated simplicial complex 𝐾. In order to build the missing subcomplex, it is necessary to go through almost the same process as it takes to build the barycentric subdivision. It still starts by taking all subsets of the edges of the hypergraph. Instead of using every subset like in the barycentric subdivision, it only stores those subsets that are not edges of H . These form the vertices of the missing subcomplex. Again the full missing subcomplex 𝑆 is the clique complex of a graph built on these vertices based on inclusions in subsets of the hypergraph, as shown in the proposition below. Proposition 5.2.1 (Poset Construction of 𝑆). The missing subcomplex 𝑆 of a hypergraph H is the same simplicial complex as the order complex (Definition 2.2.8) of the face poset (Definition 2.1.14) of Supp(H ), 𝑆H = Ξ”(𝐹𝑃Supp(H ) ). Proof. This result is a combination of Lemma 5.1.1 and Proposition 3.1.1. Lemma 5.1.1 says that 𝑆 is the same simplicial complex as the restricted barycentric subdivision 𝑅 of Supp(H ), and Proposition 3.1.1 says that 𝑅 is the same simplicial complex as the mentioned poset construction. β–‘ This is analogous to Proposition 3.1.1 for the restricted barycentric subdivision. These two constructions being so closely connected lends credence to the idea that the restricted and relative 82 barycentric homology are complementary theories. The next theorem, which is how the missing subcomplex is built in the code, is a clique complex construction of 𝑆 similar to Theorem 3.1.2. Theorem 5.2.2 (Clique Construction of 𝑆). The missing subcomplex 𝑆 of a hypergraph H is the same simplicial complex as the clique complex (Definition 2.2.7) of the edge inclusion graph (Definition 2.1.15) of its supplement Supp(H ), 𝑆H = 𝑋 (𝐸 𝐼𝐺 Supp(H ) ). Proof. Similarly to the above Proposition, utilizing Lemma 5.1.1 gives that 𝑆 is the same simplicial complex as 𝑅SuppH , and then applying Theorem 3.1.2 constructs 𝑅Supp(H ) as stated. β–‘ Once the missing subcomplex 𝑆 is constructed, we use the built in HyperNetX functions for generating its chain complex for use in the computation. Recall our long exact sequence for relative barycentric homology: . . . β†’ 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) β†’ π»π‘›βˆ’1 (𝑇) . . . In this sequence, the map 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) is the map induced on homology by the inclusion 𝑆 β†’ 𝑇. The map 𝐻𝑛 (𝑇) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) is the map induced on homology by the quotient map 𝑇 β†’ (𝑇, 𝑆), and the map π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) is derived using the snake lemma. Because of this exactness, the terms and maps listed above are enough to determine π»π‘›π‘Ÿπ‘’π‘™ (H ) without actually computing the relative homology 𝐻𝑛 (𝑇, 𝑆). We will next leverage another important fact from algebraic topology, that of Lemma 2.2.3: 𝐻𝑛 (𝑇)  𝐻𝑛 (𝐾) for all 𝑛, and they are furthermore homotopy equivalent. So anywhere in the above discussion, it is possible to replace 𝐻 (𝑇) with 𝐻 (𝐾). (Computationally, this will not affect Betti numbers, but will affect generators.) We will use 𝑖 𝑛 to denote the composition 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝑇) β†’ 𝐻𝑛 (𝐾), where the second map is a homotopy equivalence. This leads to an exact sequence: 𝑖𝑛 𝑖 π‘›βˆ’1 . . . β†’ 𝐻𝑛 (𝑆) βˆ’ β†’ 𝐻𝑛 (𝐾) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) βˆ’βˆ’βˆ’β†’ π»π‘›βˆ’1 (𝐾) . . . There are large classes of hypergraphs for which 𝑖 𝑛 is guaranteed to be the zero map (Theorem 4.3.6) and it will always be possible to write the above sequence as a direct sum decomposition. 83 In order for a homology in 𝑆 to also be in 𝐾, 𝐾 must contain a homology class that is entirely generated by simplices that are missing subedges in H , as seen in Figure 4.8. This means that 𝐾 needs a homology class that is generated entirely by simplices that are not toplexes. Therefore, any hypergraph whose associated simplicial complex does not have such a homology can have its relative barycentric homology written as 𝐻 π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝐾) βŠ• π»π‘›βˆ’1 (𝑆) by Theorem 4.3.5. This leads to the best, so far, physical interpretation of the relative barycentric homology. Even if the hypergraph does not lie in that special case where 𝐻 π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝐾) βŠ• π»π‘›βˆ’1 (𝑆), all relative barycentric homologies still come from either 𝐾 or 𝑆 (because of the exactness of the sequence). So the relative homology can be separated as either homology native to the associated simplicial complex of that hypergraph or homology coming from the poset structure of the missing subedges of the hypergraph. The latter piece (those homologies coming from 𝑆) can also be viewed as the restricted barycentric homology of the supplement hypergraph. In fact, even if 𝑖 𝑛 : 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝐾) is not 0 for all 𝑛, that map is all of the information we need to find 𝐻 π‘Ÿπ‘’π‘™ (H ). This is summarized in the next theorem. Theorem 5.2.3 (Computing Relative Barycentric Homology). Let H be a hypergraph. Recall the long exact sequence of homology groups: 𝑖𝑛 𝑖 π‘›βˆ’1 . . . β†’ 𝐻𝑛 (𝑆) βˆ’ β†’ 𝐻𝑛 (𝐾) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ) β†’ π»π‘›βˆ’1 (𝑆) βˆ’βˆ’βˆ’β†’ π»π‘›βˆ’1 (𝐾) . . . Then π»π‘›π‘Ÿπ‘’π‘™ (H ) is determined entirely by the maps 𝑖 𝑛 : 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝐾) and 𝑖 π‘›βˆ’1 : π»π‘›βˆ’1 (𝑆) β†’ π»π‘›βˆ’1 (𝐾). In fact, π»π‘›π‘Ÿπ‘’π‘™ (H ) = 𝐻𝑛 (𝑇, 𝑆)  Cok(𝑖 𝑛 ) βŠ•Ker(𝑖 π‘›βˆ’1 ), and π›½π‘Ÿπ‘’π‘™ 𝑛 (H ) = 𝛽𝑛 (𝐾) + π›½π‘›βˆ’1 (𝑆) βˆ’rk(𝑖 𝑛 ) βˆ’rk(𝑖 π‘›βˆ’1 ). Proof. This is again because of the exactness of the sequence β†’ βˆ’ βˆ’βˆ’β†’ . . . →𝐻 β†’π»π‘›π‘Ÿπ‘’π‘™ (H )βˆ’ βˆ’ 𝑛 (𝑆) 𝑖 𝑛 𝐻𝑛 (𝐾)βˆ’ β†’π»π‘›βˆ’1 (𝑆) πΌπ‘›βˆ’1 π»π‘›βˆ’1 (𝐾)βˆ’ β†’... The composition of the middle two maps is zero since the sequence is exact. This means that all homology generators of π»π‘›π‘Ÿπ‘’π‘™ (H ) either come from 𝐻𝑛 (𝐾) or map into π»π‘›βˆ’1 (𝑆), but not both. 84 First, we consider the generators that come from 𝐻𝑛 (𝐾). Since they are in the image of the map 𝐻𝑛 (𝐾) β†’ π»π‘›π‘Ÿπ‘’π‘™ (H ), they were not in the image of 𝑖 𝑛 : 𝐻𝑛 (𝑆) β†’ 𝐻𝑛 (𝐾) by exactness. Thus, they must be exactly the generators of the cokernel of 𝑖 𝑛 , denoted Cok(𝑖 𝑛 ). Recall that rk(Cok(𝑖 𝑛 )) = 𝛽𝑛 (𝐾) βˆ’ rk(𝑖 𝑛 ). Then there are the generators of π»π‘›π‘Ÿπ‘’π‘™ (H ) that map into π»π‘›βˆ’1 (𝑆). Since these are the image of that map, they become the kernel of 𝑖 π‘›βˆ’1 : π»π‘›βˆ’1 (𝑆) β†’ π»π‘›βˆ’1 (𝐾), denoted Ker(𝑖 π‘›βˆ’1 ). Recall that rk(Ker(𝑖 π‘›βˆ’1 )) = 𝛽𝑛 (𝑆) βˆ’ rk(𝑖 π‘›βˆ’1 ). As stated earlier, because of the exactness of the sequence, all homology generators of π»π‘›π‘Ÿπ‘’π‘™ (H ) either come from 𝐻𝑛 (𝐾) or map into π»π‘›βˆ’1 (𝑆), but not both. The generators that come from 𝐻𝑛 (𝐾) are exactly Cok(𝑖 𝑛 ), and the generators that map into π»π‘›βˆ’1 (𝑆) are exactly Ker(𝑖 π‘›βˆ’1 ), so π»π‘›π‘Ÿπ‘’π‘™ (H )  Cok(𝑖 𝑛 ) βŠ• Ker(𝑖 π‘›βˆ’1 ). This means that π›½π‘Ÿπ‘’π‘™ 𝑛 (H ) = rk(Cok(𝑖 𝑛 )) + rk(Ker(𝑖 π‘›βˆ’1 )) = 𝛽𝑛 (𝐾) βˆ’ rk(𝑖 𝑛 ) + 𝛽𝑛 (𝑆) βˆ’ rk(𝑖 π‘›βˆ’1 ), as was to be shown. β–‘ Note that if 𝑖 𝑛 is the zero map, then its kernel is everything in 𝐻𝑛 (𝑆) and its cokernel is everything in 𝐻𝑛 (𝐾), yielding the direct sum decomposition 𝐻 π‘Ÿπ‘’π‘™ (H )  𝐻𝑛 (𝐾) βŠ• π»π‘›βˆ’1 (𝑆) presented in Theorem 4.3.5 and recalled above. Once the missing subcomplex 𝑆 is built, we can find the homology of 𝑆 using HyperNetX. Then, it is necessary to construct the matrix for the map 𝑆 β†’ 𝐾. The inclusion from 𝑆 β†’ 𝑇 is the identity on each simplex in 𝑆, but we need to describe the map 𝑇 β†’ 𝐾. This map is induced on simplices of 𝑇 by a vertex map. Each vertex in 𝑇 represents a simplex in 𝐾, so if 𝑣 𝜎 is a vertex in 𝑆 representing {𝑣 0 , ..., 𝑣 𝑛 } ∈ 𝐾, the map 𝑆 β†’ 𝐾 takes 𝑣 𝜎 to 𝑣 0 . It always chooses the lexicographically first vertex contained in that simplex in 𝐾. The algorithm computes the matrix (in each dimension) for this map by looking at every simplex in 𝑆, writing down all of the first entries in each of the vertices comprising that simplex, and then 85 checking the simplices in 𝐾 to look for a match. If there is a match, the corresponding matrix element is made a 1. After computing that matrix, each of the homology generators of 𝑆 are multiplied by it to put them in terms of the chain groups for 𝐾. Cycles in 𝑆 are automatically cycles in 𝐾. So, using the same techniques as the homology algorithm with Smith Normal Form uses, they are projected into the cokernel to see if they are also homology generators in 𝐾. Homologies in 𝑆 that are also homologies in 𝐾 result in obstructions to the direct sum decomposition, and the number of these obstructions in each dimension is tracked in a vector called Bettiob. Lastly, the relative Betti numbers are computed, using the following formula: π›½π‘Ÿπ‘’π‘™ 𝑛 (H ) = 𝛽𝑛 (𝐾) + π›½π‘›βˆ’1 (𝑆) βˆ’ Bettiob𝑛 βˆ’ Bettiobπ‘›βˆ’1 . To close this section, we will follow along with the algorithm to compute the relative barycentric homology of the hypergraph in Figure 2.9. This is the hypergraph H = {𝐴𝐡𝐢}. First, HyperNetX takes the chain complex of the associated simplicial complex 𝐾 and, using Smith Normal Form, its homology. It records this as [1, 0, 0], denoting that 𝛽0 (𝐾) = 1 and 𝛽𝑖 (𝐾) = 0 for all 𝑖 β‰  0. Next, we have to build 𝑆. The algorithm notes that, of the subsets of 𝐴𝐡𝐢,the collection {𝐴𝐡, 𝐴𝐢, 𝐡𝐢, 𝐴, 𝐡, 𝐢} is missing from the hypergraph, and so it forms the vertex set of 𝑆. Edges are made between 𝐴 and 𝐴𝐡, and 𝐴 and 𝐴𝐢, as well as the rest of the pairs that have a subset relation, giving the graph highlighted in the figure, which is 𝑆. HyperNetX takes its chain complex and homology, returning [1, 1] as the sequence of Betti numbers for 𝑆. The map 𝑆 β†’ 𝐾 sends 𝐴, 𝐴𝐡, 𝐴𝐢 to 𝐴, 𝐡 and 𝐡𝐢 to 𝐡, and 𝐢 to 𝐢. The algorithm builds the corresponding matrix and then the homology generators of 𝑆 are multiplied by that map to see if they still generate nontrivial homology in 𝐾. In this case, the class in dimension zero maps nontrivially (since the only path component of 𝑆 is also the path component of 𝐾), but the class in dimension one does not as there is no homology in dimension one in 𝐾. So, the code returns [1, 0] to denote the rank of the map induced on homology by the map 𝑆 β†’ 𝐾. These vectors are added according to the formula to get a final answer for this hypergraph of [0, 0, 1], as expected. 86 CHAPTER 6 DYNAMIC HYPERGRAPHS If the relative and restricted barycentric homology of hypergraphs are going to be useful for studying real world data, it will be necessary to quantify how changing a hypergraph changes the homology, as real world data is constantly being modified. Our methods need to be able to account for and analyze changes in the hypergraph. This chapter takes the first steps towards doing just that. There are three ways in which a hypergraph H can change: the vertex set 𝑉 could change, the edge set 𝐸 could change, or the incidence of the vertices and edges can change. However, the third option of changing vertex-edge relationships is covered by the second case of changing the edge set. Changing vertex-edge incidence is done by removing all of the edges from 𝐸 that have a different vertex set in the new hypergraph, and then adding in all of the edges that were not a part of the original edge set. Therefore, all dynamic hypergraphs can be traced by keeping track of the vertices and edges being added or removed. Moreover, because of the invertability of the operation of adding or removing vertices and edges, it is enough to only consider the consequences of adding. The upcoming results in this chapter are written for adding vertices and edges, but they can also be read to have the opposite effect for removing a vertex or edge with the same conditions. For example, in Theorem 6.2.1, conditions are given for which adding a vertex to a hypergraph increases the dimension of all of the homology classes. It should be understood that this also implies that removing a vertex under the same conditions decreases the dimension of all the homology cycles. This chapter consists of two sections. The first gives results on the effects on the restricted and relative barycentric homology when adding an edge to a hypergraph. It is not assumed that the vertex set stays the same when adding edges, so new edges can consist partially or entirely of new vertices. These results are concentrated in dimension zero. The second section contains results on the effects of adding a vertex to a hypergraph, while keeping the edge set the same. The main result of that section, Theorem 6.2.1, is for the relative barycentric homology and applies for maximum edge hypergraphs in all dimensions. 87 6.1 Adding an Edge Throughout this section, let H B {𝑉, 𝐸 } be a hypergraph, with 𝑉 = {𝑣 1 , ...., 𝑣 𝑛 } and 𝐸 = {𝑒 1 , ...., 𝑒 π‘š | 𝑒𝑖 βŠ‚ 𝑉 }. The edge added to the hypergraph will be denoted 𝑒′ βˆ‰ 𝐸. Let 𝑉 β€² = 𝑉 βˆͺ 𝑒′ and 𝐸 β€² = 𝐸 βˆͺ {𝑒′ }, then H β€² = {𝑉 β€², 𝐸 β€² } denotes the new hypergraph with added edge. We will start by outlining the effects of adding an edge on the relative barycentric homology in dimension zero. 6.1.1 The Effects of Adding an Edge on Zeroth Dimensional Relative Homology Let H be a hypergraph. Recall that π›½π‘Ÿπ‘’π‘™ 0 (H ), the 0th relative Betti number, is the rank of 𝐻0π‘Ÿπ‘’π‘™ (H ). This is the number of path components of H that are simplicial complexes, called simplicial components from Definition 2.1.16. We will consider when adding an edge can change 𝐻0π‘Ÿπ‘’π‘™ . First, how can adding an edge to the hypergraph increase the number of connected components that are simplicial complexes? One option is to add a new connected component that was not there before. This would have to be a single new edge around one new vertex. If it is around more vertices, then there will be missing subedges, since we have only added one edge. An isolated vertex/edge pair like this that does not interact with the rest of the hypergraph in any way could be interesting and is worth tracking. This would increase π›½π‘Ÿπ‘’π‘™ 0 by 1. This case is the topic of the first proposition. Proposition 6.1.1. † Suppose 𝑒′ ∩ 𝑉 = βˆ…. Then, ο£± if |𝑒′ | = 1  0 (H ) + 1 ο£² π›½π‘Ÿπ‘’π‘™   β€²  π›½π‘Ÿπ‘’π‘™ 0 (H ) =   π›½π‘Ÿπ‘’π‘™   (H ) else. ο£³ 0 Proof. Since 𝑒′ ∩ 𝑉 = βˆ…, the new edge 𝑒′ is its own connected component in the hypergraph. This means that it cannot reduce π›½π‘Ÿπ‘’π‘™ π‘Ÿπ‘’π‘™ 0 , by Theorem 4.3.7. It will increase 𝛽0 when it is a simplicial component. If |𝑒′ | = 1, then it is simplicial. If |𝑒′ | > 1, then it is not simplicial as it will have some missing subedges, since 𝑒′ is the only edge in its connected component. β–‘ Figure 6.1 has three hypergraphs: H , H1 , and H2 . Each of H1 and H2 adds one edge that is a new connected component to H . By the above proposition, π›½π‘Ÿπ‘’π‘™ 0 (H1 ) = 𝛽0 (H ) + 1 and π‘Ÿπ‘’π‘™ 0 (H2 ) = 𝛽0 (H ) based on the number of vertices in the added edge. π›½π‘Ÿπ‘’π‘™ π‘Ÿπ‘’π‘™ 88 Figure 6.1 Three hypergraphs used as examples for Proposition 6.1.1. The second option for increasing the number of simplicial components is to turn an existing connected component into a simplicial complex by adding an edge. This would mean that there was a connected component in H that was only missing one edge, thereby finishing a simplicial component. This would increase π›½π‘Ÿπ‘’π‘™ 0 by 1. It represents the densest and second most dense types of connected components possible in a hypergraph. This is proved in the next proposition. Recall that a subedge is an edge that is contained in another edge, while a toplex is an edge that is not contained in any other edges. Every edge in a hypergraph is either a toplex or subedge. Proposition 6.1.2. † Suppose 𝑒′ βŠ‚ 𝑒 for some 𝑒 ∈ 𝐸. Denote by C β€² the connected component of H β€² containing 𝑒′. Then, ο£± C β€² is simplicial  0 (H ) + 1 ο£² π›½π‘Ÿπ‘’π‘™   β€²  π›½π‘Ÿπ‘’π‘™ 0 (H ) =   π›½π‘Ÿπ‘’π‘™   (H ) else. ο£³ 0 Proof. Since 𝑒′ is a subedge, it only intersects with one connected component of H , and that component was missing an edge, so it was not simplicial to begin with. Therefore, adding 𝑒′ cannot reduce π›½π‘Ÿπ‘’π‘™ β€² π‘Ÿπ‘’π‘™ 0 , by Theorem 4.3.7. Adding 𝑒 will only increase 𝛽0 if it finishes filling in a connected component, turning it into a simplicial component. β–‘ Something else that may be interesting here is that, if a connected component is only missing one edge, it will have trivial relative homology (Theorem 4.3.4). So if a connected component has nontrivial relative homology in dimension greater than 0, adding a subedge to it cannot add a 0 dimensional homology, proving the following corollary. 89 Corollary 6.1.3. Suppose H is a connected hypergraph with π›½π‘–π‘Ÿπ‘’π‘™ > 0 for some 𝑖 > 0. Then adding an edge to H cannot increase π›½π‘Ÿπ‘’π‘™ 0 . The previous results showed how adding an edge to a hypergraph can increase the number of simplicial components. Next, how can adding an edge to a hypergraph reduce the number of connected components that are simplicial complexes? This is done by adding an edge that intersects with a connected component that was a simplicial complex. If this is done in a way that the new edge is missing subedges, then any previous simplicial components that were connected to this new edge are no longer simplicial. What follows is the case when 𝑒′ intersects exactly one simplicial component. Proposition 6.1.4. † Suppose 𝑒′ is an that intersects one simplicial component, C. Let |𝑒′ | = 𝑑. Then, ο£± all size 𝑑 βˆ’ 1 subsets of 𝑒′ are in H  0 (H ) ο£² π›½π‘Ÿπ‘’π‘™   β€²  π›½π‘Ÿπ‘’π‘™ 0 (H ) =   π›½π‘Ÿπ‘’π‘™   (H ) βˆ’ 1 else ο£³ 0 Proof. Since 𝑒′ intersects exactly one simplicial component C, adding 𝑒′ will reduce π›½π‘Ÿπ‘’π‘™ 0 by 1 unless C remains simplicial after appending 𝑒′, by Theorem 4.3.7. This can only occur if all 𝑑 βˆ’ 1 subsets of 𝑒′ are edges in H . All of the other subsets will also be there because it was a simplicial component to begin with. β–‘ However, a newly added edge can intersect any number of components at once, by, for example, including multiple components in a single edge. If the new edge intersects with any number other than two connected components that were simplicial complexes, it will make them all nonsimplicial. This will reduce π›½π‘Ÿπ‘’π‘™ 0 by the number of connected components that were connected via the new edge. If the new hyperedge intersects with exactly two connected components that were simplicial complexes, it is possible that instead of killing both of them, it merges them into one simplicial complex, only reducing π›½π‘Ÿπ‘’π‘™ 0 by 1. This will happen exactly when the new hyperedge is between two vertices, one each in a connected component that was a simplicial complex. If there were any more 90 Figure 6.2 A hypergraph where adding the edge 𝐢𝐷 merged two simplicial components. than two vertices in it, (as would have to happen if it were intersecting more than two simplicial components), then there would be missing subedges inside of the new edge. This result is proved next. Proposition 6.1.5. † Suppose 𝑒′ is an edge that intersects π‘˜ > 1 simplicial components, and |𝑒′ | = 𝑑. Then, ο£±  0 (H ) βˆ’ 1 ο£² π›½π‘Ÿπ‘’π‘™ π‘˜=𝑑=2   β€²  π›½π‘Ÿπ‘’π‘™ 0 (H ) =   π›½π‘Ÿπ‘’π‘™   (H ) βˆ’ π‘˜ else ο£³ 0 Proof. Note that, in order to intersect π‘˜ different components, 𝑑 β‰₯ π‘˜. We will consider when 𝑑 > 2 and 𝑑 = 2 separately. If 𝑑 > 2, let {𝑣 𝑖 , 𝑣 𝑗 } be vertices in 𝑒′ where 𝑣 𝑖 is in a different simplicial component then 𝑣 𝑗 . So {𝑣 𝑖 , 𝑣 𝑗 } is a missing subedge of 𝑒′, and so the new connected component containing 𝑒′ is not a simplicial component. That means none of the formerly simplicial components that intersect 𝑒′ will be simplicial components in H β€² and π›½π‘Ÿπ‘’π‘™ 0 will decrease by the number of simplicial components that intersect 𝑒′, byt Theorem 4.3.7. In the case π‘˜ = 𝑑 = 2, 𝑒′ intersects 2 simplicial components and is an edge with 2 vertices. Notice both vertices (and hence, all of the proper subsets) in 𝑒′ are already edges in the hypergraph. Instead of making both components nonsimplicial, this merges two simplicial components into one, therefore only reducing π›½π‘Ÿπ‘’π‘™ 0 by 1. β–‘ For an example of the π‘˜ = 𝑑 = 2 case, see Figure 6.2. The hypergraph H β€² in this figure is the hypergraph after the edge 𝐢𝐷 was added. Notice how, if 𝐢𝐷 was removed from the hypergraph, 91 there would be two simplicial components, with toplexes 𝐴𝐡𝐢 and 𝐷𝐸 𝐹, so π›½π‘Ÿπ‘’π‘™ 0 (H ) = 2. The edge 𝐢𝐷 connects two simplicial components and has two vertices, so π›½π‘Ÿπ‘’π‘™ 0 (H ) = 1. Lastly, there are ways of adding an edge without changing π›½π‘Ÿπ‘’π‘™ 0 . This will probably be the most common result of adding an edge. One way to do this is by adding a new connected component which has more than one vertex, as in H2 of Figure 6.1. This does not affect any of the other existing connected components, and adds a connected component that is not a simplicial complex, so it will not change π›½π‘Ÿπ‘’π‘™ 0 . You could also add a new toplex intersecting connected components that were not simplicial complexes to begin with. This could be one or more connected components, but as long as none of them were simplicial complexes, adding toplexes will not affect π›½π‘Ÿπ‘’π‘™ 0 . Adding subedges to connected components that are missing at least two hyperedges will also not change π›½π‘Ÿπ‘’π‘™0 . So far we have enumerated what can happen to π›½π‘Ÿπ‘’π‘™0 when an isolated edge or a subedge is added to the hypergraph. Now let 𝑒′ be a toplex intersecting at least one edge in 𝐸. The change in π›½π‘Ÿπ‘’π‘™ 0 from adding 𝑒′ depends primarily on how many simplicial components it intersects. Note that the addition of a toplex cannot turn a non-simplicial component into a simplicial one. If 𝑒′ is a toplex that does not intersect any simplicial components, π›½π‘Ÿπ‘’π‘™ 0 will not change. Proposition 6.1.6. † Suppose 𝑒′ is a toplex that intersects no simplicial components, but does intersect H . Then π›½π‘Ÿπ‘’π‘™ β€² 0 (H ) = 𝛽0 (H ). π‘Ÿπ‘’π‘™ Proof. Let C be a simplicial component in H . Because 𝑒′ does not intersect C, C is still a simplicial components in H β€². Therefore, π›½π‘Ÿπ‘’π‘™ β€² 0 (H ) > 𝛽0 (H ). Propositions 6.1.1 and 6.2 detailed π‘Ÿπ‘’π‘™ β€² 0 , neither of which apply here. Therefore, 𝛽0 (H ) = all ways that adding an edge can increase π›½π‘Ÿπ‘’π‘™ π‘Ÿπ‘’π‘™ 0 (H ). π›½π‘Ÿπ‘’π‘™ β–‘ Next, we will move on to the effect of adding an edge on the restricted barycentric homology in dimension zero. 92 6.1.2 Effects of Adding an Edge on Zeroth Dimensional Restricted Barycentric Homology Recall that given a hypergraph, the rank of the zeroth dimensional restricted barycentric ho- mology group, denoted by π›½π‘Ÿπ‘’π‘  0 , is the number of fence components of the hypergraph. Next we will detail what happens to π›½π‘Ÿπ‘’π‘  0 when edges are added to the hypergraph. Again, the effects of removing an edge are the inverse of the effects of adding the same edge. How can adding an edge to the hypergraph add a new fence component to the hypergraph? The fence components of the hypergraph are given by the inclusion relations of the hypergraph, so adding a subedge will never add a new fence component to the hypergraph. In fact, even for adding toplexes, in order to create a new fence component, that new edge must not include any other edges. So in order to add an edge to increase π›½π‘Ÿπ‘’π‘  0 , it must be a toplex that does not have any subedges, although it can intersect other edges. Sometimes adding an edge can reduce π›½π‘Ÿπ‘’π‘  0 by merging fence components. As with some of the above, a single edge wrapped around what were formerly separate connected components will reduce π›½π‘Ÿπ‘’π‘  0 by an arbitrary amount. Moreover, it is possible to add subedges and merge fence components. Imagine a star type hypergraph where multiple edges that do not otherwise intersect all share a single vertex, as in Figure 6.3. If this vertex is not an edge in the hypergraph, then each edge is its own fence component, but adding in the "star vertex" will create a hypergraph with only one fence component. Unlike the case with relative barycentric homology, there will always be a fence component in whatever is left, so the merger will reduce π›½π‘Ÿπ‘’π‘  0 by 1 less than the number of components that were involved. Note that it is not possible to add an edge that is simultaneously a subedge in one fence component and a toplex in another fence component, as the larger fence component must already have contained the smaller one. This means that in order for this kind of merge to take place, the new edge must be exclusively a subedge or toplex of the fence components it is merging. Oftentimes, adding an edge to the hypergraph will not change π›½π‘Ÿπ‘’π‘  0 . This will happen when the edge added is part of exactly one fence component that was already present. It can be either a toplex or a subedge. If an edge is added that only has an inclusion relation with one other edge, then it 93 will not change the restricted homology at all (as in Theorem 3.2.6). If the edge added is a toplex, then it must have at least one subedge and all of its subedges must be totally ordered. Otherwise it would have merged more than one fence component. If the added edge is a subedge, then all of the edges that it is contained in must be able to be totally ordered. (Any subedges of the new edge would be contained in its toplexes as well, so those will not affect π›½π‘Ÿπ‘’π‘  0 .) The first result is what can happen to π›½π‘Ÿπ‘’π‘  β€² 0 when 𝑒 is a subedge. Proposition 6.1.7. † Suppose 𝑒′ is a subedge of edges representing π‘Ÿ different fence components. Then β€² π›½π‘Ÿπ‘’π‘  π‘Ÿπ‘’π‘  0 (H ) = 𝛽0 (H ) βˆ’ (π‘Ÿ βˆ’ 1) Proof. Note that it is impossible for π‘Ÿ to be 0, since 𝑒′ is a subedge of some edge 𝑒 ∈ 𝐸, and that edge must be in a fence component. If π‘Ÿ = 1, then all of the edges 𝑒 with 𝑒′ βŠ‚ 𝑒 are already in the same fence component and so 𝑒′ is also only in that fence component and the number does not change. So let 𝑒 > 1 and choose 𝑒 1 , ..., π‘’π‘Ÿ edges such that each is in a different fence component of H and 𝑒′ βŠ‚ 𝑒𝑖 βˆ€ 1 ≀ 𝑖 ≀ π‘Ÿ. Then for 𝑖 > 1, {𝑒 1 , 𝑒′, 𝑒𝑖 } is a valid fence. Thus all of the 𝑒𝑖 are now in the same fence component, and the number of fence components has been reduced by π‘Ÿ βˆ’ 1. Hence, β€² π›½π‘Ÿπ‘’π‘  π‘Ÿπ‘’π‘  0 (H ) = 𝛽0 (H ) βˆ’ (π‘Ÿ βˆ’ 1) in all cases. β–‘ One example of this theorem is a hypergraph where many edges share a central vertex, as in Figure 6.3. In the hypergraph H , each of those edges is a separate fence component, but after the edge 𝐴 is added into the hypergraph H β€², all of the edges are in the same fence component. Therefore, adding the edge 𝐴 reduced π›½π‘Ÿπ‘’π‘  0 (H ) by four. The second result in this section is what can happen to π›½π‘Ÿπ‘’π‘  β€² 0 when 𝑒 is a toplex. Proposition 6.1.8. † Suppose 𝑒′ is a toplex with subedges representing π‘Ÿ different fence components. Then β€² π›½π‘Ÿπ‘’π‘  π‘Ÿπ‘’π‘  0 (H ) = 𝛽0 (H ) βˆ’ (π‘Ÿ βˆ’ 1). 94 Figure 6.3 A hypergraph where adding the edge 𝐴 reduced π›½π‘Ÿπ‘’π‘  0 (H ) Proof. If π‘Ÿ = 0, then 𝑒′ doesn’t have any subedges, and therefore cannot form a fence with any other edges, so it is a fence component all by itself, thereby increasing π›½π‘Ÿπ‘’π‘  0 by 1. So let π‘Ÿ β‰₯ 1 and choose 𝑒 1 , ..., π‘’π‘Ÿ edges such that each is in a different fence component of H and 𝑒′ βŠƒ 𝑒𝑖 βˆ€ 1 ≀ 𝑖 ≀ π‘Ÿ. Then for 𝑖 > 1, {𝑒 1 , 𝑒′, 𝑒𝑖 } is a valid fence. Thus all of the 𝑒𝑖 are now in the same fence component, and the number of fence components has been reduced by π‘Ÿ βˆ’ 1. Thus β€² π›½π‘Ÿπ‘’π‘  π‘Ÿπ‘’π‘  0 (H ) = 𝛽0 (H ) βˆ’ (π‘Ÿ βˆ’ 1), proving the proposition. β–‘ In the first lemma of this section, it is impossible for π‘Ÿ = 0, but in the second lemma this is possible, and that is the only case where adding an edge can increase π›½π‘Ÿπ‘’π‘  0 . Figure 6.1 serves as a good example for this result. Here both H1 and H2 add a new fence component, increasing π›½π‘Ÿπ‘’π‘  0 from H . This is different from the relative case, in which only H1 increased π›½π‘Ÿπ‘’π‘™ 0 . In both the restricted and relative barycentric homology theories, increasing 𝛽0 by adding an edge seems to have the fewest number of possible causes. It will thus usually be easy to track why π›½π‘Ÿπ‘’π‘™ π‘Ÿπ‘’π‘  π‘Ÿπ‘’π‘™ π‘Ÿπ‘’π‘  0 or 𝛽0 went up, and which new edge caused the increase. If 𝛽0 and 𝛽0 both increased, this can only be the result of a new singleton edge around a vertex that was not present before, which is certainly worth tracking. In the next section, we will dive into results about the effects of adding a vertex into some existing edges. 95 6.2 Adding a Vertex It is natural to consider the effects of adding a vertex to a hypergraph. There might be a new data point that enters into existing relationships, like a new species in an ecosystem. There are two main results in this section. The first applies to the relative barycentric homology of maximum edge hypergraphs, and says that adding a vertex inside of just the maximum edge increases the dimension of all homology cycles by one. We will also give some remarks about under what conditions this can apply to hypergraphs that are not necessarily maximum edge. The second result will give a condition on which adding a vertex to a hypergraph can affect the zeroth dimensional restricted barycentric homology. 6.2.1 The Effects of Adding a Vertex to a Maximum Edge Hypergraph on the Relative Barycentric Homology Let H be a maximum edge hypergraph, as in Definition 2.1.10, with maximum edge 𝑒. Let |𝑒| = π‘š. Suppose a new vertex 𝑣 π‘š+1 is added to H such that 𝑣 π‘š+1 ∈ 𝑒 is only in the maximal edge. Denote the new hypergraph by H β€². Therefore, 𝑉 β€² = {𝑣 1 , 𝑣 2 , ..., 𝑣 π‘š , 𝑣 π‘š+1 }, with new maximum edge 𝑒′ = 𝑉 β€². The edge set is 𝐸 β€² = {{𝑒′ } βˆͺ 𝐸 \ {𝑒}}}, and, thus the hypergraph H β€² is H β€² = {𝑉 β€², 𝐸 β€² }. Theorem 6.2.1 (Add a Vertex Theorem). Suppose H β€² is built from a maximum edge hypergraph H by adding a single vertex into only the maximum edge of H . Then π»π‘›π‘Ÿπ‘’π‘™ (H β€²)  π»π‘›βˆ’1π‘Ÿπ‘’π‘™ (H ) for all 𝑛 β‰₯ 0 (assuming that π»βˆ’1 π‘Ÿπ‘’π‘™ (H ) = 0). Proof. This will be proved by showing that the missing subcomplex 𝑆′ of H β€² is homotopy equivalent to a suspension of 𝑆, the missing subcomplex of H . Recall from [18] that the suspension Σ𝑋 of a topological space 𝑋 is the join of 𝑋 and two points. Another way of thinking about the suspension 96 is as a union of two cones of 𝑋, with the copy of 𝑋 on the bases of the cones identified with itself. Recalling that cones are contractible, and an application of the Mayer-Vietoris sequence from Theorem 2.2.4, gives the result that suspending a space increases the dimension of its homology groups by one, i.e. 𝐻˜ 𝑛+1 (Σ𝑋)  𝐻˜ 𝑛 (𝑋) for all 𝑛 β‰₯ 0. Notice that this result uses the reduced homology of Definition 2.2.11, and is known as the suspension theorem. To ease notation, we will add β€² to constructions pertaining to H β€². Hence, 𝐾 β€² will be the associated simplicial complex of H β€², and in this case, 𝐾 β€² = {𝜎 | 𝜎 βŠ‚ 𝑒′ }. Further, 𝑇 β€² will be the barycentric subdivision of 𝐾 β€², and 𝑆′ will be the subcomplex generated by vertices corresponding to missing subedges of H β€², so, by definition, π»π‘›π‘Ÿπ‘’π‘™ (H β€²) = 𝐻𝑛 (𝑇 β€², 𝑆′). To avoid confusion with the vertex set of the hypergraph, we will use 𝑒 𝜎 to denote vertices in 𝑇 and 𝑇 β€² during this proof. The proof that 𝑆′ is homotopy equivalent to a suspension of 𝑆 will proceed as follows. First, we will describe the set of simplices in 𝑆′, and split it up into three groups. Second, we will show that two of those groups contract to the vertices 𝑒 πœŽπ‘’ and 𝑒 πœŽπ‘£π‘š+1 , respectively. Lastly, we will form two cones with base 𝑆 within 𝑆′, which will finish showing that 𝑆′ is homotopy equivalent to 𝑆. We begin by describing which simplices of 𝑇 β€² are in 𝑆′. Recall that a simplex in 𝑆′, Ξ©, consists of vertices representing simplices in 𝐾 β€² that are missing subedges of H β€². By assumption, 𝑒′ is the only edge of H β€² containing the new vertex 𝑣 π‘š+1 . Therefore, every simplex in 𝐾 β€² containing the vertex 𝑣 π‘š+1 except πœŽπ‘’β€² represents a missing subedge in H β€². Therefore, if 𝑒 𝜏 is a vertex in 𝑇 β€² representing a simplex 𝜏 in 𝐾 β€² that contains 𝑣 π‘š+1 , 𝑒 𝜏 is part of the generating set for 𝑆′. We will denote the set of simplices in 𝑇 β€² containing at least one such vertex 𝑒 𝜏 by 𝑆[𝑣 π‘š+1 ] to indicate their reliance on the new vertex 𝑣 π‘š+1 . Let Ξ© be a simplex in 𝑆′ that is not in 𝑆[𝑣 π‘š+1 ]. Since none of the vertices 𝑒 𝜎 in Ξ© represent simplices 𝜎 in 𝐾 β€² that contain 𝑣 π‘š+1 , Ξ© is in 𝑇. Now there are two cases, Ξ© ∈ 𝑆 or not. Note 𝑆 βŠ‚ 𝑆′ because if a subedge was missing in H , it is still a missing subedge in H β€², as the only edge added to H β€² was 𝑒′, which is not in 𝑆. Suppose though that Ξ© was not in 𝑆. This would mean that at least one simplex represented by a vertex in Ξ© was not in 𝑆, but is missing in H β€². The only edge that is missing in H β€² but was an edge in H is 𝑒. We will refer to simplices Ξ© of 𝑆′ where at least one of 97 the vertices represents the simplex 𝑒 in 𝐾 β€² as 𝑆[𝑒] to denote its containment of the vertex 𝑒 πœŽπ‘’ in 𝑆′. Note that 𝑆 does not intersect 𝑆[𝑒] or 𝑆[𝑣 π‘š+1 ] since neither 𝑒 πœŽπ‘’ nor 𝑒 πœŽπ‘£π‘š+1 is in 𝑆. Also, by the definition of how simplices are constructed in the barycentric subdivision, 𝑆[𝑒] does not intersect 𝑆[𝑣 π‘š+1 ], since in 𝐾 β€², 𝑒 and 𝑣 π‘š+1 do not have an inclusion relation. Therefore 𝑆′ = 𝑆βˆͺ𝑆[𝑒] βˆͺ𝑆[𝑣 π‘š+1 ] and those sets are disjoint. The next step of the proof is to show that 𝑆[𝑒] and 𝑆[𝑣 π‘š+1 ] are contractible. By definition, 𝑆[𝑒] is contractible, since any simplex in 𝑆[𝑒] has 𝑒 πœŽπ‘’ as a vertex. Next we will show that 𝑆[𝑣 π‘š+1 ] is contractible. Let Ξ© be a simplex in 𝑆[𝑣 π‘š+1 ]. This means that one of the vertices 𝑒 𝜏 of Ξ© represents a simplex 𝜏 in 𝐾 β€² that contains 𝑣 π‘š+1 as a vertex. Since 𝑣 π‘š+1 βŠ‚ 𝜏, that subset relationship is represented by an edge in the barycentric subdivision. Therefore, Ξ© βˆͺ 𝑒 πœŽπ‘£π‘š+1 is a simplex in 𝑆′. The set of simplices of the form Ξ© βˆͺ 𝑒 πœŽπ‘£π‘š+1 is contractible to the vertex 𝑒 πœŽπ‘£π‘š+1 , showing that 𝑆[𝑣 π‘š+1 ] is contractible. The last step in the proof that 𝑆′ is homotopy equivalent to a suspension of 𝑆 is to show that 𝑆 connects to both 𝑆[𝑒] and 𝑆[𝑣 π‘š+1 ], which were just shown to be contractible. Recalling that 𝑆 is disjoint from both of those other sets, let Ξ© be a simplex in 𝑆. Because every vertex 𝑒 𝜎 in Ξ© represents a simplex 𝜎 in 𝐾 that is a subset of 𝑒, Ξ© βˆͺ 𝑒 πœŽπ‘’ is a simplex in 𝑆′ and, in particular, in 𝑆[𝑒]. Therefore, 𝑆 connects to 𝑆[𝑒], and since 𝑆[𝑒] is contractible, it forms a cone of 𝑆. Similarly, if Ξ© is a simplex in 𝑆, Ξ© βˆͺ 𝑒 πœŽπ‘£π‘š+1 is a simplex in 𝑆′. This is now a part of 𝑆[𝑣 π‘š+1 ], and forms the other cone of S. We have shown that 𝑆′ is homotopy equivalent to two distinct cones of 𝑆. Thus, 𝑆′ is homotopy equivalent to a suspension of 𝑆. So, from the suspension theorem, for all 𝑛, 𝐻˜ 𝑛 (𝑆)  𝐻˜ 𝑛+1 (𝑆′). From the results on the homology of maximal edge hypergraphs (Theorem 4.2.3), this can be extended to the string of isomorphisms, for 𝑛 β‰₯ 1, 𝐻𝑛+1 π‘Ÿπ‘’π‘™ (H )  𝐻 (𝑆)  𝐻 β€² β€² 𝑛+1 (𝑆 )  𝐻𝑛+2 (H ), proving the theorem in dimensions higher π‘Ÿπ‘’π‘™ 𝑛 than 2. It remains to consider the homology groups π»π‘š π‘Ÿπ‘’π‘™ (H β€²) when π‘š = 0, 1, 2. 𝐻 π‘Ÿπ‘’π‘™ (H β€²) = 0 by 0 Theorem 4.2.6 as 𝑆′ is not empty since 𝑒 πœŽπ‘’ ∈ 𝑆′. 𝐻1π‘Ÿπ‘’π‘™ (H β€²) depends on 𝐻0 (𝑆′) as noted in Corollary 4.2.4. First, suppose that H was a simplicial 98 Figure 6.4 A hypergraph used as an example for Theorem 6.2.1. Z complex to begin with, so that 𝑆 is empty. Then 𝐻0π‘Ÿπ‘’π‘™ (H ) = 2Z , by Theorem 4.2.6. The suspension of the empty set is two disjoint points, so 𝐻0 (𝑆′) = Z 2Z βŠ• Z 2Z . Therefore, by Theorem 4.2.7, 𝐻1π‘Ÿπ‘’π‘™ (H β€²) = Z 2Z = 𝐻0π‘Ÿπ‘’π‘™ (H ). Next, suppose that 𝑆 was not empty. Then 𝐻0π‘Ÿπ‘’π‘™ (H ) = 0 by Theorem 4.2.6. In this case, 𝑆′ must be path connected as a suspension of 𝑆, so by Theorem 4.2.7, 𝐻1π‘Ÿπ‘’π‘™ (H β€²) = 0 In both cases, 𝐻1π‘Ÿπ‘’π‘™ (H β€²)  𝐻0 (H ). Recall that 𝐻2π‘Ÿπ‘’π‘™ (H β€²)  𝐻1 (𝑆′) by Theorem 4.2.3, and since 𝑆′ is the suspension of 𝑆, 𝐻1 (𝑆′)  𝐻˜ 0 (𝑆). Again, when 𝑆 is empty, 𝐻1π‘Ÿπ‘’π‘™ (H )  𝐻˜ 0 (𝑆) = 0, so 𝐻2π‘Ÿπ‘’π‘™ (H β€²) = 0 as well. If 𝑆 is not empty, then the following string of isomorphisms holds from the fact that 𝑆′ is a suspension of 𝑆 and Theorems 4.2.7 and 4.2.3: 𝐻1π‘Ÿπ‘’π‘™ (H )  𝐻˜ 0 (𝑆)  𝐻1 (𝑆′)  𝐻2π‘Ÿπ‘’π‘™ (H β€²). In both cases, 𝐻2π‘Ÿπ‘’π‘™ (H β€²)  𝐻1π‘Ÿπ‘’π‘™ (H ), and this concludes the proof of the theorem in all dimensions. β–‘ The images in Figure 6.4 serve to illustrate this theorem. The hypergraph H has π›½π‘Ÿπ‘’π‘™ 1 (H ) = 1, with all other relative Betti numbers equal to zero. The hypergraph H1 is an example of a single vertex being added to H . As long as the new vertex is added inside only the maximum edge, the theorem holds. Thus π›½π‘Ÿπ‘’π‘™ 2 (H1 ) = 1, and all other Betti numbers are zero. The other hypergraph in the figure, H2 , is different in that the vertex 𝐷 was added into the edge 𝐢 to make a new subedge 𝐢𝐷 as well. This hypergraph has the same relative Betti numbers, and we conjecture that this theorem holds no matter which subedges the new vertex is added into, as long as it is added 99 into the maximum edge. Even if the hypergraph is not a maximum edge hypergraph, it will still sometimes be possible to apply the above theorem. As the theorem shows, if the vertex is added to a maximum edge hypergraph, it suspends the missing subcomplex. Similarly, if a vertex is added into an existing toplex, the subcomplex of the missing subcomplex corresponding to missing subedges of that toplex will likewise be suspended. Therefore, a homology cycle that is entirely contained in the missing subedges of that toplex will see its dimension increase by one. This could also be seen by using the Mayer-Vietoris sequence, if either version applies for that hypergraph. It will not apply in the situation where the new vertex takes an edge that was a subedge and is not included in the edges which that edge was contained in, therefore creating a toplex. That situation will be addressed next for its effects on the restricted barycentric homology. 6.2.2 The Effects of Adding a Vertex on the Zeroth Restricted Barycentric Homology Recall from Theorem 3.2.3 that the restricted barycentric homology of a maximum edge hypergraph H is as follows: ο£±  Z if 𝑛 = 0   ο£² 2Z  𝐻 π‘Ÿπ‘’π‘  (H ) =   0 else.   ο£³ Adding a vertex inside of the maximum edge of a maximum edge hypergraph will not change the fact that is it a maximum edge hypergraph, and so it cannot change the restricted barycentric homology. One case where the number of fence components, and hence the zeroth dimensional restricted barycentric homology, can change is detailed below as the final result of this section. Theorem 6.2.2. Let H be a hypergraph with an edge 𝑒 that is a subedge. Suppose a vertex 𝑣 𝑛+1 is added to the hypergraph such that 𝑣 𝑛+1 is in exactly 𝑒 and its subedges. Then, π›½π‘Ÿπ‘’π‘  0 will increase, by an amount depending on the number of toplexes containing 𝑒. Proof. Let H β€² denote the hypergraph with 𝑣 𝑛+1 . Recall from Theorem 3.2.4 that π›½π‘Ÿπ‘’π‘  0 is the number of fence components. Let 𝑓 be an edge of H such that 𝑒 βŠ‚ 𝑓 . Therefore, by Definition 2.1.13, in H , 𝑒 and 𝑓 are part of the same fence component. In order to prove the theorem, it will suffice to show that in H β€², 𝑒 and 𝑓 are not part of the same fence component. 100 Figure 6.5 A hypergraph used as an example for Theorem 6.2.2. Suppose, to the contrary, that there is a fence 𝑒, 𝑒𝑖1 , 𝑒𝑖2 , . . . , 𝑒𝑖 π‘˜ , 𝑓 between 𝑒 and 𝑓 . By assumption, 𝑒 is the largest edge containing 𝑣 𝑛+1 , and is thus a toplex. Therefore, 𝑒𝑖1 must be a subedge of 𝑒, and, by assumption, must contain 𝑣 𝑛+1 as well. By definition of fence (Definition 2.1.12), 𝑒𝑖1 βŠ‚ 𝑒𝑖2 , so 𝑒𝑖2 also contains 𝑣 𝑛+1 , and is thus a subset of 𝑒. Therefore, 𝑒𝑖3 βŠ‚ 𝑒𝑖2 βŠ‚ 𝑒 and all of the edges in the fence will likewise be subsets of 𝑒. Since 𝑓 is not a subset of 𝑒, there cannot be a fence from 𝑒 to 𝑓 , and they must be in different fence components. β–‘ As an example of this theorem, see the hypergraphs in Figure 6.5. The vertex 𝐷 has been added to hypergraph H to get H β€². That vertex was added inside the edge 𝐡𝐢 to create a new edge 𝐡𝐢𝐷. In H , 𝐡𝐢 is a subedge, but in H β€², 𝐡𝐢𝐷 is a toplex. Note that H has one fence component, but H β€² β€² has two. Therefore, π›½π‘Ÿπ‘’π‘ 0 (H ) = 1, 𝛽0 (H ) = 2, and, as the theorem states, 𝛽0 has increased. π‘Ÿπ‘’π‘  π‘Ÿπ‘’π‘  101 CHAPTER 7 CONCLUSIONS AND FUTURE WORK We will close this thesis by offering some concluding remarks about the implication of its contents as well as some interesting ideas for future research along these lines. Data is rapidly gaining importance in most fields of study, including many that would not have been considered as data science fields even twenty years ago. As technology improves, we have the ability to create larger and more complex data sets. To handle complex data sets, researchers and analysts need more sophisticated methods to model data. One such method is that of hypergraphs. Hypergraphs are useful tools because they serve as generalizations for two common combinatorial objects: graphs and simplicial complexes. Graphs have been used as data models for over 150 years, whereas the science of using simplicial complexes to model data is much more recent. Hypergraphs combine useful features of both graphs and simplicial complexes. Like graphs, they are simply a list of vertices and a list of edges, and like simplicial complexes, they are naturally able to model higher order relationships. Because of the generality of hypergraph structure, they are natural models for many different types of data sets, and sometimes serve as better representations than graphs or simplicial complexes. However, with greater generality comes less rigidity and structure. When researchers study graphs, one question they often ask is about the cycles in those graphs. There is not a canonical notion of what constitutes a cycle in a hypergraph, and, in fact, there are at least five different definitions of a cycle in a hypergraph that all reduce to the definition of a cycle if the hypergraph happens to be a graph. Moreover, since hypergraphs can display higher order relationships, a natural question to ask is if there is any notion of what it would mean for a hypergraph to have a higher order cycle. This is where the idea of homology is useful. A graph can be viewed as a one dimensional simplicial complex, and when it is, the zeroth dimensional homology gives information about the connected components of that graph, and the first dimensional homology gives information about the structure of cycles in the graph. In general, the homology of simplicial complexes gives an 102 interpretation of higher order cycles. Unfortunately, the way in which hypergraphs generalize simplicial complexes means that the definition of the homology of a simplicial complex does not immediately translate to hypergraphs. The question of defining a homology theory for hypergraphs which accurately reflects the way in which hypergraphs generalize simplicial complexes is an important one as data scientists increase their usage of hypergraphs to model data. This thesis contributes towards an answer to that question. Two particular homology theories for hypergraphs, the restricted and relative barycentric ho- mology, were put forth by Emilie Purvine and collaborators [28]. This thesis takes those two theories and significantly develops them in three ways: combinatorially, topologically, and com- putationally. Combinatorially, we discussed new definitions on hypergraphs that allow for these homology theories to be more readily interpreted, such as the supplement of a hypergraph or its fence components. We took concepts standard in algebraic topology, such as the Mayer-Vietoris Sequence or the Long Exact Sequence of a Pair, and adapted them for use with these hypergraph homology theories. These adaptations are useful to simplify calculations of the homology of complicated hypergraphs. Lastly, for data science purposes, everything needs to be computable. We developed methods of building the necessary structures for computation without using the barycentric subdivision, which is computationally unwieldy, and discussed the novel algorithm that is used by HyperNetX for the computation of the restricted and relative barycentric homology of hypergraphs. This thesis helps to make the theories computable and the results interpretable, both necessary ingredients for successful data analysis. There is still more work to be done. We will close by briefly discussing some ideas for future research. To align with the three main areas of contribution, we will discuss potential questions in the combinatorial, topological, and computational directions. As mentioned above, there is a hierarchy of hypergraph acyclicities. One potential question to ask is how those different acyclicity theories fit with the relative and restricted barycentric homology of a hypergraph. Is a hypergraph with certain homology groups guaranteed a specific type of acyclicity? In graph theory, researchers often look for specific subgraphs and the effect that they might have on the properties of the entire 103 graph. Can we do something similar with hypergraph minors, and in particular, is there a certain subedge structure that always generates a homology class? In topology, there is also a notion of singular homology which applies to continuous spaces. For geometric realizations of simplicial complexes, these two notions coincide [18, 24]. One advantage of singular homology is that you can consider the homology of a subspace of a simplicial complex without it needing to be a subcomplex. In particular, we would like to prove that the restricted barycentric homology of a hypergraph H is isomorphic to the singular homology of the associated simplicial complex 𝐾 restricted to the simplices that represent edges in the hypergraph. Similarly, we conjecture that the relative barycentric homology of H is isomorphic to the singular homology of 𝐾 relative to the simplices that represent edges missing from the hypergraph. Recall that some of the theorems on the relative barycentric homology, in particular Theorem 4.2.7, give more information about the edges that are missing from the hypergraph than the edges that are present. To switch this result to a result that gives information about the edges present in the hypergraph, we could define a slightly different version of the relative barycentric homology, where instead of collapsing the missing subcomplex, the restricted barycentric subdivision is collapsed instead. Then, the analogous version of Theorem 4.2.7 would be giving information about the edges that are present in the hypergraph. This would equate Theorem 4.2.7 to Theorem 4.2.9. In general, these two theorems seem to be complementary, and when there is a maximum edge hypergraph on three vertices, they are exactly the same. Just as with many duality theorems in topology, the dimensions of homology discussed in the reference theorems add up to the dimension of the simplicial complex. One interesting question for future research is if this concept can be generalized to a duality theorem for the relative barycentric homology of hypergraphs. For areas relating to computation and data science, there are also some natural next steps. First, the code currently only returns the Betti numbers, and it would be useful to have it also give the generators for the homology classes, to add to the interpretability of the results. Also, real world data is constantly changing and it is important to continue to develop tools to handle dynamic hypergraphs and hypergraph filtrations, along the lines of [25]. Lastly, we would like to apply these 104 methods to real data sets from other disciplines, such as biology or social science, to glean insights useful to researchers in those fields, as well as motivate needed advances in the theory. Because of how quickly the field of data science is growing, researchers are continually trying to develop new methods that can be used to analyze increasingly large and complex data sets while simulataneously maintaining computational feasibility and accurate, interpretable results. This thesis not only gives computational tools towards topological methods for hypergraph analytics in the form of hypergraph homology theories; it also further develops the topology and combinatorics of these methods to make the results of the computational tools meaningfully interpretable. 105 BIBLIOGRAPHY [1] Sinan G. Aksoy et al. β€œHypernetwork science via high-order hypergraph walks”. In: EPJ Data Science 9.1 (2020). doi: 10.1140/epjds/s13688-020-00231-0. [2] Hans-JΓΌrgen Bandelt and Victor Chepoi. β€œMetric graph theory and geometry: a survey”. In: 2006. [3] Federico Battiston et al. β€œNetworks beyond pairwise interactions: Structure and dynamics”. In: Physics Reports 874 (2020). Networks beyond pairwise interactions: Structure and dynamics, pp. 1–92. issn: 0370-1573. doi: https://doi.org/10.1016/j.physrep.2020.05.004. url: https://www.sciencedirect.com/science/article/pii/S0370157320302489. [4] Austin R Benson, David F Gleich, and Desmond J Highan. Higher-order network analysis takes off, fueled by old ideas and new data. 2021. url: https://sinews.siam.org/Details-Page/ higher-order-network-analysis-takes-off-fueled-by-old-ideas-and-new-data. [5] C. Berge. Hypergraphs: Combinatorics of Finite Sets. North-Holland Mathematical Library. Elsevier Science, 1984. isbn: 9780080880235. url: https://books.google.com/books?id= jEyfse-EKf8C. [6] Christian Bick et al. β€œWhat are higher-order networks?” In: CoRR abs/2104.11329 (2021). arXiv: 2104.11329. url: https://arxiv.org/abs/2104.11329. [7] Stephane Bressan et al. The Embedded Homology of Hypergraphs and Applications. 2018. arXiv: 1610.00890. [8] A. Bretto. Hypergraph Theory: An Introduction. Mathematical Engineering. Springer International Publishing, 2013. isbn: 9783319000800. url: https://books.google.com/ books?id=lb5DAAAAQBAJ. [9] F. R. K. Chung and R. L. Graham. β€œCohomological Aspects of Hypergraphs”. In: Trans- actions of the American Mathematical Society 334.1 (1992), pp. 365–388. issn: 00029947. url: http://www.jstor.org/stable/2153987. [10] Alessandro D’Atri and Marina Moscarini. β€œOn Hypergraph Acyclicity and Graph Chordal- ity”. In: Inf. Process. Lett. 29 (1988), pp. 271–274. [11] France Dacar. β€œThe cyclicity of a hypergraph”. In: Discrete Mathematics 182.1 (1998), pp. 53–67. issn: 0012-365X. doi: https://doi.org/10.1016/S0012-365X(97)00133-7. url: https://www.sciencedirect.com/science/article/pii/S0012365X97001337. [12] Reinhard Diestel. Homological aspects of oriented hypergraphs. 2021. arXiv: 2007.09125. [13] Jean-Guillaume Dumas et al. β€œComputing Simplicial Homology Based on Efficient Smith 106 Normal Form Algorithms”. In: Algebra, Geometry and Software Systems. Ed. by Michael Joswig and Nobuki Takayama. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 177–206. isbn: 978-3-662-05148-1. [14] Eric Emtander. β€œBetti Numbers of Hypergraphs”. In: Communications in Algebra 37.5 (2009), pp. 1545–1571. doi: 10.1080/00927870802098158. eprint: https://doi.org/10. 1080/00927870802098158. url: https://doi.org/10.1080/00927870802098158. [15] Ronald Fagin. β€œDegrees of Acyclicity for Hypergraphs and Relational Database Schemes”. In: J. ACM 30.3 (July 1983), pp. 514–550. issn: 0004-5411. doi: 10.1145/2402.322390. url: https://doi.org/10.1145/2402.322390. [16] Song Feng et al. Hypergraph Models of Biological Networks to Identify Genes Critical to Pathogenic Viral Response. 2020. arXiv: 2010.03068. [17] Giorgio Gallo et al. β€œDirected hypergraphs and applications”. In: Discrete Applied Mathematics 42.2 (1993), pp. 177–201. issn: 0166-218X. doi: https://doi.org/10. 1016/0166-218X(93)90045-P. url: https://www.sciencedirect.com/science/article/pii/ 0166218X9390045P. [18] A. Hatcher, Cambridge University Press, and Cornell University. Department of Mathemat- ics. Algebraic Topology. Algebraic Topology. Cambridge University Press, 2002. isbn: 9780521795401. url: https://pi.math.cornell.edu/~hatcher/AT/AT.pdf. [19] Jeffrey Johnson. Hypernetworks in the Science of Complex Systems. IMPERIAL COLLEGE PRESS, 2014. doi: 10.1142/p533. eprint: https://www.worldscientific.com/doi/pdf/10. 1142/p533. url: https://www.worldscientific.com/doi/abs/10.1142/p533. [20] Cliff A. Joslyn et al. β€œHypergraph Analytics of Domain Name System Relationships”. In: Algorithms and Models for the Web Graph. Ed. by BogumiΕ‚ KamiΕ„ski, PaweΕ‚ PraΕ‚at, and PrzemysΕ‚aw Szufel. Cham: Springer International Publishing, 2020, pp. 1–15. isbn: 978- 3-030-48478-1. [21] Cliff A. Joslyn et al. Hypernetwork Science: From Multidimensional Networks to Computa- tional Topology. 2020. arXiv: 2003.11782. [22] Bill Kay et al. β€œHypergraph Topological Features for Autoencoder-Based Intrusion Detection for Cybersecurity Data”. In: International Conference in Machine Learning. ICML- ML4Cyber, July 2022. [23] Luis M. MΓ‘rquez et al. β€œA Virus in a Fungus in a Plant: Three-Way Symbiosis Required for Thermal Tolerance”. In: Science 315.5811 (2007), pp. 513–515. doi: 10.1126/science. 1136237. [24] J.R. Munkres. Elements Of Algebraic Topology. CRC Press, 2018. isbn: 9780429962462. 107 url: https://books.google.com/books?id=-mdQDwAAQBAJ. [25] Audun Myers et al. Topological Analysis of Temporal Hypergraphs. 2023. doi: 10.48550/ ARXIV.2302.02857. url: https://arxiv.org/abs/2302.02857. [26] A.D. Parks, S.L. Lipscomb, and NAVAL SURFACE WARFARE CENTER DAHLGREN VA. Homology and Hypergraph Acyclicity: A Combinatorial Invariant For Hypergraphs. Defense Technical Information Center, 1991. url: https://books.google.com/books?id= kUΔ²kAEACAAJ. [27] Brenda Praggastis. PNNL/HyperNetX: Python package for hypergraph analysis and visual- ization. 2021. url: https://github.com/pnnl/HyperNetX. [28] Emilie Purvine. Homology of Graphs and Hypergraphs. 2021. url: https://www.youtube. com/watch?v=XeNBysFcwOw. [29] Shiquan Ren and Jie Wu. Stability of persistent homology for hypergraphs. 2020. arXiv: 2002.02237. [30] Shiquan Ren, Jie Wu, and Mengmeng Zhang. Relative Embedded Homology of Hypergraphs. 2021. [31] Leo Torres et al. β€œThe why, how, and when of representations for complex systems”. In: SIAM Rev. 63 (2021), pp. 435–485. [32] Michelle L. Wachs. β€œPoset topology: Tools and applications”. In: Geometric Combina- torics, IAS/Park City Mathematics Series. 2004. [33] Chong Wang, Shiquan Ren, and Jian Liu. A KΓΌnneth Formula of Hypergraphs. 2021. arXiv: 2003.05142. [34] J. H. C. Whitehead. β€œSimplicial Spaces, Nuclei and m-Groups”. In: Proceedings of the London Mathematical Society s2-45.1 (1939), pp. 243–327. doi: https://doi.org/ 10.1112/plms/s2-45.1.243. eprint: https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/ 10.1112/plms/s2-45.1.243. url: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10. 1112/plms/s2-45.1.243. 108