Gray Codes from Antimatroids

Gara Pruesse ^{∗}

Department of Computer Science

University of Toronto, Toronto, Ontario, M5S 1A1, Canada

Frank Ruskey ^{†}

Department of Computer Science

University of Victoria, Victoria, B.C., V8W 2Y2, Canada

Abstract

We show three main results concerning Hamiltonicity of graphs derived from antimatroids. These results provide Gray codes for the feasible sets and basic words of antimatroids.

For antimatroid (E, F), let J(F) denote the graph whose vertices are the sets of F, where two vertices are adjacent if the corresponding sets differ by one element. Define J(F; k) to be the subgraph of J(F)^{2} induced by the sets in F with exactly k elements. Both graphs J(F) and J(F; k) are connected, and the former is bipartite.

We show that there is a Hamiltonian cycle in J(F)×K_{2}. As a consequence, the ideals of any poset P may be listed in such a way that successive ideals differ by at most two elements. We also show that J(F; k) has a Hamilton path if (E, F) is the poset antimatroid of a series-parallel poset.

Similarly, we show that G(L)×K_{2} is Hamiltonian, where G(L) is the “basic word graph” of a language antimatroid (E, L). This result was known previously for poset antimatroids.

Keywords: Antimatroid, basic word graph, combinatorial Gray code, Hamiltonicity, joindistributive lattice. AMS Classification: 05C45, 06A05, 06A06.

∗Research supported in part by NSERC.

†Research supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A3379.

1 Introduction

Antimatroids provide a very general setting in which to consider problems of generating combinatorial objects. In the context of ordering and listing the feasible sets or feasible words of antimatroids, Hamiltonicity questions naturally arise in graphs that have these feasible objects as vertices. The purpose of this paper is to raise and answer some of these Hamiltonicity questions.

A motivation for studying Hamiltonicity properties is their connections with combinatorial Gray Codes, that is, lists of combinatorial objects in which successive objects differ by a small amount. Such Gray Codes often form the basis of efficient algorithms for generating the objects.

Some proofs rely on the connectedness of distributive lattices to prove statements of the form “for every pair of objects x and y (lattice elements), there is a sequence of elementary transformations (cover relations) that transform x into y”. For example, Propp [13] uses such a technique to prove that any perfect matching in a planar graph (subject to a mild condition) may be transformed into any other by a sequence of “face rotations”. Using our results, any such statement implies a statement of the form “there is a sequence of all the objects so that successive objects differ by one or two elementary transformations”.

Antimatroids lend themselves to two different representations, ordered and unordered. The ordered version is a kind of language, and the unordered version is a kind of set system.

A set system over a finite ground set E is a pair (E, F) where F ⊆ 2^{E}. A set system is an antimatroid if the following axioms hold.

(A1) If F ∈ F with F ≠ ∅, then there exists an x ∈ F such that F \ {x} ∈ F.

(A2) If A, B ∈ F, then A ∪ B ∈ F.

A set system satisfying (A1) is said to be accessible.

A language over a finite alphabet E is a pair (E, L) with L ⊆ E^{∗}, where E^{∗} is the free monoid of words in the alphabet E. The length of α ∈ L (i.e., the number of not necessarily distinct letters in α) is denoted |α|. The support α̃ of α is the set of letters of α. A word α is simple if it contains no repeated letter (i.e., if |α| = |α̃|). By E^{(∗)} we denote the set of words in E^{∗} which are simple. A language (E, L) is simple if every word in L is simple (i.e., if each word of L is in E^{(∗)}). A simple language is a language antimatroid if the following axioms hold.

(L1) If αβ ∈ L, then α ∈ L.

(L2) If α, β ∈ L with α̃ ⊈ β̃, then there is an x ∈ α̃ with βx ∈ L.

The basic words, Basic(L), of a language antimatroid are the words α ∈ L of maximal length.

There is a one-to-one correspondence between antimatroid set systems and antimatroid languages. Given an antimatroid set system F, let L(F) be the language given by

L(F) =^{def} {x_{1}x_{2} ⋯ x_{k} : {x_{1}, x_{2}, …, x_{i}} ∈ F ∀i, 1 ≤ i ≤ k}.

Given the antimatroid language L, let F(L) = {α̃ : α ∈ L}. It is easy to see that F(L(F)) = F, and L(F(L)) = L. Thus we may switch from one representation to the other when convenient. Every antimatroid is both a set system and a language, so in order to avoid confusion over which representation we are referring to, we will most often use F or L when we wish to treat the antimatroid as a set system or language, respectively.

There are several alternate characterizations of antimatroids; one that is quite useful is in terms of “alternative precedences”. Let E be a finite set and H be a mapping that associates with each x ∈ E a set system H(x) ⊆ 2^{E\{x}}. The language

