THE POSET OF BIPARTITIONS

GÁBOR HETYEI AND CHRISTIAN KRATTENTHALER^{†}

Abstract. Bipartitional relations were introduced by Foata and Zeilberger in their characterization of relations which give rise to equidistribution of the associated inversion statistic and major index. We consider the natural partial order on bipartitional relations given by inclusion. We show that, with respect to this partial order, the bipartitional relations on a set of size n form a graded lattice of rank 3n − 2. Moreover, we prove that the order complex of this lattice is homotopy equivalent to a sphere of dimension n − 2. Each proper interval in this lattice has either a contractible order complex, or it is isomorphic to the direct product of Boolean lattices and smaller lattices of bipartitional relations. As a consequence, we obtain that the Möbius function of every interval is 0, 1, or −1. The main tool in the proofs is discrete Morse theory as developed by Forman, and an application of this theory to order complexes of graded posets, designed by Babson and Hersh, in the extended form of Hersh and Welker.

1. Introduction

The poset of partitions Π_{n} of the set {1, 2, …, n}, where the order is defined by refinement, is a classical object in combinatorics. Various aspects of this poset have been studied in the literature (cf. [21, Ch. 3]). In particular, its Möbius function has been computed by Schützenberger and by Frucht and Rota independently (cf. [19, p. 359]), and the homotopy type of its order complex is a wedge of spheres. (The latter follows from the well-known fact that Π_{n} is a geometric lattice, and from Björner’s result [5] that geometric lattices are shellable.)

Closely related, and more relevant to the present work, is the poset of ordered partitions of {1, 2, …, n}. It has a much simpler structure; for example, all intervals in this poset are isomorphic to products of Boolean lattices.

Bipartitional relations (bipartitions, for short) were introduced by Foata and Zeilberger [7], who showed that these are the relations U for which the (appropriately generalized) major index maj_{U} and inversion number inv_{U} are equidistributed on all rearrangement classes. Han [11, Th. 5] showed that these bipartitional relations can be axiomatically characterized as the relations U for which U and its complement are transitive. (Cf. [6, 17] for further work on questions of this kind.)

Bipartitional relations on {1, 2, …, n} carry a natural poset structure, the partial order being defined by inclusion of relations. We denote the corresponding poset of bipartitions by Bip({1, 2, …, n}). Figure 1 shows the Hasse diagram of Bip({1, 2}).

2000 Mathematics Subject Classification. Primary 06A07; Secondary 05A18 06A06 55P15.

Key words and phrases. bipartitions, set partitions, order complex, Möbius function, homotopy equivalence, discrete Morse theory.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

∅ {(1, 2), (2, 2)}  {(1, 1), (2, 1)}  {(2, 1), (2, 2)} {(1, 1), (1, 2)}  {(1, 1), (2, 1), (2, 2)} {(1, 1), (1, 2), (2, 2)} {(1, 2)}  {(2, 1)} {(1, 1), (1, 2), (2, 1), (2, 2)}

Figure 1. Bip({1, 2})

The poset Bip({1, 2, …, n}) contains the poset of ordered partitions of {1, 2, …, n} and its dual as subposets, and therefore can be considered as a common extension of the two. It turns out that the richness of the structure of the poset of bipartitions is comparable to that of the lattice of partitions. To begin with, Bip({1, 2, …, n}) is a graded lattice of total rank 3n − 2 (see Theorem 4.1 and Corollary 5.3), although it is neither modular (cf. Example 7.7) nor geometric, in fact not even Cohen–Macaulay (cf. Corollary 9.4). Furthermore, the Möbius function of each interval is 0, 1, or −1 (see Definition 10.1, Corollaries 9.5 and 10.3, and Theorem 10.4 for the precise statement of which intervals take which Möbius function values). We show this by proving the stronger result that the order complex of Bip({1, 2, …, n}) is homotopy equivalent to a sphere (see Theorem 9.3), and each proper interval is either the direct product of Boolean lattices and smaller lattices of bipartitions, or has a contractible order complex (see Proposition 10.2 and Theorem 10.4). The proofs of these facts form the most difficult part of our paper. They are essentially based on an adaptation of the Gray code of permutations due to Johnson [16] and Trotter [23] and on work of Babson and Hersh [1] (in the extended form by Hersh and Welker [15]) constructing a discrete Morse function in the sense of Forman [8, 9, 10] for the order complex of a graded poset. The former is needed to decompose Bip({1, 2, …, n}) into a union of distributive lattices in a shelling-like manner. This decomposition is then refined using the well-known EL-shelling of distributive lattices in order to obtain an enumeration of the maximal chains of Bip({1, 2, …, n}) to which the results of Babson, Hersh, and Welker apply. (As Example 9.1 shows, our enumeration of the maximal chains of Bip({1, 2, …, n}) is not a poset lexicographic order in the sense of [1], so that we do indeed need the extended form observed in [15].) We remark that our “two-phase” decomposition is similar in spirit as constructions by Hanlon, Hersh and Shareshian [12] and by Hersh and Welker [15]. It would be interesting to see whether there is a uniform framework for this type of shelling-like decompositions. However, we have not been able to find such a generalization.

This paper is organized as follows. The next two sections are of preliminary nature. Namely, Section 2 reviews basic facts on bipartitional relations, while Section 3 outlines the basic ideas of the construction of Babson and Hersh. Here we observe that the proofs of their main results are actually applicable to a larger class of enumerations of maximal chains, which we call “enumerations growing by creating skipped intervals.” In Section 4, we provide the proof that Bip({1, 2, …, n}) is a lattice, and we show that it is graded and compute its rank function in Section 5. The purpose of Section 6 is to show that Bip({1, 2, …, n}) may be written as union of n! distributive lattices, each indexed by a permutation, where the proof of distributivity is deferred to Section 7. We begin Section 8 by reviewing the Johnson–Trotter algorithm and an easy generalization to enumerating all elements in a direct product of symmetric groups. We continue by using these enumerations to decompose the order complex of Bip({1, 2, …, n}), and the order complex of certain intervals in it, in a shelling-like manner. Section 9 forms the core of our article. Here we construct an enumeration of the maximal chains of Bip({1, 2, …, n}) that refines the “J–T decomposition” introduced in Section 8, and to which the results of Babson and Hersh are adaptable, as reviewed in Section 3. Finally, in Section 10, we outline how the argument of the preceding section may be modified to handle the case of proper intervals of Bip({1, 2, …, n}) as well.

2. Definition and elementary properties of bipartitional relations

In Definition 2.1 below, we formally introduce bipartitional relations. This definition is (essentially) taken from Han [11]. Subsequently, we shall provide a different way to see bipartitional relations, namely in terms of ordered bipartitions. Historically, bipartitional relations were originally defined by Foata and Zeilberger in [7, Def. 1] in the latter way, and Han showed in [11, Th. 5] the equivalence with a condition which, in its turn, is equivalent to the transitivity condition that we use for defining bipartitional relations as given below.

Definition 2.1. A relation U ⊆ X × X on a finite set X is a bipartitional relation, if both U and (X × X) \ U are transitive. We denote the set of bipartitional relations on X by Bip(X).

Note that, by definition, the complement of a bipartitional relation is also a bipartitional relation. Following [11], we say that x, y ∈ X are incomparable, if either both (x, y) and (y, x) belong to U, or none of them does. We will use the notation x ∼_{U} y for such pairs.

Lemma 2.2 (Han). The incomparability relation ∼_{U} is an equivalence relation.

This is [11, Lemme 4], which may be easily verified directly, using Definition 2.1. As it was first observed by Han in [11], every bipartitional relation U induces a linear

order <_{U} on the U-incomparability classes as follows. For x ≁_{U} y we set x <_{U} y if and only if (x, y) ∈ U but (y, x) ∉ U. The U-incomparability classes form a set partition of X and we may order them by <_{U} to obtain an ordered partition of X. An ordered partition (B_{1}, B_{2}, …, B_{k}) of X is an ordered list of pairwise disjoint nonempty subsets B_{i} ⊂ X, such that X is the union of the sets B_{i}. Every bipartitional relation may be represented by a unique pair of an ordered partition (B_{1}, B_{2}, …, B_{k}) of X and a vector (ε_{1}, ε_{2}, …, ε_{k}) ∈ {0, 1}^{k} (cf. [11, Th. 5]), as follows. We set

(x, y) ∈ U ⟺ \{ \begin{matrix}x ∈ B_{i} and y ∈ B_{j} for some i < j, \\ or \\ x, y ∈ B_{i} for some i satisfying ε_{i} = 1. \end{matrix}  (2.1)

In fact, the B_{i}’s must be the ∼_{U}-equivalence classes, numbered in such a way that i < j if and only if x <_{U} y for every x ∈ B_{i} and y ∈ B_{j}. We must set ε_{i} = 1 if and only if (x, x) ∈ U for all x ∈ B_{i}.

For example, the bipartitional relation U = {(1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)} has two U-equivalence classes: {1} and {2, 3}. Since 1 <_{U} 2 and 1 <_{U} 3, we must have B_{1} = {1} and B_{2} = {2, 3}. Moreover, (1, 1) ∉ U implies ε_{1} = 0, whereas (2, 2) ∈ U and (3, 3) ∈ U imply ε_{2} = 1.

Following [7], we call the ordered partition (B_{1}, B_{2}, …, B_{k}) together with the vector (ε_{1}, ε_{2}, …, ε_{k}) an ordered bipartition, and we write it as (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}). We call the blocks B_{i} satisfying ε_{i} = 1 underlined (and, consequently, we call the blocks B_{i} satisfying ε_{i} = 0 nonunderlined). Furthermore, we call the ordered bipartition (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) defining U via (2.1) the ordered bipartition representation of U. On the other hand, every relation U defined by an ordered bipartition representation (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) in the way above is bipartitional: the transitivity of U is clear, and the transitivity of (X × X) \ U is evident from the following trivial observation.

Lemma 2.3. If U ⊆ X ×X is represented by the ordered bipartition (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) of X, then U^{c} := (X ×X)\U is represented by the ordered bipartition (B_{k}^{1−ε_{k−1}}, B_{k−1}^{1−ε_{k−1}}, …, B_{1}^{1−ε_{1}}).

We will use the notation^{1} U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) to denote the bipartitional relation defined by its ordered bipartition representation (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}). For example, the bipartitional relation U = {(1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)} from above may also be given as U({1}^{0}, {2, 3}^{1}).

Frequently, we shall write this ordered bipartition in a suggestive manner, where we physically underline the elements of underlined blocks. For example, the above bipartitional relation will also be written in the form U(\{1\}, \{\underline{2}, \underline{3}\}).

3. Discrete Morse matching via chain enumeration

Discrete Morse Theory, developed by Forman [8, 9, 10], is a combinatorial theory that helps to determine the homotopy type of a simplicial complex, considered as a CW - complex. Roughly speaking, in this theory a Morse function on the faces of a simplicial complex induces a Morse matching, which in its turn enables one to perform a sequence of elementary collapses and find a smaller, homotopy equivalent CW -complex. Only the unmatched faces of the simplicial complex “survive” the collapsing; the subcomplexes induced by these faces are the critical cells, from which the homotopy type of the complex can (hopefully) be read off. In our paper, we shall not need to know exact definitions of all these ingredients. For our purpose it will suffice to keep in mind that one of the primary goals is to identify the critical cells. For a detailed description of the theory we refer the reader to the above cited sources.

1The letter U has no specific significance here, but we selected it in tribute to the ubiquitous letter U in Foata and Zeilberger’s article [7].

In this paper we will use a method developed by Babson and Hersh [1], in the extended form of Hersh and Welker [15] (which incorporates a correction to [1] pointed out in [14, 20]). This method is designed to find the homotopy type of the order complex △(P \{ˆ0, ˆ1}) of a graded partially ordered set P with minimum element ˆ0 and maximum element ˆ1. Recall that the order complex of a partially ordered set Q is the simplicial complex whose vertices are the elements of Q and whose faces are the chains of Q. Babson and Hersh [1] find a Morse matching on the Hasse diagram of the poset of faces of △(P \{ˆ0, ˆ1}), the order relation being defined by inclusion, by fixing an enumeration of the maximal chains of P, which they call poset lexicographic order. It was observed by Hersh and Welker [15, Theorem 3.1] that the key property of a poset lexicographic order that is used in all proofs of Babson and Hersh in [1] is that the enumeration of maximal chains considered grows by creating skipped intervals (which is implicit in [1, Remark 2.1]). They call this property the crossing condition, originally introduced by Hersh [13]. The following definition is easily seen to be equivalent to this crossing condition.

Definition 3.1. Let P be a graded poset of rank n + 1 with a unique minimum element ˆ0 and a unique maximum element ˆ1. An enumeration c_{1}, …, c_{N} of all maximal chains of P grows by creating skipped intervals if for every maximal chain c_{i} there is a family of intervals I(c_{i}) with elements [a, b] = {a, a + 1, …, b} ⊆ {1, 2, …, n}, none of the intervals contained in another, with the following property: a chain c contained in a maximal chain c_{i} is also contained in a maximal chain c_{j} for some j < i if and only if the set of ranks of c is disjoint from at least one interval in I(c_{i}).

It is worth noting that the property stated in Definition 3.1 above also suffices to prove the linear inequalities shown in [2] and [3].

In the main result of Babson and Hersh [1], a second interval system, which is derived from the I-intervals, plays a crucial role. This interval system is called J-intervals J(c_{k}). The process of finding the system of J-intervals is given in [1, p. 516] and may be extended without any change to enumerations of maximal chains that grow by creating skipped intervals as follows.

Definition 3.2. Consider an enumeration of all maximal chains of a graded poset of rank n + 1 with ˆ0 and ˆ1 that grows by creating skipped intervals. Let c_{k} be a maximal chain whose associated interval system I(c_{k}) satisfies

⋃_{[u,v]∈I(c_{k})}[u, v] = {1, 2, …, n}.

We define the associated J-intervals J(c_{k}) as the output of the following process: (0) Initialize by setting I = I(c_{k}) and J = ∅.

(1) Let [u, v] be the interval in I whose left end point u is the least. Add [u, v] to J, and remove it from I.

(2) Replace each interval [x, y] in I by the intersection [x, y] ∩ [v + 1, n]. Define the “new” I to be the resulting new family of intervals.

(3) Delete from I those intervals which are not minimal with respect to inclusion.

(4) Repeat steps (1)–(3) until I = ∅. The output of the algorithm is J.

Our wording differs slightly from the one used by Babson and Hersh, since they consider the families I(c_{k}) and J(c_{k}) as families of subsets of c_{k}, whereas we consider them as families of subsets of {1, …, n}.

The following theorem presents the main theorem of Babson and Hersh [1, Th. 2.2, Cor. 2.1], in the generalized form implied by [15, Theorem 3.1] (including the aforementioned correction to [1]).

Theorem 3.3 (Babson–Hersh). Let P be a graded poset of rank n + 1 with ˆ0 and ˆ1, and let c_{1}, …, c_{N} be an enumeration of its maximal chains that grows by creating skipped intervals. Then, in the Morse matching constructed by Babson and Hersh in [1, paragraphs above Th. 2.1], each maximal chain c_{k} contributes at most one critical cell. The chain c_{k} contributes a critical cell exactly when the union of all intervals listed in J(c_{k}) equals {1, 2, …, n}. If a maximal chain c_{k} contributes a critical cell, then the dimension of this critical cell is one less than the number of intervals listed in J(c_{k}).

We will use the above result in combination with the main theorem of Discrete Morse Theory due to Forman [8, first (unnumbered) corollary], [9, Th. 0.1], [10, Th. 2.5].

