Generating Linear Extensions of Posets by Transpositions

Frank Ruskey ^{∗}

Department of Computer Science University of Victoria Victoria, B.C. V8W 2Y2, Canada

Abstract This paper considers the problem of listing all linear extensions of a partial order so that successive extensions differ by the transposition of a single pair of elements. A necessary condition is given for the case when the partial order is a forest. A necessary and sufficient condition is given for the case where the partial order consists of disjoint chains. Some open problems are mentioned.

1 Introduction

Many combinatorial objects can be represented by permutations subject to various restrictions. The set of linear extensions of a poset can be viewed as a set of permutations of the elements of the poset. If the Hasse diagram of the poset consists of two disjoint chains, then the linear extension permutations correspond to combinations. If the poset consists of disjoint chains, then the linear extension permutations correspond to multiset permutations. The extensions of the poset that is the product of a 2-element chain with an n-element chain correspond to “ballot sequences” of length 2n and thus to binary trees with n nodes. More generally, the extensions of a poset that is an ideal in the product of two chains correspond to the standard Young tableaux having a fixed shape; see Figure 1 (also, Knuth [7]).

In this paper we are concerned with the question of generating all linear extensions of a poset so that successively generated permutations differ by a single transposition. In connection with sorting algorithms, transpositions have been called “exchanges” or “interchanges” (Knuth [7]). For computer scientists, linear extensions of posets are more well-known as “topological sortings”. A number of algorithms exist for generating all the topological sortings of an arbitrary poset (or directed acyclic graph). See,

∗Research supported by the Natural Sciences and Engineering Research Council of Canada under grant A3379.

[figure]

Figure 1: (a) Poset whose linear extensions correspond to binary trees. (b) Poset whose linear extensions correspond to Young tableau of shape 6,4,4,1.

for example, Kalvin and Varol [6], Varol and Rotem [22], and Knuth and Szwarcfiter [9]. Also, Knuth [8] considers the problem of generating the inverses of all permutations compatible with a forest partial order in lexicographic order. None of these papers address the problem of generating the linear extensions by transpositions.

A natural way to generate permutations is by transpositions. For unrestricted permutations the algorithm of Steinhaus [19], Johnson [5], and Trotter [21] is wellknown and generates successive permutations by adjacent transpositions. In general, however, it is not always possible to generate all extensions by successive transpositions. For example, if the poset consists of two chains of lengths n and m, then the linear extensions can be generated by transpositions if and only if n and m are both odd (except for the trivial cases where n = 1 or m = 1), as shown independently by Buck and Wiedemann [1], Eades, Hickey, and Read [3], and Ruskey [15]. Here we generalize this result to permutations of a multiset.

There is a graph that naturally arises when generating extensions by transpositions. We call it the transposition graph of the poset. The vertices of this graph are the permutations that correspond to extensions of the poset and edges join those permutations that differ by a transposition. Note that this is always an induced subgraph of the transposition graph of all permutations. The problem of generating all the linear extensions of a poset is now transformed into that of finding a Hamiltonian path in the transposition graph of the poset. It has been observed by Ko and Ruskey [10] and Lehmer [11] in slightly different contexts that the transposition graph is bipartite. In the present context it is easy to see that the transposition graph is bipartite, since a transposition reverses the parity of a permutation. If the difference of the number of vertices in the two partite sets of the transposition graph is more than one, then it has no Hamiltonian path.

The transposition graph of a poset P is denoted G(P). The adjacent transposition graph G′(P) is the graph with the same vertex set as G(P); however, edges only exist between permutations that differ by an adjacent transposition. These graphs are identical for the posets whose extensions correspond to combinations and to binary trees (in fact, for any poset of width two, since the presence of a nonadjacent transpositions requires a 3-element antichain).

An inversion of a permutation e = e_{1}e_{2} ⋯ e_{n} of 1, 2, …, n is an ordered pair (e_{i}, e_{j}) where i < j and e_{i} > e_{j}. Note that an adjacent transposition changes the number of inversions by one. Let inv(e) denote the number of inversions of e.

Suppose that P is a partial order on the set {1, 2, …, n} and that e and f are two of its linear extensions. We may assume without loss of generality that f = 12 ⋯ n. We now claim that the distance in G′(P) between e and f is inv(e). Clearly it cannot be less. Furthermore, the elements of any adjacent inversion (e_{i}, e_{i+1}) are incomparable and thus can be transposed to obtain a linear extension that is closer to f.

By the preceding discussion G′(P) is connected, but it implies more. Let P be a partial extension of Q, meaning that every relation in Q occurs also in P. Then G′(P) is a convex subgraph of G′(Q), where a subgraph H of a graph G is convex if, for every two vertices x and y of H, every vertex on a shortest path between x and y in G is also in H.

A poset is said to be balanced if it has the same number of even and odd permutations as extensions. A conjecture of Ruskey [16] states that the transposition graph of any balanced poset has a Hamiltonian path. The major result of this paper is that this conjecture is true for posets that consist of disjoint chains. This theorem is proved in section 3.

Theorem 1 Multiset permutations can be generated by transpositions if and only if at least two types of elements have odd multiplicity, except for the trivial exceptions where there is one type of element or there are two types and one occurs with multiplicity one.

Several parameters of the adjacent transposition graph G′(P) are related to important parameters of the poset P. The jump number of a linear extension a_{1}a_{2} ⋯ a_{n} is the number of indices 1 ≤ i ≤ n − 1 such that a_{i} and a_{i+1} are incomparable. Thus the jump number of a linear extension is the same as the degree of the corresponding vertex in G′(P). The jump number of a poset is the minimum of the jump numbers of its linear extensions; so the jump number of a poset is equal to δ(G′(P)), where we use Bondy and Murty’s notation δ(G) for the minimum vertex degree in G. Jump numbers are discussed in Chein and Habib [2], Rival [13], and Sysło [20].

The bump number of a linear extension a_{1}a_{2} ⋯ a_{n} is the number of indices 1 ≤ i ≤ n − 1 such that a_{i} < a_{i+1}. The bump number of a poset is the minimum of the bump numbers of its linear extensions. Thus n − 1 minus the bump number of a poset is equal to the maximum vertex degree in G′(P). Bump numbers are discussed in Fishburn and Gehrlein [4] and Zaguia [23].

