PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 92(106) (2012), 43–51 DOI: 10.2298/PIM1206043J

COMPLEXES OF DIRECTED TREES OF COMPLETE MULTIPARTITE GRAPHS

Duško Jojić

Communicated by Rade Živaljević

Abstract. For every directed graph D we consider the complex of all directed subforests Δ(D). The investigation of these complexes was started by D. Kozlov. We generalize a result of Kozlov and prove that complexes of directed trees of complete multipartite graphs are shellable. We determine the h-vector of Δ(\overrightarrow{K}_{m,n} ) and the homotopy type of Δ(\overrightarrow{K}_{n_{1} ,n_{2} ,... ,n_{k}} ).

1. Introduction

A directed tree is a tree in which one vertex is selected as the root and all edges are oriented away from the root. If T = (V (T), E(T)) is a directed tree with root r, then for every x ∈ V (T) there exists a unique directed path from r to x. We say that a vertex y is below vertex x in a directed tree T if there exists a unique directed path from x to y. A directed forest is a family of disjoint directed trees. In this paper we write \overrightarrow{xy} for a directed edge from x to y.

An abstract simplicial complex Δ is a collection of finite nonempty sets such that A ⊆ B ∈ Δ ⇒ A ∈ Δ. The element A of Δ is called a face ( simplex) of Δ and its dimension is |A| − 1. The vertex set of Δ is the union of all faces of Δ. The dimension of the complex Δ is defined as the largest dimension of any of its faces. A facet of Δ is any simplex that is not a face of any larger simplex of Δ. A simplicial complex is pure if every of its facets has the same dimension. We denote the number of i-dimensional faces of Δ by f_{i}, and f(Δ) = (f_{−1} , f_{0}, …, f_{d−1} , f_{d}) is called the f-vector. A new invariant, the h-vector of a d-dimensional complex Δ is h(Δ) = (h_{0}, h_{1}, …, h_{d}, h_{d+1} ) defined by the formula

h_{k} = ∑_{i=0}^{k} (−1)^{k−i} \binom{d + 1 − i}{d + 1 − k} f_{i−1} .

We refer the reader to [8] for definitions of topological concepts used in this paper.

2010 Mathematics Subject Classification: Primary 52B22 ; Secondary 05C20.

Key words and phrases: shellability, directed trees, multipartite graph.

Definition 1.1. Let D be a directed graph. The vertices of the complex of directed trees Δ(D) are oriented edges of D. The faces of Δ(D) are all directed forests that are subgraphs of D.

The question of shellability of complexes of directed trees was posed by R. Stanley. Kozlov in [6] showed that the existence of a complete source in a directed graph provides a shelling of its complex of directed trees. The complex of directed trees of a graph G is recognized in [3] as a discrete Morse complex of a 1-dimensional complex. These complexes are also studied in [4] and [7].

Geometrically, a shelling of a cell complex is a way of gluing it together from its maximal cells in a well-behaved way. In this paper we use the following definition of shellability for pure simplicial complexes.

Definition 1.2. A pure simplicial complex Δ is shellable if there exists a linear ordering (shelling order) F_{1}, F_{2}, …, F_{k} of facets of Δ such that for every i < j ⩽ k there exist some l < j and a vertex v of F_{j} such that

F_{i} ∩ F_{j} ⊆ F_{l} ∩ F_{j} = F_{j} ∖ {v}.