Theorem 3.4. Suppose △ is a simplicial complex with a discrete Morse function. Then △ is homotopy equivalent to a CW complex with exactly one cell of dimension p for each critical cell of dimension p. In particular, if there is no critical cell then △ is contractible.

Remark 3.5. We point out that Babson and Hersh modify Forman’s conventions by including the empty face in the range of the Morse function, see the second paragraph after Definition 1.1 in [1]. As a consequence, a vertex might be matched to the empty face, something which is impossible in the setup of Forman. The term “critical cell” is thus slightly more restrictive in [1] than in [8, 9, 10] in that such a vertex would be a critical cell according to Forman but not according to Babson and Hersh.

4. The lattice of bipartitional relations

In this section, we formally define the order relation on the set of bipartitional relations, and we prove that the so defined poset is a lattice (see Theorem 4.1). At the end of this section, we record an auxiliary result concerning the lattice structure of Bip(X) in Lemma 4.4, which will be needed later in Section 6 in the proof of Lemma 6.2.

Let U and V be two bipartitional relations in Bip(X). We define U ≤ V if and only if U ⊆ V as subsets of X × X. In this manner, Bip(X) becomes a partially ordered set.

Theorem 4.1. For any finite set X, the poset Bip(X) is a lattice.

Proof. By [21, Prop. 3.3.1], it is sufficient to show that every pair of bipartitional relations has a join. This will be done in Proposition 4.2 below. □

We remind the reader that a pair (x, y) belongs to the transitive closure of a relation W ⊆ X × X if there exists a chain x_{0}, x_{1}, … x_{n} ∈ X with n > 0 such that x_{0} = x, x_{n} = y and (x_{i}, x_{i+1}) ∈ W for i = 0, 1, …, n − 1.

Proposition 4.2. For every U, V ∈ Bip(X) there exists a smallest bipartitional relation with respect to inclusion containing both U and V, that is, a join U ∨ V. This join is given by the transitive closure of U ∪ V.

Proof. Let W denote the transitive closure of U ∪ V. Every bipartitional relation containing both U and V contains also W by transitivity. We only need to show that W is bipartitional. It is clearly transitive, only the transitivity of (X × X) \ W remains to be seen.

Assume by way of contradiction that (x, y) and (y, z) belong to the complement of W but (x, z) ∈ W for some x, y, z ∈ X. By the definition of W, there exists a sequence x_{0}, x_{1}, …, x_{n} ∈ X such that n > 0, x_{0} = x, x_{n} = z, and for every i ∈ {0, 1, …, n − 1} we have (x_{i}, x_{i+1}) ∈ U or (x_{i}, x_{i+1}) ∈ V. Without loss of generality we may assume that we have (x_{n−1}, z) ∈ U. We cannot have n = 1 since this implies (x, z) ∈ U, in contradiction with (x, y) ∉ U ⊆ W, (y, z) ∉ U ⊆ W, and the transitivity of U^{c} (where, as before, U^{c} denotes the complement (X × X) \ U). By induction on i, we see that (x, x_{i}) belongs to W, for i = 1, 2, …, n − 1. In particular, we have (x, x_{n−1}) ∈ W. The pair (x_{n−1}, y) cannot belong to U, otherwise we have (x_{n−1}, y) ∈ W and, by the transitivity of W, also (x, y) ∈ W. On the other hand, by the transitivity of the relation U^{c}, we obtain from (x_{n−1}, y) ∉ U and (y, z) ∉ U that (x_{n−1}, z) ∉ U, in contradiction with our assumption. □

We may represent any relation R ⊆ X × X as a directed graph on the vertex set X by drawing an edge x → y exactly when (x, y) ∈ R. If we represent U ∪ V as a directed graph, we obtain that (x, y) ∈ U ∨ V if and only if there is a directed path x = x_{0} → x_{1} → … → x_{m} = y such that each edge belongs to the graph representing U ∪V. By the transitivity of U and V, a shortest such path is necessarily UV -alternating in the sense that every second edge belongs to U, the other edges belonging to V. There is no bound on the minimum length of such a shortest path, as is shown in the following example.

Example 4.3. Let X = {1, 2, …, n} and consider the bipartitional relation

U = U(\{\underline{n}, \underline{n − 1}\}, \{\underline{n − 2}, \underline{n − 3}\}, …),

where each block has two elements, except possibly for the rightmost block, which is a singleton if n is odd. Consider also

V = U(\{\underline{n}\}, \{\underline{n − 1}, \underline{n − 2}\}, \{\underline{n − 3}, \underline{n − 4}\}, …),

where each block has two elements, except for the leftmost block, which is always a singleton, and possibly for the rightmost block which is a singleton if n is even. It is easy to verify that

U ∨ V = (\{\underline{1}, \underline{2}, …, \underline{n}\}).

The shortest UV -alternating path from 1 to n is 1 → 2 → ⋯ → n, since (i, j) ∉ U ∪ V if j − i ≥ 2.

On the other hand, if only (x, y) belongs to U ∨ V but (y, x) does not, then the shortest UV -alternating path from x to y has length 1.

Lemma 4.4. Let U and V be bipartitional relations on X. If for some x, y ∈ X we have (x, y) ∈ U ∨ V and (y, x) ∉ U ∨ V then (x, y) already belongs to U ∪ V.

Proof. Assume, by way of contradiction, that the shortest UV -alternating path x = x_{0} → x_{1} → … → x_{m} = y from x to y satisfies m > 1. Then, because of m > 1, (x, y) belongs to U^{c} and V^{c}. Since (y, x) ∉ U ∨ V, the pair (y, x) also belongs to U^{c} and V^{c}. Thus x ∼_{U} y and x ∼_{V} y. We claim that we may replace x_{0} = x with y and x_{n} = y with x in the UV -alternating path x = x_{0} → x_{1} → … → x_{m} = y and obtain a UV -alternating path y → x_{1} → … → x. Indeed, x ∼_{U} y and (x, y) ∉ U imply that x and y belong to the same nonunderlined block of U. Hence, if (x_{0}, x_{1}) ∈ U, then x_{1} belongs to a block of U to the “right” of the block containing x, whence (y, x_{1}) ∈ U. Similarly, if (x_{0}, x_{1}) ∈ V, then x ∼_{V} y and (x, y) ∉ V yield (y, x_{1}) ∈ V. The proof that x_{n} may be replaced with x is analogous. We obtain that there is a UV -alternating path from y to x, implying (y, x) ∈ U ∨ V, in contradiction to our assumption. Therefore we must have m = 1. □

5. Cover relations and rank function

In this section we describe the cover relations in the bipartition lattice Bip(X). This description will allow us to show that Bip(X) is a graded poset, and to give an explicit formula for the rank function.

Theorem 5.1. Let U, V ∈ Bip(X) be bipartitional relations. Then V covers U if and only if its ordered bipartition representation may be obtained from the ordered bipartition representation of U in one of the three following ways:

(i) join two adjacent underlined blocks of U, (ii) separate a nonunderlined block of U into two adjacent nonunderlined blocks, or (iii) change a nonunderlined singleton block of U into an underlined singleton block.

Moreover, Bip(X) is a graded poset, with rank function

rk(U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}})) = 3 · ∑_{i:ε_{i}=1} |B_{i}| + |{i : ε_{i} = 0}| − |{i : ε_{i} = 1}| − 1. (5.1)

Example 5.2. The cover relations in Bip({1, 2}) are represented in Figure 1. The cover relations in a subset of Bip({1, 2, 3}) are represented in Figure 2. (The fact that the cover relations in the latter subposet are also cover relations in the entire poset Bip({1, 2, 3}) is shown in Proposition 7.8.)

Proof of Theorem 5.1. First we show that the ordered bipartition representation of V must come from the ordered bipartition representation of U in one of the three ways mentioned in the statement. For that purpose, assume that V covers U = U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}). Let us compare the restrictions of V and U to every block B_{i}. Note that the restriction of a bipartitional relation on X to a subset of X is also bipartitional.

Case 1. V |_{B_{i}} properly contains U |_{B_{i}} for some i. In this case we must have ε_{i} = 0. The relation W given by

(x, y) ∈ W if and only if \{ \begin{matrix}(x, y) ∈ U, \\ or \\ x, y ∈ B_{i} and (x, y) ∈ V, \end{matrix}

is a bipartitional relation, properly containing U, and contained in V. In fact, its ordered bipartition representation may be obtained from (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) by replacing B_{i}^{ε_{i}} = B_{i}^{0} with the ordered bipartition representation of V |_{B_{i}}. Since V covers U, we must have V = W.

If V |_{B_{i}} contains no underlined block then merging two adjacent blocks of V |_{B_{i}} yields a bipartitional relation U′ on B_{i} satisfying U |_{B_{i}} ⊆ U′ ⫋ V |_{B_{i}}. Since V covers U and, hence, V |_{B_{i}} covers U |_{B_{i}}, we must have U′ = U |_{B_{i}}. Therefore V is obtained from U by an operation of type (ii).

If V |_{B_{i}} contains an underlined block, then by changing this block to nonunderlined we may obtain a bipartional relation properly contained in V and still containing U. Hence V |_{B_{i}} must be B_{i} × B_{i}. The only case when there is no bipartition on B_{i} strictly between ∅ and B_{i} × B_{i} is when |B_{i}| = 1, and V is obtained from U by an operation of type (iii).

Case 2. V |_{B_{i}} = U |_{B_{i}} for all i. In this case every ∼_{U}-equivalence class is contained in some ∼_{V} -equivalence class, and this containment is proper for at least one of the B_{i}’s, since otherwise we must have V = U. Hence the situation of Case 1 applies to at least one of the blocks of V^{c} and U^{c}. (Clearly, U^{c} must cover V^{c}). Thus, by the already proven case, the ordered bipartition representation of U^{c} must be obtained from the ordered bipartition representation of V^{c} by an operation of type (ii) or (iii). Here we may exclude an operation of type (iii), since we are not allowed to have the ∼_{U}-equivalence classes (which are the same as the ∼_{U^{c}}-equivalence classes) to coincide with the ∼_{V} -equivalence classes. Therefore U^{c} is obtained from V^{c} by an operation of type (ii), which by Lemma 2.3 is equivalent to saying that V is obtained from U by an operation of type (i).

It is easy to see that the function rk given in (5.1) assigns zero to the empty bipartitional relation U(X^{0}), and increases by exactly one every time we perform one of the operations (i), (ii), or (iii). By the already established part of the statement, rk increases by one on every cover relation, and so Bip(X) is a graded poset with rank function rk. On the other hand, every operation of type (i), (ii), or (iii) on a bipartitional relation U must yield a bipartitional relation V covering U, since the rank function has increased by exactly one. □

Corollary 5.3. If |X| = n then Bip(X) has rank 3n − 2.

6. π-compatible bipartitions

The purpose of this section is to introduce the notion of compatibility of bipartitional relations with a given ordered partition (the latter having been defined in the paragraph after Lemma 2.2). This notion will be of crucial importance for the subsequent structural analysis of Bip(X) in the subsequent sections. As a first application, we use it in Proposition 6.4 to give a criterion to decide U ⊆ V when U and V are bipartitional relations given by their ordered bipartition representations.

Definition 6.1. We call an ordered partition π = (C_{1}, …, C_{k}) compatible with the bipartitional relation U, if for every x, y ∈ X we have

x ∈ C_{i}, y ∈ C_{j}, (x, y) ∈ U, (y, x) ∉ U imply i < j.

Equivalently, if U = U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{l}^{ε_{l}}), then every B_{i} is the union of consecutively indexed C_{j}’s. A particular case arises if π consists of singleton blocks only. In this case, given that X = {x_{1}, x_{2}, …, x_{n}}, there is a permutation ρ of the elements of X such that π = ({ρ(x_{1})}, {ρ(x_{2})}, …, {ρ(x_{n})}). By abuse of terminology, we shall often say in this case that “the ordered partition π is a permutation,” and the bipartitional relation U is compatible with such an ordered partition π if and only if the elements of B_{1}, B_{2}, …, B_{l} may be listed in such an order that placing these lists one after the other in increasing order of blocks gives the left-to-right reading of the permutation π. For any ordered partition π, we denote the subposet of π-compatible bipartitions in Bip(X) by Bip_{π}(X). The Hasse diagram of Bip_{({1},{2},{3})}({1, 2, 3}) is shown in Figure 2.

U(\{1, 2\}, \{3\}\}) U(\{\underline{1}\}, \{\underline{2}, \underline{3}\}\}) U(\{\underline{1}, \underline{2}\}, \{3\})  U(\{\underline{1}\}, \{\underline{2}\}, \{\underline{3}\})  U(\{1\}, \{\underline{2}, \underline{3}\}\}) U(\{\underline{1}\}, \{\underline{2}\}, \{3\}) U(\{\underline{1}\}, \{2\}, \{\underline{3}\})  U(\{1\}, \{\underline{2}\}, \{\underline{3}\}\}) U(\{\underline{1}\}, \{2\}, \{3\}) U(\{1\}, \{\underline{2}\}, \{3\})  U(\{1\}, \{2\}, \{\underline{3}\}\}) U(\{1, 2, 3\}) U(\{\underline{1}, \underline{2}\}, \{\underline{3}\}) U(\{\underline{1}\}, \{2, 3\})  U(\{1\}, \{2\}, \{3\})  U(\{1, 2\}, \{\underline{3}\}\}) U(\{\underline{1}, \underline{2}, \underline{3}\}) U(\{1\}, \{2, 3\})
Figure 2. Bip_{({1},{2},{3})}({1, 2, 3})

The next lemma shows that this subposet is also a sublattice.

Lemma 6.2. Let π be an ordered partition of X. If U ⊆ X × X and V ⊆ X × X are π-compatible bipartitional relations then so are U ∧ V and U ∨ V.

Proof. Let π = (C_{1}, …, C_{k}) and assume (x, y) ∈ U ∨ V but (y, x) ∉ U ∨ V for some x ∈ C_{i} and y ∈ C_{j}. By Lemma 4.4, we have (x, y) ∈ U ∪ V. Without loss of generality we may assume (x, y) ∈ U. Since U is π-compatible, we obtain i < j. Hence U ∨ V is also π-compatible. The other half of the statement follows by duality, since any bipartitional relation is (C_{1}, …, C_{k})-compatible if and only if its complement is (C_{k}, …, C_{1})-compatible. □

Using Theorem 5.1 we may deduce the following fact.

Proposition 6.3. Let c : ∅ = U_{0} ⊂ U_{1} ⊂ ⋯ ⊂ U_{3n−2} = X × X be a maximal chain in Bip(X), where n = |X|. Then there is a unique ordered partition π_{c} which is compatible with all elements of the chain. This ordered partition is a permutation.

Proof. For n = 1 the statement is trivially true. Assume n ≥ 2 and let x and y be two different elements of X. Consider the smallest i for which U_{i} contains at least one of (x, y) and (y, x). Such an i exists since U_{3n−2} = X × X, and it is positive since U_{0} = ∅. We claim that exactly one of (x, y) and (y, x) will belong to U_{i}. In fact, U_{i−1} does not contain any of them, so x and y belong to the same nonunderlined ∼_{U_{i−1}}-equivalence class. U_{i} is obtained from U_{i−1} by one of the operations described in Theorem 5.1. Since at least one of (x, y) and (y, x) was added, this operation can only be the separation of the ∼_{U_{i−1}}-equivalence class of x and y into two nonunderlined blocks. Such an operation adds exactly one of (x, y) and (y, x). Let us set x <_{c} y if (x, y) ∈ U_{i} and (y, x) ∉ U_{i}, respectively y <_{c} x if (y, x) ∈ U_{i} and (x, y) ∉ U_{i}.