L_{H} =^{def} {x_{1}x_{2} ⋯ x_{k} ∈ E^{(∗)} : ∀i, 1 ≤ i ≤ k, ∃ A ∈ H(x_{i}) s.t. A ⊆ {x_{1}, x_{2}, …, x_{i−1}}}

is called an alternative precedence language. A finite simple language is a language antimatroid if and only if it is an alternative precedence language ([11],[4]).

An element a is an atom if {a} ∈ F; or, equivalently, if a ∈ L; or, equivalently, if H(a) = {∅}. In order to simplify the notation we sometimes use F to denote the antimatroid (E, F), with the understanding that E = ∪F, where the union is over all F ∈ F. Similarly, we will use L to denote the language antimatroid (E, L), with the understanding that E = ∪α̃, where the union is over all α ∈ L.

If F is an antimatroid and A ∈ F, then we may obtain two new antimatroids by contraction and deletion as follows.

F/A =^{def} {F : F ∩ A = ∅ and F ∪ A ∈ F}.

F \ A =^{def} {F ∈ F : F ∩ A = ∅}.

Note that these two antimatroids induce a partition of the feasible sets of F if |A| = 1.

Perhaps the most important class of antimatroids are the poset antimatroids. The set system (E, F) is a poset antimatroid if E is the set of elements of a poset P and F is the set of ideals of P. The basic words of the corresponding language antimatroid are the linear extensions of P.

There are two standard “sums” of antimatroids. Let (E_{1}, F_{1}) and (E_{2}, F_{2}) be antimatroids on distinct ground sets. The direct sum F_{1} + F_{2} is the antimatroid

F_{1} + F_{2} =^{def} {X_{1} ∪ X_{2} : X_{1} ∈ F_{1} and X_{2} ∈ F_{2}}.

The ordinal sum F_{1} ⊕ F_{2} is the antimatroid

F_{1} ⊕ F_{2} =^{def} F_{1} ∪ {E_{1} ∪ X_{2} : X_{2} ∈ F_{2}}.

Observe that starting with isolated elements and then applying the operations of direct and ordinal sum results in poset antimatroids of series-parallel posets.

We now define the graphs whose Hamiltonicity properties are investigated in the following sections. For antimatroid (E, F), let J(F) denote the undirected covering graph of the sets of F ordered by inclusion.

The square of a graph G, is the graph G^{2} whose vertex set is the same as G and such that two vertices are adjacent in G^{2} if they are of distance one or two in G. Define J(F; k) to be the subgraph of J(F)^{2} induced by the sets in F with exactly k elements. Both graphs J(F) and J(F; k) are connected, and the former is bipartite. For some F, J(F) does not have a Hamilton path, even when the partite sets of J(F) are of the same cardinality; for example, consider the lattice of ideals of the seriesparallel poset 1⊕(1+1)⊕1⊕(1+1)⊕1. The graph J(F; k) can fail to have Hamilton cycle but we know of no example where J(F; k) fails to have a Hamilton path. In fact, J(F; k) can be a path. If F is the poset antimatroid of a poset consisting of two disjoint chains, both containing n − 1 elements, then J(F; n) is a path of length n.

A classic result of Ehrlich [5] and Bitner, Ehrlich and Reingold [2] is that J(P; k) is Hamiltonian if P is the poset antimatroid of an antichain. We extend this result to series-parallel posets.

The basic word graph G(L) of the antimatroid L is the graph whose vertex set is Basic(L), and such that two basic words are adjacent if they differ by the transposition of two adjacent elements. We show that G(L) × K_{2} is Hamiltonian and thus the existence of a Gray Code for basic words, where each word differs from the previous one in the listing by one or two adjacent transpositions. We give an algorithm for generating the basic words which, for some antimatroids, runs in constant amortized time. Similar questions for the graph of linear extensions were considered by Pruesse and/or Ruskey [18], [15], [16], [14] and Stachowiak [21]. The diameter of G(L) was investigated in [10] and [27].

In Section 2 we show that there is a Hamiltonian cycle in J(F) × K_{2}. As a consequence, the ideals of any poset P may be listed in such a way that successive ideals differ by at most two elements. In section 3 we show that J(F; k) has a Hamilton path if (E, F) is the poset antimatroid of a series-parallel poset. In Section 4 we show that G(L) × K_{2} is Hamiltonian.

2 The graph J(F) × K_{2} is Hamiltonian

We consider graphs of the form G × K_{2}; that is, the product of a graph G with an edge. In other words, there are two copies of G, which we denote as +G and −G, with edges joining corresponding vertices in the two copies. Given a vertex v in G, denote the corresponding vertices in G×K_{2} as +v and −v. If w is a vertex of G×K_{2} then by \overline{w} we denote the corresponding vertex in the other copy of G. The following lemma was proven in [16].