For a fixed shelling order F_{1}, F_{2}, …, F_{k} of Δ, the restriction R(F_{j}) of the facet F_{j} is defined by R(F_{j}) = {v is a vertex of F_{j} : F_{j} ∖ {v} ⊂ F_{i} for some 1 ⩽ i < j}. The type of the facet F in the given shelling order is the cardinality of R(F), i.e., type(F) = |R(F)|. If we build up Δ according to a shelling order, then R(F) is the unique minimal new face that appears when we add the facet F. For a shellable simplicial complex we have the following combinatorial interpretation of its h-vector: h_{k}(Δ) = |{F is a facet of Δ : type(F) = k}|. Further, we know that a shellable d-dimensional simpilicial complex Δ is homotopy equivalent to a wedge of h_{d} spheres of dimension d. A set of maximal simplices G of Δ is a generating set of simplices if the removal of interiors of all simplices from G makes Δ contractible. For a shellable simplicial complex Δ the set of simplices G = {F is a facet of Δ : R(F) = F } is a generating set of Δ, i.e., the simplicial complex Δ ∖ (⋃ _{F ∈G} F ) is contractible.

For more information on shellability see [1], [2] and chapter 8 of [9].

2. Graphs with a dominant pair

Kozlov in [6] used the following variant of a shelling. Let F(Γ) denote the set of all facets of a pure simplicial complex Γ. Assume that we can partition F(Γ) into the blocks F_{0}, F_{1}, F_{2}, …, F_{m} such that the following holds:

|F_{0}| = 1; for all i ⩽ j and two different facets F ∈ F_{i}, F′ ∈ F_{j} ,

(2.1) there exists k < j, a facet F′′∈ F_{k}, and a vertex v ∈ F′ such that F ∩ F′ ⊆ F′′∩ F′ = F′∖ {v}.

It is easy to check that any linear order that refines partition F_{0}, F_{1}, F_{2}, …, F_{m} (for i < j we list facets from F_{i} before facets from F_{j}) is a shelling order of Γ in the sense of Definition 1.2.

A vertex c is a complete source in a digraph D if \overrightarrow{cx} ∈ E(D) for all x ∈ V (D) ∖ {c}. The partition of F(Δ(D)) defined by Kozlov in [6] substantially uses the out-degree d_{T}(c) = |\{x : \overrightarrow{cx} ∈ E(T)\}| of c:

F_{i} = {T ∈ F(Δ(D)) : d_{T}(c) − 1 − i}.

It is not complicated to prove for a digraph with a complete source, that the above partition of the facets of Δ(D) satisfies the condition described in (2.1) (see the proof of Theorem 3.1 in [6]).

We now describe a broader family of graphs whose complexes of directed trees are shellable. For a directed graph D and a vertex u ∈ V (D) we set N(u) = {x ∈ V (D) : \overrightarrow{ux} ∈ E(D)\}. We say that a directed graph D has a dominant pair of vertices if there exist vertices u, v ∈ V (D) such that

(i) V (D) = N(u) ∪ N(v). Therefore, we have that \overrightarrow{uv}, \overrightarrow{vu} ∈ E(D).

(ii) For all x ∈ N(u)∖N(v) and y ∈ N(v)∖N(u) we have that \overrightarrow{xy}, \overrightarrow{yx} ∈ E(D).

Theorem 2.1. If a directed graph D has a dominant pair of vertices the complex Δ(D) is shellable.

Proof. We will define a partition of the facets of Δ(D) and show that this partition satisfies (2.1). Recall that facets of the complex Δ(D) correspond to subtrees of D.

Let D be a graph with a dominant pair of vertices u, v. For a directed tree T with the root r let h_{T}(x) denotes the length of the unique directed path from r to x. We classify directed trees of D by using d_{T}(u), d_{T}(v), h_{T}(u) and h_{T}(v). The trees of D in which the above defined parameters are the same form a block

F_{p,q,r,s} = {T : d_{T}(u) = p, d_{T}(v) = q, h_{T}(u) = r, h_{T}(v) = s}

of our partition of the facets of Δ(D). We say that F_{p,q,r,s} is before F_{p′,q′,r′,s′} , and write F_{p,q,r,s} < F_{p′,q′,r′,s′} , if and only if p > p′, or p = p′ and q > q′, or p′ = p, q = q′ and r < r′, or p′ = p, q = q′, r = r′ and s < s′. Note that the first block in this partition F_{|N(u)|,|N(v)∖N(u)|−1,0,1} contains only the tree with the edge set \{\overrightarrow{ux} : x ∈ N(u)\} ∪ \{\overrightarrow{vy}: y ∈ N(v) ∖ (N(u) ∪ \{u\}) \}.