We want to construct an ordered partition π_{c} which is compatible with all U_{i}’s. If x <_{c} y, this implies that x belongs to an earlier block of π_{c} than y. There is at most one such ordered partition: the permutation, induced by the relation <_{c}, provided that <_{c} is a linear order.

We are left to show that <_{c} is indeed a linear order. Clearly, for distinct x and y exactly one of x <_{c} y and y <_{c} x holds. We only need to show the transitivity of the relation <_{c}. Assume by way of contradiction that x <_{c} y, y <_{c} z and z <_{c} x hold for some {x, y, z} ⊆ X. Then we have

\begin{matrix}(x, y) ∈ U_{i}, & (y, x) ∉ U_{i}, \\ (y, z) ∈ U_{j}, & (z, y) ∉ U_{j}, \\ (z, x) ∈ U_{k}, & (x, z) ∉ U_{k}, \end{matrix}

for some i, j, k. By the cyclic symmetry of the list (x, y, z) we may assume that either i ≤ j ≤ k or k ≤ j ≤ i.

If i ≤ j ≤ k, then, since (x, y) ∈ U_{i} ⊆ U_{j} and (y, z) ∈ U_{j}, the transitivity of the relation U_{j} implies (x, z) ∈ U_{j} ⊆ U_{k}, which is in contradiction with (x, z) ∉ U_{k}.

On the other hand, if k ≤ j ≤ i, then since (y, z) ∈ U_{j} and (z, x) ∈ U_{k} ⊆ U_{j}, the transitivity of the relation U_{j} implies (y, x) ∈ U_{j} ⊆ U_{i}, which is in contradiction with (y, x) ∉ U_{i}. □

Proposition 6.3 allows us to characterize U ⊆ V when U and V are bipartitional relations given by their ordered bipartition representation.

Proposition 6.4. Let U, V ∈ Bip(X) be bipartitional relations represented as U = U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) and V = U(C_{1}^{η_{1}}, C_{2}^{η_{2}}, …, C_{l}^{η_{l}}). Then U is contained in V if and only if the following three conditions are satisfied:

(i) there is an ordered partition π = ({π_{1}}, {π_{2}}, …, {π_{n}}) that is also a permutation which is compatible with both U and V,

(ii) every underlined B_{i} is contained in some underlined C_{j}, (iii) every nonunderlined C_{i} is contained in some nonunderlined B_{j}.

Proof. Assume first that U is contained in V. Then there is a maximal chain c in Bip(X) containing both U and V. By Proposition 6.3 there is an ordered partition π_{c} compatible with every element of c, and this ordered partition is a permutation, so condition (i) is satisfied. Consider an underlined block B_{i}. For every x, y ∈ B_{i} we have (x, y) ∈ U and so (x, y) ∈ V since U ⊆ V. Hence B_{i} is contained in some C_{j}. The proof of condition (iii) is analogous.

We are left to show that whenever U is not contained in V, at least one of the given conditions is violated. Assume U ⊈ V and consider an ordered pair (x, y) ∈ U \ V. If (y, x) ∈ U holds as well then x and y are contained in the same underlined block in the representation of U. Thus condition (ii) is violated since (x, y) ∉ V. Similarly (y, x) ∉ V implies a violation of condition (iii). We are left with the case where (x, y) ∈ U, (y, x) ∉ U, (x, y) ∉ V, and (y, x) ∈ V. Now condition (i) is violated. Indeed, let π = ({π_{1}}, {π_{2}}, …, {π_{n}}) be an arbitrary ordered partition that is also a permutation, satisfying x = π_{i} and y = π_{j}. By definition, if π is compatible with U then we must have i < j while compatibility with V requires just the opposite, j < i. □

7. The distributivity of the sublattice of π-compatible bipartitions

In this section we introduce a representation of all π-compatible bipartitions, where π is an arbitrary fixed permutation. We will use this representation to show that Bip_{π}(X) is a distributive lattice, for all ordered partitions π. Without loss of generality, we may assume X = {1, 2, …, n} and, for the moment, we may even assume that π = ({1}, {2}, …, {n}). The analogous results for an arbitrary finite set X and an arbitrary permutation π may be obtained by renaming the elements.

Definition 7.1. Let U be a ({1}, {2}, …, {n})-compatible bipartitional relation, represented as U = U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}), such that the elements in each block are listed in increasing order. We define the code of U as the vector (u_{1}, …, u_{n}) where each u_{i} is an element of the set {±1, ±3}, given by the following rule:

u_{i} = \begin{cases}−1 & if i is listed as the first element in a nonunderlined block; \\ −3 & if i is in a nonunderlined block, but not listed first; \\ 1 & if i is listed as the last element in an underlined block; \\ 3 & if i is in an underlined block, but not listed last. \end{cases}

For example, the code of the bipartitional relation U(\{\underline{1}, \underline{2}\}, \{3\}, \{4, 5\}, \{\underline{6}\}) is (3, 1, −1, −1, −3, 1). Evidently, the ordered bipartition representing U may be uniquely reconstructed from its code, we only need to determine which vectors are valid codes of bipartitional relations.

The definition of the code of U is inspired by formula (5.1) giving the rank of U. According to this formula, we may compute rk(U) of a ({1}, {2}, …, {n})-compatible bipartional relation U as follows. We take the ordered bipartition representation of U, where we list the elements in increasing order. For the first element in each nonunderlined block we increase rk(U) by 1, and we associate no contribution to the other elements in nonunderlined blocks. For the last element in each underlined block we increase rk(U) by 2, and for each other element of an underlined block we increase rk(U) by 3. Thus we could equivalently define a code where the ordered list of weights (−1, −3, 1, 3) is replaced by the list (1, 0, 2, 3). The rank of U is the sum of the coordinates in this “simpler code.” The list of weights (−1, −3, 1, 3) is obtained from (1, 0, 2, 3) by the linear transformation x ↦ 2x − 3. Thus, even for the code we have chosen, rk(U) is a linear function of the sum of the coordinates in its code. Our choice of code has two “advantages” over the “more obvious” code described above:

– The description of a valid code in Corollary 7.3 below involves very simple linear inequalities with integer bounds.

– For our code, the code of U^{c} is obtained by simply taking the negative of the

code of U. In the end, it is only a matter of taste whether one prefers the list of weights (−1, −3, 1, 3) or the list (1, 0, 2, 3), and the results below may be easily transformed to fit the reader’s preference.

Lemma 7.2. A vector (u_{1}, …, u_{n}) ∈ {±1, ±3}^{n} is the code of a ({1}, {2}, …, {n})- compatible bipartitional relation if and only if the following conditions are satisfied:

(i) u_{1} ≠ −3; (ii) u_{n} ≠ 3; (iii) if u_{i} = −3 for some i > 1 then u_{i−1} < 0; (iv) if u_{i} = 3 for some i < n then u_{i+1} > 0.

Proof. The necessity of the conditions above is obvious.

Conversely, given a vector (u_{1}, …, u_{n}) ∈ {±1, ±3}^{n} satisfying the conditions above, we may find a unique ordered bipartition (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) representing a relation whose code is (u_{1}, …, u_{n}), as follows:

(a) Start the first block with 1 if u_{1} = −1 and with \underline{1} if u_{1} > 0. Continue reading the u_{i}’s, left to right.

(b) For 1 < i < n, if u_{i} = −1, start a new nonunderlined block with i. Note that rule (iv) prevents us from starting a nonunderlined block without ending a preceding underlined block.

(c) For 1 < i ≤ n, if u_{i} = −3 then add a nonunderlined i to the nonunderlined block that is currently being written (by condition (iii)).

(d) For 1 < i ≤ n, if u_{i} = 1 then end an underlined block with \underline{i}. This block is a singleton if u_{i−1} < 0, and so i − 1 belongs to a preceding nonunderlined block, or if u_{i−1} = 1, and so \underline{i − 1} ends the preceding underlined block.

(e) For 1 < i < n, if u_{i} = 3, then add an underlined \underline{i} to the current underlined

block if u_{i−1} = 3, and start a new underlined block with \underline{i} if u_{i−1} < 3. Clearly the above process yields the only U whose code is (u_{1}, …, u_{n}), and conditions (i) through (iv) guarantee that the process never halts with an error. □

Lemma 7.2 may be rephrased in terms of inequalities as follows.

Corollary 7.3. A vector (u_{1}, …, u_{n}) ∈ {±1, ±3}^{n} is the code of a ({1}, {2}, …, {n})- compatible bipartitional relation if and only if it satisfies u_{1} ≥ −1, u_{n} ≤ 1 and u_{i} − u_{i+1} ≤ 2 for i = 1, 2, …, n − 1.

Theorem 7.4. Let U and V be ({1}, {2}, …, {n})-compatible bipartitional relations with codes (u_{1}, …, u_{n}) respectively (v_{1}, …, v_{n}). Then U ⊆ V if and only if u_{s} ≤ v_{s} holds for s = 1, 2, …, n.

Proof. Assume that U = U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) and V = U(C_{1}^{η_{1}}, C_{2}^{η_{2}}, …, C_{l}^{η_{l}}). Since U and V are both ({1}, {2}, …, {n})-compatible, by Proposition 6.4, U is contained in V if and only if every underlined B_{i} is contained in some underlined C_{j} and every nonunderlined C_{i} is contained in some nonunderlined B_{j}. It suffices to show that this is equivalent to u_{s} ≤ v_{s} for all s.

Assume U ⊆ V first, and consider the possible values of u_{s}, for a fixed s ∈ {1, 2, …, n}. Let B_{j} be the block of U containing s. If u_{s} = −3, then u_{s} ≤ v_{s} is automatically true. If u_{s} = −1 then v_{s} cannot be −3, otherwise the nonunderlined block C_{i} containing s has a smaller element in C_{i}, whereas the least element of the nonunderlined block B_{j} is s. Only B_{j} could contain C_{i}, but it does not. This contradiction shows that v_{s} ≥ −1 = u_{s}. If u_{s} = 1 then s is an element in an underlined block B_{i} of U. This block B_{i} must be contained in some underlined C_{j}. In other words, s belongs to an underlined block in V showing v_{s} ≥ 1 = u_{s}. Finally, if u_{s} = 3, then \{\underline{s}, \underline{s + 1}\} is the subset of some underlined B_{i}. This B_{i} is contained in some underlined C_{j}, for which we must have \{\underline{s}, \underline{s + 1}\} ⊆ C_{j}. Thus, s is not the last element in C_{j}, forcing v_{s} ≥ 3 = u_{s}.

For the converse, assume, by way of contradiction, that u_{s} ≤ v_{s} for 1 ≤ s ≤ n, but U ⊈ V. Then either condition (ii) or (iii) of Proposition 6.4 is violated.

Case 1. Some nonunderlined C_{i} is not contained in any nonunderlined B_{j}. If the least element s of C_{i} belongs to some underlined B_{j} then, because of v_{s} < 0 and u_{s} > 0 we have u_{s} > v_{s}, a contradiction. It remains the case where s belongs to some nonunderlined B_{j}. In this case let t be the least element of C_{i} which does not belong to the same B_{j} as s. Such a t exists since the entire block C_{i} is not contained in B_{j}. Now we have v_{t} = −3 and u_{t} ≥ −1, implying v_{t} < u_{t}, again contradicting our assumption.

Case 2. Some underlined B_{i} is not contained in any underlined C_{j}. This case is the dual of the previous one, see also Lemma 7.5 below.

In both cases we obtain that U ⊈ V implies u_{t} > v_{t} for some t, which is absurd. □

Lemma 7.5. If (u_{1}, …, u_{n}) is the code of the bipartitional relation U then (−u_{n}, …, −u_{1}) is the code of U^{c}.

The proof is straightforward and is left to the reader.

Using Theorem 7.4 and Corollary 7.3 we are able to show that the sublattice of π-compatible bipartitional relations is distributive for any ordered partition π.

Theorem 7.6. Let π be any ordered partition on X. Then the lattice Bip_{π}(X) is distributive.

Proof. Without loss of generality, let X = {1, 2, …, n}. It suffices to consider the case where π = ({1}, {2}, …, {n}). For, if π = (C_{1}, C_{2}, …, C_{k}), then, from the remarks immediately following Definition 6.1, it is easy to see by compressing the blocks C_{i} to singletons {i} that

Bip_{π}({1, 2, …, n}) ≅ Bip_{({1},{2},...,{k})}({1, 2, …, k}).  (7.1)

From now on, let π = ({1}, {2}, …, {n}). By Theorem 7.4 and Corollary 7.3, the partially ordered set Bip_{π}(X) is isomorphic to the set of all vectors (u_{1}, …, u_{n}) ∈ {±1, ±3} satisfying u_{1} ≥ −1, u_{n} ≤ 1 and u_{i} − u_{i+1} ≤ 2 for i = 1, 2, …, n − 1, partially ordered by the relation (u_{1}, …, u_{n}) ≤ (v_{1}, …, v_{n}) if and only if u_{i} ≤ v_{i} holds for all i. We claim that the join and meet operations in this representation are given by

(u_{1}, …, u_{n}) ∨ (v_{1}, …, v_{n}) = (max(u_{1}, v_{1}), …, max(u_{n}, v_{n})) and

(u_{1}, …, u_{n}) ∧ (v_{1}, …, v_{n}) = (min(u_{1}, v_{1}), …, min(u_{n}, v_{n})).

Clearly the above operations yield the join and meet of the two vectors in the larger lattice of all vectors from {±1, ±3}^{n}, partially ordered by the Cartesian product of natural orders of integers. Thus we only need to show that (max(u_{1}, v_{1}), …, max(u_{n}, v_{n})) and (min(u_{1}, v_{1}), …, min(u_{n}, v_{n})) satisfy the inequalities required by Corollary 7.3, given that (u_{1}, …, u_{n}) and (v_{1}, …, v_{n}) satisfy these inequalities. The verification of this observation is straightforward and is left to the reader. The theorem now follows from the fact that the max and min operations are distributive over each other. □

The next example shows that the entire lattice Bip(X) is not distributive for |X| ≥ 2, and that, in fact, it is not even modular.

Example 7.7. Let X = {1, 2, …, n} for some n ≥ 2 and consider the bipartitional relations U_{1} = U(\{1\}, \{2\}, …, \{n\}), U_{2} = U(\{\underline{1}\}, \{\underline{2}\}, …, \{\underline{n}\}), and V = U(\{n\}, \{n − 1}, …, {1}). It is easy to verify that U_{1} is contained in U_{2}, the join U_{1} ∨ V is X × X, and the meet U_{2} ∧ V is ∅. The set {U_{1}, U_{2}, V, ∅, X × X}, shown in Figure 3, is thus a sublattice, isomorphic to the smallest example of a nonmodular lattice.

∅ = U(\{1, 2, …, n\}) V = U(\{n\}, \{n − 1\}, …, \{1\}) U_{1} = U(\{1\}, \{2\}, …, \{n\}) U_{2} = U(\{\underline{1}\}, \{\underline{2}\}, …, \{\underline{n}\}) X × X = U(\{\underline{1}, \underline{2}, …, \underline{n}\})

Figure 3. Nonmodular sublattice contained in Bip({1, 2, …, n})

By Birkhoff’s theorem [21, Th. 3.4.1], every distributive lattice is isomorphic to the lattice of order ideals in the poset of its join-irreducible elements. In order to apply this result, we need to find the join-irreducible elements in Bip_{π}(X). In preparation for the corresponding result (see Theorem 7.10 below), we first characterize the cover relations in Bip_{π}(X). Again, without loss of generality, we may assume that X = {1, 2, …, n} and π = ({1}, {2}, …, {n}).

Proposition 7.8. Let X = {1, 2, …, n}, and let π be the permutation π = ({1}, {2}, …, {n}). Let U ⫋ V be π-compatible bipartitional relations in Bip(X). Then V covers U in Bip(X) if and only if V covers U in Bip_{π}(X).