In the next section, we discuss the problem for general posets. Here the problem is too unstructured and so not much is derived. In the third section we consider posets whose Hasse diagrams are forests. We derive a necessary condition for the adjacent transposition graph to have a Hamilton path; a condition that is conjectured to also be sufficient. In the fourth section we consider posets whose Hasse diagrams consist of disjoint chains. As noted above, the linear extensions of these posets correspond to multiset permutations. In Section 4.1 the necessary condition for the existence of a Hamilton path given by Ko and Ruskey [10] is shown to also be sufficient. This is the most significant result of the paper. In Section 4.2 we restrict our attention to adjacent transpositions. Partial results on the existence of Hamiltonian paths and cycles are stated. The final section mentions some open problems.

2 General Partial Orders

Let us review some definitions and introduce some further notation. A partial order is an antisymmetric, reflexive and transitive binary relation. A poset, P, is a partial order R(P) on a set S(P). If (a, b) ∈ R(P) then we write a ≤ b; if also a ≠ b then we write a < b. For elements a, b ∈ S(P), we say that b covers a and that (a, b) is a cover relation if a < b and there is no x ∈ S(P) such that a < x < b. An element of S(P) is minimal if it covers no element; it is maximal if no element covers it. The set of all minimal elements is denoted Min(P), and the set of all maximal elements is denoted Max(P).

The Hasse diagram of a poset P is the diagram consisting of a graph whose vertices are the elements of S(P) and whose edges are the cover relations, drawn in the plane so that if a < b then b is above a (larger ordinate). Posets are often identified with their Hasse diagrams.

The number of elements of the poset P is denoted |P|. Also, if x is in S(P) then P − x denotes the poset P with the element x and all relations involving x removed.

A linear extension of a poset P is a permutation a_{1}a_{2} ⋯ a_{n} of the elements of S(P) such that a_{i} ≤ a_{j} implies i ≤ j. Let e(P) denote the number of linear extensions of the poset P. A recurrence relation for e(P) is given below.