Now, we consider two different directed trees T ∈ F_{p,q,r,s} , T′ ∈ F_{p′,q′,r′,s′} such that F_{p,q,r,s} ⩽ F_{p′,q′,r′,s′} . Assume that the edges E(T) ∩ E(T′) span a directed forest F = T_{1} ∪ T_{2} ∪ ⋯∪ T_{m}, and let r_{i} denote the root of T_{i}. Assume that r_{i_{0}} is the root of T′. Note that E(T′) ∖ E(T) contains m − 1 edges of the form \overrightarrow{xr_{i}}, where i ≠ i_{0}.

The following analysis will show that there is a tree T′′such that T, T′ and T′′ satisfy the conditions described in (2.1). First, we consider the case when u, v are in the same tree of F (w.l.o.g. we assume v, u ∈ T_{1}).

(1) If the root of T′ is a vertex r_{i} ≠ r_{1}, then there exists \overrightarrow{xr_{1}} ∈ E(T′) ∖ E(T) such that x ≠ u and x ≠ v. We set T′′= T′∖ \{\overrightarrow{xr_{1}} \} ∪ \{\overrightarrow{ur_{i}} \} (if r_{i} ∈ N(u)) or T′′= T′∖ \{\overrightarrow{xr_{1}} \} ∪ \{\overrightarrow{vr_{i}}\} (if r_{i} ∉ N(u)).

(2) Assume that r_{1} is the root of T′. If there is a vertex r_{j} ∈ N(u) for some j > 1, the assumption d_{T}(u) ⩾ d_{T′}(u) guarantees that there exists an edge \overrightarrow{xr_{i}} ∈ E(T′) ∖ E(T) such that x ≠ u, i > 1 and r_{i} ∈ N(u). Otherwise, if all of the edges \overrightarrow{ur_{i}} (for all r_{i} ∈ N(u), i > 1) are contained in E(T′), then we obtain that d_{T}(u) < d_{T′}(u). In the above described situation we set T′′= T′∖ \{\overrightarrow{xr_{i}} \} ∪ \{\overrightarrow{ur_{i}} \}. If r_{i} ∈ N(v) ∖ N(u) for all i = 2, 3, …, m, then there exists \overrightarrow{yr_{i}} ∈ E(T′) ∖ E(T), such that y ≠ v (otherwise we obtain that d_{T}(u) = d_{T′}(u) and d_{T}(v) < d_{T′}(v)). Then we set T′′= T′∖ \{\overrightarrow{yr_{i}}\} ∪ \{\overrightarrow{vr_{i}}\}.

Now, we consider the situation when the vertices u and v belong to different trees of F (w.l.o.g. we assume that u ∈ T_{1} and v ∈ T_{2}).

(3) If the root of T′ is r_{i}, r_{i} ≠ r_{1} and r_{i} ∈ N(u), then there exists \overrightarrow{xr_{1}} ∈ E(T′) ∖ E(T) such that x ≠ u and we set T′′= T′∖ \{\overrightarrow{xr_{1}} \} ∪ \{\overrightarrow{ur_{i}} \}.

(4) If the root r_{i} of T′ (again r_{i} ≠ r_{1}) is not contained in N(u) and r_{i} ≠ r_{2}, then

there exists \overrightarrow{xr_{2}} ∈ E(T′) ∖ E(T). If x ≠ u we set T′′= T′∖ \{\overrightarrow{xr_{2}} \} ∪ \{\overrightarrow{vr_{i}}\}.

If x = u, then v is below u and there exists \overrightarrow{yr_{1}} ∈ E(T′) such that y ≠ u and y ≠ v. In that case we set T′′= T′∖ \{\overrightarrow{yr_{1}}\} ∪ \{\overrightarrow{vr_{i}}\}.