Proof. Clearly, if V covers U in Bip(X) it also covers it in Bip_{π}(X). We only need to show that whenever V ⊃ U holds in Bip_{π}(X), then there is a π-compatible U′ covering U in Bip(X) such that U ⊂ U′ ⊆ V holds in Bip_{π}(X). We prove this statement by considering the codes (u_{1}, …, u_{n}) of U and (v_{1}, …, v_{n}) of V. Assume that u_{i} ≤ v_{i} holds for i = 1, 2, …, n and that j is the least index such that u_{j} < v_{j}.

Case 1. u_{j} = −3. In this case j > 1 and u_{j−1} is negative. The element j is in a nonunderlined block of U, and it is not the first element of this block. Let U′ be the ({1}, {2}, …, {n})-compatible bipartitional relation obtained from U by splitting the block containing j into two adjacent blocks, such that the second block begins with j. Then the code (u′_{1}, …, u′_{n}) of U′ is obtained from the code (u_{1}, …, u_{n}) by increasing u_{j} to u′_{j} = −1 and leaving all other coordinates unchanged. Since u_{j} < v_{j}, we have −1 ≤ v_{j}, and thus u′_{i} ≤ v_{i} holds for i = 1, 2, …, n.

Case 2. u_{j} = −1. In this case u_{j−1} (if it exists) is not 3 and U has a nonunderlined block starting at j. Since −1 = u_{j} < v_{j}, we also have 1 ≤ v_{j}, and so v_{j} is positive.

Subcase 2a. u_{j+1} = −3, i.e., j+1 belongs to the nonunderlined block of U that started at j. Thus, by condition (iii) in Lemma 7.2, v_{j+1} cannot be −3 and so −1 ≤ v_{j+1}. Let U′ be the ({1}, {2}, …, {n})-compatible bipartitional relation obtained from U by splitting the block containing j +1 into two adjacent blocks, such that the second block begins with j + 1. Just like in Case 1, the code (u′_{1}, …, u′_{n}) of U′ is obtained from the code (u_{1}, …, u_{n}) by increasing u_{j+1} = −3 to u′_{j+1} = −1, and so u′_{i} ≤ v_{i} holds for all i.

Subcase 2b. u_{j+1} ≠ −3, i.e., the nonunderlined block containing j is a singleton block. Let U′ be the ({1}, {2}, …, {n})-compatible bipartitional relation obtained from U by changing the nonunderlined block \{j\} into an underlined block \{\underline{j}\}. The code (u′_{1}, …, u′_{n}) of U′ is obtained from the code (u_{1}, …, u_{n}) by increasing u_{j} = −1 to u′_{j} = 1, leaving all other coordinates unchanged. Since v_{j} ≥ 1, we have u′_{i} ≤ v_{i} for all i.

Case 3. u_{j} = 1 (thus v_{j} = 3). There is an underlined block in U ending with j, whereas the underlined block containing j in V does not end with j.

Subcase 3a. u_{j+1} < 0. By condition (iii) of Lemma 7.2, we must have u_{j+1} = −1. Moreover, v_{j} = 3 and condition (iv) of Lemma 7.2 imply v_{j+1} ≥ 1. Therefore there is a nonunderlined block in U starting at j + 1 and, thus, u_{j+1} < v_{j+1} is satisfied. We may now repeat the reasoning of Case 2 for j + 1.

Subcase 3b. u_{j+1} > 0, i.e., there is an adjacent underlined block in U starting with j + 1. Let U′ be the ({1}, {2}, …, {n})-compatible bipartitional relation obtained from U by merging the underlined blocks containing j and j + 1. The code (u′_{1}, …, u′_{n}) of U′ is obtained from the code (u_{1}, …, u_{n}) by increasing u_{j} = 1 to u′_{j} = 3, leaving all other coordinates unchanged. Since v_{j} = 3, we have u′_{i} ≤ v_{i} for all i. □

Corollary 7.9. For any permutation π of X, every interval [U, V] in Bip_{π}(X) has the same rank as the corresponding interval [U, V] in Bip(X).

Now we are in the position to describe the join-irreducible elements in Bip_{π}(X).

Theorem 7.10. Let X = {1, 2, …, n} and π = ({1}, {2}, …, {n}). Then Bip_{π}(X) has the following 3n − 2 join-irreducible elements:

(i) E(i) := U({1, …, i − 1}, {i, …, n}) for i ∈ {2, …, n}.

(ii) F (i) := U(\{1, …, i − 1\}, \{\underline{i}\}, \{i + 1, …, n\}) for i ∈ \{1, 2, …, n\}. Here the first

block is omitted for i = 1 and the last block is omitted for i = n. (iii) G(i) := U(\{1, …, i − 1\}, \{\underline{i}, \underline{i + 1}\}, \{i + 2, …, n\}) for i ∈ \{1, 2, …, n − 1\}. Here

the first block is omitted for i = 1 and the last block is omitted for i = n − 1. Moreover, the bipartitional relations listed under (i) and (ii) are also join-irreducible elements in Bip(X).

Proof. The bipartitional relations of type (i) above have rank 1 and are clearly joinirreducible elements even in the larger lattice Bip(X). By Theorem 5.1, a bipartitional relation of type (ii) covers exactly one element of Bip(X), namely U({1, …, i − 1}, {i}, {i + 1, …, n}). This bipartitional relation belongs of course also to Bip_{π}(X). Thus the bipartitional relations listed under (ii) are again join-irreducible elements even in the larger lattice Bip(X).

The element G(i) in (iii) is not join-irreducible in Bip(X) since, by Theorem 5.1, it covers exactly the two elements

U(\{1, 2, …, i − 1\}, \{\underline{i}\}, \{\underline{i + 1}\}, \{i + 2, …, n\})

and

U(\{1, 2, …, i − 1\}, \{\underline{i + 1}\}, \{\underline{i}\}, \{i + 2, …, n\}).

However, only one, namely the former, is π-compatible. Hence, by Proposition 7.8, G(i) covers exactly one element in Bip_{π}(X), which means that it is join-irreducible in Bip_{π}(X).

Conversely, if V is join-irreducible in Bip_{π}(X), then, be definition, it covers exactly one element, U say, in Bip_{π}(X). By Proposition 7.8, V covers U also in Bip(X). (V may cover other elements in Bip(X) as well, but they must not be π-compatible.) By Theorem 5.1, U can be obtained from V by either splitting an underlined block into adjacent underlined blocks, or by joining two adjacent nonunderlined blocks, or by changing a singleton underlined block into a nonunderlined block. V is join-irreducible if and only if exactly one such operation yields a π-compatible U. This excludes the possibility of V having two underlined blocks, or an underlined block with more than two elements, or three adjacent nonunderlined blocks. Furthermore, it also excludes the possibility of V having an underlined block at the same time as having two adjacent nonunderlined blocks. It is now obvious that only the possibilities listed under (i)–(iii) remain. □

Figure 4 indicates the Hasse diagram of the subposet of join-irreducible elements of Bip_{({1},{2},...,{n})}({1, …, n}).

F (n) F (1)  F (2)  F (3) ⋯ F (n − 1) E(2) G(1)  G(n − 1) E(n) G(2) E(3)

Figure 4. Join-irreducible elements of Bip_{({1},{2},...,{n})}({1, …, n})

8. The J–T decomposition of the order complex of an interval in the bipartition lattice

This section contains preparatory material for the proofs of our main results in Sections 9 and 10. The ultimate goal is to construct an enumeration of all maximal chains in Bip(X), respectively in any interval thereof, such that the results of Babson and Hersh reviewed in Section 3 become applicable. The way that we propose here to arrive there proceeds in two steps. Recall that, by Proposition 6.3, each maximal chain c determines a unique permutation π such that all elements of c are π-compatible. The first step, performed in this section, will consist of finding a suitable enumeration of all permutations. This induces a “pre-enumeration” of the maximal chains, by putting them together in smaller groups according to their associated permutations and enumerating these groups. Then, in the subsequent sections, we shall refine this pre-enumeration further to a full enumeration of all maximal chains by declaring how to enumerate the maximal chains corresponding to the same permutation.

For all of Bip(X), the proposed enumeration of all permutations of X will be obtained by the classical Johnson–Trotter algorithm [16, 23]. For proper intervals in Bip(X), we will need to consider a variant adapted to enumerate only specific subgroups of the full permutation group (namely Young subgroups, although this term will be of no importance in the sequel; the interested reader may consult [22, Sec. 7.18] for more information). We recall the Johnson–Trotter algorithm next, and subsequently describe its variant. In Theorem 8.7 we prove a property of the Johnson–Trotter algorithm and of its variant which will be crucial in proving the key lemma, Lemma 9.2, and of its adaptation to the results of Section 10, showing that the enumerations of maximal chains that we construct grows by creating skipped intervals. The adaptation of Lemma 9.2 to the case of intervals in Section 10 is made possible by the introduction of the J–T decomposition of the order complex of an interval in Definition 8.9, and by Theorem 8.10, discussing the properties of this decomposition.

The original version of the Johnson–Trotter algorithm [16, 23] is used to enumerate all permutations of {1, 2, …, n} in such a way that each permutation differs from the preceding one by a transposition of adjacent elements. It may be described recursively as follows.

(1) The Johnson–Trotter enumeration of all permutations of {1} is ({1}).

(2) Assume we are given the Johnson–Trotter enumeration of all permutations of {1, 2, …, n−1}. If the permutation ({σ_{1}}, …, {σ_{n−1}}) is an odd numbered item in this enumeration, then we replace it with the list

({σ_{1}}, …, {σ_{n−1}}, {n}), ({σ_{1}}, …, {n}, {σ_{n−1}}), …, ({n}, {σ_{1}}, …, {σ_{n−1}}).

Otherwise we replace it with the list

({n}, {σ_{1}}, …, {σ_{n−1}}), ({σ_{1}}, {n}, …, {σ_{n−1}}), …, ({σ_{1}}, …, {σ_{n−1}}, {n}).

For example, the Johnson–Trotter enumeration of all permutations of {1, 2, 3} is

({1}, {2}, {3}), ({1}, {3}, {2}), ({3}, {1}, {2}),
({3}, {2}, {1}), ({2}, {3}, {1}), ({2}, {1}, {3}).

Before we are able to describe the announced variant, we need to first review some facts about ordered partitions and their relation to bipartitions.

Definition 8.1. We say that an ordered partition π of X refines the ordered partition (C_{1}, …, C_{k}) if each block C_{i} is the union of consecutive blocks of π.

Lemma 8.2. For an ordered partition π of X, a bipartitional relation U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) ⊆ X × X is π-compatible if and only if π refines the ordered partition (B_{1}, B_{2}, …, B_{k}).

Refinement defines a partial order on the ordered partitions of X. The poset thus obtained is isomorphic to the subposet of Bip(X) formed by all bipartitions having only underlined blocks. This isomorphism is made precise in the following definition.

Definition 8.3. Let (C_{1}, C_{2}, …, C_{k}) be an ordered partition of X. We define the underlined representation of (C_{1}, C_{2}, …, C_{k}) in Bip(X) as the bipartitional relation U(C_{1}^{1}, C_{2}^{1}, …, C_{k}^{1}), and we denote it by \underline{U}(C_{1}, C_{2}, …, C_{k}).

Lemma 8.4. Let π and ρ be ordered partitions of X. Then π refines ρ if and only if \underline{U}(π) ≤ \underline{U}(ρ) in Bip(X).

If U = U(B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) and V = U(C_{1}^{η_{1}}, C_{2}^{η_{2}}, …, C_{l}^{η_{l}}), then we will be interested in finding all permutations refining the ordered partition (B_{1}, B_{2}, …, B_{k}), as well as the ordered partition (C_{1}, C_{2}, …, C_{l}).

Corollary 8.5. A permutation π of X refines the ordered partitions (B_{1}, B_{2}, …, B_{k}) and (C_{1}, C_{2}, …, C_{l}) if and only if

\underline{U}(π) ≤ \underline{U}(B_{1}, B_{2}, …, B_{k}) ∧ \underline{U}(C_{1}, C_{2}, …, C_{l}).

Note that \underline{U}(B_{1}, B_{2}, …, B_{k}) ∧ \underline{U}(C_{1}, C_{2}, …, C_{l}) is taken in Bip(X). Hence, the resulting bipartitional relation may also have nonunderlined blocks in its ordered bipartition representation. By Proposition 6.4, such a bipartitional relation cannot contain a bipartition having only underlined blocks, and in that case there is no permutation refining both (B_{1}, B_{2}, …, B_{k}) and (C_{1}, C_{2}, …, C_{l}). If, however, \underline{U}(B_{1}, B_{2}, …, B_{k}) ∧ \underline{U}(C_{1}, C_{2}, …, C_{l}) has an ordered bipartition representation (D_{1}^{1}, …, D_{m}^{1}) consisting of underlined blocks only, then π refines both (B_{1}, B_{2}, …, B_{k}) and (C_{1}, C_{2}, …, C_{l}) if and only if it refines (D_{1}, …, D_{m}). Therefore enumerating all permutations associated to some maximal chain containing U and V is equivalent to enumerating all permutations refining a given ordered partition.

Now we adapt the Johnson–Trotter algorithm to list all permutations refining a given ordered partition (C_{1}, …, C_{k}) of {1, 2, …, n} such that each permutation differs from the preceding one by a transposition of adjacent blocks, as follows.

(1) For n = 1 we may only have k = 1, C_{1} = {1}, and we list the permutation ({1}).

(2) Assume we already know how to build the Johnson–Trotter enumeration of all permutations refining any given ordered partition of {1, 2, …, n − 1}. Let (C_{1}, …, C_{k}) be an ordered partition of {1, 2, …, n}. If {n} = C_{m} is a block by itself, then (C_{1}, …, C_{m−1}, C_{m+1}, …, C_{k}) is an ordered partition of {1, 2, …, n− 1}. List all permutations π of {1, 2, …, n−1} refining (C_{1}, …, C_{m−1}, C_{m+1}, …, C_{n}), and insert {n} between the last block of π contained in C_{m−1} and the first block of π contained in C_{m+1}. (At most one of these blocks may be missing if m = 1 or m = k.) We obtain an appropriate enumeration.

From now on we may assume that the block C_{m} containing n contains at least one more element. Introducing C′_{j} = C_{j} \ {n} for j = 1, …, k, (C′_{1}, …, C′_{k}) is an ordered partition of {1, 2, …, n − 1}, and we consider the Johnson–Trotter enumeration of all permutations refining this ordered partition. Let

π = ({π_{1}}, …, {π_{r}}, …, {π_{s}}, …, {π_{n}})

be a permutation in this enumeration, where C′_{m} = {π_{r}, …, π_{s}}. (Note that r and s are the same for all permutations in the enumeration.) If π is an odd numbered item in this enumeration, then we replace it with the list

({π_{1}}, …, {π_{r}}, …, {π_{s}}, {n}, …, {π_{n}}),

({π_{1}}, …, {π_{r}}, …, {n}, {π_{s}}, …, {π_{n}}),

…, ({π_{1}}, …, {n}, {π_{r}}, …, {π_{s}}, …, {π_{n}}),

otherwise we replace it with the list

({π_{1}}, …, {n}, {π_{r}}, …, {π_{s}}, …, {π_{n}}),

({π_{1}}, …, {π_{r}}, {n}, …, {π_{s}}, …, {π_{n}}),

…, ({π_{1}}, …, {π_{r}}, …, {π_{s}}, {n}, …, {π_{n}}).

For example, the Johnson–Trotter enumeration of all permutations refining ({1, 3}, {2, 4}) is built recursively as follows.