e(P) = \{ \begin{matrix}1 & if |P| = 1 \\ ∑_{x∈Min(P)} e(P − x) & otherwise \end{matrix}  (1)

Formula (1) is obtained by classifying the permutations according to their first element. As it stands, (1) is not an efficient means of calculating e(P) since it essentially involves generating all linear extensions.

A formula similar to (1) for computing the difference between the number of vertices in the two partite sets of G(P) can be derived. Define the canonical permutation to be 12 ⋯ n, where n = |P|. We assume that the elements of the poset have been labeled in such a way that 12 ⋯ n is a linear extension. Let the parity difference d(P) be the number of even permutations that are extensions minus the number of odd permutations that are extensions. Stictly speaking, the parity difference is not solely a function of the poset since its sign depends on how the poset is labeled, but this will not cause us any problems. Below is a recurrence relation for d(P).

[figure: 3; 4; 1; 2; 1324; 2134; 1243; 1234; 2143]

Figure 2: Example showing a poset and its adjacent transposition graph.

d(P) = \{ \begin{matrix}1 & if |P| = 1 \\ ∑_{x∈Min(P)}(−1)^{x−1}d(P − x) & otherwise \end{matrix}  (2)

In applying (2) it is assumed that the same ordering of the elements is used in defining the canonical permutation in P − x as was used in P. Formula (2) is true since the parity difference for those permutations that begin with x is d(P − x) and it then takes x − 1 adjacent transpositions to bring the x into its proper place in the canonical permutation.

Recurrence relations (1) and (2) can be solved in special cases. Often this uses the fact that we could have used Max(P) instead of Min(P) and the recurrence relations would still be valid. This will be applied in the next section.

The example of Figure 2 illustrates some of the preceding discussion. The poset has been labeled in such a way that 1234 can be the canonical permutation. The transposition graph has 5 vertices (i.e., e(P) = 5), the parity difference is −1 (i.e., d(P) = −1) and the graph has a Hamiltonian path but no Hamiltonian cycle.

We now prove a small but useful lemma. The proof of this lemma serves to remind the reader of the “sweeping” idea behind the Steinhaus-Johnson-Trotter algorithm.

Lemma 1 Let z be incomparable to every element of S(P). If G(P) has a Hamiltonian path (cycle) then G(P ∪ {z}) has a Hamiltonian path (cycle).

Proof: Let p_{1}, p_{2}, …, p_{N} be the successive linear extensions along the Hamiltonian path (cycle) in G(P). Suppose that |P| = n. Then p_{1}z becomes zp_{1} after n adjacent transpositions, where each transposition moves the z one position to the left. We say that the z has been “swept from right-to-left”. Now change zp_{1} to zp_{2} and sweep the z from left-to-right through p_{2}. Continue in this manner: sweeping the z from right-left through p_{i} when i is odd, and from left-right when i is even. Since G(P) is bipartite, if it has a Hamiltonian cycle then N is even. Thus the initial and final linear extensions of the Hamiltonian path of G(P ∪ {z}) are p_{1}z and p_{N}z; hence these two extensions differ by a transposition and there is a Hamiltonian cycle in G(P ∪ {z}). □

Note that the same proof given above can be used to prove the corresponding lemma with G replaced by G′.

Lemma 2 If G′(P) has a Hamiltonian path (cycle) then G′(P ∪ {z}) has a Hamiltonian path (cycle).

Repeatedly applying the preceding lemma to the poset with n elements and no relations produces the Steinhaus-Johnson-Trotter algorithm for generating all n! permutations of n elements.

3 Forests

If the Hasse diagram of a poset is a rooted forest then the recurrence relations (1) and (2) can be solved. We assume that the roots of the trees in the forest are the maximal elements of the poset and that the forest has been given a preorder labeling. A forest with t + 1 trees is denoted

F = T_{0}, T_{1}, …, T_{t}

where each T_{i} is a tree. The forest that results when the root of a tree T is removed is denoted s(T). Also, the following notation is introduced.

F_{i} = T_{0}, T_{1}, …, s(T_{i}), …, T_{t}

As before, e(F) denotes the number of linear extensions of the forest F. A root is to the right of the elements in its subtrees in a linear extension. If the forest consists of chains (all vertices having one or zero children) then the scenario reduces to permutations of a multiset.

By summing over Max(F) in formulas (1) and (2) we obtain (3) and (4) below.

e(F) = \{ \begin{matrix}1 & if k = 1, |T_{1}| = 1 \\ ∑_{i=1}^{k} e(F_{i}) & otherwise \end{matrix}  (3)

d(F) = \{ \begin{matrix}1 & if t = 0, |T_{0}| = 1 \\ ∑_{i=0}^{t}(−1)^{|T_{0}|+···+|T_{i−1}|}d(F_{i}) & otherwise \end{matrix}  (4)

Suppose that there are n nodes in the forest and that the number of descendants of the ith node is d_{i} (a node is regarded as being a descendant of itself). It is an exercise in Knuth [7] (pg. 70) for the binary tree case to show that

e(F) = \frac{n!}{d_{1}d_{2} ⋯ d_{n}}  (5)

This equation also holds for rooted forests. It is similar to the “hook-length formula” for counting standard Young tableau [7].

We now show that there is a solution analogous to (5) to solve the parity difference recurrence relation (4).

Definition 1 A forest F has a pairing if there is a 1-factor (perfect matching) in F or F_{i} for some i.

The pairing, if it exists, is unique and can be constructed “bottom-up”, from the leaves towards the root(s).

Definition 2 The collapsed forest \overline{F} of a forest F with a pairing is the forest obtained by contracting the matched edges of F and deleting the unmatched root, if there is one.

Lemma 3 For a forest F the parity difference is

d(F) = \{ \begin{matrix}e(\overline{F}) & if F has a pairing \\ 0 & otherwise \end{matrix}

Proof: We define an involution ϕ on the set of linear extensions of F. Consider the elements of the permutation as being paired up from left to right. If n = |F| is even then the number of pairs is n/2; otherwise it is (n − 1)/2. The involution takes the leftmost pair of a permutation π, say xy, for which y is not an ancestor of x (it cannot be a descendant), and returns the permutation which is identical to π except that the elements of the pair are transposed to yx. If there is no such pair then the involution returns π. Notice that if π is not a fixed point of ϕ then π and ϕ(π) have opposite parity.

Clearly, if ϕ has no fixed points then the parity difference is zero. Any fixed point induces the pairing of the forest F and every fixed point has the same parity. Thus the number of fixed points is equal to the number of linear extensions of the collapsed forest. If n is odd then the isolated root of the tree with an odd number of vertices must be the last element of any permutation that is a fixed point and so it can be omitted. □

Some of the preceding ideas are illustrated in Figures 3 and 4. In Figure 3 all vertices except one can be paired, but the unpaired vertex is not a root vertex so the

Figure 3: No pairing is possible; d(P) = 0.

[figure]

Figure 4: Pairing and collapsed forest; d(P) = 30.

pairing is illegal. It is perhaps worth noting that the proof of Lemma 3 shows that G′(F) always has a matching of cardinality equal to the size of the smaller partite set; if d(F) = 0 then there is a perfect matching.

We believe that G(F) has a Hamiltonian path if d(F) is zero. If F is such that every vertex either is a leaf or has at least two children, then we can prove that G(F) has a Hamiltonian path. The proof of this theorem gives us a warm-up for the arguments of the next section. This theorem may also be proved by using the results of Pruesse and Ruskey [12].

Theorem 2 If F is a forest poset of at least two trees in which no vertex has one child, then G(F) has a Hamiltonian cycle.

Proof: The roots of the trees of the forest can be generated by adjacent transpositions by using the Steinhaus-Johnson-Trotter algorithm. Expand the forest top-down by adding children to an existing leaf vertex x. Let z_{1}, z_{2}, …, z_{m} with m > 1 be the children of x. Consider a generic permutation αxβ before the children have been added. We wish to insert the m children in all possible ways into α. First insert the two children z_{1} and z_{2} such that the initial permutation is z_{1}z_{2}αxβ and the final permutation is z_{2}z_{1}αxβ. That this is possible can be seen from Figures 5 and 6, where n = |α|. In these figures the elements of α are represented by n y’s, the vertices are all ways of inserting z_{1} and z_{2} into α. In the lower triangular portion z_{1} is to the left of z_{2} and in the upper triangular portion z_{2} is to the left of z_{1}. Horizontal edges are transpositions of z_{1} and a y, and vertical edges are transpositions of z_{2} and a y. The diagonal edges are transpositions of z_{1} and z_{2}.

[figure: z_{1}yyyyyyyz_{2}; z_{1}z_{2}yyyyyyy; yyyyyyyz_{2}z_{1}; z_{2}yyyyyyyz_{1}]

Figure 5: Hamiltonian cycle for n odd (n = 7).

[figure: z_{1}yyyyyyz_{2}; z_{1}z_{2}yyyyyy; yyyyyyz_{2}z_{1}; z_{2}yyyyyyz_{1}]

Figure 6: Hamiltonian cycle for n even (n = 6).

The remaining children z_{3}, …, z_{m} are added, a child at a time, using the Steinhaus-Johnson-Trotter “sweeping” idea; the initial permutation after adding the children is z_{m} ⋯ z_{3}z_{1}z_{2}αxβ and the final permutation is z_{m} ⋯ z_{3}z_{2}z_{1}. If α′xβ′ is the permutation that follows αxβ, then we proceed as before, except that the roles of z_{1} and z_{2} are reversed. Thus the initial permutation is z_{m} ⋯ z_{3}z_{2}z_{1}α′xβ′ and the final permutation is z_{m} ⋯ z_{3}z_{1}z_{2}α′xβ′. □

Note that the proof of Theorem 2 does not provide a Hamiltonian cycle in G′(P) because the transposition of z_{1}αz_{2} to z_{2}αz_{1} used in Figure 6 is not an adjacent transposition.

It would be interesting to know more about the structure of G′(F). We can say something about the vertices of minimum degree. See also section 4.4.

Lemma 4 If F is a forest with l leaves, then δ(G′(F)) = l −1 and there are l! vertices with this minimum degree.

Proof: As noted earlier, the degree of a vertex in G′(F) equals the jump number of the corresponding linear extension. A linear extension e_{1}e_{2} ⋯ e_{n} is greedy if, for each 1 ≤ i < n, if there is a minimal element x ∈ S(P) − {e_{1}, e_{2}, …, e_{i}} satisfying x > e_{i}, then e_{i+1} > e_{i}. For example, refering to Figure 2, the greedy extensions are 1324, 2134, and 2143. According to a result of Rival [13], there is a one-to-one correspondence between greedy linear extensions and linear extensions with minimum jump number, if the poset is N-free. Forests are obviously N-free. A forest with l leaves has l! greedy linear extensions, and the jump number of the forest is l − 1. □

4 Multisets

In this section we consider posets that consist only of disjoint chains. A chain with k elements is denoted C_{k}. Since such a poset is completely determined by the number of elements in each of the chains, the notation n = n_{0}, n_{1}, …, n_{t} is adopted to denote the poset consisting of t + 1 chains where the ith chain (counting from 0) has n_{i} elements.

Of course, e(n) is the multinomial coefficient n!/(n_{0}!n_{1}! ⋯ n_{t}!), where n = n_{0} + n_{1} + ⋯ + n_{t}. The recurrence relation for the parity difference for multisets was given and solved in [10] and [14], or can be derived from Lemma 3 of the previous section. Let Odd(n) denote the number of n_{i} that are odd.

Lemma 5 For multisets the parity difference is

d(n) = \{ \begin{matrix}e(m) & if Odd(n) ≤ 1 \\ 0 & otherwise \end{matrix}

where m_{i} = ⌊n_{i}/2⌋ and m = m_{0}, m_{1}, …, m_{t}.

Lemma 5 establishes the necessity of the condition of Theorem 1; i.e., the parity difference will exceed one if n has fewer than 2 odd values (except for the trivial cases).

4.1 Hamiltonian Paths in G

In this subsection we show that the transposition graph G(n) has a Hamiltonian path whenever n is balanced. The approach is inductive in t and the length of the chains. The base case is when t = 2, n_{0} = n_{1} = 1 (i.e., the poset consists of two isolated elements). We will show how to construct a Hamiltonian path in G(n) that can be modified to obtain a Hamiltonian path in G(n′), where n′ is obtained from n by increasing the length of any chain by two or by adding a new chain of size at most two.

The actual Hamiltonian paths that are constructed might be called sequentially adjacent. This means that any transposition, say between elements x and y from the ith and jth chains, respectively, where i < j, satisfies the constraint that any element z lying between x and y is from a chain of index greater than j. In particular, the elements from the last chain (of size n_{t}) only participate in adjacent transpositions.

It will prove useful to have some terminology to refer to the edges along some Hamiltonian paths in transposition graphs.

Definition 3 Let p_{1}, p_{2}, ⋯, p_{N} be a Hamiltonian path in the transposition graph of a balanced poset (thus N is even). The edges [p_{i}, p_{i+1}] for i odd are called expandable edges or e-edges; the edges [p_{i}, p_{i+1}] for i even are called interface edges or i-edges.

The permutations corresponding to vertices of the Hamiltonian path should be thought of as belonging to their respective expandable edges. The interface edges then only specify the transposition that is used in going from one e-edge to the next e-edge. In our subsequent constructions, the two permutations of an e-edge are replaced by larger sets of permutations, but the i-edges still specify the same transposition as before. In this way we think of interface edges as representing the interface between two sets of permutations.

An example will be used to explain our approach. Suppose that a Hamiltonian path in G(5, 3, 2) has already been constructed and that we are now trying to construct a Hamiltonian path in G(5, 3, 4). Let a, b, and z represent the elements from the chains of lengths 5, 3, and 2, respectively. As in [15], each linear extension p of G(5, 3, 2) is “expanded” into the set of linear extensions of G(5, 3, 4) that are identical to p when their two rightmost z’s are deleted.

Suppose that [p, q] is an e-edge, where p = abzazabaab and q = azbazabaab. Inserting the two additional z’s to the right of all existing z’s in p in all possible ways produces the adjacent transposition graph shown on the left in Figure 7. The lower left corner is the permutation abzazabaabzz, the upper right vertex is abzazzzabaab, and the lower right corner is abzazzabaabz. In general, this graph is denoted I_{n}, where n is the number of elements to the right of the rightmost z. It is isomorphic to G(2, n). For n > 1 there is no Hamiltonian path in I_{n}; this is the reason for considering pairs of vertices. Of course, the graph for inserting the two z’s into q is also I_{5}. The adjacent transposition graph for inserting two z’s into p and q is the Cartesian product graph of I_{5} and an edge, which is denoted H_{5} (in general, H_{n}). The vertices of the graph H_{n} will be drawn as shown in Figure 7. In order to keep the Hamiltonian paths shown in later figures uncluttered, no edges not on the path are drawn; they are left implicit. There are many Hamiltonian paths in H_{n} graphs. We are interested in paths that start in one of the copies of I_{n} and end in the other copy.

The only other type of e-edge that can occur is when the rightmost z is involved in the transposition, which conveniently did not happen above. For example, consider the edge [p, q], where p = abzazaabab and q = abzzaaabab. The adjacent transposition graph from inserting two additional z’s into p and q is different from the graphs defined before. It is a I_{n} graph and a I_{n+1} graph with corresponding vertices joined by edges and is denoted J_{n}. The graph J_{6} from our example is illustrated in Figure 8. As

[figure: abaabzz; zabaabz; zzabaab]
Figure 7: The graphs I_{5} and H_{4}.

[figure]

Figure 8: Forbidden e-edges in J_{n} (for n = 6).

before, the edges of the graph are usually not shown (ignore the edges shown for now). Note that there is a pendant (degree one) vertex in J_{n} and thus this vertex must be the initial or final vertex of any Hamiltonian path in J_{n}. We wish to find Hamiltonian paths that begin in the copy of I_{n+1} and end in the copy of I_{n}, or vice-versa.

Given Hamiltonian paths in H_{n} and J_{n} graphs, we would be able to produce a list of all permutations in G(5, 3, 4), but the permutations at the interfaces of two successive expanded e-edges would not necessarily differ by a transposition. To ensure that they do differ by a transposition, we need to be careful about where the Hamiltonian paths in H_{n} and J_{n} graphs start and end. It will be necessary to define several different Hamiltonian paths.

The inductive hypothesis needs to be strengthened in order for the proof to proceed. Below we define a special type of Hamiltonian path in a transposition graph.

Definition 4 A Hamiltonian path p_{1}, p_{2}, ..., p_{N} with N even in a transposition graph is a z-proper path if both of the following conditions are met:

Figure 9: Forbidden e-edges in H_{n} (for n = 6).

1. [The sequentially adjacent condition.] If two successive permutations differ by a transposition involving z, then the transposition is an adjacent transposition.

2. [The forbidden e-edge condition.] There is no e-edge [p, q] or [q, p], where p = αxzβ, q = αzxβ, |β| is odd and β contains no element greater than z.

Note that the parity of the number of vertices in J_{n} is the same as the parity of n and that the number of vertices in H_{n} is always even. In order for our approach to work the Hamiltonian paths constructed must start and end with e-edges and so the graphs must have an even number of vertices. Thus we can only use J_{n} graphs for n even. This is the reason for the “forbidden e-edge condition”. Inductively, this places an additional constraint on the Hamiltonian paths. Movement of the rightmost z in an I_{n} graph (as drawn in Figure 7) corresponds to a vertical move. Thus certain vertical edges cannot be used (or horizontal edges in the reflected copies of I_{n}) as e-edges. The forbidden e-edges are shown in Figures 8 and 9. Those edges can (and will) be used as i-edges.

We adopt the convention that the lower case letters a, b, c, x, y, z represent single elements of the multiset permutations under consideration (all elements from the same chain are represented by the same letter). The letter z is always used to represent an element of the chain whose length is being increased or a new chain that is being added to the poset. The letters p and q always denote multiset permutations. Greek letters α, β, and γ represent sequences of zero or more elements of a permutation. The letter β is always a permutation that does not contain any z’s.

Let us strengthen Lemma 1 in the context of proper paths. The corresponding result for adding a new chain of length two is implicit in our later results concerning the lengthening of chains by two.

Lemma 6 If G(P) has a Hamiltonian path (cycle) then G(P ∪ C_{1}) also has a Hamiltonian path (cycle). If e(P) is even then the resulting path (cycle) is proper with respect to the added element z.

The different paths we use in H_{n} and J_{n} graphs are given in the two lemmas listed below. For any e-edge [p, q] in which the transposition between p and q does not involve the final z, the transposition graph of all extensions arising by adding two z’s is isomorphic to H_{n}, where n is the number of elements in p or q after the last z. Given p corresponding to the upper copy of I_{n} and q corresponding to the lower copy, the vertices are completely specified by indicating where the two new z’s are inserted among the last n elements, and whether this insertion is in p (upper) or q (lower). Thus we indicate the vertices of H_{n} by L: or U : followed by a permutation of two z’s and n x’s. The transposition between p and q may trade two of the elements indicated by x’s, or two elements not among the final n, or one of each type.

Lemma 7 There are z-proper Hamiltonian paths in H_{n} from the initial vertex to the final vertex as indicated in the table below.

type conditions initial  final
H1 n odd L:zzx^{n} U:zzx^{n}
H2 n > 0, even L:xzzx^{n−1} U:xzzx^{n−1}
H3  n > 0  L:zzx^{n}  U:xzzx^{n−1}
H4  n > 0  L:xzzx^{n−1} U:x^{n}zz
H5  n ≥ 0  L:zzx^{n}  U:x^{n}zz

Lemma 8 For any even n, there are z-proper paths in J_{n} from the initial vertex to the final vertex as indicated in the table below.

type condition initial final
J1 n even  zzx^{n+1} zzx^{n}
J2 n > 0, even zzx^{n+1} xzzx^{n−1}

Each of the preceding lemmas has a “dual” version where the path is followed in the opposite direction. In the dual version of Lemma 7 the path still goes from L: representing p to U : representing q and is indicated by interchanging both L: and U : and ‘initial’ with ‘final’. We will denote the original version of the lemma by using a plus (+) superscript and the dual version by a minus (−) superscript. Path types H1 and H2 are self-dual and thus require no superscript. Here is the theorem that uses these lemmas.

Theorem 3 If G(n_{0}, n_{1}, …, n_{t}) has a z-proper path, where z is the symbol used to represent the elements of the chain of length n_{t}, then G(n_{0}, n_{1}, …, n_{t} + 2) also has a z-proper path.

Proof: Let p_{1}, p_{2}, …, p_{N} be the permutations along a proper path in G(n_{0}, n_{1}, …, n_{t}). The two additional z’s are inserted into all possible positions to the right of the rightmost z in p_{i} and p_{i+1} in every e-edge [p_{i}, p_{i+1}] (for i = 1, 3, 5, …).

Assume that all interfaces previous to the interface between p_{i+1} and p_{i+2} differ by a transposition (initially there is no interface to worry about). We need to consider the various types of interfaces that can occur.

The interface types are classified I, II, III, and IV, depending upon the placement and movement of the rightmost z within p_{i} and p_{i+1}. Class I consists of those e-edges where the rightmost z does not move and there are an even number of symbols to its right and Class II consists of those e-edges where the rightmost z does not move and there are an odd number of symbols to its right. Class III consists of those e-edges where the rightmost z moves one position left and Class IV consists of those e-edges where the rightmost z moves right. In both class III and class IV, the condition of starting with a z-proper path implies that the shorter number of symbols to the right of the rightmost z is even.

Each of the 18 possibilities is illustrated by an example from G(5, 3, 2) in Table 1. The rightmost z is shown as a bold z to make it easier to see. Denote the initial permutation after expanding the e-edge e by i(e) and the final permutation by f(e). The cases where the rightmost z is the rightmost symbol of p_{i+1} or p_{i+2} are easily handled, and so we assume in the rest of the proof that there is at least one symbol to the right of the rightmost z in p_{i+1} and p_{i+2}.

[p_{i}, p_{i+1}] in Class I:

If e_{1} = [p_{i}, p_{i+1}] is in Class I then it was expanded in the previous step by using path type H2, H3, H4, H5, or one of their duals. The final permutation after the expansion is then either r = L:zzx^{n}, s = E:xzzx^{n−1}, or t = U:x^{n}zz, where the E: indicates either L: or U:. We now show that we may choose f(e_{1}) = s or f(e_{1}) ≠ s as needed for the interface with p_{i+2}.

If f(e_{1}) ≠ s then H3^{−} or H5^{−} was used to get f(e_{1}) = r, or H4^{+} or H5^{+} was used to get f(e_{1}) = t. If H3^{−} was used then it is valid to use H2 instead since they both have the same initial permutation (i.e., xzzx^{n−1}). By using H2 we have f(e_{1}) = s. Similarly, if H5^{−}, H4^{+}, or H5^{+} was used then use H4^{−}, H2, or H3^{+} instead, respectively. By using the alternatives we always have f(e_{1}) = s.

If f(e_{1}) = s then H2, H3^{+}, or H4^{−} was used to expand e_{1}. Instead of H2 we can use H4^{+} to get f(e_{1}) = t (or H3^{−} to get f(e_{1}) = r). Instead of H3^{+} we can use H5^{+} to get f(e_{1}) = t and instead of H4^{−} we can use H5^{+} to get f(e_{1}) = r. By using the alternatives we always have f(e_{1}) ≠ s. The argument of this paragraph is dual to the argument given in the previous paragraph.

Now consider the expansion of e_{2} = [p_{i+2}, p_{i+3}]. For e_{2} in cases I, II, III, or IV we assume that f(e_{1}) = s; for e_{2} in case II′ we assume that f(e_{1}) ≠ s. The following table indicates how e_{2} can be expanded in such a way that f(e_{1}) differs by a transposition from the initial permutation in the expansion of e_{2}.

Class I  Class II  Class III Class IV
p_{i} azazbabaab azabzabaab azabazbaab azzababaab
p_{i+1} azazbaabab azabzaabab azabzabaab azazbabaab
I p_{i+2} azazbaaabb azazbaabab azazbabaab azazbaabab
p_{i+3} zaazbaaabb zaazbaabab zaazbabaab zaazbaabab
I′ p_{i+2}  azabazabab
p_{i+3}  zaabazabab
II p_{i+2} azabzaabab azabzaaabb azabzaabab azabzabaab
p_{i+3} zaabzaabab zaabzaaabb zaabzaabab zaabzabaab
II′ p_{i+2} azzabaabab
p_{i+3} zazabaabab
III p_{i+2} azazbaaabb azazbaabab azazbabaab azazbaabab
p_{i+3} azzabaaabb azzabaabab azzababaab azzabaabab
IV p_{i+2} azabzaabab azabzaaabb azabzaabab azabzabaab
p_{i+3} azabazabab azabazaabb azabazabab azabazbaab

Table 1: The 18 possibilities.

Case of e_{2}  I  II  II′ II′ III IV
f(e_{1})  s  s  r  t  s  s
To expand e_{2} H2 H1 H3^{−} H4^{−} J1^{−} J1^{+}
or H3^{−} H3^{+} H4^{+} H5^{−} J2^{+}
or  H4^{+} H5^{+}

For the example of Class I to Class I given in Table 1, we could use the H2 path to obtain i(e_{2}) = azazbzzaaabb and f(e_{2}) = zaazbzzaaabb, or the H3^{−} path to obtain f(e_{2}) = zaazzzbaaabb, or the H4^{+} path to obtain f(e_{2}) = zaazbaaabbzz.

[p_{i}, p_{i+1}] in Class II:

If e_{1} = [p_{i}, p_{i+1}] is in Class II then it was expanded in the previous step by using path type H1, H3, H4, or H5. The final permutation after the expansion is then either r = E : zzx^{n}, s = E : xzzx^{n−1}, or t = U : x^{n}zz. We can show, as was done above for e_{1} in Class I, that we may choose f(e_{1}) = r or f(e_{1}) ≠ r as needed for the interface with p_{i+2}.

Now consider the expansion of e_{2} = [p_{i+2}, p_{i+3}]. For e_{2} in cases I, II, III, or IV we assume that f(e_{1}) = r; for e_{2} in case I′ we assume that f(e_{1}) ≠ r.

Case of e_{2}  I  I′  I′  II  III IV
f(e_{1})  r  s  t  r  r  r
To expand e_{2} H2 H3^{+} H4^{−} H1 J2^{−} J1^{+}
or  H3^{−} H5^{+} H5^{−} H3^{+}  J2^{+}
or  H4^{+}  H5^{+}

[p_{i}, p_{i+1}] in Class III or IV:

In Class III we must have f(e_{1}) = zzx^{n+1}. In Class IV we may assume, without loss of generality, that f(e_{1}) = xzzx^{n−1} (i.e., that J2^{+} was used in expanding e_{1}), n being even in either case. Note from the table that under this assumption the resulting i(e_{2}) after the interface transposition following f(e_{1}) does not depend on whether e_{1} is in Class III or Class IV. For e_{2} in Class I,II,III,IV, we have i(e_{2}) = xzzx^{n−1}, zzx^{n+1}, zzx^{n+1}, or xzzx^{n−1}, respectively, where n is even.

Case of e_{2}  I  II  III  IV
To expand e_{2} H2, H3^{−}, H4^{+} H1, H3^{+}, H5^{+} J2^{+} J1^{−}, J2^{−}

This completes the proof of Theorem 3. □

Theorem 1 is an immediate corollary of Theorem 3. We could have proven Theorem 3 by modifying the proof for t = 1 given in Ruskey [15]. The advantage of the proof given here is that it relies only on the statements of Lemmas 7 and 8, and not on the specific paths that were used to prove those lemmas; this allows us to present a complete proof of reasonable length. The proof in [15] relies on the specific paths that are used and many details are left to the reader to verify.

As in [15] our proof of Theorem 3 leads directly to an algorithm that generates all multiset permutations in constant average time. By constant average time we mean that the total number of computational steps divided by the number of multiset permutations generated is bounded by a constant.

We now indicate how to prove Lemmas 7 and 8. Once appropriate paths are exhibited in H_{1}, H_{2}, and J_{2}, the paths for n can be expanded into corresponding paths for n+2 to complete an iductive proof. Each proof is suggested by a figure illustrating the appropriate path in H_{n} or J_{n} for a specific value of n as shown in Figures 10, 11, 12, 13, and 14. Some paths depend on the parity of n. In the figures the e-edges are denoted by either thick edges or wavy edges. The thick edges correspond to transpositions not involving the rightmost z and the wavy edges correspond to transpositions involving the rightmost z. Note that the wavy edges avoid the forbidden e-edges of Figures 8 and 9. In H_{0} we need only use paths of type H5, and in J_{0} we need on use paths of type J1.

Although we have shown the existence of a Hamiltonian path in G, it remains an open question as to whether there is a Hamiltonian path in the spanning subgraph G′. We conjecture that there is a Hamiltonian path in this case also.

[figure]

Figure 10: Hamiltonian path of type H1 (n = 7).

[figure]

Figure 11: Hamiltonian path of type H2 (n = 6).

[figure]

Figure 12: Hamiltonian path of type H3 (n = 6, 7).

[figure]

Figure 13: Hamiltonian paths of type H4 and H5 (n = 7).

Figure 14: Hamiltonian path of type J1 and J2 (n = 6).

4.2 Hamiltonian Paths and Cycles in G′(n)

In this section, we provide partial results about Hamiltonian paths and cycles in G′(n). An editorial decision was made to omit the proofs; these proofs may be obtained from the author. We believe that G(n) has a Hamiltonian cycle whenever n is balanced and there are at least three symbols (i.e., t > 1). As observed before, there cannot be a Hamiltonian cycle if t = 1, since then G′(n) has two pendant vertices. Our first result shows that even when there are no pendant vertices, the adjacent transposition graph G′ can fail to have a Hamiltonian cycle (although G has a Hamiltonian cycle for this example).

Lemma 9 The graph G′(1, 1, n) has a Hamiltonian cycle if and only if n is odd.

The graphs G′(1, 1, n) with n even and the graphs G(n, m) = G′(n, m) with n and m both odd are the only examples we know where a Hamiltonian path in G′(n) exists but not a Hamiltonian cycle. We believe these graphs to be the only exceptions. In the remainder of this section we show that certain other adjacent transposition graphs have Hamiltonian cycles or paths.

Lemma 10 Let P be a balanced poset. If G′(P) has a Hamiltonian path then G′(P ∪ C_{2}) has a Hamiltonian path. If |P| ≥ 3 and G′(P) has a Hamiltonian cycle then G′(P ∪ C_{2}) has Hamiltonian cycle.

Corollary 1 The graph G′(n, m, 2) has a Hamiltonian path if and only if n and m are both odd (assuming n, m ≥ 1).

For the rest of this section we are going to consider what happens when two isolated elements are added to a poset. The resulting poset is always balanced.

Definition 5 A tree-of-cycles (TOC) is a graph, defined recursively as follows.

1. A single edge is a TOC.

2. An even length cycle is a TOC.

3. If G is a TOC and β is a pendant vertex then the graph G′ obtained by adding a new pendant vertex α, adjacent to β, is a TOC.

4. If G is a TOC and β is a pendant vertex then the graph G′ obtained by replacing β with an even length cycle is a TOC.

5. If G is a TOC and β is a two-valent vertex on a cycle then the graph G′ obtained by adding a new pendant vertex α, adjacent to β, is a TOC.

Another way of defining a TOC is to say that it is a connected graph in which every cycle has even length, every vertex lies on at most one cycle, every vertex on a cycle has degree 2 or 3 and every vertex not on a cycle has degree 1 or 2. We will be interested in TOCs as spanning subgraphs of various adjacent transposition graphs. A spanning TOC is abbreviated STOC.

Lemma 11 If G′(P) has a STOC then G′(P ∪ C_{1} ∪ C_{1}) has a Hamiltonian cycle.

We can show that G′(m, n) has a STOC. Bitstrings of m 0’s and n 1’s are used to denote the vertices of G′(m, n). Note that 0^{m}1^{n} and 1^{n}0^{m} must be pendant vertices in any STOC of G′(m, n) since they are pendant vertices in G′(m, n) itself.

Lemma 12 For any m, n ≥ 1 there is a STOC in G′(m, n). If m, n ≥ 3 then G′(m, n) has a STOC that contains at least one cycle and pendant vertices 0^{m−1}1^{n}0 and 1^{n−1}0^{m}1.

And as an immediate consequence of Lemmas 11 and 12 we have the following theorem.

Theorem 4 The graph G′(1, 1, m, n) has a Hamiltonian cycle for any m, n ≥ 1.

4.3 Counting Edges

Although not of use in the discussion above, it is of some interest to know the number of edges in the adjacent transposition graphs. Defining f(P) to be the number of edges in G′(P), the following recurrence relation holds.

f(P) = ∑_{x∈Min(P)} f(P − x) + ∑_{x,y∈Min(P)} e(P − x − y)  (6)

This recurrence relation can be solved in the case of multisets. The number of edges in G′(n_{0}, n_{1}, …, n_{t}) is

\begin{aligned}f(n) & = & (n − 1) ∑_{0≤i<j≤t} ( \begin{matrix}n − 2 \\ n_{0}, …, n_{i} − 1, …, n_{j} − 1, …, n_{t} \end{matrix} ) \\ & = & \frac{1}{2}(n − 1) [( \begin{matrix}n \\ n_{0}, …, n_{t} \end{matrix} ) − ∑_{0≤i≤t} ( \begin{matrix}n − 2 \\ n_{0}, …, n_{i} − 2, …, n_{t} \end{matrix} )] \end{aligned}

The first expression is obtained by counting the number of edges induced by one of the n − 1 adjacent pairs of positions within a permutation. The last expression simplifies for unrestricted permutations (an antichain) and for combinations (two disjoint chains).

Permutations: f(1, 1, …, 1) = \frac{1}{2}(n − 1)n!

Combinations: f(m, n) = \frac{(m + n − 1)!}{(m − 1)!(n − 1)!}

It would be nice to have something analogous to (5) for counting the number of edges in the case where the poset is a tree.

5 Final Remarks

We have raised more questions than have been answered. The main problem that we would like to see resolved is the following conjecture:

Conjecture 1 If P is a balanced poset then G(P) has a Hamiltonian path.

This conjecture is known to be true for posets of disjoint chains (this paper), for the binary tree posets (e.g., Figure 2, see [18]), for fences ([17]), for crowns, subset lattices, partition lattices, etc. ([12]), and for many other small posets. In fact, evidence indicates that the conjecture may even be true with G replaced by G′. The following questions will be the subject of future investigations.

1. Does a Hamiltonian path exist in G′(n) whenever d(n) is zero?

2. Does a Hamiltonian cycle exist in G(n) whenever d(n) is zero and t > 1?

3. Does a Hamiltonian cycle exist in G′(n) whenever d(n) is zero and n is neither of n, m with n and m both odd or 1, 1, m with m odd?

4. If n and m are odd, then does G(n, m) − {0^{n}1^{m}, 1^{m}0^{n}} have a Hamiltonian cycle? In other words, are the two pendant vertices the “only” reason that G(n, m) is not Hamiltonian?

5. What is d(P) if P is an order ideal I of C_{m} × C_{n}? The linear extensions of I correspond to Young Tableau of shape specified by I.

6. What is d(C_{n} × C_{m}) and does G(C_{m} × C_{n}) have a Hamiltonian path whenever its parity difference is zero? The Hasse diagram of C_{m} × C_{n} is an m by n grid rotated by 45^{∘}. We can show that d(C_{n} × C_{m}) = 0 whenever m and n are both even by using a parity reversing involution ϕ on the set of linear extensions. Consider a linear extension

π = a_{1}a_{2} ⋯ a_{mn}

Let a_{2i}, a_{2i+1} be the leftmost pair of incomparable elements (a_{1} ignored since it is the minimum). If there is no such pair then the involution returns π (i.e., π is a fixed-point), and if there is such a pair then

ϕ(π) = a_{1}a_{2} ⋯ a_{2i−1}a_{2i+1}a_{2i}a_{2i+2} ⋯ a_{mn}

If n and m are both even, then any fixed point induces a perfect matching in the Hasse diagram of C_{m} × C_{n} with the maximum and minimum elements removed. However, there is no perfect matching in an m by n grid with two extreme vertices removed. The reasoning is the same as that used to solve the well-known problem of covering a chess board with two opposite corners removed with dominoes.

If m and n are both odd, then ϕ does have fixed points, but the parity difference seems to be zero (see table below).

If m = 2 then the linear extensions correspond to binary trees, and it is shown by Ruskey and Proskurowski [18] and Ruskey [14] that the parity difference is

d(C_{2} × C_{n}) = \{ \begin{matrix}e(C_{2} × C_{(n−1)/2}) & if n odd \\ 0 & if n is even \end{matrix}  (7)

The number e(C_{2} ×C_{n}) is the nth Catalan number (2n)!/((n+1)!n!). Equation (7) can be derived using the involution ϕ given above. If n is odd then every fixed point induces the same perfect matching in the grid with two extreme vertices removed and thus the fixed points all have the same parity. Collapsing the poset C_{2} × C_{n}, as was done in Lemma 3, yields the poset C_{2} × C_{(n−1)/2}.

The following table was generated by computer.

1 2  3  4  5  6
1 1
2 1 0
3 1 1  0
4 1 0  2  0
5 1 2  0  12  0
6 1 0  12  0 286  0
7 1 5  0 286  0 33592
8 1 0  110  0 33592  0
9 1 14  0 12376  ?  ?
10 1 0 1274  0  ?  0
11 1 42  0  ?  ?  ?
12 1 0 17136  0  ?  0
13 1 132  0  ?  ?  ?
14 1 0 255816  0  ?  0

7. An easier question than The Conjecture is whether G(P) has a perfect matching for every balanced poset P.

8. If the parity difference is not zero, then a Hamiltonian cycle does not exist in the transposition graph. To pose an interesting question in the case of d(P) > 0, we may ask for the shortest spanning closed walk. The length (number of edges) in a spanning closed walk is at least e(P) + d(P); a spanning closed walk with this length is said to be minimal. Lehmer [11] considered a special type of spanning closed walk where any vertex occurs at most twice and those that occur twice are separated by only one vertex. Such a walk can be modeled by what we call a cyclic comb. This is a cycle with some pendant edges. More precisely, a cyclic comb is a connected unicyclic graph in which every vertex not on the cycle has degree one and every vertex on the cycle has degree two or three. There is a minimal cyclic comb in G′(2, n) for any n ≥ 2. The exact comb depends on n mod 4. See Figure 15. The strongest statement to which we do not have a counterexample is: G′(P) has a cyclic comb with d(P) pendant vertices.

6 Acknowledgement.

The presentation of this paper has been greatly improved as a result of numerous detailed comments and suggestions by one of the referees. The author would also like

Figure 15: (a) n ≡ 0 mod 4 (b) n ≡ 3 mod 4

to thank Michelle Wachs, Donald J. Miller and Dominique Roelants van Baronaigien for helpful discussions and Ken Wong for writing some programs.

References

[1] M. Buck and D. Wiedemann. Gray codes with restricted density. Discrete Math., 48:163–171, 1984.

[2] M. Chein and M. Habib. The jump number of dags and posets: an introduction. Discrete Applied Math., 9:189–194, 1980.

[3] P. Eades, M. Hickey, and R.C. Read. Some Hamilton paths and a minimal change algorithm. JACM, 31:19–29, 1984.

[4] P.C. Fishburn and W.V. Gehrlein. Minimizing bumps in linear extensions of ordered sets. Order, 1:3–14, 1986.

[5] S.M. Johnson. Generation of permutations by adjacent transpositions. Math. Computation, 17:282–285, 1963.

[6] A.D. Kalvin and Y.L. Varol. On the generation of all topological sortings. J. Algorithms, 4:150–162, 1983.

[7] D.E. Knuth. Sorting and Searching. Addison-Wesley, 1973.

[8] D.E. Knuth. Lexicographic permutations with restrictions. Discrete Applied Math., 1:117–125, 1979.

[9] D.E. Knuth and J. Szwarcfiter. A structured program to generate all topological sorting arrangements. Information Processing Letters, 2:153–157, 1974.

[10] C.W. Ko and F. Ruskey. Solution of some multi-dimensional lattice path parity difference recurrence relations. Discrete Math., 71:47–56, 1988.

[11] D.H. Lehmer. Permutation by adjacent interchanges. American Math. Monthly, 72:36– 46, 1965.

[12] G. Pruesse and F. Ruskey. Generating the linear extensions of certain posets by transpositions. SIAM J. Discrete Mathematics, to appear.

[13] I. Rival. Optimal linear extensions by interchanging chains. Proc. American Math. Society, 89:387–394, 1983.

[14] F. Ruskey. Solution of some lattice path parity difference recurrence relations using involutions. Congressus Numerantium, 59:257–266, 1987.

[15] F. Ruskey. Adjacent interchange generation of combinations. J. Algorithms, 9:162–180, 1988.

[16] F. Ruskey. Research problem 90. Discrete Math., 70:111–112, 1988.

[17] F. Ruskey. Transposition generation of alternating permutations. Order, 6:227–233, 1989.

[18] F. Ruskey and A. Proskurowski. Generating binary trees by transpositions. J. Algorithms, 11:68–84, 1990.

[19] H. Steinhaus. One Hundred Problems in Elementary Mathematics. Basic, 1964.

[20] M.M. Sysło. A graph-theoretic approach to the jump number problem. In I. Rival, editor, Graphs and Order, pages 185–215. Reidel, Dordrecht, 1985.

[21] H.F. Trotter. Algorithm 115: Perm. Comm. ACM, 5:434–435, 1962.

[22] Y.L. Varol and D. Rotem. An algorithm to generate all topological sorting arrangements. Computer J., 24:83–84, 1981.

[23] N. Zaguia. Minimizing bumps for posets of width two. Discrete Applied Math., 21:157– 162, 1988.