(5) If r_{2} is the root of T′ (recall that r_{2} ∈ N(v) ∖ N(u) and therefore r_{2} ≠ v), then there exists an edge \overrightarrow{xr_{1}} ∈ E(T′) ∖ E(T). If r_{1} ∈ N(v) and x ≠ v, we set T′′= T′∖ \{\overrightarrow{xr_{1}} \} ∪ \{\overrightarrow{vr_{1}}\}.

If x = v (and therefore r_{1} ∈ N(v)), then we find an edge \overrightarrow{yr_{i}} ∈ E(T′) ∖ E(T) such that y ≠ u, i > 2 and r_{i} ∈ N(u) (or \overrightarrow{zr_{j}} ∈ E(T′) ∖ E(T) such that z ≠ v, r_{j} ∈ N(v) ∖ N(u), j > 2) by using the same arguments as in the proof of (2). Then we set T′′= T′∖ \{\overrightarrow{yr_{i}}\} ∪ \{\overrightarrow{ur_{i}} \} or T′′= T′∖ \{\overrightarrow{zr_{j}} \} ∪ \{\overrightarrow{vr_{j}} \}.

If r_{1} ∉ N(v), then there exists \overrightarrow{xr_{1}} ∈ E(T′) ∖ E(T), x ≠ u, x ≠ v and we set T′′ = T′ ∖ \{\overrightarrow{xr_{1}} \} ∪ \{\overrightarrow{r_{1}r_{2}} \}. In that case we obtain that d_{T′′}(u) = d_{T′}(u), d_{T′′}(v) = d_{T′}(v) and h_{T′′}(u) < h_{T′}(u).

If the root of T′ is r_{1}, then we have the following possibilities.

(6) There exists i > 1 such that r_{i} ∈ N(u). Because we have that d_{T}(u) ⩾ d_{T′}(u) it follows that there exists \overrightarrow{xr_{j}} ∈ E(T′) ∖ E(T) such that x ≠ u, r_{j} ∈ N(u) and j > 1. In that case we set T′′= T′∖ \{\overrightarrow{xr_{j}} \} ∪ \{\overrightarrow{ur_{j}} \}.

(7) If all vertices r_{i} for i = 2, 3, …, m are contained in N(v)∖N(u) and r_{1} ∈ N(v) (recall that r_{1} is the root of T′), then there exists \overrightarrow{xr_{2}} ∈ E(T′) ∖ E(T), x ≠ u and we set T′′= T′∖ \{\overrightarrow{xr_{2}} \} ∪ \{\overrightarrow{vr_{1}}\}.

(8) Finally, we assume that r_{1} ∈ N(u) ∖ N(v), r_{i} ∈ N(v) ∖ N(u) for all i > 1,

and r_{1} is the root of T′. In that case we have that d_{T}(u) = d_{T′}(u).

If m > 2, from d_{T}(v) ⩾ d_{T′}(v) we conclude that there exists r_{i} ∈ N(v) for i > 2 and an edge \overrightarrow{yr_{i}} ∈ E(T′) ∖ E(T) such that y ≠ v. Then we set T′′= T′∖ \{\overrightarrow{yr_{i}}\} ∪ \{\overrightarrow{vr_{i}}\}.

For m = 2, we again consider the edge \overrightarrow{xr_{2}} ∈ E(T′) ∖ E(T). If x = r_{1}, we have that d_{T}(u) = d_{T′}(u), d_{T}(v) = d_{T′}(v) and

T = T′∖ \{\overrightarrow{r_{1}r_{2}} \} ∪ \{\overrightarrow{zr_{1}}\} or T = T′∖ \{\overrightarrow{r_{1}r_{2}} \} ∪ \{\overrightarrow{yr_{2}}\}.