(1) The list of all permutations refining ({1}) is ({1}).

(2) The list of all permutations refining ({1}, {2}) is ({1}, {2}).

(3) The list of all permutations refining ({1, 3}, {2}) is

({1}, {3}, {2}), ({3}, {1}, {2}).

(4) The list of all permutations refining ({1, 3}, {2, 4}) is

({1}, {3}, {2}, {4}), ({1}, {3}, {4}, {2}),
({3}, {1}, {4}, {2}), ({3}, {1}, {2}, {4}).

Recall (see [5, p. 324]) that the shelling of a simplicial complex △ is an enumeration F_{1}, …, F_{m} of its facets such that each facet has the same dimension as △ and, for each i > 1, any face τ ⊂ F_{i} that is contained in some preceding F_{k}, is also contained in a preceding F_{j} whose intersection F_{j} ∩ F_{i} with F_{i} has codimension one (that is, making F_{j} ∩ F_{i} “as large as possible”). Our next goal is to decompose each order complex △([U, V] \ {U, V }) in a manner resembling a shelling. In the decomposition we are going to describe, the role of the facets in a shelling will be played by subcomplexes of the form

△([U, V]_{π} \ {U, V }),  (8.1)

where π is a permutation such that U and V are π-compatible, and [U, V]_{π} stands for the subposet of [U, V] consisting of all π-compatible bipartitional relations. As a consequence, we need to understand intersections of subcomplexes of the form (8.1). For this, it is necessary to know when a bipartitional relation is simultaneously compatible with two different ordered partitions. In this regard, Lemma 8.4 yields the following immediate characterization.

Corollary 8.6. A bipartitional relation U is simultaneously compatible with the ordered partitions (B_{1}, …, B_{k}) and (C_{1}, …, C_{l}) if and only if U is compatible with the ordered partition (D_{1}, …, D_{m}) given by

\underline{U}(D_{1}, …, D_{m}) = \underline{U}(B_{1}, …, B_{k}) ∨ \underline{U}(C_{1}, …, C_{l}).

Obviously (D_{1}, …, D_{m}) is the “finest common coarsening” of the ordered partitions (B_{1}, …, B_{k}) and (C_{1}, …, C_{l}). In particular, in the case where X = {1, 2, …, n} and the permutations σ = ({σ_{1}}, …, {σ_{n}}) and π = ({π_{1}}, …, {π_{n}}) differ in a transposition of adjacent blocks, say, π = ({σ_{1}}, …, {σ_{i+1}}, {σ_{i}}, … {σ_{n}}), then

\underline{U}(σ) ∨ \underline{U}(π) = (\{\underline{σ_{1}}\}, …, \{\underline{σ_{i}}, \underline{σ_{i+1}}\}, …, \{\underline{σ_{n}}\}).

Thus \underline{U}(σ) ∨ \underline{U}(π) covers \underline{U}(σ) and \underline{U}(π) in Bip(\{1, 2, …, n\}), and the intersection Bip_{σ}({1, 2, …, n}) ∩ Bip_{π}({1, 2, …, n}) has the largest possible rank that a proper intersection of two lattices of the form Bip_{σ}({1, 2, …, n}) may have. As a consequence, for every interval [U, V] such that U and V are simultaneously σ- and π-compatible, the subcomplexes △([U, V]_{σ} \ {U, V }) and △([U, V]_{π} \ {U, V }) are either equal or their intersection has codimension 3 in both subcomplexes (recall the formula (5.1) for the rank function and the fact that, in the latter case, the above intersection arises by identifying σ_{i} and σ_{i+1}). This makes such intersections analogous to codimension 1 faces in a shelling (recall again the definition [5, p. 324] of a shelling).

The following technical result is the key result for establishing the above indicated shelling-like property of the announced J–T decomposition (to be defined in Definition 8.9) in Theorem 8.10.(iii).

Theorem 8.7. Let (C_{1}, …, C_{k}) be an ordered partition of the set {1, 2, …, n} and consider the Johnson–Trotter enumeration of all permutations refining this ordered partition. If τ precedes σ in this enumeration, then there is a permutation π preceding σ in this enumeration, which differs from σ only in a transposition of adjacent blocks, and which satisfies

\underline{U}(τ) ∨ \underline{U}(σ) ≥ \underline{U}(π) ∨ \underline{U}(σ) ⋗ \underline{U}(σ).

Here, V_{1} ⋗ V_{2} means that V_{1} covers V_{2}.

Example 8.8. The permutation τ = ({4}, {1}, {2}, {3}) precedes σ = ({4}, {2}, {3}, {1}) in the Johnson–Trotter enumeration of all permutations of {1, 2, 3, 4}, and we have

\underline{U}(τ) ∨ \underline{U}(σ) = (\{\underline{4}\}, \{\underline{1}, \underline{2}, \underline{3}\}).

The permutation π = ({4}, {3}, {2}, {1}) also precedes σ in the Johnson–Trotter enumeration, and π differs from σ only in the transposition of the adjacent blocks {2} and {3}. Thus we have

\underline{U}(π) ∨ \underline{U}(σ) = (\{\underline{4}\}, \{\underline{2}, \underline{3}\}, \{\underline{1}\}),

implying

(\{\underline{4}\}, \{\underline{1}, \underline{2}, \underline{3}\}) ≥ (\{\underline{4}\}, \{\underline{2}, \underline{3}\}, \{\underline{1}\}) ⋗ (\{\underline{4}\}, \{\underline{2}\}, \{\underline{3}\}, \{\underline{1}\}).

We should perhaps also point out that, here, π does not immediately precede σ in the Johnson–Trotter enumeration.

Proof of Theorem 8.7. We prove the statement by induction on n. There is nothing to prove for n = 1. Assume that the statement holds up to n − 1. Consider a τ preceding a σ in the Johnson–Trotter enumeration of all permutations refining the ordered partition (C_{1}, …, C_{k}) of {1, 2, …, n}. Let σ \ n, respectively τ \ n, denote the permutations obtained from σ, respectively τ, by deleting the block {n}. Let (C′_{1}, …, C′_{l}) be the ordered partition considered right before inserting n in the Johnson– Trotter enumeration associated to (C_{1}, …, C_{k}). In other words, we have l = k − 1 and (C′_{1}, …, C′_{k−1}) = (C_{1}, …, C_{m−1}, C_{m+1}, …, C_{k}) if {n} = C_{m} is a block by itself (for some m), and we have l = k and C′_{j} = C_{j} \ {n} for all j otherwise. Note that σ \ n and τ \ n belong to the set of all permutations of {1, 2, …, n − 1} refining (C′_{1}, …, C′_{l}).

Case 1. σ \ n ≠ τ \ n. Then τ \ n precedes σ \ n in the Johnson–Trotter enumeration of all permutations refining (C′_{1}, …, C′_{l}). By our induction hypothesis, there is a permutation π′ preceding σ \ n in this enumeration such that we have

\underline{U}(τ \ n) ∨ \underline{U}(σ \ n) ≥ \underline{U}(π′) ∨ \underline{U}(σ \ n) ⋗ \underline{U}(σ \ n).  (8.2)

Here, for some i, we have

\underline{U}(π′) ∨ \underline{U}(σ \ n) = (\{\underline{σ_{1}}\}, …, \{\underline{σ_{i}}, \underline{σ_{i+1}}\}, …, \{\underline{σ_{n−1}}\}),

and we may assume

σ \ n = ({σ_{1}}, …, {σ_{i}}, {σ_{i+1}}, …, {σ_{n−1}})

and

π′ = ({σ_{1}}, …, {σ_{i+1}}, {σ_{i}}, …, {σ_{n−1}}).

Subcase 1a. σ = ({σ_{1}}, …, {σ_{j}}, {n}, {σ_{j+1}}, …, {σ_{n−1}}) holds for some j ≠ i. Then we set

π := ({π′_{1}}, …, {π′_{j}}, {n}, {π′_{j+1}}, …, {π′_{n−1}}),

where π′ = ({π′_{1}}, …, {π′_{n−1}}). In other words, we insert {n} at the same place into π′ as the place where it needs to be inserted into σ \ n to obtain σ. By the recursive structure of the Johnson–Trotter enumeration, π precedes σ in the enumeration of all permutations refining (C_{1}, …, C_{k}). Moreover, π differs from σ only in transposing the adjacent blocks {σ_{i}} and {σ_{i+1}}. Thus,

\underline{U}(π) ∨ \underline{U}(σ) = (\{\underline{σ_{1}}\}, …, \{\underline{σ_{i}}, \underline{σ_{i+1}}\}, …, \{\underline{σ_{n}}\}),  (8.3)

and it covers \underline{U}(σ) in Bip(\{1, 2, …, n\}). Finally, by (8.2), the ordered bipartition representation of \underline{U}(τ \ n) ∨ \underline{U}(σ \ n) contains σ_{i} and σ_{i+1} in the same underlined block. Therefore σ_{i} and σ_{i+1} are also in the same underlined block in the ordered bipartition representing \underline{U}(τ)∨\underline{U}(σ)- Together with (8.3), this implies \underline{U}(τ)∨\underline{U}(σ) ≥ \underline{U}(π)∨\underline{U}(σ).

Subcase 1b. σ = ({σ_{1}}, …, {σ_{i}}, {n}, {σ_{i+1}}, …, {σ_{n−1}}). In the same way as at the end of the previous subcase, the fact that σ_{i} and σ_{i+1} belong to the same underlined block of \underline{U}(τ \ n) ∨ \underline{U}(σ \ n) implies that they also belong to the same underlined block of \underline{U}(τ) ∨ \underline{U}(σ). Now, (σ_{i}, n) ∈ \underline{U}(σ) and (n, σ_{i+1}) ∈ \underline{U}(σ) imply that n also belongs to the same underlined block of \underline{U}(τ) ∨ \underline{U}(σ). Thus \underline{U}(τ) ∨ \underline{U}(σ) contains the bipartitional relation V represented by the ordered bipartition

(\{\underline{σ_{1}}\}, …, \{\underline{σ_{i−1}}\}, \{\underline{σ_{i}}, \underline{n}, \underline{σ_{i+1}}\}, \{\underline{σ_{i+2}}\}, …, \{\underline{σ_{n−1}}\}).

As a consequence, by Lemma 8.4, the block C_{m} containing n also contains σ_{i} and σ_{i+1}. Therefore the permutations

ρ′ = ({σ_{1}}, …, {n}, {σ_{i}}, {σ_{i+1}}, …, {σ_{n−1}})

and

ρ′′ = ({σ_{1}}, …, {σ_{i}}, {σ_{i+1}}, {n}, …, {σ_{n−1}})

both refine (C_{1}, …, C_{k}). By the structure of the Johnson–Trotter enumeration, one of them precedes σ. This one may be chosen as π. It follows that

\underline{U}(τ) ∨ \underline{U}(σ) ≥ V ≩ \underline{U}(π) ∨ \underline{U}(σ) ⋗ \underline{U}(σ).

Case 2. σ \ n = τ \ n. Without loss of generality, we may assume that σ \ n = τ \ n is an even numbered item in the Johnson–Trotter enumeration of all permutations refining (C′_{1}, …, C′_{l}). Since τ precedes σ in the Johnson–Trotter enumeration of all permutations refining (C_{1}, …, C_{k}), we must have

τ = ({σ_{1}}, …, {σ_{i}}, {n}, {σ_{i+1}}, …, {σ_{n−1}})

and

σ = ({σ_{1}}, …, {σ_{j}}, {n}, {σ_{j+1}}, …, {σ_{n−1}})

for some i < j ≤ n − 1. It is easy to see that

\underline{U}(τ) ∨ \underline{U}(σ) = U(\{\underline{σ_{1}}\}, …, \{\underline{σ_{i}}\}, \{\underline{σ_{i+1}}, … \underline{σ_{j}}, \underline{n}\}, \{\underline{σ_{j+1}}\}, …, \{\underline{σ_{n−1}}\}).

As a consequence, by Lemma 8.4, the block C_{m} containing n also contains σ_{i+1}, … σ_{j}. Therefore the permutation

π = ({σ_{1}}, …, {σ_{j−1}}, {n}, {σ_{j}}, …, {σ_{n−1}})

also refines (C_{1}, …, C_{k}) and it precedes σ in the Johnson–Trotter enumeration. We have

\underline{U}(π) ∨ \underline{U}(σ) = (\{\underline{σ_{1}}\}, …, \{\underline{σ_{j−1}}\}, \{\underline{n}, \underline{σ_{j}}\}, \{\underline{σ_{j+1}}\} …, \{\underline{σ_{n−1}}\}).

In particular, \underline{U}(π)∨\underline{U}(σ) covers \underline{U}(σ), and \underline{U}(π)∨\underline{U}(σ) is contained in \underline{U}(τ)∨\underline{U}(σ). □

Using Theorem 8.7, we now show that, for any interval [U, V] ⊆ Bip(X), the order complex △([U, V] \ {U, V }) has a “shelling-like” decomposition. Namely, we may write

△([U, V] \ {U, V }) = ⋃_{π} △([U, V]_{π} \ {U, V }),  (8.4)

where the union is taken over all permutations π such that both U and V are πcompatible. (The notation [U, V]_{π} was defined just after (8.1).) We may enumerate these permutations using the Johnson–Trotter enumeration. To see the similarity with a shelling, the reader should imagine that the role of facets in a shelling is played in the decomposition (8.4) by the subcomplexes △([U, V]_{π} \ {U, V }), all of which have the same dimension as △([U, V] \ {U, V }) by Corollary 7.9. Moreover, by Theorem 7.6, each poset [U, V]_{π} is a distributive lattice and, by a result due to Provan [18] (cf. also [4, Cor. 2.2]), the order complex △([U, V]_{π} \ {U, V }) is either the order complex of a Boolean lattice (and thus isomorphic to the boundary complex of a simplex) or it is a polyhedral ball. In the case where U = ∅ and V = X × X, i.e., when [U, V] = Bip(X), the sublattice [U, V]_{π} is never a Boolean lattice, thus we decompose the order complex as a union of balls. Note next that for proper intervals [U, V] ⊂ Bip(X) it may happen that △([U, V]_{π} \ {U, V }) = △([U, V]_{σ} \ {U, V }) holds for some π ≠ σ. For example, in the case where the ordered bipartition (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}) representing U and the ordered bipartition (C_{1}^{η_{1}}, C_{2}^{η_{2}}, …, C_{l}^{η_{l}}) representing V satisfy ε_{1} = η_{1} = 0 and B_{1} = C_{1} = {1, 2} then a permutation π = ({π_{1}}, …, {π_{n}}) refining both (B_{1}, B_{2}, …, B_{k}) and (C_{1}, C_{2}, …, C_{l}) must satisfy {π_{1}, π_{2}} = {1, 2}, but it does not matter whether π_{1} = 1 and π_{2} = 2 or π_{1} = 2 and π_{2} = 1. By Proposition 6.3, π arises as the only ordered partition that is compatible with all elements of some maximal chain c containing U and V, but the choice of the values of π_{1} and π_{2} is related to the part of c that is outside the interval [U, V]. We may overcome this difficulty by keeping only the first copy of each △([U, V]_{π} \ {U, V }).

Definition 8.9. Let [U, V] ⊆ Bip(X) be an interval, where U = (B_{1}^{ε_{1}}, B_{2}^{ε_{2}}, …, B_{k}^{ε_{k}}), V = (C_{1}^{η_{1}}, C_{2}^{η_{2}}, …, C_{l}^{η_{l}}), and let the ordered partition (D_{1}, …, D_{m}) be given by

\underline{U}(D_{1}, …, D_{m}) = \underline{U}(B_{1}, B_{2}, …, B_{k}) ∧ \underline{U}(C_{1}, C_{2}, …, C_{l}).