Lemma 1 If G is bipartite and G × K_{2} is Hamiltonian, then G^{2} is Hamiltonian.

Theorem 1 For every antimatroid F and any atom x of F, the graph J(F) × K_{2} has a Hamilton cycle that includes the edges [+∅, −∅] and [+∅, +x].

Proof: Our proof is by induction on n = |E|. If n = 1 then J(F) × K_{2} is the 4-cycle +∅, +{x}, −{x}, −∅, where E = {x}.

If n > 1, then let {x} ∈ F and consider the antimatroid F/x. We consider two cases depending upon the number of singleton sets in F.

If x is the only atom of F, then inductively we may assume that there is a Hamilton cycle +∅ = X_{1}, X_{2}, …, X_{p} = −∅ in J(F/x). This may be extended to the Hamilton cycle

+∅, X_{1} ∪ {x}, X_{2} ∪ {x}, …, X_{p} ∪ {x}, −∅

in J(F). Clearly, this cycle contains the edges [+∅, −∅] and [+∅, +{x}].

If there are at least two distinct elements x, y ∈ E such that {x}, {y} ∈ F, then inductively there are Hamilton cycles

+∅ = X_{1}, X_{2}, …, X_{p} = −∅ in J(F/x)

and

+∅ = Y_{1}, Y_{2}, …, Y_{q} = −∅ in J(F \ x),

where X_{2} = Y_{2} = {y}. The following is thus a Hamilton cycle in G(F).

Y_{1}, X_{1} ∪ {x}, X_{p} ∪ {x}, X_{p−1} ∪ {x}, …, X_{2} ∪ {x}, Y_{2}, Y_{3}, …, Y_{q−1}, Y_{q}

This cycle contains the edges [+∅, −∅] and [+∅, +{x}]. □

Observe that the preceeding proof maintains the following invariant:

The Hamilton path in J(F) × K_{2} has the property that any feasible set I between two signed feasible sets ±F and ∓F on the path satisfies F ⊂ I.

Thus the list of feasible sets has the structure of a well-formed parentheses string with |F| types of parentheses.

Corollary 1 For every antimatroid (E, F), there is a listing X_{1}, X_{2}, …, X_{|F|} of the feasible sets F such that successive sets (including the first and last) differ by at most two elements.

Proof: Since J(F) is bipartite, we may apply Lemma 1 to conclude that J(F)^{2} is Hamiltonian. □

3 Feasible sets of fixed size

Recall that the Hamming distance between two bitstrings is the number of positions in which they differ. Regarding the bitstrings as the characteristic vectors of a set the Hamming distance D between two sets is D(A, B) = |(\overline{A} ∪ \overline{B}) ∩ (A ∪ B)|. In other words, the Hamming distance of two sets is the number of elements which are in one set but not in the other.

We defined J(P; k) to be the subgraph of J(P)^{2} induced by those vertices (feasible sets) with exactly k elements. In other words, J(P; k) = (V, E) where V = {A ∈ F : |A| = k} and E = {{A, B} : A, B ∈ V and D(A, B) = 2}. The graph J(F; k) is not bipartite in general (for example, the graph J(2^{{1,2,...,n}}; 1) is the complete graph K_{n}), but it is always connected.

Lemma 2 For every antimatroid (E, F), the graph J(F; k) is connected.

Proof: Our proof is by induction on |E|. The lemma is clearly true if k = 0, 1 or if |E| = 0, 1. So assume that |E| > 1 and k > 1.

Let x be an atom of F. Inductively, J(F \ x; k) and J(F/x; k − 1) are connected. Thus, the vertices of J(F; k) which contain x are connected, as are those which do not contain x. If F ∈ F \ x with |F | = k, then there is a y ∈ E \ {x} such that F \ {y} ∈ F \ x. By closure under union F′ = F \ {y} ∪ {x} ∈ F; i.e., F \ {y} ∈ F/x. Since F and F′ are adjacent in J(F; k), all vertices in J(F; k) are connected. □

If H is a Hamilton path, then first(H) and last(H) have the obvious meanings of the first and last vertices of H, respectively.

Definition 1 The sequence H_{0}(P), H_{1}(P), …, H_{n}(P) is a complete set of Hamilton paths for the poset P if 1. Each H_{k}(P) is a Hamilton path in J(P; k) for k = 1, 2, …, n.

2. D(first(H_{i}), first(H_{i+1})) = 1 for i = 0, 1, …, n − 1.

3. D(last(H_{i}), last(H_{i+1})) = 1 for i = 0, 1, …, n − 1.