But, then we have that h_{T}(u) > h_{T′}(u) or h_{T}(u) = h_{T′}(u), h_{T}(v) > h_{T′}(v) which is a contradiction with the assumption. Therefore, in this case (m = 2) we have that x ≠ r_{1}. If we set T′′= T′∖ \{\overrightarrow{xr_{2}} \} ∪ \{\overrightarrow{r_{1}r_{2}} \}, then we obtain that d_{T′}(u) = d_{T′′}(u), d_{T′}(v) = d_{T′′}(v), h_{T′′}(u) = h_{T′}(u) and h_{T′′}(v) < h_{T′}(v).

□

3. A complete multipartite graph

Let K_{n_{1} ,n_{2} ,...,n_{k}} denote a complete multipartite graph. Assume that its vertex set is V = V_{1} ∪ V_{2} ∪ ⋯∪ V_{k}, where |V_{i}| = n_{i}. Furthermore, we assume that all sets V_{i} are linearly ordered. We may choose one vertex in V_{1} and one in V_{2} and denote them by 1 and −1.

Let \overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} denote a directed graph obtained from a complete multipartite graph K_{n_{1} ,n_{2} ,...,n_{k}} when one replaces all edges by pairs of directed edges going in opposite directions. Note that 1, −1 is a dominant pair of vertices in \overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} and from Theorem 2.1 we know that Δ(\overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} ) is shellable. We use a slight modification of the algorithm described in [5] to encode directed trees in \overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} .

Remark 3.1. For each directed tree T of \overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} we associate the set of sequences {C_{0}, C_{1}, …, C_{k}} of the vertex set such that

(i) The length of the sequence C_{0} is k − 1 and any x ∈ V can occur in C_{0}. (ii) For any i > 0 the length of C_{i} is n_{i} − 1 and C_{i} contains vertices from V ∖ V_{i}.

Let r denote the root of T. For a vertex v ∈ V, v ≠ r, let U_{T}(v) denote the unique vertex u such that \overrightarrow{uv} ∈ E(T). We say that the depth of a vertex v in T (denoted by depth(v)) is the length of the longest directed path from v to a leaf of T. For all i = 1, 2, …, k let v′_{i} denote the vertex from V_{i} with the maximal depth in T (if there are more than one vertex in V_{i} with maximal depth for v′_{i}, we choose the greatest one among them in the linear order of V_{i}). If the root of T is a vertex that belongs to V_{i_{0}} , then we have that v′_{i_{0}} = r.

The sequence C_{0} contains vertices {U_{T}(v′_{i}) : i ≠ i_{0}}, and the vertex U_{T}(v′_{j}) is before U_{T}(v′_{s}) in C_{0} if and only if depth(v′_{j}) < depth(v′_{s}) or depth(v′_{j}) = depth(v′_{s}) and j < s. For any i > 0 the entries of the sequence C_{i} are n_{i} − 1 vertices {U_{T}(v) : v ∈ V_{i}, v ≠ v′_{i}} and we order the set of these vertices in the same way as in C_{0}. Vertices from V_{j} that appear in C_{i} and have the same depth, we order in C_{i} by using the linear order defined on V_{j}. We say that {C_{0}, C_{1}, …, C_{k}} is the code for the tree T. The proof that the map T ↦ {C_{0}, C_{1}, …, C_{k}} is a bijection, as well as more details about this construction can be found in [5].

It is easily seen from the above remark that there are

n^{k−1} (n − n_{1})^{n_{1} −1} (n − n_{2})^{n_{2} −1} ⋯ (n − n_{k})^{n_{k} −1}

directed trees in \overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} . These are the facets of Δ(\overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} ).

Theorem 3.1. The h-vector of Δ(\overrightarrow{K}_{m,n} ) is given by
h_{k}(Δ(K_{m,n} )) = ∑_{p+q=k} \binom{m − 1}{p} (n − 1)^{p}\binom{n − 1}{q} (m − 1)^{q}