We define the J–T decomposition of △([U, V] \ {U, V }) as follows:

(1) We list the order complexes △([U, V]_{π} \ {U, V }) in the order of the Johnson– Trotter enumeration of permutations π refining (D_{1}, …, D_{m}). (By Corollary 8.5, these are the permutations π such that U and V are both π-compatible.)

(2) If the same simplicial complex occurs several times in the above enumeration, we keep only its first occurrence and remove all other occurrences.

(3) The remaining list △_{1}, …, △_{N} is the J–T decomposition of △([U, V] \ {U, V }).

Theorem 8.10. The J–T decomposition △_{1}, …, △_{N} of △([U, V] \ {U, V }) has the following properties:

(i) each △_{i} has the same dimension as △([U, V] \ {U, V }); (ii) each △_{i} is either isomorphic to the boundary complex of a simplex or it is a

polyhedral ball; (iii) for i > 1, any face contained in △_{i}∩(⋃_{j<i} △_{j}) is also contained in △_{k} for some

k < i such that there are permutations σ and π that differ only in a transposition of adjacent blocks, with △_{i} = △([U, V]_{σ} \{U, V }) and △_{k} = △([U, V]_{π} \{U, V }).

Proof. We only need to show (iii) since, as mentioned above, item (i) follows from Corollary 7.9, and item (ii) follows from Provan’s result [18, 4]. Assume △_{i} = △([U, V]_{σ} \ {U, V }) and consider a face γ that is also contained in △_{j} = △([U, V]_{τ} \ {U, V }) for some j < i. This means that the elements of γ are σ-compatible and τ-compatible bipartitional relations. By Corollary 8.6, these bipartitional relations are also compatible with the ordered bipartition ρ given by \underline{U}(ρ) = \underline{U}(τ) ∨ \underline{U}(σ). By Theorem 8.7, there is a permutation π preceding σ in the Johnson–Trotter enumeration of all permutations ρ with the property that both U and V are ρ-compatible, such that \underline{U}(τ) ∨ \underline{U}(σ) ≥ \underline{U}(π) ∨ \underline{U}(σ) ⋗ \underline{U}(σ). Thus the elements of the face γ are also π-compatible, and γ is contained in

△([U, V]_{σ} \ {U, V }) ∩ △([U, V]_{π} \ {U, V }).

Here △([U, V]_{π} \ {U, V }) = △_{k} for some k < i in the J–T decomposition, in particular, △_{k} ≠ △_{i}. □

9. The topology of the order complex of Bip(X) \ {∅, X × X}

In this section we determine the homotopy type of the order complex of Bip(X) \ {∅, X ×X}. To achieve this goal, we construct a listing of all maximal chains contained in Bip(X) and then use the results of Babson and Hersh [1] as described in Section 3 to see that there is exactly one critical cell in this order complex with respect to the induced discrete Morse matching.

We now describe the announced listing of all maximal chains of Bip(X). Without loss of generality, we may assume that X = {1, 2, …, n}. The construction involves the following three steps.

Step 1. By Proposition 6.3, for each maximal chain c in Bip(X), there is a unique permutation σ such that all elements of c are σ-compatible. Let us list the permutations of X using the Johnson–Trotter enumeration and associate to each permutation σ the set of all σ-compatible maximal chains, or, equivalently, of all maximal chains in Bip_{σ}(X).

Step 2. By Theorem 7.6, for a fixed σ, the lattice Bip_{σ}(X) is distributive. By [5, Th. 4.5], it has an EL-labelling using its join-irreducible elements. In this EL-labelling, an edge UV, where U and V are elements of Bip_{σ}(X) such that U is covered by V, is labelled by the unique join-irreducible element W ∈ Bip_{σ}(X) such that W ⊆ V but W ⊈ U. We use this EL-labelling to order the maximal chains of Bip_{σ}(X) in the following way. The join-irreducible elements of Bip_{σ}(X) for σ = ({1}, {2}, …, {n}) are given in Proposition 7.10. By permuting the elements of X, it is easy to see that the join-irreducible elements of Bip_{σ}(X) are the following:

(i) E(σ, i) := ({σ_{1}, …, σ_{i−1}}, {σ_{i}, …, σ_{n}}) for i ∈ {2, …, n}, (ii) F (σ, i) := (\{σ_{1}, …, σ_{i−1}\}, \{\underline{σ_{i}}\}, \{σ_{i+1}, …, σ_{n}\}) for i ∈ \{1, 2, …, n\}, (iii) G(σ, i) := (\{σ_{1}, …, σ_{i−1}\}, \{\underline{σ_{i}}, \underline{σ_{i+1}}\}, \{σ_{i+2}, …, σ_{n}\}) for i ∈ \{1, 2, …, n − 1\}.

For all what follows in this section, we fix the linear extension

E(σ, 2) ≺ F (σ, 1) ≺ E(σ, 3) ≺ F (σ, 2) ≺ G(σ, 1) ≺ ⋯
≺ E(σ, k + 2) ≺ F (σ, k + 1) ≺ G(σ, k) ≺ ⋯
E(σ, n) ≺ F (σ, n − 1) ≺ G(σ, n − 2) ≺ F (σ, n) ≺ G(σ, n − 1).  (9.1)

(Here, we use the symbol ≺ to distinguish the linear extension in (9.1) from the order relation in Bip_{σ}(X).) Now, as announced above, we associate to each maximal chain c : ∅ = U_{0} ⋖ ⋯ ⋖ U_{3n−2} = X × X contained in Bip_{σ}(X) the word z_{1}z_{2} ⋯ z_{3n−2}, where the letter z_{i} is the unique join-irreducible element contained in U_{i} but not contained in U_{i−1}. We list the maximal chains in Bip_{σ}(X) according to the lexicographic order of their associated words.

Step 3. Given a σ-compatible maximal chain c and a σ′-compatible maximal chain c′, the chain c precedes c′ if and only if either σ precedes σ′ in the Johnson–Trotter enumeration, or if σ = σ′ and c precedes c′ in the ordering of the maximal chains in Bip_{σ}(X) described in Step 2.

The list of chains we thus obtain is in general not a poset lexicographic order as defined in [1], as may be seen in the following example.

Example 9.1. Consider the cover relations U({1, 2, 3, 4}) ⋖ U({1, 2}, {3, 4}) and U({1, 2, 3, 4}) ⋖ U({1, 4}, {2, 3}) in Bip({1, 2, 3, 4}). Here U({1, 2}, {3, 4}) is ({1}, {2}, {3}, {4})-compatible and ({2}, {1}, {3}, {4})-compatible, but not ({1}, {4}, {2}, {3})-compatible, whereas U({1, 4}, {2, 3}) is ({1}, {4}, {2}, {3})-compat-ible but not ({1}, {2}, {3}, {4})-compatible nor ({2}, {1}, {3}, {4})-compatible . In the Johnson–Trotter enumeration of all permutations of {1, 2, 3, 4}, the permutations ({1}, {2}, {3}, {4}), ({1}, {4}, {2}, {3}), ({2}, {1}, {3}, {4}) follow in this order. It is not true that every maximal chain extending U({1, 2, 3, 4}) ⋖ U({1, 2}, {3, 4}) precedes every maximal chain extending U({1, 2, 3, 4}) ⋖ U({1, 4}, {2, 3}) since any ({1}, {4}, {2}, {3})-compatible maximal chain precedes any ({2}, {1}, {3}, {4})-com-patible maximal chain. On the other hand, it is also not true that every maximal chain extending U({1, 2, 3, 4})⋖U({1, 4}, {2, 3}) precedes every maximal chain extending U({1, 2, 3, 4}) ⋖ U({1, 2}, {3, 4}) since any ({1}, {2}, {3}, {4})-compatible maximal chain precedes any ({1}, {4}, {2}, {3})-compatible maximal chain.

However, our list of maximal chains still grows by skipped intervals, as defined in Definition 3.1, which we prove in the lemma below. In the proof of the lemma, and also later, we use the following well-known property of the EL-labelling of distributive lattices which we recalled in Step 2 above, and which involves the notion of a descent in a word z_{1}z_{2} ⋯ z_{3n−2}: an index i for which z_{i} ≻ z_{i+1} is called a descent. When we list the maximal chains of Bip_{σ}(X) in lexicographic order as described in Step 2, then a subset {U_{i_{1}}, …, U_{i_{k}}} of a maximal chain c with associated word z_{1}z_{2} ⋯ z_{3n−2} does not belong to any previously listed maximal chain if and only if the set of their ranks contains all descents of z_{1}z_{2} ⋯ z_{3n−2}.

Lemma 9.2. Let X = {1, 2, …, n}, and let σ = ({σ_{1}}, {σ_{2}}, …, {σ_{n}}) be a permutation of X. Furthermore, let c be a σ-compatible maximal chain of Bip(X), and assume that the word z_{1}z_{2} ⋯ z_{3n−2} is associated to c in Bip_{σ}(X). As before, we list the maximal chains in Bip_{σ}(X) according to the lexicographic order of their associated words, as described in Step 2 at the beginning of this section. Then a chain contained in c is also contained in an earlier listed maximal chain of Bip_{σ}(X) if and only if the set of its ranks is disjoint from at least one of the following intervals:

(i) all singletons [i, i] = {i} such that z_{i} ≻ z_{i+1}; (ii) all intervals [i, j] with z_{i} = E(σ, q), z_{j+1} = G(σ, q − 1), for some q, such that

the permutation π obtained from σ by exchanging the adjacent blocks {σ_{q−1}} and {σ_{q}} precedes σ in the Johnson–Trotter enumeration.

Proof. Consider first the intersection of c : ∅ = U_{0}⋖⋯⋖U_{3n−2} = X ×X with another σcompatible maximal chain that was listed earlier. As noted in the paragraph preceding the lemma, a chain belongs to such an intersection if and only if its set of ranks does not contain the descent set {i : z_{i} ≻ z_{i+1}} of the word z_{1}z_{2} ⋯ z_{3n−2} or, equivalently, if it is disjoint from at least one of the singletons listed in (i).

Consider next the intersection of c with a τ-compatible maximal chain c′, where τ precedes σ in the Johnson–Trotter enumeration. This intersection is contained in Bip_{τ}(X) ∩ Bip_{σ}(X) which, by part (iii) of Theorem 8.10, is contained in some Bip_{π}(X), where π is obtained from σ by exchanging the adjacent blocks {σ_{q−1}} and {σ_{q}}, for some q, and π precedes σ in the Johnson–Trotter enumeration. We may extend the intersection c ∩ c′ to a π-compatible maximal chain. Clearly, the intersection c ∩ c′ is then a chain in Bip_{π}(X) ∩ Bip_{σ}(X). Consider now the word z_{1}z_{2} ⋯ z_{3n−2} associated to c and define i and j by z_{i} = E(σ, q) and z_{j+1} = G(σ, q − 1). Equivalently, i is the smallest rank at which we find a bipartition U_{i} that contains q − 1 and q in different (nonunderlined) blocks, and j + 1 is the smallest rank at which we find a bipartition U_{j+1} containing q − 1 and q in the same underlined block. Thus the chain

U_{0} ⋖ U_{1} ⋖ ⋯ ⋖ U_{i−1} < U_{j+1} ⋖ U_{j+2} ⋖ ⋯ ⋖ U_{3n−2}  (9.2)

is π-compatible and σ-compatible, whereas any U_{k} of rank k ∈ [i, j] is only σ-compatible. The intersection c ∩ c′ must be contained in (9.2), whence its set of ranks must be disjoint from [i, j]. Therefore, the intersection c ∩ c′ satisfies condition (ii) with the above π.

Conversely, let γ be a subchain of c such that the set of its ranks avoids an interval [i, j], where the interval is one of the intervals described in item (ii). Then γ is a subchain of

U_{0} ⋖ U_{1} ⋖ ⋯ ⋖ U_{i−1} < U_{j+1} ⋖ U_{j+2} ⋖ ⋯ ⋖ U_{3n−2}.

This chain may be extended to the π-compatible maximal chain obtained from c by replacing each U_{k}, i ≤ k ≤ j, by the bipartitional relation U′_{k} obtained from U_{k} by swapping the elements σ_{q−1} and σ_{q}. Therefore γ is contained in the intersection of c with a π-compatible maximal chain, where π precedes σ. □

Theorem 9.3. The order complex

△(Bip(X) \ {∅, X × X})  (9.3)

is homotopy equivalent to a sphere of dimension |X| − 2.

Proof. As before, without loss of generality, we may assume that X = {1, 2, …, n}. Lemma 9.2 says that the enumeration of maximal faces of the order complex (9.3) described in Steps 1–3 at the beginning of this section grows by creating skipped intervals. Consequently, by Theorem 3.3, in the Morse matching constructed by Babson and Hersh [1] from such an enumeration, at most one critical cell is contributed per maximal chain, namely exactly when the set of intervals I(c) (defined in Definition 3.1) covers all elements of the set of ranks {1, …, 3n − 2}.

We are going to show that there is exactly one maximal chain in our enumeration that contributes a critical cell. This maximal chain is the lexicographically first chain among the maximal chains that are compatible with the last permutation in the Johnson– Trotter enumeration, namely

τ̂ := ({2}, {1}, {3}, {4}, …, {n}).  (9.4)

According to our construction, the lexicographically first chain which is compatible with this permutation is

∅ ≺ H_{1} ≺ H_{1} ∨ H_{2} ≺ ⋯ ≺ H_{1} ∨ H_{2} ∨ ⋯ ∨ H_{3n−2},  (9.5)

where H_{1}, H_{2}, …, H_{3n−2} is the enumeration of the join-irreducible elements in (9.1), with σ replaced by τ̂. Subsequently, we will compute the dimension of the critical cell contributed by this maximal chain, using the last part of Theorem 3.3. The proof will be completed by taking recourse to Theorem 3.4.

Consider now a σ-compatible chain c, whose associated word is z_{1}z_{2} ⋯ z_{3n−2} (compare Step 2 at the beginning of this section), and assume that it contributes a critical cell. Our first goal is to determine the set of intervals I(c). According to Lemma 9.2, it consists of those intervals listed in items (i) and (ii) in this lemma that are minimal with respect to inclusion. Clearly, all singletons listed in item (i) of Lemma 9.2 belong to I(c). Because of the property of EL-labellings of distributive lattices that we recalled in the paragraph before Lemma 9.2, this implies in particular that any other interval [i, j], i < j, can only be minimal with respect to inclusion if the substring z_{i}z_{i+1} ⋯ z_{j+1} of z_{1}z_{2} ⋯ z_{3n−2} contains no descent. It is then not difficult to see from the choice of the linear extension (9.1) of the subposet of join-irreducible elements (cf. Figure 4) that an interval [i, j] listed in item (ii) of Lemma 9.2 belongs to I(c) if and only if we have z_{i} ≺ z_{i+1} ≺ ⋯ ≺ z_{j+1}, there is a q such that z_{i} = E(σ, q) and z_{j+1} = G(σ, q − 1), and the permutation π obtained from σ by exchanging the adjacent blocks {σ_{q−1}} and {σ_{q}} precedes σ in the Johnson–Trotter enumeration.

The question remains, how exactly the join-irreducible elements in (9.1) can be aligned in a word z_{1}z_{2} ⋯ z_{3n−2} such that the above described minimal intervals in I(c) cover all of [1, 3n − 3], and what properties the permutation σ must have. (While reading the subsequent paragraphs, the reader is advised to keep Figure 4 in mind.)

In order to answer the above question, we claim that, if the above described minimal intervals in I(c) cover all of {1, 2, …, n}, for all k = 1, 2, …, n we have the following three properties:

(a) The letters appearing in the union of intervals

