arXiv:1501.06754v1 [math.CO] 27 Jan 2015 MATCHING TREES FOR SIMPLICIAL COMPLEXES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS DEMET TAYLAN Abstract. We generalize some homotopy calculation techniques such as splittings and matching trees that are introduced for the computations in the case of the independence complexes of graphs to arbitrary simplicial complexes, and exemplify their efficiency on some simplicial complexes, the devoid complexes of graphs, D(G; F ) whose faces are vertex subsets of G that induce F -free subgraphs, where G is a multigraph and F is a family of multigraphs. Additionally, we compute the homotopy type of dominance complexes of chordal graphs. 1. Introduction In recent years the efficiency of topological methods on solving combinatorial problems has been demonstrated in various papers, whose starting point lies in Lov´asz’s proof of the Kneser’s conjecture. In this guise, determining the homotopy types of simplicial complexes plays a crucial role. When a simplicial complex ∆ is flag, that is, if it is the independence complex ∆ = Ind(G) of a graph G, the underlying combinatorial structure of G can provide enough information that may ease the calculation of the homotopy type. For instance, there exists a reduction technique that splits the independence complex homotopically into a wedge of smaller ones, namely that Ind(G) ≃ Ind(G−x)∨Σ(Ind(G− NG [x]) for any vertex x of the graph that possesses a neighborhood y satisfying NG [y] ⊆ NG [x] in G [1, 14]. Similarly, in the case of the independence complexes, BousquetM´elou, et al. in [5] have introduced the notion of a matching tree in order to construct a Morse matching for Ind(G) and used it to compute the homotopy types of independence complexes of some grid graphs. Our primary aim here is to generalize these techniques that may be in help to compute the homotopy types of non-flag simplicial complexes as well. For example, for an arbitrary simplicial complex ∆ and a subset A ⊆ V (∆), if we define D(A) := {F ∈ ∆ : F ∪ A ∈ / ∆}, then we have the homotopy equivalence ∆ ≃ del∆ (p) provided that there exists a vertex q other than p satisfying D({q}) ⊆ D({p}). Similarly, we introduce the notion of matching trees for an arbitrary simplicial complex by considering the sets D(A) that enables us to construct a Morse matching for such a complex. We exhibit the effectiveness of such generalizations by computing the homotopy types of certain non-flag simplicial complexes. The complexes that we consider are again Date: January 28, 2015. 2000 Mathematics Subject Classification. 05C69, 05C70, 55U10. Key words and phrases. Discrete Morse theory, homotopy type, independence complex, devoid complex, graphs, simplicial complex. ¨ ITAK, ˙ The author is supported by TUB grant no: 111T704. 1 2 DEMET TAYLAN parametrized by graphs. To be more specific, if G is a (multi)graph and F is a family of (multi)graphs, we then define the devoid complex D(G; F ) to be the simplicial complex on V (G) whose faces are those subsets D ⊆ V (G) such that G[D] is F -free (see Section 3 for details). As an application, we compute the homotopy type of D(Cn ; Pk ) as follows: Theorem 5.2. For the devoid complex D(Cn ; Pk ), the following homotopy equivalence holds: k S t(k−1)−1 , if n = (k + 1)t, S t(k−1)−1 , if n = (k + 1)t + 1, D(Cn ; Pk ) ≃ t(k−1)+d−2 S , if n = (k + 1)t + d, t(k−1)+k−2 S , if n = (k + 1)t + k, where 2 ≤ d ≤ k − 1. We further compute the homotopy types of D(Pn ; Pk ) (Theorem 3.10) and D(F ; P3) (Theorem 3.14), where F is a forest. The paper is organized as follows. In Section 2 we recall some basic notions about graphs and simplicial complexes, and collect some necessary topological background. We review the basics of the discrete Morse theory, and recall the construction of Morse matchings via matching trees for independence complexes of graphs which was introduced in [5]. In Section 3 we describe some homotopy reduction techniques for arbitrary simplicial complexes, and apply them to calculate the homotopy type of some devoid complexes. In Section 4 we construct a matching tree as a tool to find Morse matchings for arbitrary simplicial complexes, and apply this machinery to determine the homotopy type of some particular simplicial complexes in Section 5. 2. Preliminaries In this section we recall some general notions and exhibit the tools from discrete Morse theory. 2.1. Graphs. By a graph G we mean an undirected (multi)graph. If G is a graph, V (G) and E(G) (or simply V and E) denote its vertex and edge sets. An edge between u and v is denoted by e = (u, v). A forest is a cycle-free graph, while a tree is a connected forest. If U ⊆ V then G \ U is the graph induced on the vertex set V \ U. We abbreviate G \ {x} to G \ x. The subgraph of G that is induced by U will be denoted by G[U]. The degree of a vertex x in G will be denoted by dG (x). A vertex x of G is called discrete if dG (x) = 0. We denote the set of neighbors of a vertex x of G by NG (x) (or N(x)). The closed neighborhood of a vertex x of G is denoted by NG [x] (or N[x]) and N[x] = N(x) ∪ {x}. If two graphs G and H are isomorphic, we denote it by G ∼ = H. A graph is called F -free if it contains no subgraph which is isomorphic to F , and if F is a family of graphs, then a graph G is said to be F -free, if G is F -free for each F ∈ F . A subset I of the vertex set V of G is called independent if no two vertices of I are adjacent. A matching of G is a set of pairwise disjoint edges. Maximum size of a matching of G is called the matching number of G and denoted by m(G). A subset D of V is said to be a dominating set in G if every vertex not in D is adjacent to at least one vertex of MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 3 D. A vertex cover of G is a subset C ⊆ V such that every edge of G contains a vertex of C. The vertex covering number of a graph G is the minimum size of a vertex cover of G and it is denoted by v(G). Throughout Kn , Cn , Pn will denote the complete, cycle and path graphs on n vertices, respectively. Also Km,n denotes the complete bipartite graph with partitions of size m and n. In particular, a 2-cycle C2 corresponds to a double-edge. The following definition seems to first appear in [2]. Definition 2.1. Let F and G be graphs. An F -matching in G is a set of pairwise vertex disjoint copies of F . An induced F -matching in G is an F -matching such that no additional edge of G is spanned by the vertices of G covered by the matching. Note that a matching is a K2 -matching. We will denote the maximum size of an induced F -matching of a graph G by indF (G). In the particular case where F = Pk , we write indk (G) instead of indPk (G) for any k ≥ 3. A subset S ⊆ V is called a complete of G if G[S] is isomorphic to a complete graph. In particular, a complete that is maximal with respect to inclusion is called a clique of G. A graph G is chordal if every induced cycle in G has length at most 3. A simplicial vertex is a vertex v such that N[v] is a clique. Every chordal graph has a simplicial vertex due to Dirac [6]. 2.2. Simplicial Complexes. An abstract simplicial complex ∆ on a finite vertex set V is a set of subsets of V , called faces, satisfying the following properties: (1) {v} ∈ ∆ for all v ∈ V . (2) If F ∈ ∆ and H ⊆ F , then H ∈ ∆. For a given a subset U ⊂ V , the complex ∆[U] := {σ : σ ∈ ∆ , σ ⊆ U} is called the induced subcomplex by U. If two simplicial complexes ∆ and ∆′ are isomorphic, we denote it by ∆ ∼ = ∆′ . A simplicial complex ∆ is called flag if each of its minimal non-faces consists of two elements. Let ∆ be a simplicial complex. For a given face σ, the link link∆ (σ) and the deletion del∆ (σ) are defined respectively by link∆ (σ) = {τ ∈ ∆ : τ ∩ σ = ∅ and τ ∪ σ ∈ ∆} and del∆ (σ) = {τ ∈ ∆ : τ ∩ σ = ∅}. For a vertex x in ∆, we abbreviate del∆ ({x}) and link∆ ({x}) to del∆ (x) and link∆ (x) respectively. The independence complex of a graph G = (V, E) is the simplicial complex on V consisting independent sets of G and is denoted by Ind(G). The dominance complex of a graph G = (V, E) is the simplicial complex Dom(G) = {σ : V \ σ is a dominating set of G}. Equivalently, the minimal non-faces of Dom(G) are the minimal elements of {N[x] : x ∈ V }. Throughout this paper, S n will denote the n-dimensional sphere. If two topological spaces X and Y are homotopy equivalent, we denote it by X ≃ Y . The join and the wedge of two simplicial complexes ∆0 and ∆1 are denoted by ∆0 ∗ ∆1 and ∆0 ∨ ∆1 , respectively. A simplicial complex ∆ on V is a cone with apex v ∈ V if for every σ ∈ ∆ we have σ ∪ {v} ∈ ∆. A well known fact is that if a simplicial complex ∆ is a cone with apex v, then it is contractible. The suspension of a simplicial complex ∆ and the cone over ∆ will be denoted by Σ∆ and Cone(∆), respectively. The followings are well-known in Combinatorial Topology [10, 3, 11]. 4 DEMET TAYLAN Theorem 2.2. Let ∆ be a simplicial complex. If link∆ (x) is contractible in del∆ (x) for some vertex x of ∆, then ∆ ≃ del∆ (x) ∨ Σ link∆ (x) holds. Theorem 2.3. Let ∆ be a contractible simplicial complex and let Γ be a nonempty subcomplex of ∆. Then the quotient complex ∆/Γ is homotopy equivalent to the suspension Σ(Γ). For spaces X0 , X1 , A with A ⊆ X1 and a map f : A → X0 , the space X0 with X1 attached along A via f is a quotient space obtained from the disjoint union of X0 and X1 by identifying each point a ∈ A with its image f (a) ∈ X0 and is denoted by X0 ⊔f X1 . Theorem 2.4. [10] If (X1 , A) is a CW pair and the two attaching maps f, g : A → X0 are homotopic, then X0 ⊔f X1 ≃ X0 ⊔g X1 . The following theorem is a special instance of the Bj¨orner’s generalized homotopy complementation formula. Theorem 2.5. [4] Let ∆ be a simplicial complex on V and assume that there exists a subset A ⊆ V such that dim(∆[A]) = 0 and ∆[V \ A] is contractible, then we have the homotopy equivalence ∆ ≃ ∨x∈A Σ(link∆ (x)). 2.3. Discrete Morse theory. Discrete Morse theory was introduced by R. Forman in [8], and now it is counted as one of the most powerful techniques in topological combinatorics. The existence of a Morse matching on a simplicial complex ∆ enables us to perform collapses for every matched pair in the matching, and therefore a new CW complex is formed having the same homotopy type with the initial simplicial complex ∆. To every simplicial complex ∆, one can associate a poset P (∆) called the face poset of ∆, which is the set of faces of ∆ ordered by inclusion. Now consider the Hasse diagram of the face poset P (∆) which is a directed graph with edges pointing down from large to small elements. A set M of pairwise disjoint edges of this graph is called a matching of P (∆). So a matching M corresponds exactly to a pairing of faces of ∆ such that each face appears at most once. A matching M is perfect if it covers all elements of the face poset P (∆). When we have the Hasse diagram of the poset P (∆) and a matching M, a modified Hasse diagram can be constructed by reversing the direction of the edges contained in M. A matching M is said to be Morse, if the modified Hasse diagram is acyclic. The main theorem of discrete Morse theory can now be stated as follows. Theorem 2.6. [9] Let ∆ be a simplicial complex with a Morse matching M. Assume that for each i ≥ 0, there are cj unmatched i-dimensional simplices. Then, ∆ is homotopy equivalent to a CW complex with exactly cj cells of each positive dimension i and c0 + 1 cells of dimension 0. Corollary 2.7. Let ∆ be a simplicial complex with a Morse matching M such that cj = 0 for all but one i. Then for this particular i, we have ∆ ≃ ∨ci S i . The following lemma is due to Jonsson [11] that allows us to combine acyclic matchings on families of subsets of a finite set to form a larger acyclic matching. Lemma 2.8. Let ∆0 and ∆1 be disjoint families of subsets of a finite set such that τ σ if σ ∈ ∆0 and τ ∈ ∆1 . If Mi is an acyclic matching on ∆i for i = 0, 1, then M0 ∪ M1 is an acyclic matching on ∆0 ∪ ∆1 . MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 5 2.4. Matching Trees For The Independence Complexes. In this subsection we recall the definition of matching trees which were introduced by Bousquet-M´elou, et al. in [5] to construct a Morse matching on the independence complex Ind(G) of a graph G = (V, E). Let Σ(A, B) := {I ∈ Ind(G) : A ⊆ I and B ∩ I = ∅}, where A, B ⊆ V are two subsets such that A ∩ B = ∅ and N(A) := ∪a∈A N(a) ⊆ B. The nodes of the matching tree represent sets of yet unmatched elements and they are of the form Σ(A, B). The root of the matching tree is I(∅, ∅) = Ind(G), and other nodes are defined recursively as follows. If the node is the empty set, it is declared as a leaf. Otherwise, the node is of the form Σ(A, B), which is a non-empty set. If A ∪ B = V , this node also is declared as a leaf. Then the remaining nodes are of the form Σ(A, B), with A ∪ B = V . Pick a vertex p in V ′ = V \ (A ∪ B) and proceed as follows: • If p has at most one neighbour in V ′ , define ∆(A, B, p) to be the subset of Σ(A, B) formed of sets that do not intersect N(p). So ∆(A, B, p) = {I ∈ Ind(G) : A ⊆ I and B ∩ I = I ∩ N(p) = ∅}. Then M(A, B, p) = {(I, I ∪ {p}) : I ∈ ∆(A, B, p) and p ∈ / I} gives a perfect matching of ∆(A, B, p) and p is called a pivot of this matching. The node Σ(A, B) has a unique child, namely the set U = Σ(A, B) \ ∆(A, B, p) of unmatched elements. If p has no neighbour in V ′ , this set is empty. If p has exactly one neighbour v in V ′ , then U = Σ(A ∪ {v}, B ∪ N(v)). The 3-tuple (A, B, p) is called a matching site of the tree. • Otherwise, choose one neighbour v of p in V ′ . The node Σ(A, B) has two children. The left child is Σ(A, B ∪ {v}) and the right child is Σ(A ∪ {v}, B ∪ N(v)). Here, (A, B, p) is called a splitting site of the tree. Theorem 2.9. [5] For any graph G and any matching tree of G, the matching of Ind(G) obtained by taking the union of all partial matchings M(A, B, p) performed at the matching sites is Morse. 3. Some Reduction Techniques In this section, we introduce some homotopy reduction techniques in greater generality, and provide some applications. Let ∆ be a simplicial complex on V . For a given subset A ⊆ V , we define, D(A) := {H ∈ ∆ : H ∪ A ∈ / ∆}. In particular, if A has only one element p, we simply write D(p) instead of D({p}), and set D[v] := D(v) ∪ {{v}}. Theorem 3.1. Let ∆ be a simplicial complex. If u and v are vertices of ∆ such that D(u) ⊆ D(v), then ∆ is homotopy equivalent to del∆ (v). Proof. Suppose that u and v are vertices of ∆ satisfying D(u) ⊆ D(v). However, this containment implies that link∆ (v) = ∆ \ D[v] that in turn forces link∆ (v) to be a cone with apex u. The theorem now follows from Theorem 2.2. 6 DEMET TAYLAN Example 3.2. Consider the simplicial complex ∆ depicted in Figure 1. Note that we have D(1) = {{3, 4}} and D(2) = {{4}, {1, 4}, {3, 4}} so that D(1) ⊆ D(2) holds. We therefore conclude that ∆ ≃ del∆ (2). 1 2 1 111 000 000 111 000 111 000 111 000 111 000 111 4 ∆ ≃ 3 4 3 Figure 1. Theorem 3.3. Let ∆ be a simplicial complex. If u, v are vertices of ∆ such that D[u] ⊆ D[v], then the following homotopy equivalence ∆ ≃ del∆ (v) ∨ Σ link∆ (v) holds. Proof. We first prove that there is a cone C such that link∆ (v) ⊆ C ⊆ del∆ (v) so that link∆ (v) is contractible in del∆ (v). Assume that A ∈ link∆ (v). It follows that A ∈ / D[v]. However, the assumption D[u] ⊆ D[v] implies that A ∈ / D[u] as well. Therefore, we have that A∪{u} is a face of ∆ so that C = link∆ (v)∗u is the desired cone. Now for the second part, we need to show that the inclusion map i : link∆ (v) → del∆ (v) is null-homotopic. The map H : link∆ (v)×[0, 1] → del∆ (v) defined by H(x, t) = (1−t)x+tu gives the desired homotopy equivalence between the maps i and the constant map c : link∆ (v) → del∆ (v) with c(x) = u. The result now follows from Theorem 2.2. We next consider the homotopical effect of removing a non-face from a simplicial complex, and compare the homotopy type of the resulting complex with that of the initial complex. For a simplicial complex ∆ on V and a minimal non-face K of ∆, we define FK∆ := {F ⊆ V : K ⊆ F such that if K = H F then H ∈ ∆}. Theorem 3.4. Let ∆ be a simplicial complex. If K is a minimal non-face of ∆ such that ∆[K] ∗ link∆′ (K) is contractible in ∆, then we have the following homotopy equivalence: ∆′ ≃ ∆ ∨ Σ(S |K|−2 ∗ link∆′ (K)), where ∆′ = ∆ ∪ {K} ∪ K and K ⊆ FK∆ . Proof. We write ∆′ as a union of two subcomplexes ∆0 = ∆ and ∆1 = K ∗ link∆′ (K). Note that ∆0 ∩ ∆1 = ∆[K] ∗ link∆′ (K) and ∆1 is contractible. Now let i : ∆0 ∩ ∆1 → ∆0 be the identity embedding and let c : ∆0 ∩ ∆1 → ∆0 be any constant map. Since ∆[K] ∗ link∆′ (K) is contractible in ∆0 , the maps i and c are homotopic. It then follows that ∆0 ∪i ∆1 ≃ ∆0 ∪c ∆1 by Theorem 2.4. On the other hand, we have ∆0 ∪c ∆1 ≃ ∆0 ∨ ∆1 /(∆0 ∩ ∆1 ) ≃ ∆0 ∨ Σ(∆0 ∩ ∆1 ) by Theorem 2.3, since ∆0 ∩ ∆1 is contractible in ∆0 . MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 7 Remark 3.5. We note that in the specific case of the independence complexes, Theorems 3.1 and 3.3 reduce to the fold lemma of [7] and the splitting result [1, 14]. Similarly, Theorem 3.4 generalizes the following splitting result of Adamaszek in [1]:If Ind(e ∪ (G \ N[e]) is contractible in Ind(G), then there is a splitting Ind(G \ e) ≃ Ind(G) ∨ Σ2 (Ind(G \ N[e])), where e is an edge of G. Remark 3.6. Recall that for a simplicial complex ∆, the removal of a pair of faces {γ, τ } is called an elementary collapse, if τ is a unique maximal face containing γ and dim(τ ) = dim(γ) + 1. It is a well-known fact in simple-homotopy theory [3, Section 11.1] that an elementary collapse preserves the homotopy type. This result can be proven easily by Theorem 3.4. Namely, since link∆ (γ) = ∗, it follows that ∆′ ≃ ∆ by Theorem 3.4, where ∆ = ∆′ ∪ {γ} ∪ {τ }. Example 3.7. Consider the simplicial complex ∆1 depicted in Figure 2. We note that link∆1 ({b, e}) is contractible so that by Theorem 3.4, that ∆1 is homotopy equivalent to the simplicial complex ∆2 depicted in Figure 2. Furthermore, since ∆3 [{d, e}] ∗ link∆2 ({d, e}) is contractible in ∆3 , we have ∆2 ≃ ∆3 ∨ Σ(S 0 ∗ ∅) by Theorem 3.4 that implies the homotopy equivalence ∆2 ≃ S 1 ∨ S 1 . a d c 1111 0000 0000 1111 0000 1111 b e ∆1 a d a c b d c e ∆2 b ∆3 e Figure 2. Definition 3.8. Let G = (V, E) be a graph and let F be a family of graphs. Then devoid complex D(G; F ) of the graph G with respect to F is a simplicial complex on V whose faces are those subsets S ⊆ V such that G[S] is F -free for all F ∈ F . We particularly note that the independence complexes are examples of devoid complexes, since Ind(G) ∼ = D(G; {K2}) for any (simple) graph G. We also abbreviate D(G; F ) to D(G; F ) whenever F = {F }. We next provide a splitting theorem for a particular devoid complex. Theorem 3.9. Let D(G; F ′) be a devoid complex of a graph G = (V, E) with respect to F ′ , where F ′ = F ∪ {C2 }, and F is a family of graphs such that no member of the family F is isomorphic to a graph that contains an isolated vertex. For a vertex u of G, if G[NG [u]] is a double complete graph (i.e. any two vertices induce a double-edge), then we have the following homotopy equivalence: D(G; F ′) ≃ ∨v∈N (u) Σ(D(G; F ′) \ D[v]) Proof. Since the set A = N(u) satisfies dim(D(G; F ′)[A]) = 0, and D(G; F ′)[V \ A] is contractible, the result follows from Theorem 2.5. 8 DEMET TAYLAN As an application of Theorem 3.1, we next calculate the homotopy type of the devoid complex D(Pn ; Pk ). Theorem 3.10. For the devoid complex D(Pn ; Pk ), the following homotopy equivalence holds: tk−t−1 , if n = (k + 1)t, S tk−t+k−2 D(Pn ; Pk ) ≃ S , if n = (k + 1)t + k, ∗, otherwise where n ≥ k. Proof. We begin by choosing a different labeling of vertices of Pn which is more suitable for our purposes. So, assume that n = (k + 1)t + d, where 0 ≤ d ≤ k, and let the vertices of Pn are labeled as ij where 1 ≤ i ≤ ⌈ n−d ⌉, 1 ≤ j ≤ k + 1, and the vertices ij and rl k+1 form an edge if and only if i = r and |j − l| = 1 or |i − r| = 1 and j = k + 1, l = 1. (1) Suppose that d = 0, i.e. n = (k + 1)t. Since D(11) ⊆ D(1(k + 1)), we have D(Pn ; Pk ) ≃ D(Pn \ 1(k + 1); Pk ). Since D(21) ⊆ D(2(k + 1)) for the complex D(Pn \ 1(k + 1); Pk ), we have D(Pn \ 1(k + 1); Pk ) ≃ D(Pn \ {1(k + 1), 2(k + 1)}; Pk). If we continue in this way, we conclude that D(Pn ; Pk ) ≃ D(Pn \ {1(k + 1), 2(k + 1), . . . , t(k + 1)}; Pk ). The result now follows by noticing that the graph (Pn \{1(k +1), 2(k +1), . . . , t(k + 1)} is isomorphic to t disjoint k-paths. (2) If d ≤ k−1, then D(Pn ; Pk ) is contractible, since when we apply the same procedure as in (1), we obtain (t + 1) disjoint paths, and one of them has length d. (3) Now suppose that d = k. Applying the same procedure as above, the resulting graph is isomorphic to (t + 1) disjoint k-paths. Our next task is to calculate the homotopy type of D(F ; P3), where F is a forest. However, we first need some technical results. Definition 3.11. Let F be a forest and let H be the subgraph of F obtained by removing all leaves in F . Then a vertex x in F is called a saddle vertex of F if the degree of x in H is 1 or 0. Lemma 3.12. Let T be a tree with |T | ≥ 3. Then there exists at least one saddle vertex x of T . Proof. After removing all leaves of the tree T , we obtain a forest, and every forest has a vertex of degree 0 or degree 1. Lemma 3.13. Let T be a tree with |T | ≥ 3. Suppose that T ′ = T \ N[x] and T ′′ = T \ (N[x] ∪ N[w]), where x is a saddle vertex of T , and w is the unique non-leaf neighbour of x (if exists). Then we have the followings: (1) ind3 (T ′′ ) ≤ ind3 (T ) − 1. (2) If dG (x) ≥ 3, then ind3 (T ′ ) = ind3 (T ) − 1. MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 9 Proof. Suppose that T is a tree with |T | ≥ 3 and let T ′ and T ′′ be the subgraphs of T such that T ′ = T \ N[x] and T ′′ = T \ (N[x] ∪ N[w]), where x is a saddle vertex of T . Moreover, let w be the unique non-leaf neighbour of x if it exists. (1) Let a be a leaf neighbour of x in T . Assume that M ′′ is a maximum induced P3 -matching of T ′′ . Then M ′′ ∪ {P } is an induced P3 -matching of T , where P is the 3-path with vertex set {a, x, w} so that the inequality ind3 (T ′′ ) ≤ ind3 (T ) − 1 holds. (2) Now assume that dG (x) ≥ 3. Let a, u ∈ N(x), b ∈ N(w) and c ∈ N(b) be arbitrary vertices of T such that a, u = w, b = x and c = w. If M ′ is a maximum induced P3 -matching of T ′ , then M ′ ∪ {P } is an induced P3 -matching of T , where P is the 3-path with vertices a, x, u; hence, the inequality ind3 (T ′ ) ≤ ind3 (T ) − 1 holds. Now suppose that M is a maximum induced P3 -matching of T . If M contains a 3-path from the subgraph T [N[x] \ {w}], then M can not contain a 3-path with a vertex w. We therefore have ind3 (T ) = |M| = 1 + ind3 (T ′ ). If M contains a 3-path P with vertex set {a, x, w}, then M can not contain any 3-path with a vertex in {a, x, w} or any neighbours of them. We obtain the subgraph T ′′ of T by removing these vertices. Notice that T ′′ is a subgraph of T ′ . We therefore have ind3 (T ) = |M| = 1 + ind3 (T ′′ ) ≤ 1 + ind3 (T ′ ). If M contains a 3-path P with vertices x, w, b, then M can not contain any 3-path with a vertex in {x, w, b} or any neighbours of them. Let T1 be the subgraph of T obtained by removing these vertices. We note in this case that T1 is a subgraph of T ′ . Therefore, we have ind3 (T ) = |M| = 1 + ind3 (T1 ) ≤ 1 + ind3 (T ′ ). If M contains a 3-path P with vertex set {w, b, c}, then M can not contain any 3-path with a vertex in {w, b, c} or any neighbours of them. Let T2 be the subgraph of T obtained by removing these vertices. It is clear that T2 contains all leaf neighbours of x as isolated vertices. Since these vertices have no contribution to the number ind3 (T2 ), we remove them so that the remaining graph T2∗ is a subgraph of T ′ . Therefore, we have ind3 (T ) = |M| = 1 + ind3 (T2 ) = 1 + ind3 (T2∗ ) ≤ 1 + ind3 (T ′ ) which proves the inequality ind3 (T ) ≤ 1 + ind3 (T ′ ). Theorem 3.14. Let F be a forest. Then D(F ; P3) is contractible or is homotopy equivalent to a wedge of spheres of dimension at most 2 ind3 (F ) − 1. Proof. It is enough to prove this for a tree T . If x is a saddle vertex of T , the complex delD(T,{P3 }) (x) is contractible. We therefore have D(T ; P3 ) ≃ Σ linkD(T ;P3 ) (x). Note that linkD(T ;P3 ) (x) ∼ = D(Gx ; {P3 , C2 }). Here, the graph Gx is the graph obtained from T by placing an extra edge (resp. a double-edge) between any two vertices a and b if ab ∈ E (resp. ab ∈ / E), whenever the set {a, b, x} induces a 3-path, and then deleting the vertex x. Observe that if u ∈ NT (x) and u is a leaf, then NGx [u] induces a double complete graph in Gx . Now we apply Theorem 3.9 to conclude the homotopy equivalence: D(T ; P3) ≃ ∨v∈NGx (u) Σ2 (D(Gx ; {P3 , C2 }) \ D[v]). If T ∼ = K1,n , then D(T ; P3) ≃ ∨v∈NGx (u) Σ2 S −1 . Thus D(T ; P3) is homotopy equivalent to a wedge of spheres of dimension 1. On the other hand, if T ≇ K1,n , then there exists a vertex w in T which is the unique non-leaf neighbour of x. If v = w, then we 10 DEMET TAYLAN have D(Gx ; {P3 , C2 }) \ D[v] ≃ D(T ′ ; P3 ), where T ′ = T \ N[x], whereas if v = w, then D(Gx ; {P3 , C2 }) \ D[v] ≃ D(T ′′ ; P3 ), where T ′′ = F \ (NT [x] ∪ NT [w]). Now, if dT (x) = 2, we then have D(T ; P3) ≃ ∨v∈NGx (u) Σ2 (D(Gx ; {P3 , C2 }) \ D[v]) = Σ2 D(T ′′ ; P3 ). It follows that ind3 (T ′′ ) ≤ ind3 (T )−1 by Lemma 3.13. Therefore, D(T ′′ ; P3 ) is contractible or is homotopy equivalent to a wedge of spheres of dimension at most 2(ind3 (T ) − 1) − 1) by the induction; hence, the complex D(T ; P3) is contractible or is homotopy equivalent to a wedge of spheres of dimension at most 2 ind3 (T ) − 1 as claimed. If dT (x) > 2, then D(T ; P3) ≃ ∨|NGx (u)|−1 Σ2 D(T ′ ; P3 ) ∨ Σ2 D(T ′′; P3 ). We analyze every component of this wedge keeping in mind that ind3 (T ′ ) = ind3 (T ) − 1 and ind3 (T ′′ ) ≤ ind3 (T ) − 1 by Lemma 3.13. If a component of this wedge is not contractible then D(T ′ ; P3 ) and D(T ′′ ; P3 ) is homotopy equivalent to a wedge of spheres of dimension at most 2 ind3 (T ′ )−1 and 2 ind3 (T ′′ )−1, respectively. Applying the suspensions, we obtain a wedge of spheres of dimension at most 2 ind3 (T ′ ) − 1 + 2 = 2 ind3 (T ′ ) + 1 = 2(ind3 (T ) − 1) + 1 = 2 ind3 (T ) − 1 or 2 ind3 (T ′′ ) − 1 + 2 ≤ 2(ind3 (T ) − 1) + 1 ≤ 2 ind3 (T ) − 1. This completes the proof. 4. Matching Trees For a Simplicial Complex This section is devoted to the construction of a Morse matching through matching trees for an arbitrary simplicial complex. Our departure in this direction begins by generalizing the notion of matching trees which is due to Bousquet-M´elou, et al. in [5] for the case of the independence complexes. Main motivation for this section comes from the following idea. Let ∆ be a simplicial complex on a vertex set V . We pick an element p of V , and define ∆p = {I ∈ ∆ : if H ∈ D(p) then H I}. Then, we notice that the set of pairs (I, I ∪ {p}) forms a perfect matching of ∆p ; hence, a matching of ∆. We call p the pivot of this matching. The unmatched elements of ∆ are exactly the faces of ∆ which contain at least one element from the family D(p). We now choose another pivot p′ to match some elements of ∆ \ ∆p , and continue the same procedure. Now let us describe the construction of a matching tree to facilitate the study. The nodes of the matching tree represent sets of yet unmatched elements, and they are of the form Σ(A, B) := {I ∈ ∆ : A ⊆ I and ∅ = B I for all B ∈ B}, where A ⊆ V , and for all D ∈ D(A), there exists some B ∈ B such that B ⊆ D, where B is a family of subsets of V for which A ∩ V (B∗ ) = ∅ and B∗ is the subfamily of B consisting of all one point sets of B with ground set V (B∗ ). The root of the matching tree is I(∅, {∅}) = ∆, and other nodes are defined recursively as follows. If the node is the empty set, it is declared as a leaf. Otherwise, the node is of the form Σ(A, B), which is a non-empty set. If A ∪ V (B∗ ) = V , then Σ(A, B) = {A} is a node with an unmatched element of cardinality |A| in which case we also declare this node a leaf. The remaining nodes are of the form Σ(A, B) with A ∪ V (B∗ ) = V . Furthermore, if Σ(A, B) is a child of B′ Σ(A′ , B′ ), we then define Dup (A) to be the set consisting of the minimal elements of the ′ ′ family D(A) ∪ {B \ A : B ∈ B′ }. Now we pick a vertex p in V ′ = V \ (A ∪ V (B∗ )) and proceed as follows: MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 11 B • If there exists at most one element γ ∈ Dup (p) such that B γ for all B ∈ B, we define ∆(A, B, p) to be the subset of Σ(A, B) formed of sets that do not contain B any element from Dup (p), that is, B I for all B ∈ B and if H ∈ Dup (p) then H ∆(A, B, p) = {I ∈ ∆ : A ⊆ I, ∅ = B I}. Then, M(A, B, p) = {(I, I ∪ {p}) : I ∈ ∆(A, B, p) and p ∈ / I} gives a perfect matching of ∆(A, B, p) and p is called a pivot of this matching. We should note that if I ∈ ∆(A, B, p), then I ∪ {p} is in ∆(A, B, p): We clearly B (p), then p ∈ / H so that H I ∪ {p}. have A ⊆ I ∪ {p}. Moreover, if H ∈ Dup We claim that B I ∪ {p} for any B ∈ B. To verify this, assume otherwise that there exists B ∈ B such that B ⊆ I ∪ {p}. However, this forces p ∈ B, since B B I. It follows that there exists some C ∈ Dup (p) such that C ⊆ B \ {p}; hence, C I ∪ {p} which implies that B I ∪ {p}, a contradiction. Therefore, we have B I ∪ {p} as claimed. Now, associate a unique child to the node Σ(A, B), namely the set U = Σ(A, B)\ B ∆(A, B, p) of unmatched elements. Note that if for any γ ∈ Dup (p), there exists some B ∈ B such that B ⊆ γ, then U = ∅. If there exists exactly one element B B (γ)). The (p) such that B γ for all B ∈ B, then U = Σ(A ∪ γ, B ∪ Dup γ ∈ Dup 3-tuple (A, B, p) is called a matching site of the tree. We label the new edge by the pivot p. B (p) satisfying B γ and B γ′ • If there exists at least two elements γ, γ ′ ∈ Dup whenever B ∈ B, then the set U is not of the form Σ(A′ , B′ ). This is because some of the unmatched elements I contain γ, some others do not. However, we eventually want all nodes to be of the form Σ(A′ , B′ ). Such a problem can be resolved by first splitting the original set Σ(A, B) into two disjoint subsets of the form Σ(A′ , B′ ). By using, say γ, we can write Σ(A, B) = Σ(A, B∪{γ})⊎Σ(A∪γ, B∪ B Dup (γ)) and then examine each subset separately. So, the node Σ(A, B) has two B (γ)). children. The left child is Σ(A, B ∪{γ}) and the right child is Σ(A∪γ, B ∪Dup The 3-tuple (A, B, γ) is called a splitting site of the tree. We label the two new edges by γ. Example 4.1. Consider the simplicial complex ∆ depicted in Figure 3. 3 4 2 1 ∆ 5 Figure 3. We will construct a matching tree of ∆, and to simplify the notation, we write D(p) B instead of Dup (p). We choose the vertex 1 as a pivot. The sets {2, 3} and {4} belong to the family D(1). So, the set D(1) has at least two elements. Let us choose one element 12 DEMET TAYLAN from D(1), say {2, 3}. Then Σ(∅, {∅}) has two children, namely they are Σ(∅, {{2, 3}}) and Σ({2, 3}, {{1}, {4}, {5}}). We illustrate it in Figure 4 and label the edge with the chosen set {2, 3}. We have that Σ({2, 3}, {{1}, {4}, {5}}) = {{2, 3}}. We now choose the vertex 2 as a pivot for the node Σ(∅, {{2, 3}}). Then the sets {3} and {4, 5} belong to the family D(2). We next consider the element {3} from the family D(2). Then Σ(∅, {{2, 3}}) has two children, namely they are Σ(∅, {{3}}) and Σ({3}, {{2}, {4}, {5}}). Now let us first find the children of Σ({3}, {{2}, {4}, {5}}). For that purpose, we choose the vertex 1 as a pivot, and it is clearly the only possibility. Now, B = {{2}, {4}, {5}}), and for any γ ∈ D(1), there exists B ∈ B such that B ⊆ γ. Thus, the child of Σ({3}, {{2}, {4}, {5}}) is just the empty family. Now, consider the vertex 2 as a pivot for the node Σ(∅, {{3}}). The node Σ(∅, {{3}}) has only one child, namely Σ({4, 5}, {{1}, {2}, {3}}), since D(2) has exactly one element which does not contain {3}. Thus the unmatched elements of ∆ are {2, 3} and {4, 5}; hence, we conclude that ∆ ≃ S 1 ∨ S 1 . Our matching tree gives the Morse matching {(∅, 2), (1, 12), (4, 24), (5, 25), (3, 13)}. Σ(∅, {∅}) {2, 3} {2, 3} Σ(∅, {{2, 3}}) {3} Σ({2, 3}, {{1}, {4}, {5}}) {3} Σ(∅, {{3}}) Σ({3}, {{2}, {4}, {5}}) 2 1 Σ({4, 5}, {{1}, {2}, {3}}) ∅ Figure 4. Lemma 4.2. Every matching tree satisfies the following properties: (1) For every matching site (A, B, p), the matching M(A, B, p) is a Morse matching of ∆(A, B, p). B (2) Let (A, B, p) be a matching site with a non-empty child Σ(A ∪ γ, B ∪ Dup (γ)). Let B I ∈ ∆(A, B, p) and J ∈ Σ(A ∪ γ, B ∪ Dup (γ)) be given. Then J I. (3) Let (A, B, γ) be a splitting site, and let I ∈ Σ(A, B ∪ {γ}) and J ∈ Σ(A ∪ γ, B ∪ B Dup (γ)) be given. Then J I. Proof. (1) We know that M(A, B, p) is a perfect matching of ∆(A, B, p). Hence, we need only to verify that the modified Hasse diagram of the face poset ∆(A, B, p) is acyclic. Now, consider a directed edge in the modified Hasse diagram. The up MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 13 edges join two elements of the form I \ {p} and I, so they correspond to adding the vertex p. The down edges correspond to deleting a vertex different from p. This cannot lead to a directed cycle; hence, the claim holds. B (2) Assume that J ⊆ I. If J ∈ Σ(A ∪ γ, B ∪ Dup (γ)), then γ ⊆ J. Moreover, if B I ∈ ∆(A, B, p), then γ I, since γ ∈ Dup (p). However, it follows that γ ⊆ J ⊆ I, which in turn implies γ ⊆ I, a contradiction. B (3) If I ∈ Σ(A, B ∪ {γ}) and J ∈ Σ(A ∪ γ, B ∪ Dup (γ)), then we have γ I and γ ⊆ J so that J I as claimed. Theorem 4.3. For any simplicial complex ∆ and any matching tree of ∆, the matching of ∆ obtained by taking the union of all partial matchings M(A, B, p) performed at the matching sites is Morse. Proof. We prove this by backward induction from the leaves to the root, that is, we show that the union of the partial matchings performed at the descendants of a node Γ (including Γ itself) of the matching tree is a Morse matching of Γ. We denote this matching by UM(Γ) (the union of matchings). The empty matching is performed at the leaves of the tree and it is therefore Morse. Now consider a non-leaf node Σ(A, B) of the tree. Suppose that (A, B, p) is a matching site implying M(A, B, p) to be a Morse matching by Lemma 4.2. Since it is a matching site, it has a unique child which is either B empty or of the form Σ(A∪γ, B∪Dup (γ)). If the child is empty, then UM(Γ) = M(A, B, p) B (γ)), then UM(Γ′ ) is which is Morse, and we are done. If the child is Γ′ = Σ(A ∪ γ, B ∪ Dup ′ Morse by induction hypothesis. If we write Γ = ∆(A, B, p) ⊎Γ , then the Morse matchings on ∆(A, B, p) and Γ′ are M(A, B, p) and UM(Γ′ ) respectively. By applying Lemma 2.8 and 4.2, we conclude that UM(Γ) is Morse. Now suppose that (A, B, γ) is a splitting site. If the children are Σ(A, B ∪ {γ}) and B B Σ(A ∪ γ, B ∪ Dup (γ)), then we can write Γ = Σ(A, B ∪ {γ}) ⊎ Σ(A ∪ γ, B ∪ Dup (γ)). By the induction hypothesis, we have the Morse matchings UM(Σ(A, B ∪ {γ}) and UM(Σ(A ∪ B B γ, B ∪ Dup (γ)) on Σ(A, B ∪ {γ}) and Σ(A ∪ γ, B ∪ Dup (γ)) respectively. Once again, by B Lemma 2.8 and 4.2, the union UM(Γ) of UM(Σ(A, B ∪{γ}) and UM(Σ(A∪γ, B ∪Dup (γ)) is Morse. This completes the induction. 5. Some Applications Of Matching Trees on Simplicial Complexes In this section, we compute the homotopy type of some devoid complexes as an application of the techniques introduced in the previous section. In more detail, we calculate the homotopy type of D(Cn ; Pk ) for which we first characterize the unmatched elements of D(Pn ; Pk ) in order to find those of D(Cn ; Pk ). Also note that the case where k = 2 corresponds to the independence complexes of cycles whose homotopy types have already been computed by Kozlov [12, 13]. Furthermore, we calculate the homotopy types of dominance complexes of chordal graphs that complements the work of Marietti and Testa [14, 15]. We assume that the graph Pn has vertex set [1, n] = {1, 2, . . . , n} and two vertices i and j form an edge if and only if |i − j| = 1. Lemma 5.1. For the devoid complex D(Pn ; Pk ), where n ≥ k we have the following properties: 14 DEMET TAYLAN (1) if n = (k + 1)t then there exists a unique unmatched element of cardinality tk − t, (2) if n = (k + 1)t + k then there is a unique unmatched element of cardinality tk − t + k − 1, (3) otherwise, there is no unmatched element in D(Pn , {Pk }). Proof. We choose the vertex 1 as our first pivot. Then the family D(1) has only one element, namely {2, 3, 4, . . . , k}. If n = k = (k+1)t+k = (k+1)0+k, then D({2, 3, 4, . . . , k}) = {{1}}. Note that Σ(∅, {∅}) has a unique child Σ({2, 3, 4, . . . , k}, {{1}}) = {{2, 3, 4, . . . , k}}. Therefore it has a unique unmatched element of cardinality k−1 = k0−0+k−1. This verifies the induction base. Now consider the case where n > k. Then D({2, 3, 4, . . . , k}) = {{1}, {k + 1}} so that Σ(∅, {∅}) has a unique child, namely Σ({2, 3, 4, . . . , k}, {{1}, {k + 1}}). The graph obtained by deleting {2, 3, 4, . . . , k} ∪ {1, k + 1} is Pn−(k+1) ; hence, the unmatched elements of D(Pn ; Pk ) can be obtained by adding the vertices 2, 3, . . . , k to the unmatched elements of D(Pn−(k+1) ; Pk ). Suppose that n = (k + 1)t. Then n−(k+1) = (k+1)t−k−1 = (k+1)(t−1). By the induction hypothesis, we conclude that D(Pn−(k+1) ; Pk ) has a unique unmatched element of cardinality (t−1)k−(t−1). Therefore, D(Pn ; Pk ) has a unique unmatched element of cardinality (t−1)k −(t−1) + k −1 = tk −t. Assume now that n = (k + 1)t + k. Then n − (k + 1) = (k + 1)t + k − k − 1 = (k + 1)t − 1 = (k+1)(t−1)+k. By induction hypothesis D(Pn−(k+1) ; Pk ) has a unique unmatched element of cardinality (t−1)k +k −(t−1)−1 = kt−t. So, the complex D(Pn ; Pk ) has a unique unmatched element of cardinality kt−t+ k −1. Finally, suppose that n = (k + 1)t+ d, where 1 ≤ d ≤ k − 1, which implies that n − (k + 1) = (k + 1)t + d − (k + 1) = (k + 1)t + d − k − 1. However, we then have that the latter is equivalent to (k + 1)t + d by mod(k + 1). More precisely, (k + 1)t + d − k − 1 ≡ (k + 1)t + d − k − 1 + k + 1 ≡ (k + 1)t + d (mod k + 1). By the induction hypothesis, D(Pn−(k+1) ; Pk ) has no unmatched element. Thus, D(Pn ; Pk ) has no unmatched element. This completes the proof. Suppose that the vertex set of Cn is {1, 2, . . . , n} such that i and j form an edge if and only if |i − j| = 1 (mod n) where i, j ∈ {1, 2, . . . , n}. In order to simplify the notation, we write Iij = [i, j] ⊆ [1, n] = {1, 2, . . . , n} for the set {i, i + 1, . . . , j}. Theorem 5.2. For the devoid complex D(Cn ; Pk ), the following homotopy equivalence holds: k S t(k−1)−1 , if n = (k + 1)t S t(k−1)−1 , if n = (k + 1)t + 1 , D(Cn ; Pk ) ≃ t(k−1)+d−2 S , if n = (k + 1)t + d t(k−1)+k−2 S , if n = (k + 1)t + k where 2 ≤ d ≤ k − 1. Proof. We again choose the vertex 1 as our first pivot. Then I(∅, {∅}) = D(Cn ; Pk ) has two children, since the family D(1) has more than one element. If we choose the element I2k = [2, k] from the family D(1), the children are A1 = Σ(∅, {I2k }) and B1 = Σ(I2k , {{1}, {k + 1}}). MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 15 Now we can choose 2 as a pivot element for A1 . There exists at least two elements in D(2) which does not contain I2k for A1 , and we choose I3k from that family. Then the children of A1 are given by A2 = Σ(∅, {I2k , I3k }) = Σ(∅, {I3k }) and k+2 k+2 B2 = Σ(I3k , {I2k , {2}, Ik+1 }) = Σ(I3k , {{2}, Ik+1 }). Similarly, choose now 3 as a pivot for A2 , and consider the element I4k from the family D(3) for A2 . The children of A2 are A3 = Σ(∅, {I2k , I3k , I4k }) = Σ(∅, {I4k }) and k+3 k+3 B3 = Σ(I4k , {I2k , I3k , {3}, Ik+1 }) = Σ(I4k , {{3}, Ik+1 }). We continue in this manner by branching each new Ai using the vertex i + 1 as a pivot and denoting the children of Ai by Ai+1 and Bi+1 . We stop this procedure when we reach the pivot k − 1. We write the last two branchings in details. When we have that k − 2 is our pivot, Ak−3 has two children, namely k k Ak−2 = Σ(∅, {I2k , I3k , I4k , . . . , Ik−1 }) = Σ(∅, {Ik−1 }) and k k 2k−2 k 2k−2 Bk−2 = Σ(Ik−1 , {I2k , I3k , . . . , Ik−2 , {k − 2}, Ik+1 }) = Σ(Ik−1 , {{k − 2}, Ik+1 }). We take k − 1 as a pivot for Ak−2 so that the children of Ak−2 are k Ak−1 = Σ(∅, {I2k , I3k , I4k , . . . , Ik−1 , {k}}) = Σ(∅, {{k}}) and k 2k−1 2k−1 Bk−1 = Σ({k}, {I2k , I3k , . . . , Ik−1 , {k − 1}, Ik+1 }) = Σ({k}, {{k − 1}, Ik+1 }). Now note that Ak−1 = Σ(∅, {{k}}) = D(Pn−1 ; Pk ). Furthermore, the graph obtained by deleting I2k ∪ {1, k + 1} is Pn−(k+1) . Thus the elements of B1 can be obtained by adding 2, 3, . . . , k to the unmatched elements of D(Pn−(k+1) ; Pk ). So, we only need to examine the sets Bi for all 2 ≤ i ≤ k − 1. A typical element of these sets can be written of the form k 2k−l Bk−l = Σ(Ik−l+1 , {{k − l}, Ik+1 }). Note that B1 corresponds to the case where k − l = 1 so that we assume that k − l = 1, and by using appropriate pivots, we next describe the children of Bk−l . We choose {k − l − 1} as a pivot. Since no element in Bk−l contains {k − l}, it follows k−l−2 . At this point, we should also that D(k − l − 1) has only one element, namely In−l k−l−2 note that |In−l | = k − 1. Thus there exists a unique child of Bk−l , and its child is Ck−l−1 = Σ(A, B), where k k−l−2 A = Ik−l+1 ∪ In−l 16 DEMET TAYLAN and 2k−l B = {{k − l}, Ik+1 , {k − l − 1}, {n − l − 1}}. We now consider {n − l − 2} as a pivot. Since no element in Ck−l−1 contains {n − l − 1}, there exists a unique child Cn−l−2 = Σ(A, B) of Ck−l−1, where k k−l−2 n−l−3 A = Ik−l+1 ∪ In−l ∪ In−l−k−1 , 2k−l B = {{k − l}, Ik+1 , {k − l − 1}, {n − l − 1}, {n − l − 2}, {n − l − k − 2}}. If we choose n − l − k − 3 as the pivot, Cn−l−2 has a unique child Cn−l−k−3 = Σ(A, B), where k−l−2 n−l−3 n−l−k−4 k A = Ik−l+1 ∪ In−l ∪ In−l−k−1 ∪ In−2k−l−2 B = {{k − 2k−l l},Ik+1 , {k and − l − 1}, {n − l − 1}, {n − l − 2}, {n − l − k − 2}, {n − l − k − 3}, {n − 2k − l − 3}}. We continue in the same fashion until we reach the element 3k − l + d + 1 as our pivot in which case the unique child is C3k−l+d+1 = Σ(A, B), where k k−l−2 n−l−3 n−l−k−4 3k−l+d A = Ik−l+1 ∪ In−l ∪ In−l−k−1 ∪ In−2k−l−2 ∪ · · · ∪ I2k−l+d+2 and 2k−l B = {{k − l},Ik+1 , {k − l − 1}, {n − l − 1}, {n − l − 2}, {n − l − k − 2}, {n − l − k − 3}, {n − 2k − l − 3}, . . . , {3k − l + d + 1}, {2k − l + d + 1}}. Now assume that n = (k + 1)t + d, where d ≥ 0. We can choose 2k − l + d as a pivot so that the unique child is C2k−l+d = Σ(A, B), where k k−l−2 n−l−3 n−l−k−4 3k−l+d 2k−l+d−1 A = Ik−l+1 ∪ In−l ∪ In−l−k−1 ∪ In−2k−l−2 ∪ · · · ∪ I2k−l+d+2 ∪ Ik−l+d+1 , and 2k−l B = {{k − l}, Ik+1 , {k − l − 1}, {n − l − 1}, {n − l − 2}, {n − l − k − 2}, {n − l − k − 3}, {n − 2k − l − 3}, . . . , {3k − l + d + 1}, {2k − l + d + 1}, {2k − l + d}, {k − l + d}}. We will examine this case in detail: Case.1: Suppose that d = 0. Then the node above is C2k−l = Σ(A, B), where k k−l−2 n−l−3 n−l−k−4 3k−l 2k−l−1 A = Ik−l+1 ∪ In−l ∪ In−l−k−1 ∪ In−2k−l−2 ∪ · · · ∪ I2k−l+2 ∪ Ik−l+1 B = {{k − 2k−l l}, Ik+1 , {k and − l − 1}, {n − l − 1}, {n − l − 2}, {n − l − k − 2}, {n − l − k − 3}, {n − 2k − l − 3}, . . . , {3k − l + 1}, {2k − l + 1}, {2k − l}}. Note that there is no more vertices that we can use as a pivot, since A∪V (B∗ ) = V (Cn ). 2k−l−1 k−l−2 n−l−3 n−l−k−4 3k−l k Moreover, we have Ik−l+1 ⊂ Ik−l+1 so that In−l ⊎ In−l−k−1 ⊎ In−2k−l−2 ⊎ · · · ⊎ I2k−l+2 ⊎ 2k−l−1 Ik−l+1 is the unique unmatched element of cardinality t(k − 1). Case.2: Assume that 1 ≤ d ≤ k − 1. • Suppose first that d ≤ l. We return back to the pivot 2k − l + d. If there is an element in D(2k − l + d), it must be of the form [k − l + d + 1, 2k − l + d − 1], since no set in C3k−l+d+1 contains {2k − l + d + 1}. Observe that k − l + d + 1 ≤ k + 1 due to the assumption that d ≤ l. Therefore the set [k − l + d + 1, 2k − l + d − 1] must contain the set [k + 1, 2k − l] which is impossible, since no set in C3k−l+d+1 MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 17 contains [k + 1, 2k − l]. Thus C3k−l+d+1 has no children implying that there is no unmatched element. • Assume that d = l + 1. We then have C2k−l+d = C2k+1 = Σ(A, B), where k k−l−2 n−l−3 n−l−k−4 3k+1 2k A = Ik−l+1 ∪ In−l ∪ In−l−k−1 ∪ In−2k−l−2 ∪ · · · ∪ I2k+3 ∪ Ik+2 and 2k−l B = {{k − l}, Ik+1 , {k − l − 1}, {n − l − 1}, {n − l − 2}, {n − l − k − 2}, {n − l − k − 3}, {n − 2k − l − 3}, . . . , {3k + 2}, {2k + 2}, {2k + 1}, {k + 1}}. k−l−2 n−l−3 n−l−k−4 3k+1 k 2k Therefore, Ik−l+1 ⊎ In−l ⊎ In−l−k−1 ⊎ In−2k−l−2 ⊎ · · · ⊎ I2k+3 ⊎ Ik+2 is the unique unmatched element of cardinality t(k − 1) + l = t(k − 1) + d − 1. • Now suppose that l + 2 ≤ d ≤ k and choose k − l + d − 1 as a pivot. Any set k−l+d−2 in D(k − l + d − 1) must be of the form Id−l . Since d − l ≤ k − l, this set must contain the vertex k − l. However this is impossible, since no set in C2k−l+d contain k − l. Thus there exists no unmatched element. We next summarize the results we have so far in order to complete the proof: (1) n = (k + 1)t. We recall that Ak−1 = Σ(∅, {{k}}) = D(Pn−1; Pk ). Since n − 1 = (k + 1)t − 1 = (k + 1)(t − 1) + k, we conclude that Ak−1 has a unique unmatched element of cardinality t(k − 1). Also recall that the elements of B1 can be obtained by adding 2, 3, . . . , k to the unmatched elements of D(Pn−(k+1) ; Pk ). Since n − (k + 1) = (k + 1)t − k − 1 = (k + 1)(t − 1), it follows that B1 has a unique unmatched element of cardinality (t − 1)k − (t − 1) + k − 1 = t(k − 1). For each Bi , there is a unique unmatched element of cardinality t(k − 1), where 2 ≤ i ≤ k − 1. We therefore have k unmatched elements of cardinality t(k − 1) in this case. (2) n = (k + 1)t + 1. Only Ak−1 has an unmatched element and its cardinality is t(k − 1). (3) n = (k + 1)t + d with 2 ≤ d ≤ k − 1. The only unmatched element comes from a Bi in the case d = l + 1, and its cardinality is t(k − 1) + d − 1. (4) n = (k + 1)t + k. Then there exists a unique unmatched element coming from B1 of cardinality t(k − 1) + k − 1. Our next task is to compute the homotopy types of dominance complexes of chordal graphs as we promised. Lemma 5.3. Let G be a (simple) graph with a vertex u such that the set N[u] induces a clique in G. Then v(G′ ) = v(G) − dG (u), where G′ = G − N[u]. Proof. Assume that C is a minimum covering set for G. Then C must contain a set A having exactly dG (u) elements from N[u], since otherwise there would be some edges in G[N[u]] that is not covered. It follows that C \ A covers G′ . We therefore have v(G′ ) ≤ v(G) − dG (u). Now, let C ′ be a minimum covering set for G′ . Clearly C ′ ∪ N(u) is a covering set for G so that v(G) ≤ v(G′ ) + dG (u). Theorem 5.4. Let G be a chordal graph. Then the dominance complex Dom(G) of G is homotopy equivalent to a sphere of dimension v(G) − 1. 18 DEMET TAYLAN Proof. We show by an induction that there exists a unique unmatched element in Dom(G) of cardinality v(G). Since G is a chordal graph, there exists a vertex u such that N[u] is a clique. We choose u as a pivot. Then the family D(u) has only one element, namely N(u). Therefore, Σ(∅, {∅}) has a unique child Σ(A, B), where A = N(u) and B consists of the sets of minimal elements of B′ = {N[x] ∩ (V \ N[u]) : x is adjacent to one of the vertices in N(u)} ∪ {{u}}. Now, if we write G′ = G−N[u], then we note that the elements in Σ(A, B) can be obtained by adding N(u) to the unmatched elements of Dom(G′ ). So, Dom(G′ ) has a unique unmatched element of dimension v(G′ ) by the induction; hence, the complex Dom(G) has a unique unmatched element of dimension v(G′ ) + dG (u) = v(G) − dG (u) + dG (u) = v(G). Lemma 5.5. Let T be a tree with a saddle vertex x. If the vertex a is the unique non-leaf neighbour of x, then m(T ) = m(T ∗ ) + 1, where T ∗ = T \ (N[x] \ {a}). Proof. Assume that x is a saddle vertex of T , and let a be the unique non-leaf neighbour of x. Suppose further that M ∗ is a maximum matching of T ∗ . Let u be a leaf neighbour of x. Clearly, the set M ∗ ∪{(u, x)} is a matching of T so that m(T ) ≥ m(T ∗ )+1. Let M be a maximum matching of T . If M contains an edge from the subgraph G[N[x] \ {a}], say the edge (u, x), then M \{(u, x)} is a matching of T ∗ ; hence, m(T ∗ ) ≥ |M|−1 = m(T )−1. If M contains the edge (x, a), then M \{(x, a)} is a matching of T ′ , where T ′ is a subgraph of T ∗ obtained by deleting N[x] from T . Thus we have m(T ∗ ) ≥ m(T ′ ) ≥ |M| − 1 = m(T ) − 1. Finally, note that all the other possibilities are covered by one of these two cases. Theorem 5.6. [14, 15] The dominance complex Dom(F ) of a forest F is homotopy equivalent to a sphere of dimension m(F ) − 1. Proof. It is enough to verify this for a tree T . Suppose that x is a saddle vertex of T , and let the vertex u in T be a leaf neighbour of x. We choose u as a pivot. Then the family D(u) has only one element, that is, D(u) = {{x}}. Therefore, Σ(∅, {∅}) has a unique child Σ(A, B), where A = {x} and B consists of the sets of minimal elements of B′ = {N[y] ∩ (V \ N[u]) : y is adjacent to x} ∪ {{u}}. Now let T ∗ be the graph obtained by deleting N[x] \ {a}, where a is the unique non leaf neighbour of x. Then the elements in Σ(A, B) can be obtained by adding {x} to the unmatched elements of Dom(T ∗ ). Since the complex Dom(T ∗ ) has a unique unmatched element of dimension m(T ∗ ) by the induction, we conclude that Dom(T ) has a unique unmatched element of dimension m(T ∗ ) + 1, which is equal to m(T ) by Lemma 5.5. Acknowledgement I would like to thank Professor Yusuf Civan for introducing me the devoid simplicial complexes and for his invaluable comments and generous encouragement. References [1] M. Adamaszek, Splittings of independence complexes and the powers of cycles, J. Combinatorial Theory, Series A, 119:5, (2012), 1031-1047. MATCHING TREES AND HOMOTOPY TYPE OF DEVOID COMPLEXES OF GRAPHS 19 [2] N. Alon, S. Haber and M. Krivelevich, The number of F -matchings in almost every tree is a zero residue, Elect. J. Comb., 18:1, (2011), #P30. [3] A. Bj¨orner, Topological methods, Handbook of Combinatorics, Vol. 1,2, Elsevier, Amsterdam, (1995), 1819-1872. [4] A. Bj¨orner, A general homotopy complementation formula, Discrete Mathematics, 193, (1998), 8591. [5] M. Bousquet-M´elou, S. Linusson and E. Nevo, On the independence complex of square grids, J. Algebraic Combin., 27:4, (2008), 423-450. [6] G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, (1961), 71-76. [7] A. Engstr¨om, Complexes of directed trees and independence complexes, Discrete Mathematics, 309, (2009), 3299-3309. [8] R. Forman, Morse theory for cell complexes, Adv. Math., 134:1, (1998), 90-145. [9] R. Forman, A user’s guide to discrete Morse theory, Sem. Lothar. Combin., 48, (2002), B48c. [10] A. Hatcher, Algebraic topology, Cambridge University Press, (2002). [11] J. Jonsson, Simplicial complexes of graphs, Springer, (2008). [12] D. Kozlov, Complexes of directed trees, J. Combinatorial Theory, Series A, 88, (1999), 112-122. [13] D. Kozlov, Combinatorial algebraic topology, Springer, (2008). [14] M. Marietti and D. Testa, Cores of simplicial complexes, Discrete Comput. Geom., 40, (2008), 444-468. [15] M. Marietti and D. Testa, A uniform approach to complexes arising from forests, Elect. J. Comb., 15, (2008), #R101. Department of Mathematics, University Of Bremen, 28359 Bremen, Germany E-mail address: [email protected] Department of Mathematics, Bozok University, Yozgat, 66900, Turkey. E-mail address: [email protected]

© Copyright 2016 ExploreDoc