+ (m + n − 1) ∑_{p+q=k−1} \binom{m − 1}{p} (n − 1)^{p}\binom{n − 1}{q} (m − 1)^{q}.

Proof. Note that Δ(\overrightarrow{K}_{m,n} ) is (m + n − 2)-dimensional complex. We consider the shelling order of Δ(\overrightarrow{K}_{m,n} ) described in Theorem 2.1. Recall that

R(T) = \{\overrightarrow{xy} ∈ E(T) : E(T) ∖ \{\overrightarrow{xy}\} ⊂ E(S) for some tree S that precedes T \}.

In other words, an edge \overrightarrow{xy} ∈ E(T) is in R(T) if it can be replaced with another edge \overrightarrow{zw} ∉ E(T) such that (T ∖ \{\overrightarrow{xy}\})∪ \{\overrightarrow{zw}\} is a new directed tree which precedes T in considered shelling order.

It is easy to check that the following statements hold:

(i) The restriction R(T) does not contain the edge \overrightarrow{1x}. A replacement of \overrightarrow{1x} will decrease the out-degree of 1.

(ii) A replacement of the edge \overrightarrow{−1x} in T will decrease the out-degree of −1. A new tree T′ = (T ∖ \{\overrightarrow{−1x} \}) ∪ \{\overrightarrow{yz}\} precedes T in the considered shelling order only if we increase the out-degree of 1. We can do this if and only if the vertex y = 1 is below −1 in T and z ∈ V_{2} is the root of T. Other edges \overrightarrow{−1x′} can not be replaced.

(iii) Let r be the root of T. For a vertex x ∈ V_{1}, x ≠ 1, and an edge \overrightarrow{xy} we have: (a) if 1 is not below y the tree (T ∖ \{\overrightarrow{xy}\}) ∪ \{\overrightarrow{1y}\} precedes T.

(b) If 1 is below y and if r belongs V_{2}, we have that (T ∖ \{\overrightarrow{xy}\}) ∪ \{\overrightarrow{1y}\} is before T.

(c) If r ∈ V_{1} (recall that 1 is below y) we set S = (T ∖ \{\overrightarrow{xy}\}) ∪ \{\overrightarrow{yr}\}. Then we have d_{T}(1) = d_{S}(1), d_{T}(−1) = d_{S}(−1), h_{T}(1) > h_{S}(1) and therefore the tree S precedes T.

So, any of the considered edges \overrightarrow{xy} is contained in R(T).

A similar analysis shows that an edge \overrightarrow{xy}, where x ∈ V_{2}, x ≠ −1, is contained in R(T) except when x is the root of T, −1 is below y and 1 is not below y.

From the above remarks we have that for a directed tree T

(3.1)  type(T) = m + n − 1 − d_{T}(1) − d_{T}(−1)

except for the following trees:

(A1) Trees in which the root r belongs to V_{2} and the vertex 1 is below of −1. The

type of a such tree T is type(T) = m + n − d_{T}(1) − d_{T}(−1). (A2) Trees in which the root r ∈ V_{2}, r ≠ −1, there exists an edge \overrightarrow{rx} ∈ E(T)

such that −1 is below x and 1 is not below x. The type of this tree is type(T) = m + n − d_{T}(1) − d_{T}(−1) − 2.

Now, we count the number of trees in Δ(\overrightarrow{K}_{m,n} ) with given d_{T}(1) + d_{T}(−1). Let {{r}, C_{1}, C_{2}} be the set of sequences of vertices associated to a tree T (r is the root of T) in Remark 3.1. We set

p = |{x ∈ C_{1} : x ≠ −1}|, q = |{y ∈ C_{2} : y ≠ 1}|.

From Remark 3.1 we obtain that there are

(m + n − 2) ∑_{p+q=k−1}  \binom{m − 1}{p} (n − 1)^{p}\binom{n − 1}{q} (m − 1)^{q}

+ 2 ∑_{p+q=k} \binom{m − 1}{p} (n − 1)^{p}\binom{n − 1}{q} (m − 1)^{q}