⋃_{j=2}^{k}[E(σ, j), G(σ, j − 1)]  (9.6)

in the poset of join-irreducible elements of Bip_{σ}({1, 2, …, n}) appear in increasing order (with respect to the linear order described in (9.1)) in z_{1}z_{2} ⋯ z_{3n−2} (from left to right).

(b) For j = 2, …, k, the permutation obtained from σ by exchanging the blocks {σ_{j−1}} and {σ_{j}} precedes σ in the Johnson–Trotter enumeration.

(c) For j = 2, …, k, the substring E(σ, j) ⋯ G(σ, j − 1) of z_{1}z_{2} ⋯ z_{3n−2} contains no descents.

We prove these assertions by induction on k. All three statements are vacuously true for k = 1. Assume now that the statements are true for some k ∈ {1, 2, …, n − 1}. We will show that they also hold if we increase k to k + 1.

Let us for the moment suppose that k = 1. Since E(σ, 2) < G(σ, 1) holds in Bip({1, 2, …, n}), the letter E(σ, 2) must appear before the letter G(σ, 1) in the word z_{1}z_{2} ⋯ z_{3n−2}, and the substring E(σ, 2) ⋯ G(σ, 1) contains an ascent, i.e., a letter followed by a larger letter. Let z_{l} ≺ z_{l+1} be the leftmost such ascent.

On the other hand, if k ≥ 2, then, by (c), we know that the substring E(σ, k) ⋯ G(σ, k−1) contains no descent. Moreover, since E(σ, k) < G(σ, k) in Bip({1, 2, …, n}), the letter G(σ, k) must appear after the letter E(σ, k). From these facts taken together, we infer that G(σ, k) must appear after G(σ, k − 1), and the substring G(σ, k − 1) ⋯ G(σ, k) contains an ascent. Let z_{l} ≺ z_{l+1} be the leftmost such ascent.

To summarize both cases, in z_{1}z_{2} ⋯ z_{3n−2} we find

E(σ, k + 1) ⋯ G(σ, k − 1) ⋯ z_{l}z_{l+1} ⋯ G(σ, k),  (9.7)

where z_{l} ≺ z_{l+1} marks the ascent that we identified in both cases, and where G(σ, k −1) is not present if k = 1. It is allowed that z_{l} = G(σ, k − 1) (or even that z_{l} = E(σ, 2) in the case that k = 1) or z_{l+1} = G(σ, k).

The position l of the ascent z_{l} ≺ z_{l+1} cannot be covered by a singleton listed under item (i) in Lemma 9.2, thus it must be covered by a minimal interval [i, j] listed under item (ii) in Lemma 9.2. In particular, i ≤ l.

Assume, by way of contradiction, that the interval [i, j] is not associated to E(σ, k+1) and G(σ, k). Then we must have z_{i} = E(σ, q) and z_{j+1} = G(σ, q −1) for some q ≠ k +1. We claim that q > k + 1. This is immediate when k = 1. For k ≥ 2, the inequality q > k + 1 follows from the fact that criterion (a) does not allow any letter G(σ, q − 1) satisfying q ≤ k to appear after G(σ, k − 1) (recall (9.7)).

Let us compare now the position of the letter E(σ, q) with the position of E(σ, 2) if k = 1, or with the position of the letter G(σ, k − 1) if k ≥ 2. The letter E(σ, q) cannot appear before E(σ, 2) when k = 1, nor can it appear before G(σ, k − 1) when k ≥ 2, because E(σ, q) ≻ E(σ, 2), respectively E(σ, q) ≻ G(σ, k − 1), would force a descent in the substring E(σ, q) ⋯ G(σ, q − 1), making [i, j] nonminimal. However, E(σ, q) cannot appear after E(σ, 2) when k = 1, nor can it appear after G(σ, k − 1) when k ≥ 2. For, if this is the case, then we have an ascent in the substring in E(σ, 2) ⋯ E(σ, q), respectively in the substring G(σ, k − 1) ⋯ E(σ, q), and thus an ascent that occurs before E(σ, q) = z_{i}, a contradiction with our choice that z_{l} ≺ z_{l+1} was the leftmost ascent in the substring E(σ, 2) ⋯ G(σ, 1), respectively in G(σ, k − 1) ⋯ G(σ, k) (recall that i ≤ l).

Thus we must have z_{i} = E(σ, k + 1) and z_{j+1} = G(σ, k), and the permutation obtained by exchanging the blocks {σ_{k}} and {σ_{k+1}} must precede σ in the Johnson– Trotter enumeration. This proves that (b) remains valid when we increase k to k + 1. Furthermore, the substring E(σ, k+1) ⋯ G(σ, k) must not contain any descents, proving that (c) remains valid when we increase k to k + 1. As a consequence, the elements in [E(σ, k + 1), G(σ, k)] in the poset of join-irreducible elements of Bip_{σ}({1, 2, …, n}) appear in increasing order in z_{1}z_{2} … z_{3n−2}. The letter E(σ, k + 1) must appear before G(σ, k −1) since E(σ, k +1) < G(σ, k −1) holds in Bip({1, 2, …, n}). This implies that the substrings E(σ, k) ⋯ G(σ, k − 1) and E(σ, k + 1) ⋯ G(σ, k) overlap, with G(σ, k) following after G(σ, k − 1). In addition, both substrings contain no descents. Therefore (a) remains also valid when we increase k to k + 1. This concludes the proof of the properties (a)–(c).

For k = n, statement (b) forces σ to be the last permutation in the Johnson–Trotter enumeration. Statement (a) implies that z_{1}z_{2} ⋯ z_{3n−2} must not contain any descents, making c the first maximal chain in Bip_{σ}({1, 2, …, n}). (Note that, for k = n, the union of intervals (9.6) contains all 3n − 2 join irreducible elements of Bip_{σ}({1, 2, …, n}).)

Thus far we have shown that the only maximal chain c that may contribute a critical cell is the lexicographically first τ̂-compatible chain (that is, the chain (9.5), with τ̂ being given in (9.4)), where τ̂ is the last permutation in the Johnson–Trotter enumeration, given in (9.4). We show that this chain c contributes a critical cell, by computing explicitly the minimal intervals I(c), and then we find the dimension of the critical cell by calculating the simplified system J(c), as given in Definition 3.2, and by applying the last part of Theorem 3.3.

Since the word z_{1}z_{2} ⋯ z_{3n−2} associated to c contains no descents, it must be the string of join-irreducible elements listed in the order described in (9.1), and all intervals [i, j], where z_{i} = E(σ, k) and z_{j+1} = G(σ, k − 1), with k = 2, 3, …, n, belong to I(c). Using the list (9.1), we obtain that

I(c) = \begin{cases}\{[1, 3]\} & if n = 2; \\ \{[1, 4]\} ∪ ⋃_{k=1}^{n−3}\{[3k, 3k + 4]\} ∪ \{[3n − 6, 3n − 3]\} & if n ≥ 3. \end{cases}  (9.8)

For any n ≥ 2, the union of intervals contained in I(c) is {1, 2, …, 3n−3}, therefore c does contribute a critical cell by Theorem 3.3. We are left to find the family of intervals J(c), using Definition 3.2 and (9.8) above. It is easy to see that J(c) is given by

J(c) = \begin{cases}\{[1, 3]\} & if n = 2; \\ \{[1, 4]\} ∪ ⋃_{k=1}^{n−3}\{[3k + 2, 3k + 4]\} ∪ \{[3n − 4, 3n − 3]\} & if n ≥ 3. \end{cases}  (9.9)

Since |J(c)| = n − 1, the dimension of the only critical cell is n − 2 by the last part of Theorem 3.3. The theorem now follows upon invoking Theorem 3.4. □

The above theorem implies in particular that △(Bip(X) \ {∅, X × X}) has a nonvanishing homology below the top dimension. This has the following immediate consequence.

Corollary 9.4. The order complex

△(Bip(X) \ {∅, X × X})

is not Cohen–Macaulay.

If we combine Theorem 9.3 with Philip Hall’s theorem [21, Prop. 3.8.6] stating that the Möbius function of a graded poset P with minimum element ˆ0 and maximum element ˆ1 is the reduced Euler characteristic of the order complex △(P \ {ˆ0, ˆ1}), then we obtain the following immediate corollary.

Corollary 9.5. The Möbius function of the minimum and maximal element in Bip(X) is given by

μ(∅, X × X) = (−1)^{|X|}.

10. Regular and irregular intervals in Bip(X)

In this concluding section, we handle proper intervals of Bip(X). We distinguish between two kinds of intervals, regular and irregular ones (see Definition 10.1.) As we show in Proposition 10.2, regular intervals are isomorphic to the direct product of Boolean lattices and smaller bipartition lattices. Since the Möbius function of Boolean lattices is well-known, and since we computed the Möbius function of bipartition lattices in Corollary 9.5, it is then easy to compute the Möbius function of regular intervals, see Corollary 10.3. For irregular intervals we prove that their order complexes are always contractible, see Theorem 10.4. Hence, the Möbius function of an irregular interval vanishes. We must leave the question of the topological structure of regular intervals open.

Definition 10.1. We say that an interval [U, V] ⊆ Bip(X) is regular if every x satisfying (x, x) ∈ V \ U also satisfies {y ∈ X : x ∼_{U} y} = {y ∈ X : x ∼_{V} y}. Otherwise we call [U, V] irregular.

In other words, an interval [U, V] is regular if and only if, for every x belonging to a nonunderlined block in U and to an underlined block in V, the block containing x in U is equal to the block containing x in V in the ordered bipartition representations of U and V, respectively. We remark that all of Bip(X), that is, the interval [∅, X × X], is a regular interval. Indeed, assuming without loss of generality that X = {1, 2, …, n}, we have

[∅, X × X] = [U(\{1, 2, …, n\}), U(\{\underline{1}, \underline{2}, …, \underline{n}\})].

Proposition 10.2. Every regular interval [U, V] ⊆ Bip(X) is isomorphic to a direct product of Boolean lattices and lattices of the form Bip(B), where each B is a block in the ordered bipartition representation of U and of V such that B is nonunderlined in U and underlined in B.

Proof. We prove the statement by induction on the total number of blocks in the ordered bipartition representations of U and V.

Assume first that there is no x ∈ X such that x is contained in an underlined block of V and in a nonunderlined block of U. By Proposition 6.4, every nonunderlined block of V is contained in some nonunderlined block of U, and every underlined block of U is contained in some underlined block of V. Thus, by our assumption, X may be uniquely written as a disjoint union X = X_{1}∪X_{2}∪⋯∪X_{m} where each X_{i} is either an underlined block of V (which is also the union of some consecutive underlined blocks of U) or a nonunderlined block of U (which is also the union of some consecutive nonunderlined blocks of V). Moreover, since every X_{i} is either a block of U, or the union of consecutive blocks of U, we may order the blocks X_{i} in such a way that, for all i < j, the relation x <_{U} y holds for all x ∈ X_{i} and y ∈ X_{j}. Since U ⊆ V, it is easy to see that, for all i < j, x ∈ X_{i} and y ∈ X_{j}, we also have x <_{V} y. A relation W ⊆ X × X is bipartitional and belongs to the interval [U, V] if and only if, for each i, the restriction W |_{X_{i}} is bipartitional, belongs to [U |_{X_{i}} , V |_{X_{i}}], and we have x <_{W} y for all x ∈ X_{i}, y ∈ X_{j} satisfying i < j. Thus the interval [U, V] is isomorphic to the direct product ∏_{i=1}^{m}[U |_{X_{i}} , V |_{X_{i}}].

Given an interval [U |_{X_{i}} , V |_{X_{i}}], there are two possibilities: either U |_{X_{i}} has a single nonunderlined block, or V |_{X_{i}} has a single underlined block. It is then easily seen by compressing the (nonunderlined) blocks of V |_{X_{i}}, respectively the (underlined) blocks of U |_{X_{i}}, to singleton blocks, that each interval [U |_{X_{i}} , V |_{X_{i}}] is isomorphic to a Boolean lattice.

Assume finally that there is at least one x ∈ X such that (x, x) ∈ V \ U. Since [U, V] is regular, the nonunderlined block Y_{1} (say) of U containing x is an underlined block of V. Let Y_{0} (Y_{2}) be the (possibly empty) union of all blocks listed before (after) Y_{1} in the ordered bipartition representation of U. Since Y_{1} is also a block of V, and since U ⊆ V, it is easy to see that Y_{0} (Y_{2}) is also the union of all blocks listed before (after) Y_{1} in the ordered bipartition representation of V. A relation W ⊂ X × X is bipartitional and belongs to [U, V] if and only if for each i ∈ {0, 1, 2} the restriction W |_{Y_{i}} is bipartitional, belongs to [U |_{Y_{i}} , V |_{Y_{i}}] and, for all i < j, x_{i} ∈ Y_{i} and x_{j} ∈ Y_{j} implies x_{i} <_{W} x_{j}.

(Here we assume that the restriction of any relation to the empty set is the empty set, hence Y_{i} = ∅ implies |[U |_{Y_{i}} , V |_{Y_{i}}]| = 1.) Thus the interval [U, V] is isomorphic to ∏_{i=0}^{2}[U |_{Y_{i}} , V |_{Y_{i}}]. We may apply the induction hypothesis to the intervals [U |_{Y_{0}} , V |_{Y_{0}} ] and [U |_{Y_{2}} , V |_{Y_{2}} ], whereas the interval [U |_{Y_{1}} , V |_{Y_{1}} ] is isomorphic to Bip(Y_{1}). □

From the previous proposition, we obtain the following immediate corollary for the Möbius function of regular intervals.

Corollary 10.3. Let [U, V] be a regular interval in Bip(X). Then we have

μ(U, V) = (−1)^{rk(V)−rk(U)}.

Proof. By [21, Prop. 3.8.2], the Möbius function behaves multiplicatively for products of posets. Furthermore, it is well-known that the Möbius function of the minimum and maximum element in a Boolean lattice of rank m is equal to (−1)^{m}. Finally, by Corollary 9.5, we also know that the Möbius function of the minimum and maximum element in a bipartition lattice of rank 3n − 2 is equal to (−1)^{n} = (−1)^{3n−2}. If we put all this together and also recall that the rank function of products of posets is additive, we obtain the claim. □

Our final theorem says that irregular intervals have a contractible order complex.

Theorem 10.4. If [U, V] ⊆ Bip({1, 2, …, n}) is not regular, then the order complex △([U, V] \ {U, V }) is contractible. In particular, the Möbius function μ(U, V) vanishes in Bip({1, 2, …, n}).

We show Theorem 10.4 by adapting the proof of Theorem 9.3. Again, we need to define a listing of all maximal chains of [U, V] to which the results of Section 3 are applicable. As in Section 9, the construction of this listing involves three steps.

Step 1. We list the order complexes △([U, V]_{σ} \ {U, V }), where σ is a permutation of X such that U and V are σ-compatible, using the Johnson–Trotter decomposition of △([U, V] \ {U, V }) as defined in Definition 8.9.

Step 2. By Theorem 7.6, for a fixed σ, the lattice Bip_{σ}(X) is distributive, and, hence, also the subposet [U, V]_{σ} is distributive. As in Step 2 in Section 9, [U, V]_{σ} has an EL-labelling using its join-irreducible elements, due to [5, Th. 4.5].

Evidently, the join-irreducible elements of [U, V]_{σ} may be identified with those elements E(σ, i), F (σ, i), and G(σ, i) which are contained in V but not in U. More precisely, a join-irreducible element H ∈ Bip_{σ}(X) is identified with the join-irreducible element U ∨H ∈ [U, V]_{σ}. In the sequel, by abuse of terminology, when we speak of “the join-irreducible elements of [U, V]_{σ},” then we shall always mean the join-irreducible elements H ∈ Bip_{σ}(X) which are contained in V but not in U, keeping the above identification in mind.

