Group Actions on Boolean Algebras

5 Group actions on boolean algebras. Let us begin by reviewing some facts from group theory. Suppose that X is an n-element set and that G is a group. We say that G acts on the set X if for every element λ of G we associate a permutation (also denoted λ) of X, such that for all x √ X and λ, β √ G we have λ(β(x)) = (λβ)(x). Thus [why?] an action of G on X is the same as a homomorphism � : G � SX , where SX denotes the symmetric group of all permutations of X. We sometimes write λ · x instead of λ(x). 5.1 Example. (a) Let the real number � act on the xy-plane by rotation counterclockwise around the origin by an angle of � radians. It is easy to check that this defines an action of the group R of real numbers (under addition) on the xy-plane. (b) Now let � √ R act by translation by a distance � to the right (i.e., adding (�, 0)). This yields a completely different action of R on the xy-plane. (c) Let X = {a, b, c, d} and G = Z2 × Z2 = {(0, 0), (0, 1), (1, 0), (1, 1)}. Let G act as follows: (0, 1) · a = b, (0, 1) · b = a, (0, 1) · c = c, (0, 1) · d = d (1, 0) · a = a, (1, 0) · b = b, (1, 0) · c = d, (1, 0) · d = c. The reader should check that this does indeed define an action. In particular, since (1, 0) and (0, 1) generate G, we don’t need to define the action of (0, 0) and (1, 1) — they are uniquely determined. (d) Let X and G be as in (c), but now define the action by (0, 1) · a = b, (0, 1) · b = a, (0, 1) · c = d, (0, 1) · d = c (1, 0) · a = c, (1, 0) · b = d, (1, 0) · c = a, (1, 0) · d = b. Again one can check that we have an action of Z2 × Z2 on {a, b, c, d}. Recall what is meant by an orbit of the action of a group G on a set X. Namely, we say that two elements x, y of X are G-equivalent if λ(x) = y for some λ √ G. The relation of G-equivalence is an equivalence relation, and the equivalence classes are called orbits. Thus x and y are in the same orbit if λ(x) = y for some λ √ G. The orbits form a partition of X, i.e, they are pairwise-disjoint, nonempty subsets of X whose union is X. The orbit containing x is denoted Gx; this is sensible notation since Gx consists of all elements λ(x) where λ √ G. Thus Gx = Gy if and only if x and y are G-equivalent (i.e., in the same G-orbit). The set of all G-orbits is denoted X/G. 5.2 Example. (a) In Example 5.1(a), the orbits are circles with center (0, 0) (including the degenerate circle whose only point is (0, 0)). (b) In Example 5.1(b), the orbits are horizontal lines. Note that although in (a) and (b) the same group G acts on the same set X, the orbits are different. (c) In Example 5.1(c), the orbits are {a, b} and {c, d}. (d) In Example 5.1(d), there is only one orbit {a, b, c, d}. Again we have a situation in which a group G acts on a set X in two different ways, with different orbits. We wish to consider the situation where X = Bn , the boolean algebra of rank n (so |Bn | = 2n ). We begin by defining an automorphism of a poset P to be an isomorphism � : P � P . (This definition is exactly analogous to the definition of an automorphism of a group, ring, etc.) The set of all automorphisms of P forms a group, denoted Aut(P ) and called the automorphism group of P , under the operation of composition of functions (just as is the case for groups, rings, etc.) Now consider the case P = Bn . Any permutation λ of {1, . . . , n} acts on Bn as follows: If x = {i1 , i2 , . . . , ik } √ Bn , then λ(x) = {λ(i1 ), λ(i2 ), . . . , λ(ik )}. (24) This action of λ on Bn is an automorphism [why?]; in particular, if |x| = i, then also |λ(x)| = i. Equation (24) defines an action of the symmetric group Sn of all permutations of {1, . . . , n} on Bn [why?]. (In fact, it is not hard to show that every automorphism of Bn is of the form (24) for λ √ Sn .) In particular, any subgroup G of Sn acts on Bn via (24) (where we restrict λ to belong to G). In what follows this action is always meant. 5.3 Example. Let n = 3, and let G be the subgroup of S3 with elements e and (1, 2). Here e denotes the identity permutation, and (using disjoint cycle notation) (1, 2) denotes the permutation which interchanges 1 and 2, and fixes 3. There are six orbits of G (acting on B3 ). Writing e.g. 13 as short for {1, 3}, the six orbits are {Ø}, {1, 2}, {3}, {12}, {13, 23}, and {123}. We now define the class of posets which will be of interest to us here. Later we will give some special cases of particular interest. 5.4 Definition. Let G be a subgroup of Sn . Define the quotient poset Bn /G as follows: The elements of Bn /G are the orbits of G. If O and O ◦ are two orbits, then define O � O ◦ in Bn /G if there exist x √ O and y √ O ◦ such that x � y in Bn . (It’s easy to check that this relation � is indeed a partial order.) 5.5 Example. (a) Let n = 3 and G be the group of order two generated by the cycle (1, 2), as in Example 5.2. Then the Hasse diagram of B3 /G is shown below, where each element (orbit) is labeled by one of its elements. � 123 �� �� � � � �� 12 � 13 �� �� � � � � � ���1 3� � � � � ���Ø (b) Let n = 5 and G be the group of order five generated by the cycle (1, 2, 3, 4, 5). Then B5 /G has Hasse diagram � 12345 � 1234 �� �� � � � � �� 124 123 � � �� �� � � ��� � � � 12 13 � � � � ���1 �Ø One simple property of a quotient poset Bn /G is the following. 5.6 Proposition. The quotient poset Bn /G defined above is graded of rank n and rank-symmetric. Proof. We leave as an exercise the easy proof that Bn /G is graded of rank n, and that the rank of an element O of Bn /G is just the rank in Bn of any of the elements x of O. Thus the number of elements pi (Bn /G) of rank i is equal to the number of orbits O √ (Bn )i /G. If x √ Bn , then let x̄ denote the set-theoretic complement of x, i.e., x̄ = {1, . . . , n} − x = {1 � i � n : i ∈√ x}. Then {x1 , . . . , xj } is an orbit of i-element subsets of {1, . . . , n} if and only if {¯ x1 , . . . , x¯j } is an orbit of (n − i)-element subsets [why?]. Hence |(Bn )i /G| = |(Bn )n−i /G|, so Bn /G is rank-symmetric. � Let λ √ Sn . We associate with λ a linear transformation (still denoted λ) λ : R(Bn )i � R(Bn )i by the rule ⎞ � � � cx λ(x), λ� c x x⎝ = x�(Bn )i x�(Bn )i where each cx is a real number. (This defines an action of Sn , or of any subgroup G of Sn , on the vector space R(Bn )i .) The matrix of λ with respect to the basis (Bn )i is just a permutation matrix, i.e., a matrix with one 1 in every row and column, and 0’s elsewhere. We will be interested in elements of R(Bn )i which are fixed by every element of a subgroup G of Sn . The set of all such elements is denoted R(Bn )G i , so R(Bn )G i = {v √ R(Bn )i : λ(v) = v for all λ √ G}. 5.7 Lemma. A basis for R(Bn )G i consists of the elements � vO := x, x�O where O √ (Bn )i /G, the set of G-orbits for the action of G on (Bn )i . Proof. First note that if O is an orbit and x √ O, then by definition of orbit we have λ(x) √ O for all λ √ G. Since λ permutes the elements of (Bn )i , it follows that λ permutes the elements of O. Thus λ(vO ) = vO , so vO √ R(Bn )G i . It is clear that the vO ’s are linearly independent since any x √ (Bn )i appears with nonzero coefficient in exactly one vO . � It remains to show that the vO ’s span R(Bn )G i , i.e., any v = x�(Bn )i cx x √ G R(Bn )i can be written as a linear combination of vO ’s. Now a vector v √ R(Bn )i will belong to R(Bn )G i if and only if its coefficients are con­ stant on G-orbits and hence if and only if it is a linear combination of vO ’s for the various G-orbits O. Now let us consider the effect of applying the order-raising operator Ui to an element v of R(Bn )G i . 5.8 Lemma. G If v √ R(Bn )G i , then Ui (v) √ R(Bn )i+1 . Proof. Note that since λ √ G is an automorphism of Bn , we have x < y in Bn if and only if λ(x) < λ(y) in Bn . It follows [why?] that if x √ (Bn )i then Ui (λ(x)) = λ(Ui (x)). Since Ui and λ are linear transformations, it follows by linearity that Ui λ(u) = λUi (u) for all u √ R(Bn )i . (In other words, Ui λ = λUi .) Then λ(Ui (v)) = Ui (λ(v)) = Ui (v), so Ui (v) √ R(Bn )G i+1 , as desired. � We come to the main result of this section, and indeed our main result on the Sperner property. 5.9 Theorem. Let G be a subgroup of Sn . Then the quotient poset Bn /G is graded of rank n, rank-symmetric, rank-unimodal, and Sperner. Proof. Let P = Bn /G. We have already seen in Proposition 5.6 that P is graded of rank n and rank-symmetric. We want to define order-raising ˆ i : RPi � RPi−1 . operators Uˆi : RPi � RPi+1 and order-lowering operators D Let us first consider just Ûi . The idea is to identify the basis element vO of RBnG with the basis element O of RP , and to let Ûi : RPi � RPi+1 correspond to the usual order-raising operator Ui : R(Bn )i � R(Bn )i+1 . More precisely, suppose that the order-raising operator Ui for Bn given by (18) satisfies � Ui (vO ) = cO,O∩ vO∩ , (25) O ∩ �(Bn )i+1 /G where O √ (Bn )i /G. (Note that by Lemma 5.8, Ui (vO ) does indeed have the form given by (25).) Then define the linear operator Ûi : R((Bn )i /G) � R((Bn )i /G) by � Ûi (O) = cO,O∩ O ◦ . O ∩ �(Bn )i+1 /G ˆi is order-raising. We need to show that if cO,O∩ ∈= 0, We claim that U � ◦ then O > O in Bn /G. Since vO∩ = x∩ �O∩ x◦ , the only way cO,O∩ ∈= 0 in (25) is for some x◦ √ O ◦ to satisfy x◦ > x for some x √ O. But this is just what it means for O ◦ > O, so Uˆi is order-raising. Now comes the heart of the argument. We want to show that Ûi is oneto-one for i < n/2. Now by Theorem 4.7, Ui is one-to-one for i < n/2. Thus the restriction of Ui to the subspace R(Bn )G i is one-to-one. (The restriction of a one-to-one function is always one-to-one.) But Ui and Ûi are exactly the same transformation, except for the names of the basis elements on which they act. Thus Ûi is also one-to-one for i < n/2. An exactly analogous argument can be applied to Di instead of Ui . We ˆ i : R(Bn )G � R(Bn )G for obtain one-to-one order-lowering operators D i i−1 i > n/2. It follows from Proposition 4.4, Lemma 4.5, and (20) that Bn /G is rank-unimodal and Sperner, completing the proof. � We will consider two interesting applications of Theorem 5.9. For our first �m� application, we let n = 2 for some m ← 1, and let M = {1, . . . , m}. Let � � X = M2 , the set of all two-element subsets of M . Think of the elements of X as (possible) edges of a graph with vertex set M . If BX is the boolean algebra of all subsets of X (so BX and Bn are isomorphic), then an element x of BX is a collection of edges on the vertex set M , in other words, just a simple graph on M . Define a subgroup G� of� SX as follows: Informally, G consists of all permutations of the edges M2 that are induced from permutations of the vertices M . More precisely, if λ √ Sm , then define λ ˆ √ SX by λ̂({i, j}) = {λ(i), λ(j)}. Thus G is isomorphic to Sm . When are two graphs x, y √ BX in the same orbit of the action of G on BX ? Since the elements of G just permute vertices, we see that x and y are in the same orbit if we can obtain x from y by permuting vertices. This is just what it means for two simple graphs x and y to be isomorphic — they are the same graph except for the names of the vertices (thinking of edges as pairs of vertices). Thus the elements of BX /G are isomorphism classes of simple graphs on the vertex set M . In particular, #(BX /G) is the number of nonisomorphic m-vertex simple graphs, and #((BX /G)i ) is the number of nonisomorphic such graphs with i edges. We have x � y in BX /G if there is some way of labelling the vertices of x and y so that every edge of x is an edge of y. Equivalently, some spanning subgraph of y (i.e., a subgraph of y with all the vertices of y) is isomorphic to x. Hence by Theorem 5.9 there follows the following result, which is by no means obvious and has no known non-algebraic proof. 5.10 Theorem. (a) Fix m ← 1. Let pi be the number of nonisomorphic simple graphs with m vertices and i edges. Then the sequence p0 , p1 , . . . , p(m) 2 is symmetric and unimodal. (b) Let T be a collection of nonisomorphic simple graphs with m vertices such that no element of T is isomorphic to a subset of another element of T . Then |T | is�maximized by taking T to consist of all nonisomorphic simple � 1 m graphs with ⊂ 2 2 ⊆ edges. Our second example of the use of Theorem 5.9 is somewhat more subtle and will be the topic of the next section.