Theorem 2 If Q and R both have complete sets of Hamilton paths then P = Q ⊕ R has a complete set of Hamilton paths.

Theorem 3 If Q and R both have complete sets of Hamilton paths then P = Q + R has a complete set of Hamilton paths.

Corollary 2 Series-parallel posets have complete sets of Hamilton paths.

Corollary 3 Forest posets have complete sets of Hamilton paths.

Proof (of Theorem 2): Let p = |S(P)|, q = |S(Q)|, r = |S(R)|, and thus p = q +r. Given the complete sets of Hamilton paths H_{k}(Q) (for k = 0, 1, …, q) and H_{k}(R) (for k = 0, 1, …, r), we need to show a complete set of Hamilton paths H_{k}(P) (for k = 0, 1, …, p). For k ≤ q set H_{k}(P) = H_{k}(Q). For k > q set H_{k}(P) = S(Q) ∪ H_{k−q}(R), where the union is taken componentwise. □

Proof (of Theorem 3): Let p = |S(P)|, q = |S(Q)|, r = |S(R)|, and assume without loss of generality that 0 < r ≤ q < p. The complete set of Hamilton paths for Q is denoted H_{k}(Q) (for k = 0, 1, …, q), and similarly H_{k}(R) for R. We will show how to construct a complete set of Hamilton paths H_{k}(P) (for k = 0, 1, …, p).

The global structure of the path for H_{k}(P) consists of, for increasing values of i, Hamilton paths p_{i,k−i} in the subgraph H_{i}(Q) × H_{k−i}(R) of J(P; k).

In the forward direction, the (i, k − i) path starts with

first(H_{i}(Q)) ∪ first(H_{k−i}(R)) or first(H_{i}(Q)) ∪ last(H_{k−i}(R)),  (1)

and ends at

last(H_{i}(Q)) ∪ first(H_{k−i}(R)) or last(H_{i}(Q)) ∪ last(H_{k−i}(R)).  (2)

To be specific, let

H_{i}(Q) = a_{1}, a_{2}, …, a_{M} and H_{k−i}(R) = b_{1}, b_{2}, …, b_{N} Starting in the forward direction from (1), the Hamilton path in the subgraph J(Q; i)× J(R; k − i) starts out

a_{1}b_{1}, a_{1}b_{2}, …, a_{1}b_{N},  a_{1}b_{N}, a_{1}b_{N−1}, …, a_{1}b_{1},
a_{2}b_{N}, …, a_{2}b_{2}, a_{2}b_{1},  a_{2}b_{1}, …, a_{2}b_{N−1}, a_{2}b_{N},
a_{3}b_{1}, a_{3}b_{2}, …, a_{3}b_{N},  or a_{3}b_{N}, a_{3}b_{N−1}, …, a_{3}b_{1},
a_{4}b_{N}, …, a_{4}b_{2}, a_{4}b_{1},  a_{4}b_{1}, …, a_{4}b_{N−1}, a_{4}b_{N},
…  …

and if M is odd ends at

a_{M}b_{1}, a_{M}b_{2}, …, a_{M}b_{N} or a_{M}b_{N}, a_{M}b_{N−1}, …, a_{M}b_{1},

and if M is even ends at

a_{M}b_{N}, …, a_{M}b_{2}, a_{M}b_{1} or a_{M}b_{1}, a_{1}b_{2}, …, a_{M}b_{N}.