directed trees in \overrightarrow{K}_{m,n} such that d_{T}(1) + d_{T}(−1) = m + n − 1 − k. Note that the summands in the second row correspond with the trees in which the root is 1 or −1. From the relation (3.1) we have that all of these trees are of the type k, except the trees described in (A1) and (A2).

The remaining trees of \overrightarrow{K_{m,n}} of the type k are all

(B1) trees described in (A2) in which d_{T}(1) + d_{T}(−1) = m + n − 2 − k; or (B2) trees described in (A1) in which d_{T}(1) + d_{T}(−1) = m + n − k.

Let T be a directed tree as considered in (B1). If \overrightarrow{ry} is the first edge on the path from r to 1, then T′ = (T ∖ \{\overrightarrow{ry}\}) ∪ \{−\overrightarrow{1y}\} is a tree as described in (A1). Note that the map T ↦ T′ is an injection, and all trees described in (A1) are contained in the image of this map except the trees whose root is −1. From Remark 3.1 it follows that there are

∑_{p+q=k} \binom{m − 1}{p} (n − 1)^{p}\binom{n − 1}{q} (m − 1)^{q}

trees with −1 as the root and d_{T}(1) + d_{T}(−1) = m + n − 1 − k, which should be subtracted while calculating h_{k}(Δ(\overrightarrow{K}_{m,n} )).

Further, if T is a tree described in (A2), and \overrightarrow{rx} is the first edge of the path from r to 1, then T′ = (T ∖ \{\overrightarrow{rx}\}) ∪ \{−\overrightarrow{1x}\} is a tree as in (B2). This map is an injection, and a tree from (B2) is not in the image of this map if and only if its root is −1.

There are

∑_{p+q=k−1} \binom{m − 1}{p} (n − 1)^{p}\binom{n − 1}{q} (m − 1)^{q}

trees with −1 as the root and d(1) + d(−1) = m + n − k that should be added when determining h_{k}(Δ(\overrightarrow{K}_{m,n} )). □

From the above theorem we obtain that the generating facets for Δ(\overrightarrow{K}_{m,n} ) are:

(i) All directed trees of \overrightarrow{K}_{m,n} in which the vertices 1 and −1 are leaves and the root of such a tree is a vertex contained in V_{1}.

(ii) All directed trees of \overrightarrow{K}_{m,n} in which the root is from V_{2}, the vertex 1 is a leaf below −1, and the out-degree of the vertex −1 in such a tree is one.

Corollary 3.1. The complex Δ(\overrightarrow{K}_{m,n} ) is homotopy equivalent to a wedge of (m + n − 1)(m − 1)^{n−1} (n − 1)^{m−1} spheres of dimension m + n − 2.

Theorem 3.2. The complex Δ(\overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} ) is homotopy equivalent to a wedge of (n−1)^{k−1} (n−n_{1}−1)^{n_{1} −1} (n−n_{2}−1)^{n_{2} −1} ⋯ (n−n_{k}−1)^{n_{k} −1} spheres of dimension n − 2.

Proof. We use a shelling of Δ(\overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} ) described in Theorem 2.1 to recognize generating faces. These are

(A) directed trees in which the vertex 1 is a leaf, and there does not exist an edge \overrightarrow{−1v} , for a vertex v ∈ V_{1}

except the tress of the above form in which

(A_{1}) the root is a vertex v_{2} ∈ V_{2}, there is an edge \overrightarrow{v_{2}v_{1}} for a vertex v_{1} ∈ V_{1},

the vertex −1 is below v_{1}, and 1 is not below v_{1}; and (A_{2}) the root is a vertex v_{1} ∈ V_{1} and the leaf 1 is below −1.

Generating facets of Δ(\overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} ) are also: (B) directed trees in which the root is a vertex r ∈ V ∖ V_{1}, there is only one edge of the form −1v_{1} for a vertex v_{1} ∈ V_{1} and 1 is a leaf below v_{1}.

