A PERMUTATION GROUP DETERMINED BY AN ORDERED SET

ANDERS CLAESSON, CHRIS D. GODSIL, AND DAVID G. WAGNER

Abstract. Let P be a finite ordered set, and let J(P) be the distributive lattice of order ideals of P. The covering relations of J(P) are naturally associated with elements of P; in this way, each element of P defines an involution on the set J(P). Let Γ(P) be the permutation group generated by these involutions. We show that if P is connected then Γ(P) is either the alternating or the symmetric group. We also address the computational complexity of determining which case occurs.

Let P be a finite ordered set, and let J(P) be the distributive lattice of order ideals (also called down–sets) of P. For each p ∈ P, define a permutation σ_{p} on J(P) as follows: for every S ∈ J(P),

σ_{p}(S) := \{ \begin{matrix}S ∪ \{p\} & if p is minimal in P ∖ S, \\ S ∖ \{p\} & if p is maximal in S, \\ S & otherwise. \end{matrix}

Each of these permutations is an involution. We let Γ(P) denote the subgroup of the symmetric group Sym(J(P)) generated by all these involutions. Plain curiosity led us to wonder about the structure of these permutation groups. As we shall see, this can be determined quite precisely.

As an example, for

P = [figure: c; d; a; b]

we may number the down–sets {∅, a, b, ab, bd, abc, abd, abcd} of P by 1 through 8, and then

J(P) = [figure: 8; 6; d; 7; c; 4; c; d; 5; a; 2; b; 3; a; d; 1; a; b] and \{ \begin{matrix}σ_{a} & = & (1 2)(3 4)(5 7) \\ σ_{b} & = & (1 3)(2 4) \\ σ_{c} & = & (4 6)(7 8) \\ σ_{d} & = & (3 5)(4 7)(6 8) \end{matrix}

Key words and phrases. ordered set, distributive lattice, permutation group.

Research supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.

in which we have labeled the edges of the Hasse diagram of J(P) to indicate the action of each σ_{p} on J(P). By using GAP [1] (or otherwise) one finds that Γ(P) is the symmetric group Sym(J(P)) in this case.

We use the following notation for ordered sets. The set of minimal elements of P is P_{min} and the set of maximal elements of P is P_{max}. A covering relation in P is denoted by a <· b. For S ⊆ P we let ↓S = {p ∈ P : p ≤ b for some b ∈ S} denote the down–set (order ideal) generated by S, we let ↑S = {p ∈ P : b ≤ p for some b ∈ S} denote the up–set (dual order ideal) generated by S, and we let ↕ {p} = ↓S ∪ ↑S be the set of elements comparable with S. The set P with the opposite order is denoted by P^{op}. For more background on finite ordered sets and distributive lattices, see Chapter 3 of Stanley [2], for instance.

The first observation is completely elementary. Lemma 1. Let P and Q be disjoint finite ordered sets. Then

Γ(P ∪ Q) = Γ(P) × Γ(Q).

Proof. Since P ∪ Q is the disjoint union of P and Q we may regard J(P ∪ Q) as J(P) × J(Q) via the bijection S ↔ (S ∩ P, S ∩ Q). For such a down–set S of P ∪ Q we have σ_{p}(S) = (σ_{p}(S ∩ P), S ∩ Q) for all p ∈ P, and σ_{q}(S) = (S ∩ P, σ_{q}(S ∩ Q)) for all q ∈ Q. This proves the result. □

The problem is thus reduced to determining Γ(P) for connected ordered sets P. Theorem 2. Let P be a finite connected ordered set. Then Γ(P) is either the alternating group Alt(J(P)) or the symmetric group Sym(J(P)).

This is, of course, something of a disappointment – we had hoped that some ordered sets would exhibit groups with more interesting structure. Our proof of Theorem 2 is by induction on |J(P)|. We begin with a few simple observations. Lemma 3. For any finite ordered set P, the permutation group Γ(P) acts transitively on J(P).

Proof. This follows immediately from connectedness of the Hasse diagram of J(P).

□

Lemma 4. For any finite ordered set P, Γ(P^{op}) ≃ Γ(P).

Proof. One checks that the bijection S ↦ P ∖ S from J(P) to J(P^{op}) commutes with the actions of Γ(P) on J(P) and Γ(P^{op}) on J(P^{op}). □

An element of an ordered set is extremal if it is either minimal or maximal. Lemma 5. Every finite connected ordered set P with at least two elements has an extremal element p ∈ P such that P ∖ {p} is also connected.

Proof. Form the bipartite graph G with bipartition (P_{min}, P_{max}) and with edges a ∼ b whenever a < b in P. Then G has at least two elements, and P is connected if and only if G is connected. Let T be a spanning tree of G, and let p be a leaf of T. Then G ∖ {p} is connected, so that P ∖ {p} is connected. □

Lemma 6. Let P be a finite ordered set, and let p ∈ P_{max}. Then

\frac{1}{2}|J(P)| ≤ |J(P ∖ \{p\})| < |J(P)|.

Further, if P is connected and |P | ≥ 2 then the first inequality is strict.

Proof. The second inequality is trivial. Let L be the set of down–sets of P which contain p, so that J(P) = J(P ∖{p})∪L. The function from L to J(P ∖{p}) given by S ↦ S∖{p} is injective, so that |L| ≤ |J(P ∖{p})| and the first inequality follows. If equality holds then the above function is a bijection, so that p ∈ P_{min} ∩ P_{max}. When |P | ≥ 2 this implies that P is not connected. □

Lemma 7. Let P be a finite ordered set, and let p ∈ P. Then Γ(P ∖ {p}) is a quotient of a subgroup of Γ(P).

Proof. The subgroup H = ⟨σ_{a} : a ∈ P ∖ {p}⟩ of Γ(P) has two orbits on J(P)

– namely J(P ∖ {p}) and L, with the notation of the proof of Lemma 6. The homomorphism γ ↦ γ|_{J(P ∖{p})} from H to Γ(P ∖ {p}) is surjective, and the result follows. □

Proposition 8. Let P be a finite connected ordered set. Then Γ(P) is 2–transitive (and hence primitive).

Proof. Since Γ(P) is transitive, by Lemma 3, it suffices to show that the stabilizer Γ(P)_{∅} of ∅ in Γ(P) is transitive on J(P) ∖ {∅}. We prove this by induction on |P |, the basis |P | = 1 being trivial.

For the induction step |P | ≥ 2, so that by Lemma 5 there is an extremal element p ∈ P such that P ∖ {p} is connected. By Lemma 4, (replacing P by P^{op} if necessary) we may assume that p is maximal in P.

For each A ⊆ P_{min}, let J_{A}(P) be the set of down–sets S ∈ J(P) such that S ∩ P_{min} = A. Each of these is a distributive lattice – in fact J_{A}(P) ≃ J(P_{A}) in which P_{A} is obtained by deleting the up–set ↑(P_{min} ∖ A) from P, then deleting the set A of minimal elements of the result; see Figure 1 for an example. The covering relations of J(P_{A}) correspond to elements of P_{A} ⊆ P ∖ P_{min}. By Lemma 3, Γ(P_{A}) acts transitively on J(P_{A}). Therefore, the subgroup D = ⟨σ_{v} : v ∈ P ∖ P_{min}⟩ of Γ(P) acts transitively on each of the sets J_{A}(P) separately, for all A ⊆ P_{min}. In fact, these are the orbits of D acting on J(P). The subgroup D is contained in the stabilizer Γ(P)_{∅}.

Now, P ∖ {p} is connected, so that Γ(P ∖ {p}) is 2–transitive on J(P ∖ {p}), by induction. Since Γ(P ∖ {p}) is a quotient of a subgroup of Γ(P), it follows that Γ(P)_{∅} is transitive on J(P ∖ {p}) ∖ {∅} as well. Since J(P_{min}) ∖ {∅} ⊆ J(P ∖ {p}) ∖ {∅}, it follows that J(P_{min}) ∖ {∅} is contained in a single orbit of Γ(P)_{∅} acting on J(P). Since J(P) ∖ {∅} is the union of the J_{A}(P) for all ∅ ≠ A ⊆ P_{min}, it follows that Γ(P)_{∅} acts transitively on J(P) ∖ {∅}. This completes the induction step, and the proof. □

A well–known lemma ([3] Theorem 13.3) states that if a primitive permutation group of degree n contains a 3–cycle then it contains Alt(n). We can apply this in the following circumstance. A covering relation a <· b in P is dominant provided that every element of P is comparable with either a or b. Proposition 9. If a finite ordered set P has a dominant covering relation, then Alt(J(P)) ≤ Γ(P).

Proof. Notice that since P has a dominant covering relation a <· b, it follows that P is connected. Proposition 8 thus implies that Γ(P) is primitive. We claim that the element γ = σ_{b}σ_{a}σ_{b}σ_{a} of Γ(P) is a 3–cycle, which suffices to prove the result.

[figure: •; •; •; •; •; •; •; J_{ab}(P); •; •; d; •; •; c; J_{a}(P); •; e; J_{b}(P); •; a; b; J_{∅}(P)]

Figure 1. The partition of J(P) for P = [figure: c; d; e; a; b]

Consider any down–set S of P on which both σ_{a} and σ_{b} act nontrivially. Then we have either a ∈ S_{max} or a ∈ (P ∖ S)_{min}, and either b ∈ S_{max} or b ∈ (P ∖ S)_{min}. Since a < b and S is a down–set, the only consistent possibility is that a ∈ S_{max} and b ∈ (P ∖ S)_{min}. If c ∈ S_{max} and c ≠ a, then a and c are incomparable – since a <· b is dominant it follows that c < a. Therefore, S ⊆ ↓{b} ∖ {b}. Since b ∈ (P ∖ S)_{min}, it follows that S = ↓{b} ∖ {b}. That is, this down–set ↓{b} ∖ {b} is the only element of J(P) on which both σ_{a} and σ_{b} act nontrivially. From this and the fact that σ_{a} and σ_{b} are involutions, it follows that σ_{b}σ_{a} consists of one 3–cycle and some 2–cycles and fixed points. Therefore γ = (σ_{b}σ_{a})^{2} is a 3–cycle, as claimed. □

The induction step for the proof of Theorem 2 is a consequence of the following lemma. Lemma 10. Let Γ be a primitive group of permutations on a set X with |X| ≥ 9. Assume that Γ has a subgroup H which has exactly two orbits Y and \overline{Y} on X, such that |Y | > |\overline{Y} | and Alt(Y) ≤ H|_{Y}. Then Alt(X) ≤ Γ.

Proof. Let K be the preimage of Alt(Y) under the quotient map H → H|_{Y}. If the pointwise stabilizer K\overline{Y} is trivial then K acts faithfully on \overline{Y}, and therefore Alt(Y) acts faithfully on \overline{Y}. Since |\overline{Y} | < |Y | this is not possible, so that K\overline{Y} is not trivial. Therefore, H contains a nontrivial element h fixing \overline{Y} pointwise. The conjugates of h under H generate a normal subgroup G of H with nontrivial image in H|_{Y}. Since Alt(Y) is simple it follows that Alt(Y) ≤ G. In particular, G (and hence Γ) contains a three–cycle. Since Γ is primitive, it follows that Alt(X) ≤ Γ. □

Proof of Theorem 2. We prove Theorem 2 by induction on |J(P)|. If P is a connected ordered set of width at most two then P contains a dominant covering relation, so that Alt(J(P)) ≤ Γ(P) by Proposition 9. If P is a connected ordered set of width at least three, then |J(P)| ≥ 9. Thus, the basis of induction |J(P)| ≤ 8 is established. For the induction step, let P be a connected ordered set with |J(P)| ≥ 9. Replacing P by P^{op}, if necessary (by Lemma 4) we may assume that p ∈ P_{max} is such that P ∖{p} is connected (by Lemma 5). Now Lemmas 6 and 7, Proposition 8, and the induction hypothesis imply that Γ = Γ(P), X = J(P), H = ⟨σ_{a} : a ∈ P ∖ {p}⟩, and Y = J(P ∖ {p}) satisfy the hypotheses of Lemma 10. It follows that Alt(J(P)) ≤ Γ(P), completing the induction step and the proof. □

The only remaining issue is to determine, for each finite connected ordered set, which case of the conclusion of Theorem 2 holds. This seems to be difficult, but it is equivalent to a problem which appears superficially to be easier. Proposition 11. Let P be a finite connected ordered set. Then Γ(P) = Alt(J(P)) if and only if for every p ∈ P, the cardinality of J(P ∖ ↕{p}) is even.

Proof. The statement follows by observing that for each p ∈ P, the two–cycles of the involution σ_{p} correspond bijectively with the elements of J(P ∖ ↕ {p}). Thus, the condition is equivalent to requiring that Γ(P) is contained in Alt(J(P)). □

Proposition 11 suggests the following two decision problems.

The Group Problem:

Instance: A finite connected ordered set P.
Problem: Determine whether Γ(P) equals Alt(J(P)) or Sym(J(P)).

The Parity Problem:

Instance: A finite ordered set P.
Problem: Determine whether |J(P)| is even or odd.

A decision problem 𝒜 is polynomially reducible to a decision problem ℬ when the following holds: from any instance A of 𝒜 of size n one can compute several instances B_{1}, …, B_{m} of ℬ such that:

• the number of operations required to compute {B_{i}} is bounded by a polynomial function of n; and

• given a solution to ℬ for each B_{i}, a solution to 𝒜 for A can be computed using a number of operations which is bounded by a polynomial function of n. Two decision problems each of which is polynomially reducible to the other are said to be polynomially equivalent. [We are being rather informal with these issues of computational complexity. To be precise, the size of an instance is the number of bits required to represent it, and the operations discussed above are bit operations.] Theorem 12. The Group Problem and the Parity Problem are polynomially equivalent.

Proof. First, we reduce the Parity Problem to the Group Problem. Given a finite ordered set P as an instance of the Parity Problem, let x, y, z be distinct new elements, and construct the ordered set Q with elements P ∪ {x, y, z} and order relations given by those of P together with {x, y} × (P ∪ {z}). Then Q is a finite connected ordered set. Assume that we have a solution to the Group Problem for Q. By Proposition 11, we know whether or not all of the |J(Q∖ ↕ {b})| for b ∈ Q are even. Now, if b ∈ P then Q∖ ↕ {b} = (P ∖ ↕ {b}) ∪ {z}, so that J(Q∖ ↕{b}) = J(P ∖ ↕{b})×J({z}) has even cardinality since |J({z})| = 2. Also, if b ∈ {x, y} then |Q∖ ↕{b}| = 1 so that |J(Q∖ ↕{b})| = 2. Thus, Γ(Q) = Alt(J(Q)) if and only if |J(Q∖ ↕ {z})| is even. Since Q∖ ↕ {z} = P, this reduces the Parity Problem to the Group Problem. One checks easily that the computations can be made with only polynomially many operations.

Conversely, we reduce the Group Problem to the Parity Problem. Given a connected finite ordered set P as an instance of the Group Problem, consider the set {P ∖ ↕ {p} : p ∈ P } of instances of the Parity Problem. This set can be computed from P using only polynomially many operations. Given a solution to the Parity Problem for each instance in this set, we check whether all these parities are even – Proposition 11 implies that if so, then Γ(P) = Alt(J(P)); otherwise Γ(P) = Sym(J(P)). This reduces the Group Problem to the Parity Problem, and completes the proof. □

References

[1] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.3; 2002,

   (http://www.gap-system.org).

[2] R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge U.P., Cambridge, 1997.

[3] H. Wielandt, Finite permutation groups (translated by R. Bercov) Academic Press, New York/London, 1964.

Department of Mathematics, Chalmers University of Technology, S-412 96 Göteborg, Sweden

   E-mail address: claesson@math.chalmers.se

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

   E-mail address: cgodsil@uwaterloo.ca

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

   E-mail address: dgwagner@math.uwaterloo.ca