For defining the EL-labelling, however, we need to start with a linear extension of the join-irreducible elements of [U, V]_{σ}. Unlike in Section 9, we select a different linear extension for each σ, the individual choices being independent from each other. Lemma 10.5 below describes the details of these choices.

Analogously to Section 9, we associate to each maximal chain c : U = U_{0}⋖⋯⋖U_{m} = V contained in [U, V]_{σ} the word z_{1}z_{2} ⋯ z_{m} (here m + 1 is the rank of [U, V]_{σ}), where the letter z_{i} is the unique join-irreducible element of Bip_{σ}(X) contained in U_{i} but not contained in U_{i−1}. We list the maximal chains in [U, V]_{σ} according to the lexicographic order of their associated words.

Step 3. Assume that △([U, V]_{σ} \ {U, V }) and △([U, V]_{σ′} \ {U, V }) appear in the J–T decomposition of △([U, V] \ {U, V }). Given a σ-compatible maximal chain c and a σ′-compatible maximal chain c′, the chain c precedes c′ if and only if either △([U, V]_{σ} \ {U, V }) precedes △([U, V]_{σ′} \ {U, V }) in the J–T decomposition, or if σ = σ′ and c precedes c′ in the ordering of [U, V]_{σ} described in Step 2.

Lemma 10.5. Let [U, V] be an interval in Bip({1, 2, …, n}), and let σ = ({σ_{1}}, {σ_{2}}, …, {σ_{n}}) be a permutation such that △([U, V]_{σ} \ {U, V }) appears in the J–T decomposition of △([U, V] \ {U, V }). Assume that some p ∈ {2, …, n} has the following properties:

(a) Exactly one of E(σ, p) and G(σ, p − 1) is contained in V but not in U.

(b) At least one of F (σ, p − 1) and F (σ, p) is contained in V but not in U. Then there is a linear extension of the join-irreducible elements of [U, V]_{σ} such that, no matter what linear extension we select for the other subcomplexes △([U, V]_{π} \ {U, V }), no maximal chain of [U, V]_{σ} contributes a critical cell.

Proof. Consider first the case where E(σ, p) is contained in V but not in U, and G(σ, p− 1) is either contained in U or not contained in V. Without loss of generality, we may assume that F (σ, p) is contained in V but not in U (otherwise we may simply replace F (σ, p) by F (σ, p − 1) in the subsequent argument). This means that, when we label the cover relations U_{1} ⋖ V_{1} in [U, V]_{σ} by the unique join-irreducible element of Bip_{σ}({1, 2, …, n}) that is contained in V_{1} but not in U_{1}, the elements E(σ, p) and F (σ, p) appear among the labels used but G(σ, p−1) does not. Select a linear extension of the join-irreducible elements of [U, V]_{σ} (recall the convention explained in Step 2 after the statement of Theorem 10.4), in which E(σ, p) is the least element. This is possible since E(σ, p) is a minimal element among the join-irreducible elements. We claim that for this labelling, no maximal chain of [U, V]_{σ} contributes a critical cell.

Consider a maximal chain c in [U, V]_{σ}, and assume by way of contradiction that it contributes a critical cell. By Theorem 3.3, this means that the set of intervals I(c) covers all elements of the set of ranks of [U, V]. Let z_{1}z_{2} ⋯ z_{m} be the word associated to c according to Step 2 after Theorem 10.4. In analogy to Lemma 9.2, a chain contained in c is also contained in an earlier listed maximal chain if and only if the set of its ranks is disjoint from at least one of the following intervals:

(i) all singletons [i, i] = {i} such that z_{i} ≻ z_{i+1}, (ii) all intervals [i, j] with z_{i} = E(σ, q), z_{j+1} = G(σ, q − 1), for some q, such that

the permutation π obtained from σ by exchanging the adjacent blocks {σ_{q−1}} and {σ_{q}} makes △([U, V]_{π} \ {U, V }) precede △([U, V]_{σ} \ {U, V }) in the J–T decomposition of △([U, V] \ {U, V }) as described in Definition 8.9.

The proof is essentially the same, and is thus omitted.

Next we have to determine the subset I(c) of the above intervals which are minimal with respect to inclusion. Clearly, I(c) contains all singletons listed under (i). In the same way as in the proof of Theorem 9.3, it can be seen that an interval [i, j] listed in item (ii) belongs to I(c) only if we have z_{i} ≺ z_{i+1} ≺ ⋯ ≺ z_{j+1}. (Note that we do not have an “if and only if” statement anymore, since the “if” part in the proof of Theorem 9.3 followed from the particular choice of the linear extension (9.1) of the poset of join-irreducible elements, which we do not and need not guarantee in the present situation.)

Since E(σ, p) < F (σ, p) holds in Bip({1, 2, …, n}), the letter E(σ, p) must appear before the letter F (σ, p) in z_{1}z_{2} ⋯ z_{m}. Moreover, because of E(σ, p) ≺ F (σ, p), the substring E(σ, p) ⋯ F (σ, p) contains an ascent. Let the leftmost such ascent be at position l, so that we encounter

E(σ, p) ⋯ z_{l}z_{l+1} ⋯ F (σ, p),

with z_{l} ≺ z_{l+1}. The position l of the ascent is not covered by a singleton listed under (i) above, thus it must be covered by a minimal interval [i, j] listed under (ii) above. In particular, we have i ≤ l. The interval [i, j] is associated to z_{i} = E(σ, q) and z_{j+1} = G(σ, q − 1) for some q ≠ p since G(σ, p − 1) is not a join-irreducible element in [U, V]_{σ}. Since the interval [i, j] is minimal, the substring E(σ, q) ⋯ G(σ, q − 1) cannot contain any descents. By our choice of the linear extension of the join-irreducible elements of [U, V]_{σ}, we have E(σ, p) ≺ E(σ, q). Consider now the relative position of the letters E(σ, p) and E(σ, q). If the letter E(σ, q) appears after E(σ, p) in z_{1}z_{2} ⋯ z_{m}, then we encounter

E(σ, p) ⋯ E(σ, q) ⋯ z_{l}z_{l+1} ⋯ F (σ, p).

(It is allowed that z_{l} = E(σ, q) or z_{l+1} = F (σ, p).) Then the substring E(σ, p) ⋯ E(σ, q) contains an ascent which is not covered by the interval [i, j] (recall that z_{i} = E(σ, q)), in contradiction to having selected the leftmost ascent in the substring E(σ, p) ⋯ F (σ, p). On the other hand, if the letter E(σ, q) appears before E(σ, p) in z_{1}z_{2} ⋯ z_{m} then we encounter

E(σ, q) ⋯ E(σ, p) ⋯ z_{l}z_{l+1} ⋯ G(σ, q − 1).

(It is allowed that z_{l} = E(σ, p) or z_{l+1} = G(σ, q − 1).) Because of E(σ, q) ≻ E(σ, p), there is a descent in the substring E(σ, q) ⋯ E(σ, p), in contradiction to the fact that the substring E(σ, q) ⋯ G(σ, q − 1) does not contain any descents.

Consider now the case where G(σ, p−1) is contained in V without being contained in U, and E(σ, p) is either contained in U or not contained in V. This case is similar to the previous one, thus we only outline the necessary changes. Without loss of generality, we may assume that F (σ, p) is contained in V, without being contained in U. Take a linear extension of the partial order on the set of join-irreducible elements of [U, V]_{σ} such that G(σ, p − 1) is the maximal element, and consider the word z_{1}z_{2} ⋯ z_{m} associated to a maximal chain c that contributes a critical cell. Again, by Theorem 3.3, this means that the set of intervals I(c) covers all elements of the set of ranks of [U, V]. Since F (σ, p) < G(σ, p − 1) holds in Bip({1, 2, …, n}), the letter F (σ, p) must appear before the letter G(σ, p − 1) in z_{1}z_{2} ⋯ z_{m}, and the substring F (σ, p) ⋯ G(σ, p − 1) contains an ascent. Consider the rightmost such ascent. This ascent must be covered by an interval [i, j] where z_{i} = E(σ, q) and z_{j+1} = G(σ, q − 1) for some q ≠ p since E(σ, p) is not a join-irreducible element in [U, V]_{σ}. Whether the letter G(σ, p − 1) appears before or after G(σ, q − 1) in z_{1}z_{2} ⋯ z_{m}, we obtain a contradiction, by either finding an ascent in the substring G(σ, p−1) ⋯ G(σ, q−1) to the right of the supposedly rightmost ascent in F (σ, p) ⋯ G(σ, p − 1), or we find a descent in G(σ, q − 1) ⋯ G(σ, p − 1) in contradiction to the substring E(σ, q) ⋯ G(σ, q − 1) not containing any descents. □

Proof of Theorem 10.4. Assume that [U, V] is irregular. Then there is an x ∈ {1, 2, …, n} such that (x, x) ∈ V \ U and the block B of x in U is not equal to the block C of x in V. The goal is to construct an enumeration of all maximal chains of [U, V] using Steps 1–3 after the statement of the theorem such that no maximal chain contributes a critical cell according to Theorem 3.3. The only undetermined place in Steps 1–3 concerned the choice of linear extension of the join-irreducible elements of [U, V]_{σ}.

Let σ be an arbitrary permutation such that U and V are σ-compatible. It suffices to find a p ∈ {2, …, n} which satisfies the criteria given in Lemma 10.5. List the elements σ_{1}, …, σ_{n}, in this order. The elements of B and C form sublists of consecutive elements: B = {σ_{i}, σ_{i+1}, …, σ_{j}} and C = {σ_{k}, σ_{k+1}, …, σ_{l}}, for some i, j, k, l ∈ {1, 2, …, n}, where i ≤ j and k ≤ l, and where the intersection of the intervals [i, j] and [k, l] is not empty since x ∈ B ∩ C. Thus, since B ≠ C, one of the following four situations arises:

Case 1. i < k. In this case, we have {σ_{k−1}, σ_{k}} ⊆ B but {σ_{k−1}, σ_{k}} ∩ C = {σ_{k}}. Thus, G(σ, k − 1) ⊈ V, while E(σ, k) is contained in V, without being contained in U. Similarly, F (σ, k) is contained in V, without being contained in U. We set p = k.

Case 2. i > k. In this case, we have {σ_{i−1}, σ_{i}} ⊆ C but {σ_{i−1}, σ_{i}} ∩ B = {σ_{i}}. Thus, E(σ, i) ⊆ U, while G(σ, i − 1) is contained in V, without being contained in U. Similarly, F (σ, i) is contained in V, without being contained in U. We set p = i.

Case 3. i = k and j < l. In this case, we have {σ_{j}, σ_{j+1}} ⊆ C but {σ_{j}, σ_{j+1}} ∩ B = {σ_{j}}. Thus, E(σ, j+1) ⊆ U, while G(σ, j) is contained in V, without being contained in U. Similarly, F (σ, j) is contained in V, without being contained in U. We set p = j +1.

Case 4. i = k and j > l. In this case, we have {σ_{l}, σ_{l+1}} ⊆ B but {σ_{l}, σ_{l+1}} ∩ C = {σ_{l}}. Thus, G(σ, l) ⊈ V, while E(σ, l +1) is contained in V, without being contained in U. Similarly, F (σ, l) is contained in V, without being contained in U. We set p = l + 1.

We may therefore apply Lemma 10.5 to conclude that there is an enumeration of the maximal chains of [U, V] such that, by Theorem 3.3, there are no critical cells contributed by the associated Morse matching. Consequently, by Theorem 3.4, the order complex △([U, V] \ {U, V }) is contractible. □

Acknowledgments

This project started in 1996 during the authors’ stay at the Mathematical Sciences Research Institute, Berkeley, during the Combinatorics Program 1996/97, organized by Louis Billera, Anders Björner, Curtis Greene, Rodica Simion, and Richard Stanley. It was completed while the first author was on reassignment of duties from UNC Charlotte, enjoying the hospitality of the University of Vienna in Spring 2009. We are indebted to an anonymous referee for an extremely careful reading of the original manuscript and for several valuable suggestions and references concerning the Morse theory part of this paper.

References

[1] E. Babson and P. Hersh, Discrete Morse functions from lexicographic orders, Trans. Amer. Math. Soc. 357 (2004), 509–534.

[2] L. J. Billera and G. Hetyei, Linear inequalities for flags in graded partially ordered sets, J. Combin. Theory, Ser. A 89 (2000), 77–104.

[3] L. J. Billera and G. Hetyei, Decompositions of partially ordered sets, Order 17 (2000), 141–166.

[4] L. J. Billera, S. K. Hsiao and J. S. Provan, Enumeration in convex geometries and associated polytopal subdivisions of spheres, Discrete Comput. Geom. 39 (2008), 123–137.

[5] A. Björner, Shellable and Cohen–Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), 159–183.

[6] D. Foata and C. Krattenthaler, Graphical major indices II, Séminaire Lotharingien Combin. 34 (1995), Article B34k, 16pp.

[7] D. Foata and D. Zeilberger, Graphical major indices, J. Comput. Appl. Math. 68 (1996), 79–101.

[8] R. Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), 90–145.

[9] R. Forman, Discrete Morse theory and the cohomology ring, Trans. Amer. Math. Soc. 354 (2002), 5063–5085.

[10] R. Forman, A user’s guide to discrete Morse theory, Séminaire Lotharingien Combin. 48 (2002), Article B48c, 35 pp.

[11] G.-N. Han, Ordres bipartitionnaires et statistiques sur les mots, Electronic J. Combin. 3 (1996), Article #R3, 5 pp.

[12] P. Hanlon, P. Hersh and J. Shareshian, A GL_{n}(q)-analogue of the partition lattice, preprint, 2009.

[13] P. Hersh, Lexicographic shellability for balanced complexes, J. Algebraic Combin. 17 (2003), 225–254.

[14] P. Hersh, On optimizing discrete Morse functions, Adv. Appl. Math. 35 (2005), 294–322.

[15] P. Hersh and V. Welker, Gröbner basis degree bounds on T or_{.}^{k[Λ]}(k, k)_{.} and discrete Morse theory for posets, in: Integer points in polyhedra–geometry, number theory, algebra, optimization, Contemp. Math., vol. 374, Amer. Math. Soc., Providence, RI, 2005, pp. 101–138.

[16] S. Johnson, Generation of permutations by adjacent transposition, Math. Comp. 17 (1963), 282– 285.

[17] A. Kasraoui, A classification of mahonian maj-inv statistics, Adv. Appl. Math. 42 (2009) 342–357.

[18] J. S. Provan, Decompositions, shellings, and diameters of simplicial complexes and convex polyhedra, Ph.D. thesis, Cornell University, Ithaca, 1997.

[19] G.-C. Rota, On the foundation of combinatorial theory I. Theory of Möbius functions, Z. Wahrsch. Verw. Gebiete 2 (1964), 340–368.

[20] B. E. Sagan and V. Vatter, The Möbius function of a composition poset, J. Algebraic Combin. 24 (2006), 117–136.

[21] R. P. Stanley, “Enumerative Combinatorics, Vol. I,” 2nd ed., Cambridge University Press, Cambridge, 1997.

[22] R. P. Stanley, “Enumerative Combinatorics, Vol. II,” Cambridge University Press, Cambridge, 1999.

[23] H. F. Trotter, Algorithm 115, Perm. Comm. ACM 5 (1962), 434–435.

Department of Mathematics and Statistics, UNC-Charlotte, Charlotte NC 28223-

0001. WWW: http://www.math.uncc.edu/~ghetyei/.

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna,

Austria. WWW: http://www.mat.univie.ac.at/~kratt.