Now, we define a map between a subset of the trees of the type (B) and directed trees of type (A_{1}) or (A_{2}). If T is a tree of the type (B) with the root r ∈ V ∖ V_{1} and −1 → v_{1} → x → y → ⋯→ 1 is the unique path from −1 to 1, then

T′= T ∖ \{\overrightarrow{−1v_{1}} , \overrightarrow{v_{1}x}\} ∪ \{\overrightarrow{xv_{1}}, \overrightarrow{v_{1}r}\} is a tree of type A_{1} if x ∈ V_{2},
T′′= T ∖ \{\overrightarrow{−1v_{1}} , \overrightarrow{v_{1}x}\} ∪ \{\overrightarrow{−1x} , \overrightarrow{v_{1}r}\} is a tree of type A_{2} if x ∈ V ∖ (V_{1} ∪ V_{2}).

The above map is a bijection that exhausts all trees of type (B) except the trees in which \overrightarrow{−11} is an edge. Therefore, in order to estimate the number of the generating simplices of Δ(\overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} ) we have to count directed trees in \overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} in which

(*) 1 is a leaf, there are no other edges of the form \overrightarrow{−1v} , for a vertex v ∈ V_{1};

or (**) 1 is a leaf, \overrightarrow{−11} is an edge, there are no other edges of the form \overrightarrow{−1v} , for

a vertex v ∈ V_{1}, and the root is a vertex r ∈ V ∖ V_{1}.

From Remark 3.1 we obtain that the code of a tree described in (*) or (**) does not contain label −1 in the sequences C_{0} at the place reserved for the deepest vertex of V_{1}. Also, a tree described in (*) does not contain −1 in the sequence C_{1}. For a tree described in (**) the vertex −1 appears in C_{1} only in the first place, and the last entry of C_{0} (the root of such a tree) is not from V_{1}. Therefore, in the code of such a tree there exists v ∈ V ∖ V_{1} that appears in C_{0} as U(v′_{1}). We replace this vertex v with −1 and obtain the bijection between generating simplices of Δ(\overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} ) and directed trees of \overrightarrow{K}_{n_{1} ,n_{2} ,...,n_{k}} in which −1 does not occur in C_{1} and 1 does not occur at all. For a tree described in (*) the code remains unchanged. The number of these trees is

(n − 1)^{k−1} (n − n_{1} − 1)^{n_{1} −1} (n − n_{2} − 1)^{n_{2} −1} ⋯ (n − n_{k} − 1)^{n_{k} −1} .  □

References

1. A. Björner, Topological methods, in: R. L. Graham, M. Grötschel, and L. Lovász (eds.), Handbook of Combinatorics, Elsevier, Amsterdam, 1995, 1819–1872.

2. A. Björner and M. L. Wachs, Shellable nonpure complexes and posets I, Trans. Amer. Math. Soc. 348(4) (1996), 1299–1327.

3. M. K. Chari and M. Joswig, Complexes of discrete Morse functions, Discrete Math. 302(1-3) (2005), 39–51.

4. A. Engström, Complexes of directed trees and independence complexes, Discrete Math. 309(10) (2009), 3299–3309.

5. G. H. Hurlbert, On encodings of spanning trees, Discrete Appl. Math. 155(18) (2007), 2594– 2600.

6. D. N. Kozlov, Complexes of directed trees, J. Combin. Theory Ser. A 88(1) (1999), 112–122.

7. D. N. Kozlov, Directed trees in a string, real polynomials with triple roots, and chain mails, Discrete Comput. Geom. 32(3) (2004), 373–382.

8. J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley, Menlo Park, CA, 1984.

9. G. M. Ziegler, Lectures on Polytopes, Springer-Verlag, New York, 1995.

Department of Mathematics (Received 14 04 2012) University of Banja Luka Banja Luka Bosnia and Herzegovina

    ducci68@blic.net