On this list successive feasible sets have the form a_{s}b_{t}, a_{s}b_{t+1} or a_{s}b_{t}, a_{s+1}b_{t} and thus have Hamming distance 2. Thus for given values of i and k, there are two alternative lists. These two lists can be distinguished by their first elements. A (i, k − i)-list p_{i,k−i} is first-first if it begins at a_{1}b_{1} (i.e., first(H_{i}(Q)) ∪ first(H_{k−i}(R)); it is firstlast if it begins at a_{1}b_{N}. The lists can also be distinguished by their last elements. A (i, k − i)-list is last-last if it ends at a_{M}b_{N}; it is last-first if it ends at a_{M}b_{1}. If M is odd, a first-first path is also last-last; otherwise, it is last-first.

We form the path H_{k}(P) by stringing together paths p_{i,k−i} for all valid values of i, where each p_{i,k−i} is a path of one of the two types described above, and may appear either in the forward direction or in reverse; the reverse direction will be denoted with the superscript R. For example, when k ≤ r ≤ q,

H_{k}(P) = \{ \begin{matrix}p_{k,0}, (p_{k−1,1})^{R}, …, p_{0,k} & if k even, \\ p_{k,0}, (p_{k−1,1})^{R}, …, (p_{0,k})^{R} & if k odd. \end{matrix}

In order for H_{k}(P) to be a path in J(P, k), the type of each p_{i,k−i} (i.e., first-first or first-last) must be selected so that there is Hamming distance 2 in going from one path to the next. For example if p_{i,k−i} is a first-first path and appears in reverse order in H_{k}(P), then p_{i−1,k−i+1} must be a first-first path. Note that the p_{i,k−i}’s are not necessarily all of the same type for a given k, because the number M of ideals of size i of Q may be even for some values of i, odd for others.

Observe that for any k and i, the type of p_{i,k−i} can be selected, and that selection determines the type of p_{j,k−j} for all other valid values of j.

Thus we have shown how to construct a set of paths H_{k}(P) with Property 1; i.e., such that each H_{k}(P) is a Hamilton path in J(P, k) for k = 0, 1, …, n. We now show inductively how to select the types for the paths p_{i,k−i} in H_{k}(P) so that Properties 2 and 3 are maintained.

Initially, H_{0}(P) is the path on one vertex, the empty set. Suppose the paths H_{0}(P), H_{1}(P), …, H_{k}(P) have been constructed so as to satisfy all three properties. Then H_{k+1}(P) can be constructed so as to have Properties 2 and 3 in the following way.

[Case where k < r ≤ q:] Assume for the sake of illustration that k is even; similar arguments hold when k is odd. Then

\begin{matrix}H_{k}(P) = & p_{k,0}, (p_{k−1,1})^{R}, …, p_{0,k}, \\ H_{k+1}(P) = & p_{k+1,0}, (p_{k,1})^{R}, …, (p_{0,k+1})^{R}. \end{matrix}

Note that, regardless of type, D(first(p_{k,0}), first(p_{k+1,0})) = 1. If the type of p_{0,k} is last-last, then set the type of p_{0,k+1} to be first-last; otherwise, set it to be first-first. H_{0}(Q) just contains the empty set, so a_{1} = a_{M}, and D(first(H_{0}(Q)), last(H_{0}(Q))) = 0. By definition,

D(last(H_{k}(R)), last(H_{k+1}(R))) = 1.

Therefore D(last(H_{k}(P)), last(H_{k+1}(P))) = 1.

[Case where r ≤ k < q:] In this case, the number of paths strung together is r + 1. Suppose r is even. Then

\begin{matrix}H_{k}(P) = & p_{k,0}, (p_{k−1,1})^{R}, …, p_{k−r,r}, \\ H_{k+1}(P) = & p_{k+1,0}, (p_{k,1})^{R}, …, p_{k+1−r,r}. \end{matrix}

By a similar argument as given in the first case,

D(first(H_{k}(P)), first(H_{k+1}(P))) = D(last(H_{k}(P)), last(H_{k+1}(P))) = 1,

regardless of type. A similar argument holds when r is odd.

[Case r ≤ q < k:] For q + r − k even,

\begin{matrix}H_{k}(P) = & p_{q,k−q}, (p_{q−1,k+1−q})^{R}, …, p_{k−r,r}, \\ H_{k+1}(P) = & (p_{q,k+1−q})^{R}, p_{q−1,k+2−r}, …, p_{k+1−r,r}. \end{matrix}

If p_{q,k−q} is first-first, set p_{q,k+1−q} to be last-first. It is easy to confirm that Properties 2 and 3 are upheld. A similar argument holds when q + r − k is odd.

This completes the proof. □

4 The graph G(L) × K_{2} is Hamiltonian

In this section, we show the existence of a certain kind of Gray code for the basic words of an antimatroid. We begin with a definition and two lemmas.

Definition 2 For a word α, let α − x be the word βγ, where α = βxγ, or α − x = α, if x ∉ α.

Note that if x is an atom that L/{x} = {α − x : α ∈ L}.

Lemma 3 Let (E, L) be an antimatroid in which the elements of E are {a, x_{1}, x_{2}, …, x_{n}} where a is an atom. For all 1 ≤ i ≤ j < n, if

π = x_{1} ⋯ x_{i}x_{i+1} ⋯ x_{j}ax_{j+1} ⋯ x_{n} ∈ L,

then

π′ = x_{1} ⋯ x_{i}ax_{i+1} ⋯ x_{j}x_{j+1} ⋯ x_{n} ∈ L.

Proof: Let H be a alternative precedence mapping for L. Since a is an atom, H(a) = {∅} and so a needs no precedent set. For the x_{l} (1 ≤ l ≤ n) elements, it is clear that the same precedent constraints met in π are also met in π′. □

Definition 3 A B-poset is a poset P whose elements can be partitioned into two disjoint chains, x_{1} ≺ x_{2} ≺ ⋯ ≺ x_{n} and y_{1} ≺ y_{2} ≺ ⋯ ≺ y_{m}, such that y_{j} ⪯̸ x_{i} for all i and j, where 1 ≤ i ≤ n and 1 ≤ j ≤ m.

The following lemma was proved in [15].

Lemma 4 Let P be a B-poset as defined above and denote κ = x_{1}x_{2} ⋯ x_{n}y_{1}y_{2} ⋯ y_{m}. There is a Hamiltonian cycle in G(P) × K_{2} which uses the edge [+κ, −κ].

We now give the main theorem of this section. The theorem and proof given here are generalizations of the main theorem and proof in [16], which showed the following result for poset antimatroids.

Theorem 4 For every antimatroid L, the graph G(L) × K_{2} is Hamiltonian.

Proof: The proof of the theorem is by induction on |E|. For the base cases of the induction, L is the antimatroid on zero or one elements; in these cases G(F) × K_{2} is an edge.

Suppose |E| > 1. If L has exactly one atom a, then G(L) ≅ G(L/{a}), and by the inductive hypothesis G(L/{a}) × K_{2} is Hamiltonian.

Otherwise, let L have two atoms a and b. By the inductive hypothesis, the graph G(L/{a, b}) × K_{2} has a Hamiltonian cycle H_{1}. Replace each signed basic word +α_{i} on H_{1} with abα_{i}; replace each basic word −α_{i} with baα_{i}. Call the resulting sequence H_{2}. By Lemma 3, both abα_{i} and baα_{i} are basic words of L; therefore H_{2} is a cycle β_{1}, β_{2}, …, β_{M}, where M = 2 · e(L/{a, b}), in G(L), which visits exactly those basic words in L in which have the prefix ab or ba.

For each β_{i} = x_{i}y_{i}ζ_{i}, where {x_{i}, y_{i}} = {a, b}, let B_{i} be the poset which consists of the two chains, x_{i}y_{i} and ζ_{i}, plus the relations given (directly or transitively) by the following rule. For z ∈ ζ̃_{i}, where σ and ρ are such that ζ_{i} = σzρ, if x_{i}σzy_{i}ρ ∉ L then y_{i} <_{B_{i}} z; similarly, if σzx_{i}y_{i}ρ ∉ L then x_{i} <_{B_{i}} z.

Consider a linear extension ω = δx_{i}γy_{i}ϵ of B_{i}. By the construction of B_{i}, x_{i}δγy_{i}ϵ ∈ L, and δx_{i}y_{i}γϵ ∈ L. By Lemma 3, ω ∈ L. Therefore every linear extension of B_{i} is a basic word of L.

We observe also that B_{i} is a B-poset. Therefore by Lemma 4, there is a Hamiltonian path through G(B_{i}) × K_{2} from +β_{i} to −β_{i}. We substitute the occurrence of β_{i} with this path in H_{2}, for each odd i. For each even i, we substitute the reverse of this path for the occurrence of β_{i}. Call the resulting walk H.

For each B_{i}, every linear extension of B_{i} is a basic word of L; therefore H is a closed walk in G(L)×K_{2}. To prove that H is a Hamiltonian cycle through G(L)×K_{2}, it is necessary to show that for each basic word γ of L, +γ and −γ both occur exactly once on H. Let ζ = γ − a − b. Suppose γ induces the order xy on {a, b} and the order ζ on S(L)\{a, b}. Then xyζ is a basic word of L, and therefore xyζ = β_{i} is on the cycle H_{2} of G(L). Therefore γ is a linear extension of the B_{i}, and so both +γ and −γ are on the cycle H. Also, for every other B-poset B_{j} generated, where j ≠ i, one of xy or ζ is not a subword of B_{j}, as in that case β_{i} = β_{j}, which contradicts the construction of H_{2}. Therefore, each of +γ and −γ are generated exactly once. □

We call a pair a, b of elements of E siblings in a language L if for all basic words in L, transposing a and b yields another word in L. Let L + ab denote the language consisting of the words of L in which a precedes b. If L is an antimatroid, then so is L+ab: we may simply add a to each A ∈ H(b) where H is the alternative precedence function of L, yielding an alternative precedence representation for L + ab.

Let G′(L) be the graph with the basic words of L as the vertex set, and such that two basic words are adjacent in G′(L) if they differ by the transposition of two (not necessarily adjacent) elements. Thus G′(L) is a supergraph of G(L), on the same vertex set.

Corollary 4 If L is an antimatroid with a pair of siblings, then G′(L) is Hamiltonian.

Proof: Suppose L has a pair of siblings a, b. By Theorem 4, G(L + ab) × K_{2} is Hamiltonian; therefore G′(L + ab) × K_{2} is Hamiltonian. Note that G′(L) ≅ G′(L + ab) × K_{2}. Therefore G′(L) is Hamiltonian. □

It is an open problem to determine whether G(L) is Hamiltonian, where L is an antimatroid with a pair of siblings.

The graph G(L) is bipartite; therefore applying Theorem 4 and Lemma 1, we conclude the following corollary, which establishes a Gray Code for basic words of an antimatroid.

Corollary 5 For any antimatroid L, there is a listing of the basic words of L such that each word differs from it predecessor in the list by one or two adjacent transpositions.

This is the best possible, in that not all antimatroids admit a listing of the basic words such that each differs from its predecessor by one transposition. The seriesparallel poset antimatroid (1 ⊕ 1) + (1) ⊕ 1) provides such an example. In that case, the difference in the cardinality of the two partite sets of G(L), which quantity we will call the parity difference of L, exceeds one (i.e., there are two more odd basic words than even), so there can exist no Hamiltonian path or cycle in the basic word graph. The following conjecture of Ruskey [19] suggests a characterization of the posets which are generable by transpositions.

Conjecture 1 For a poset P, if the parity difference of P does not exceed one, then G(P) has a Hamilton path; if the parity difference is zero and G(P) has no vertex of degree one, then G(P) is Hamiltonian.

This conjecture cannot be extended to all antimatroids; an antimatroid with zero parity difference for which G(L) has no Hamilton path is shown in Figure 1.

A generation algorithm runs in constant amortized time if its running time is O(e), where e is the number of objects generated. An O(f(n)) transposition oracle of an antimatroid is an oracle which determines in time O(f(n)) whether αxyβ is a basic word of L, given that αyxβ is a basic word of L.

The algorithm GenLE and the proof of its correctness given in [16] to generate linear extensions uses only those properties of posets that are shared by all antimatroid languages. The queries to the antimatroid are of the type, “Is αxyβ in L?”, where αyxβ is in L. Therefore, given an antimatroid with an O(f(n)) transposition oracle, GenLE is a O(f(n)) amortized time generation algorithm. In particular, we have the following result.

[figure: 1; 2; 3; 4; ^{1423 1243 1234 4123  1432 4132 4312 4321}]

Figure 1: The path P_{4}, and G(L), where L is the leaf shelling antimatroid for P_{4}.

Theorem 5 Let L be an antimatroid with an O(1) transposition oracle. Then the basic words of an antimatroid can be generated in constant amortized time, such that each word differs from the next by no more than two transpositions.

Clearly poset antimatroids have O(1) transposition oracles. Another example of an antimatroid with an O(1) transposition oracle is given below.

For a tree G, the leaf shelling sequence of G is a sequence v_{1}, v_{2}, …, v_{l}, where v_{i} ∈ V (G), for all 1 ≤ i ≤ l, and v_{i} is a leaf of the subgraph of G which remains when the vertices {v_{1}, v_{2}, …, v_{i−1}} are removed. I.e., these are ways of removing the vertices of G such that we only ever remove a leaf from the current tree. It is easy to verify that leaf shelling sequences form an antimatroid language. Suppose that αxyβ is a leaf shelling sequence of G. If β is empty, or if x and y are non-adjacent, then αyxβ is also a leaf shelling sequence; otherwise x and y are adjacent, and x and y are not that last two vertices to be removed, so removing y before removing x will disconnect x from the rest of the tree. Therefore αyxβ is not a shelling sequence. Testing these conditions can be done in time O(1), so by Theorem 5, the complete shelling sequences of a tree (i.e., the shelling sequences which contain all the vertices of G) can be generated in consant amortized time.

Chordal graphs admit a decomposition sequence; i.e., a sequence v_{i}, v_{2}, …, v_{n}, where for each v_{i}, its neighbourhood in the graph G induced on v_{i+1}, v_{i+2}, …, v_{n} is a clique. The decomposition sequences of a chordal graph form an antimatroid language. However, a constant time transposition oracle is not known to exist for this language.

5 Final Remarks

The remarks at the end of the last section show that there are efficient (constant amortized time) algorithms for generating the basic words of an antimatroid; but what about the efficient generation of feasible sets and, in particular, the ideals of a poset? Algorithms for generating the ideals of a poset were given by Schrage and Baker [20], Lawler [12], Ball and Provan [1], and Steiner [22]. The best of these algorithms appears to be that of Steiner, whose running time is O(n · i(P)), where n is the number of elements of the poset and i(P) is the number of ideals of P. We have developed an algorithm based on the results of Section 2 whose running time is O(i(P)), but only on certain posets; in the worst case it is also O(n · i(P)), so it remains an open problem to develop a constant amortized time algorithm for generating the ideals of a general poset. Beyer and Ruskey [3] and Koda and Ruskey [9] have shown that the ideals of a forest poset could be generated in time O(i(P)); the latter paper contains a “loopfree” algorithm.

To end the paper we propose two conjectures.

Conjecture 2 Let P be a poset and consider the subgraph G of J(P) induced by the vertices of J(P; k)∪J(P; k +1). The graph G is bipartite, say with bipartition (A, B). If |A| = |B| then is there a Hamilton cycle in G? If |A| = |B| + 1 then is there a Hamilton path in G? We conjecture that the answer is yes in both cases.

Note that this conjecture contains the famous “middle two levels of the boolean algebra lattice problem” as a special case and so is most likely very difficult (e.g., Kierstead and Trotter [8] or Hurlbert [6]), if indeed it is true.

Conjecture 3 For every antimatroid (E, F) and every k, the graph J(F; k) has a Hamilton path.

This cannot be strengthened to Hamilton cycle since J(F; k) is a path if F is the poset antimatroid of a poset consisting of two disjoint chains.

References

[1] M.O. Ball and J.S. Provan, “Calculating bounds on reachability and connectedness in stochastic networks”, Networks, 13 (1983) 253-278.

[2] J. Bitner, G. Ehrlich, and E. Reingold, “Efficient Generation of the Binary Reflected Gray Code and its Applications,” Communications of the ACM, 19 (1976) 517-521.

[3] T. Beyer and F. Ruskey, “Constant Average Time Generation of Subtrees of Bounded Size,” unpublished manuscript, May, 1989.

[4] A. Björner and G.M. Ziegler, “Introduction to Greedoids”, in Matroid Applications (ed. N. White), Cambridge University Press, 1992.

[5] G. Ehrlich, “Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations,” JACM, 20 (1973) 500-513.

[6] G. Hurlbert, “The antipodal layers problem”, Discrete Math., to appear.

[7] J.T. Joichi, D.E. White, and S.G. Willamson, “Combinatorial Gray Codes,” SIAM J. Computing, 9 (1980) 130-141.

[8] H.A. Kierstead and W.T. Trotter, “Explicit matchings in the middle levels of the Boolean lattice”, Order 5 (1988) 163-171.

[9] Y. Koda and F. Ruskey, “A Gray Code for the Ideals of a Forest Poset”, J. Algorithms, to appear.

[10] B. Korte and L. Lovasz, “Basis graphs of greedoids and two-connectivity”, Mathematical Programming Study, 24 (1985) 158-165.

[11] B. Korte, L. Lovasz, R. Schrader, Greedoids, Springer-Verlay, 1991.

[12] E.L. Lawler, “Eficient implementation of dynamic programming algorithms for sequencing problems”, Report BW106/79, Stichting Mathematisch Centrum, Amsterdam, 1979.

[13] J. Propp, “Partial Ordering for Matchings of Bipartite Planar Graphs”, 23rd S.E. Intl. Conference on Combinatorics, Graph Theory and Computing, 1992.

[14] G. Pruesse, “Generating Linear Extensions of Series-Parallel Posets by Transpositions”, manuscript.

[15] G. Pruesse and F. Ruskey, “Generating the Linear Extensions of Certain Posets by Transpositions”, SIAM J. Discrete Math., 4 (1991) 413-422.

[16] G. Pruesse and F. Ruskey, “Generating Linear Extensions Fast”, to appear in SIAM J. Computing.

[17] Reingold, Nievergelt, and Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall, 1977.

[18] F. Ruskey, “Generating Linear Extensions of Posets by Transpositions”, J. Combinatorial Theory (B), 54 (1992) 77-101.

[19] F. Ruskey, “Research Problem 90”, Discrete Math., 70 (1988) 111-112.

[20] L. Schrage and K.R. Baker, “Dynamic programming solution for sequencing problems with precedence constraints”, Operations Research, 26 (1978) 444-449.

[21] G. Stachowiak, “Hamilton Paths in Graphs of Linear Extensions for Unions of Posets”, SIAM J. Discrete Math., 5 (1992) 199-206.

[22] G. Steiner, “An Algorithm to Generate the Ideals of a Partial Order,” Operations Research Letters, 5 (1986) 317-320.

[23] F. Ruskey, “Listing and Counting Subtrees of a Tree,” SIAM J. Computing, 10 (1981) 141-150.

[24] F. Ruskey, “Generating Linear Extensions of Posets,” J. Combinatorial Theory (B), 54 (1992) 77-101.

[25] R.P. Stanley, Enumerative Combinatorics, Vol. I., Wadsworth, 1986.

[26] H.S. Wilf, Combinatorial Algorithms: An Update, SIAM, CBMS 55.

[27] G.M. Ziegler, “Branchings in rooted graphs and the diameter of greedoids”, Combinatorica, 8 (1988) 217-234.