Printer Friendly

The topology of restricted partition posets.

1 Introduction

The study of partitions with restrictions on their block sizes began in the dissertation by Sylvester [16], who studied the poset [[PI].sup.2.sub.n] of partitions where every block has even size. He proved that the Mobius function of this poset is given by [mu]([[PI].sup.2.sub.n] [union]{[??]}) = [(-1).sup.n/2] x [E.sub.n-1], where [E.sub.n] denotes the nth Euler number. Recall that the nth Euler number enumerates the number of alternating permutations, that is, permutations [alpha] = [[alpha].sub.1] ... [[alpha].sub.n] in the symmetric group [G.sub.n] such that [[alpha].sub.1] < [[alpha].sub.2] > [[alpha].sub.3] < [[alpha].sub.4] > .... Stanley [13] generalized this result to the d-divisible partition lattice [[PI].sup.d.sub.n], that is, the collection of partitions of {1, 2, ..., n} where each block size is divisible by d. His results states that the Mobius function [mu]([[PI].sup.d.sub.n] [union] {[??]}) is, up to the sign [(-1).sup.n/d], the number of permutations in [G.sub.n-1] with descent set {d, 2d, ..., n - d}, in other words, the number of permutations with descent composition (d, ..., d, d - 1).

Calderbank, Hanlon and Robinson [3] extended these results by considering the action of the symmetric group [G.sub.n-1] on the top homology group of the order complex of [[PI].sup.d.sub.n] - {[??]}. They showed this action is the Specht module on the border strip corresponding the composition (d, ..., d, d - 1).

Wachs [17] showed that the d-divisible partition lattice has an EL-shelling, and hence as a corollary obtained that the homotopy type is a wedge of spheres of dimension n/d - 2. She then gave a more explicit proof of the representation of the top homology of [[PI].sup.d.sub.n] - {[??]}.

So far we note that the d-divisible partition lattice is closely connected with the permutations having the descent composition (d, ..., d, d - 1). We explain this phenomenon in this paper by introducing pointed partitions. They are partitions where one block is considered special, called the pointed block. We obtain such a partition by removing the element n from its block and making this block the pointed block. We now extend the family of posets under consideration. For each composition [??] = ([c.sub.1], ..., [c.sub.k]) of n we define a poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that the Mobius function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the sign [(-1).sup.k] times the number of permutations with descent composition [??]. Furthermore, the order complex of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is homotopy equivalent to a wedge of spheres of dimension k - 2. Finally, we show the action of the symmetric group on the top homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the Specht module corresponding to the composition [??].

Our techniques differ from Wachs' method for studying the d-divisible partition lattice. Using Quillen's fiber lemma, we are able to change the poset question into studying the subcomplexes of the complex of ordered partitions. These subcomplexes are in fact order complexes of rank-selected Boolean algebras and hence shellable. The homotopy equivalence given by Quillen's fiber lemma also carries the action of the symmetric group.

Ehrenborg and Readdy [4] studied the Mobius function of filters of the partition lattice. They defined the notion of a knapsack partition. For a filter of a knapsack partition they showed that its Mobius function was a sum of descent set statistics. We now extend these results topologically by showing that the associated order complex is a wedge of spheres. The proof follows the same outline as the previous study except that we use discrete Morse theory to determine the homotopy type of the associated complexes of ordered set partitions. Furthermore we obtain that the action of the symmetric group on the the top homology is a direct sum of Specht modules.

We end the paper with open questions for future research.

2 Preliminaries

Forbasic notions concerning partially ordered sets (posets), see the book by Stanley [14]. For topological background, see the article by Bjorner [2] and the book by Kozlov [10]. Finally, for representation theory for the symmetric group, see Sagan [12].

Let [n] denote the set {1,2, ..., n} and for i [less than or equal to] j let [i, j] denote the interval {i, i + 1, ..., j}. A pointed set partition [pi] of the set [n] is a pair ([sigma], Z), where Z is a subset of [n] and [sigma] = {[B.sub.1], [B.sub.2], ..., [B.sub.k]} is a partition of the set difference [n] - Z. We will write the pointed partition [pi] as

[pi] = {[B.sub.1], [B.sub.2], ..., [B.sub.k], [Z.bar]},

where we underline the set Z and we write 1358|4|267 as shorthand for {{1,3,5,8},{4},{2,6,7}}. Moreover, we call the set Z the pointed block. Let [[PI].sup.[??].sub.n] denote the set of all pointed set partitions on the set [n]. The set [[PI].sup.[??].sub.n] has a natural poset structure. The order relation is given by

{[B.sub.1], [B.sub.2], ..., [B.sub.k], [Z.bar]} < {[B.sub.1] [union] [B.sub.2], ..., [B.sub.k], [Z.bar]},

{[B.sub.1], [B.sub.2], ..., [B.sub.k], [Z.bar]} < {[B.sub.2], ..., [B.sub.k], [[[B.sub.1] [union] Z].bar]}.

The lattice [[PI].sup.[??].sub.n] is isomorphic to the partition lattice [[PI].sub.n+1] by the bijection {[B.sub.1], ..., [B.sub.k], [Z.bar]} [??] {[B.sub.1], ..., [B.sub.k], Z [union] {n + 1}}. However it is to our advantage to work with pointed set partitions.

For a permutation [alpha] = [[alpha].sub.1] ... [[alpha].sub.n] in the symmetric group [G.sub.n] define its descent set to be the set

{i [member of] [n - 1] : [[alpha].sub.i], > [[alpha].sub.i+1]}.

Subsets of [n - 1] are in a natural bijective correspondence with compositions of n. Hence we define the descent composition of the permutation [alpha] to be the composition

Des([alpha]) = ([s.sub.1], [s.sub.2] - [s.sub.1], [s.sub.3] - [s.sub.2], ..., [s.sub.k-1] - [s.sub.k-2], n - [s.sub.k- 1]),

where the descent set of [alpha] is the set {[s.sub.1] < [s.sub.2] < ... < [s.sub.k-1]}. We define an integer composition [??] = ([c.sub.1], ..., [c.sub.k]) to be a list of positive integers [c.sub.1], ..., [c.sub.k-1] and a non-negative integer [c.sub.k] with [c.sub.1] + ... + [c.sub.k] = n. Note that the only part allowed to be 0 is the last part. Let [beta]([??]) denote the number of permutations in [alpha] [member of] [G.sub.n] with descent composition [??] for [c.sub.k] > 0. If [c.sub.k] = 0, let [beta]([??]) = 0 for k [greater than or equal to] 2 and [beta]([??]) = 1 for k = 1.

On the set of compositions on n we define an order relation by letting the cover relation be adding adjacent entries, that is,

([c.sub.1], ..., [c.sub.i], [c.sub.i+1], ..., [c.sub.k]) < ([c.sub.1], ..., [c.sub.i] + [c.sub.i+1], ..., [c.sub.k]).

Observe that this poset is isomorphic to the Boolean algebra [B.sub.n] on n elements and the maximal and minimal elements are the two compositions (n) and (1, ..., 1,0).

An integer partition [lambda] of a non-negative integer n is a multiset of positive integers whose sum is n. We will indicate multiplicities with a superscript. Thus {5, 3, 3, 2, 1, 1, 1} = {5, [3.sup.2], 2, [1.sup.3]} is a partition of 16. A pointed integer partition ([lambda], m) of n is pair where m is a non-negative integer and [lambda] is a partition of n - m. We write this as {[[lambda].sub.1], ..., [[lambda].sub.p], [m.bar]} where [lambda] = {[[lambda].sub.1], ..., [[lambda].sub.p]} is the partition and m is the pointed part. This notion of pointed integer partition is related to pointed set partitions by defining the type of a pointed set partition [pi] = {[B.sub.1], [B.sub.2], ..., [B.sub.k], [Z.bar]} to be the pointed integer partition

type([pi]) = {[absolute value [B.sub.1]], [absolute value of [B.sub.2]], ..., [absolute value of [B.sub.k]], [absolute value of [Z.bar]]}.

Similarly, the type of a composition [??] = ([c.sub.1], ..., [c.sub.k]) is the pointed integer partition

type([??]) = {[c.sub.1], ..., [c.sub.k-1], [[c.sub.k].bar]}.

We now define the poset central to this paper.

Definition 2.1 For [??] a composition of n, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the subposet of the pointed partition lattice [[PI].sup.[??].sub.n] described by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In other words, the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] consists of all pointed set partitions such that their type is the type of some composition [??] which is greater or equal to the composition [??] in the composition order.

Example 2.2 Consider the composition [??] = (d, ..., d, d - 1) of the integer n = d x k - 1. For a composition to be greater than or equal to [??], it is equivalent to all its parts must be divisible by d except the last part which is congruent to d - 1 modulo d. Hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] consists of all pointed set partitions where the block sizes are divisible by [??] except the pointed block whose size is congruent to d - 1 modulo d. Hence the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is isomorphic to the d-divisible partition lattice [[PI].sup.d.sub.n+1].

Example 2.3 We note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is in general not a lattice. Consider the composition [??] = (1,1, 2,1) and the four pointed set partitions

[[pi].sub.1] = 1|2|34|[5.bar], [[pi].sub.2] = 2|5|34|[1.bar], [[pi].sub.3] = 34|[125.bar] and [[pi].sub.4] = 2|[1345.bar]

in [[PI].sup.[??].sub.1,1,2,1)]. In the pointed partition lattice [II.sup.[??].sub.5] we have that [[pi].sub.1], [[pi].sub.2] < 2|34|[15.bar] < [[pi].sub.3], [[pi].sub.4]. Since the pointed set partition 2|34|[15.bar] does not belong to [II.sup.[??].sub.(1,1,2,1)], we conclude that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not a lattice.

For a poset P define its order complex to be the simplicial complex [DELTA](P) where the vertices of the complex [DELTA](P) are the elements of the poset P and the faces are the chains in poset. In other words, the order complex of P is given by

[DELTA](P) = {{[x.sub.1], [x.sub.2], ..., [x.sub.k]} : [x.sub.1] < [x.sub.2] < ... < [x.sub.k], [x.sub.1], ..., [x.sub.k] [member of] P}.

For the remainder of this section, we restrict ourselves to considering compositions of n where the last part is positive. Such a composition lies in the interval from (1, ..., 1) to (n). This interval is isomorphic to the Boolean algebra [B.sub.n-1] which is a complemented lattice. Hence for such a composition [??] there exists a complementary composition [??]' such that [??] [conjunction] [??]' = (1, ..., 1) and [??] [disjunction] [??] = (n). As an example, the complement of the composition (1, 3, 1, 1, 4) = (1, 1 + 1 + 1, 1, 1, 1 + 1 + 1 + 1) is obtained by exchanging commas and plus signs, that is, (1 + 1, 1, 1 + 1 + 1 + 1, 1, 1, 1) = (2, 1, 4, 1, 1, 1). Note that the complementary composition has n - k + 1 parts.

For a composition [??] = ([c.sub.1], ..., [c.sub.k]) define the intervals [R.sub.1], ..., [R.sub.k] by [R.sub.i] = [[c.sub.1] + ... + [c.sub.i-1] + 1, [c.sub.1] + ... + [c.sub.i]]. Define the subgroup [G.sub.[??]] of the symmetric group [G.sub.n] by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [K.sub.1], ..., [K.sub.n-k+1] be the corresponding intervals for the complementary composition [??]'. Define the subgroup [G'.sub.[??]] by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A border strip is a connected skew shape which does not contain a 2 by 2 square [15, Section 7.17]. For each composition [??] there is a unique border strip B that has k rows and the ith row from below consists of [c.sub.i] boxes. If we label the n boxes of the border strip from southwest to northeast, then the intervals [R.sub.1], ..., [R.sub.k] correspond to the rows and the intervals [K.sub.1], ..., [K.sub.n-k+1] correspond to the columns. Furthermore, the group [G.sub.[??] is the row stabilizer and the group [G.sub.[??] is the column stabilizer of the border strip B.

3 The simplicial complex of ordered set partitions

An ordered set partition [tau] of set S is a list of blocks ([C.sub.1], [C.sub.2], ..., [C.sub.m]) where the blocks are subsets of the set S satisfying:

(i) All blocks except possibly the last block are non-empty, that is, [C.sub.i] [not equal to] 0 for 1 [less than or equal to] i [less than or equal to] m - 1.

(ii) The blocks are pairwise disjoint, that is, [C.sub.1] [intersection] [C.sub.j] = 0 for 1 [less than or equal to] i < j [less than or equal to] m.

(iii) The union of the blocks is S, that is, [C.sub.1] [union] ... [union] [C.sub.m] = S.

To distinguish from pointed partitions we write 36-127-8-45 for ({3,6}, {1,2, 7}, {8}, {4,5}). The type of an ordered set partitions, type([tau]), is the composition ([absolute value of [C.sub.1]], [absolute value of [C.sub.2]] ,..., [absolute value of [C.sub.m]]).

Let [[DELTA].sub.n] denote the collection of all ordered set partitions of the set [n]. We view [[DELTA].sub.n] as a simplicial complex. The ordered set partition [tau] = ([C.sub.1], [C.sub.2], ..., [C.sub.m]) is an (m - 2)-dimensional face. It has m - 1 facets, which are [tau] = ([C.sub.1], ..., [C.sub.i] [union] [C.sub.i+1], ..., [C.sub.m]) for 1 [less than or equal to] i [less than or equal to] m - 1. The empty face corresponds to the ordered partition ([n]). The complex [[DELTA].sub.n] has [2.sup.n] - 1 vertices that are of the form ([C.sub.1], [C.sub.2]) where [C.sub.1] [not equal to] 0. Moreover there are n! facets corresponding to permutations in the symmetric group [G.sub.n], that is, for a permutation [alpha] = [[alpha].sub.1] ... [[alpha].sub.n], the associated facet is ({[[alpha].sub.1]}, {[[alpha].sub.2]}, ..., {[[alpha].sub.n]}, 0).

The permutahedron is the (n - 1)-dimensional polytope obtained by taking the convex hull of the n! points ([[alpha].sub.1], ..., [[alpha].sub.n]) where [alpha] = [[alpha].sub.1] ... [[alpha].sub.n] ranges over all permutations in the symmetric group [G.sub.n]. Let [P.sub.n] denote the boundary complex of the dual of the (n - 1)-dimensional permutahedron. Since the permutahedron is a simple polytope the complex [P.sub.n] is a simplicial complex homeomorphic to an (n - 2)-dimensional sphere. In fact, it is the boundary of the complex [[DELTA].sub.n].

For a permutation [alpha] = [[alpha].sub.1] ... [[alpha].sub.n] in the symmetric group [G.sub.n] and a composition [??] = ([c.sub.1], ..., [c.sub.k]) of n, define the ordered partition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We write [sigma]([alpha]) when it is clear from the context what the composition [??] is.

For a composition [??] define the subcomplex [[DELTA].sub.[??]] to be

[[DELTA].sub.[[??]] = {[tau] [member] [[DELTA].sub.n] : [??] [less than or equal to] type([tau])}.

This complex has all of its facets of type [??]. Especially, each facet has the form [sigma]([alpha], [??]) for some permutation [alpha]. As an example, note that [[DELTA].sub.(1, 1, ...,1)] is the complex [P.sub.n].

However for a facet F in [[DELTA].sub.[??]] there are [??]! = [c.sub.1]! ... [c.sub.k]! permutations that map to it by the function [sigma]. Let [[sigma].sup.-1](F) denote the unique permutation [alpha] that gets mapped to the facet F which satisfies the inequalities

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for 0 [less than or equal to] i [less than or equal to] k - 1. Furthermore, the descent composition of the permutation [[sigma].sup.-1](F) is greater than or equal to the composition [??], that is, Des([[sigma].sup.-1](F)) [greater than or equal to] [??].

Lemma 3.1 If the composition [??] = ([c.sub.1], ..., [c.sub.k]) ends with 0, then the simplicial complex [[DELTA].sub.[??]] is a cone over the complex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with apex ([n], 0) and hence contractible.

Theorem 3.2 Let [??] be a composition not ending with a zero. Then the simplicial complex [[DELTA].sub.[??]] is shellable. The spanning facets (also known as the homology facets) are of the form [sigma]([alpha]) where [alpha] ranges over all permutations in the symmetric group [G.sub.n] with descent composition [??], that is, Des([alpha]) = [??]. Hence the complex [[DELTA].sub.[??]] is homotopy equivalent to wedge of [beta]([??]) spheres of dimension k - 2.

By observing that [[DELTA].sub.[??]] is the order complex of a rank selection of the Boolean algebra [B.sub.n], this result is a direct consequence of that [B.sub.n] is EL-shellable [1].

4 The homotopy type of the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We now will use Quillen's fiber lemma to show that the chain complex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is homotopy equivalent to the simplicial complex [[DELTA].sub.[??]]. Recall that a simplicial map f from a simplicial complex [GAMMA] to a poset P sends vertices of [GAMMA] to elements of P and faces of the simplicial complex to chains of P. We have the following result due to Quillen [11].

[FIGURE 1 OMITTED]

Theorem 4.1 (Quillen's Fiber Lemma) Let f be a simplicial map from the simplicial complex [GAMMA] to the poset P such that for all x in P, the subcomplex [DELTA]([f.sup.-1]([P.sub.[greater than or equal to] x])) is contractible. Then the order complex [DELTA](P) and the simplicial complex [GAMMA] are homotopy equivalent.

Quillen's proof of this result uses homotopy colimits. The proof of this result due to Walker [19] shows that the continuous function f : [absolute value of [GAMMA]] [right arrow] [absolute value of [DELTA](P)] has a homotopy inverse. We will use this later when we study the action of the symmetric group in Section 6.

Recall that the barycentric subdivision of a simplicial complex [GAMMA] is the simplicial complex sd([GAMMA]) whose vertices are the non-empty faces of [GAMMA] and faces are subsets of chains of faces in [GAMMA] ordered by inclusion. It is well-known that [GAMMA] and sd([GAMMA]) are homeomorphic (since they have the same geometric realization) and hence are homotopy equivalent.

Consider the map [phi] that sends an ordered set partition ([C.sub.1], [C.sub.2], ..., [C.sub.k]) to the pointed partition {[C.sub.1], [C.sub.2], ..., [C.sub.k-1], [[C.sub.k].bar]}. We call this map the forgetful map since it forgets about the order between the blocks except it keeps the last part as the pointed block. Observe that the inverse image of the pointed partition {[C.sub.1], [C.sub.2], ..., [C.sub.k-1], [[C.sub.k].bar]} consists of (k - 1)! ordered set partitions.

Lemma 4.2 Let [pi] be the pointed partition {[B.sub.1], ..., [B.sub.m-1], [[B.sub.m].bar]} where m [greater than or equal to] 2. Let [OMEGA] be the subcomplex of the complex [[DELTA].sub.[??]] whose facets are given by the inverse image

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then the complex [OMEGA] is a cone over the apex ([n] - [B.sub.m], [B.sub.m]) and hence is contractible.

Theorem 4.3 The order complex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is homotopy equivalent to the barycentric subdivision sd([[DELTA].sub.[??]]) and hence [[DELTA].sub.[??]].

By considering the reduced Euler characteristic of the complex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we have the following corollary.

Corollary 4.4 The Mobius function of the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is given by [(- 1).sup.k] x [beta]([??]).

We note that this corollary can be given a combinatorial proof which avoids Quillen's fiber lemma.

5 Cycles in the complex [[DELTA].sub.[??]]

In this section and the next we assume that the last part of the composition [??] is non-zero, since in the case [c.sub.k] = 0 the homology group is the trivial group; see Lemma 3.1.

For [alpha] a permutation in the symmetric group [G.sub.n], define the subcomplex [[summation].sub.[alpha]] of the complex [[DELTA].sub.[??]] to be the simplicial complex whose facets are given by {[sigma]([alpha] [omicron] [gamma]) : [gamma] [member of] [G'.sub.[??]]}.

Lemma 5.1 The subcomplex [[summation].sub.[alpha]] is isomorphic to the join of the duals of the permutahedra [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and hence it is sphere of dimension k - 2.

Observe that the facets of [[DELTA].sub.[??]] are in bijection with permutations [alpha] such that Des([alpha]) [greater than or equal to] [??] in the composition order.

Recall that the boundary map of the face [sigma] = ([C.sub.1], ..., [C.sub.r]) in the chain complex of [[DELTA].sub.[??]] is defined by

[partial derivative](([C.sub.1], ..., [C.sub.r])) = [r-1.summation over (i=1)] [(-1).sup.i-1] x ([C.sub.1], ..., [C.sub.i] [union] [C.sub.i+1], ..., [C.sub.r]).

Lemma 5.2 For [alpha] [member of] [G.sub.n], the element

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in the chain group [C.sub.k-2] ([[DELTA].sub.[??]]) belongs to the kernel of the boundary map and hence to the homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 5.3 The cycles [g.sub.[alpha]], where [alpha] ranges over all permutations with descent composition [??], form a basis for the homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

6 Representation of the symmetric group

The symmetric group [G.sub.n] acts naturally on the the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by relabeling the elements. Hence it also acts on the order complex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Lastly, the symmetric group acts on the top homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We show in this section that this action is a Specht module of the border strip B corresponding to the composition [??]. For an overview on the representation theory of the symmetric group, we refer the reader to Sagan's book [12].

The forgetful map [phi] from sd([[DELTA].sub.[??]]) to the order complex of the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] commutes with the action of the symmetric group [G.sub.n]. In other words, we have the commutative diagram

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [gamma] belongs to [G.sub.n]. Observe that the map [phi] extends to a continuous function from the geometric realization [absolute value of sd([[DELTA].sub.[??]]] to the geometric realization [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and hence we have the map between the homology groups [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By applying homology, we obtain that the following diagram of homology groups commutes:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From the Quillen's fiber lemma we know that the function [phi] has a homotopic inverse, say [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that [[phi].sub.*] and [[psi].sub.*] are inverses of each other. The function [psi] may not commute with the group action. However, since [[gamma].sub.*] [omicron] [[psi].sub.*] = [[psi].sub.*] [omicron] [[phi].sub.*] [omicron] [[gamma].sub.*] [omicron] [[psi].sub.*] = [[psi].sub.*] [omicron] [[gamma].sub.*] [omicron] [[phi].sub.*] [omicron] [[psi].sub.*] = [[psi].sub.*] [omicron] [[gamma].sub.*] we have that [[psi].sub.*] commutes with the group action. We formulate this statement as follows.

Proposition 6.1 The two homology groups [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are isomorphic as [G.sub.n]-modules.

It is clear that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are isomorphic as [G.sub.n] modules. Hence in the remainder of this section we will study the action the symmetric group [G.sub.n] on [[DELTA].sub.[??]] and its action on the homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let B be the border strip that has k rows where the ith row consists of [c.sub.i] boxes. Recall that a tableau is a filling of the boxes of the shape B with the integers 1 through n. A standard Young tableau is a tableau where the rows and columns are increasing. A tabloid is an equivalence class of tableaux under the relation of permuting the entries in each row. See [12, Section 2.1] for details.

Observe that there is a natural bijection between tabloids of shape B and facets of the complex [[DELTA].sub.[??]] by letting the elements in each row form a block and letting the order of the blocks go from lowest to highest row. Let [M.sup.B] be the permutation module corresponding to shape B, that is, the linear span of all tabloids of shape B. Notice that the above bijection induces a [G.sub.n]-module isomorphism between the permutation module [M.sup.B] and the chain group [C.sub.k-2] ([[DELTA].sub.[??]]).

Furthermore, there is a bijection between tableaux of shape B and and permutations by reading the elements in the northeast direction from the border strip. Recall that the group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the column stabilizer of the border strip B. Let t be a tableau and [alpha] its association permutation. Hence the polytabloid [e.sub.t] corresponding to the tableau t is the element [g.sub.[alpha]] presented in Lemma 5.2. Since the Specht module [S.sup.B] is the submodule of [M.sup.B] spanned by all polytabloids, Lemma 5.2 proves that the Specht module [S.sup.B] is isomorphic to a submodule of the kernel of the boundary map [[partial derivative].sub.k-2]. Since the kernel is the top homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and the Specht module [S.sup.B] and the homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have the same dimension [beta]([??]), we conclude that they are isomorphic. To summarize we have:

Proposition 6.2 The top homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is isomorphic to the Specht module [S.sup.B] as [G.sub.n]-modules.

By combining Propositions 6.1 and 6.2, the main result of this section follows.

Theorem 6.3 The top homology group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is isomorphic to the Specht module [S.sup.B] as [G.sub.n]-modules.

7 Knapsack partitions

We now turn our attention to filters in the pointed partition lattice [[PI].sup.[??].sub.n] that are generated by a pointed knapsack partition. These filters were introduced in [4].

Recall that we view an integer partition [lambda] as a multiset of positive integers. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an integer partition, where we assume that the [[lambda].sub.i]'s are distinct. If all the ([e.sub.1] + 1) ... ([e.sub.q] + 1) integer linear combinations

{[q.summation over (i=10)] [f.sub.i] x [[lambda].sub.i] : 0 [less than or equal to] [f.sub.i] [less than or equal to] [e.sub.i]}

are distinct, we call [lambda] a knapsack partition. A pointed integer partition {[lambda], [m.bar]} is called a pointed knapsack partition if the partition [lambda] is a knapsack partition.

Definition 7.1 For a pointed knapsack partition {[lambda], [m.bar]} = {[[lambda].sub.1], [[lambda].sub.2], ..., [[lambda].sub.k], [m.bar]} of n define the sub-poset [[PI].sup.[??].sub.{[lambda],[m.bar]]} to be the filter of [[PI].sup.[??].sub.n] generated by all pointed set partitions of type {[lambda], [m.bar]} and define the subcomplex [[LAMBDA].sub.{[lambda],[m.bar]}] of the complex [[DELTA].sub.n] by

[[LAMBDA].sub.{[lambda],[m.bar]}] = {[tau] = ([C.sub.1], ..., [C.sub.r-1], ([C.sub.r]) [member of] [[DELTA].sub.n] : {[C.sub.1], ..., [C.sub.r-1], [[C.sub.r].bar]} [member of] [[PI].sup.[??].sub.{[lambda],[m.bar]}}.

For a pointed knapsack partition {[lambda], [m.bar]} of n define F to be the filter in the poset of compositions of n generated by compositions [??] such that type([??]) = {[lambda], [m.bar]}. Now define V([lambda], [m.bar]) to be the collection of all pointed compositions [??] = ([c.sub.1], [c.sub.2], ..., [c.sub.r]) in the filter F such that each [c.sub.i], 1 [less than or equal to] i [less than or equal to] r - 1, is a sum of distinct parts of the partition [lambda] and [c.sub.r] = m. As an example, for [lambda] = {1,1,3,7} we have (4, 8, m) [member of] V([lambda], [m.bar]) but (2,10, m) [not member of] V([lambda], [m.bar]).

For a composition [??] in V([lambda], [m.bar]) define [epsilon]([??]) to be the composition of type {[lambda], [m.bar]}, where each entry [d.sub.i] of [??] has been replaced with a decreasing list of parts of [lambda]. That is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 2 OMITTED]

As an example, for the pointed knapsack partition [lambda] = {2,1,[bar.1]} we have [epsilon]((3,1)) = (2,1,1), [epsilon]((2,1,1)) = (2,1,1) and [epsilon]((1, 2,1)) = (1, 2,1). Also note [epsilon]([??]) [less than or equal to] [??] in the partial order of compositions.

Similar to Theorem 3.2 we have the following topological conclusion. However, this time the tool is not shelling, but discrete Morse theory.

Theorem 7.2 There is a Morse matching on the simplicial complex [[LAMBDA].sub.{[lambda],[m.bar]}] such that the only critical cells are of the form [sigma]([alpha], [epsilon]([??])) where [??] ranges in the set V([lambda], [m.bar]) and [alpha] ranges over all permutations in the symmetric group [G.sub.n] with descent composition [??]. Hence, the simplicial complex [[LAMBDA].sub.{[lambda],m}] is homotopy equivalent to wedge of [[summation].sub.[??][member of]V([lambda],[m.bar])] [beta]([??]) spheres of dimension k - 1.

Example 7.3 Consider the pointed knapsack partition {[lambda], [m.bar]} = {2,1,[1.bar]}, whose associated complex [[LAMBDA].sub.{2,1,[1.bar]}] is shown in Figure 2. Note that V([lambda],[m.bar]) = {(1,2,1), (2,1,1), (3,1)}. The critical cells of the complex [[LAMBDA].sub.{2,1,[1.bar]}] are as follows:
          [beta]  [epsilon]
[??]      ([??])   ([??])    critical cells

(1, 2,1)    5     (1, 2,1)   2-14-3, 3-14-2, 3-24-1, 4-13-2, 4-23-1
(2,1,1)     3      (2,1,1)   14-3-2, 24-3-1, 34-2-1
(3,1)       3      (2,1,1)   12-4-3, 13-4-2, 23-4-1


Note that [[LAMBDA].sub.{2,1,[1.bar]}] is homotopy equivalent to a wedge of 11 circles.

Now by the same reasoning as in Section 4, that is, using the forgetful map [phi] and Quillen's fiber lemma, we obtain the homotopy equivalence between the order complex of pointed partitions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the simplicial complex of ordered set partitions [[LAMBDA].sub.{[lambda],[m.bar]}].

Theorem 7.4 The order complex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is homotopy equivalent to the barycentric subdivision sd([[LAMBDA].sub.{[lambda],[m.bar]}]) and hence the simplicial complex [[LAMBDA].sub.{[lambda],m}].

As a corollary we obtain the Mobius function of the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; see [4].

Corollary 7.5 (Ehrenborg-Readdy) The Mobius function of the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By the same reasoning as Sections 5 and 6, we have the following isomorphism.

Theorem 7.6 The two homology groups [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [[??].sub.k-1] ([[LAMBDA].sub.{[lambda],[m.bar]}]) are isomorphic as [G.sub.n]-modules. Furthermore, they are isomorphic to the direct sum of Specht modules

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

8 Concluding remarks

We have not dealt with the question whether the poset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is EL- shellable. Recall that Wachs proved that the d-divisible partition lattice [[PI].sup.d.sub.n] [union] {[??]} has an EL-labeling. Ehrenborg and Readdy gave an extension of this labeling to prove that [[PI].sup.[??].sub.(d, ..., d, m)] is EL-shellable [5]. Furthermore, Woodroofe [20] showed that the order complex [DELTA]([[PI].sup.d.sub.n] - {[??]}) has a convex ear decomposition. This is not true in general for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Can these techniques be used for studying other subposets of the partition lattice? One such subposet is the odd partition lattice, that is, the collection of all partition where each block size is odd. More generally, what can be said about the case when all the block sizes are congruent to r modulo d? These posets have been studied in [3] and [18]. Moreover, what can be said about the poset [[PI].sup.[??].sub.{[lambda], [m.bar]}] when {[lambda], [m.bar]} is not a pointed knapsack partition?

Another analogue of the partition lattice is the Dowling lattice. Subposets of the Dowling lattice have been studied in [5] and [8, 9]. Here the first question to ask is what is the right analogue of the ordered set partitions.

Acknowledgements

The authors thank Serge Ochanine for many helpful discussions and Margaret Readdy for her comments on an earlier draft of this paper.

References

[1] A. BJORNER, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), 159-183.

[2] A. BJORNER, Topological methods in Handbook of combinatorics, Vol. 1, 2, 1819-1872, Elsevier, Amsterdam, 1995.

[3] A. R. CALDERBANK, P. HANLON AND R. W. ROBINSON, Partitions into even and odd block size and some unusual characters of the symmetric groups, Proc. London Math. Soc. (3) 53 (1986), 288-320.

[4] R. EHRENBORG AND M. READDY, The Mobius function of partitions with restricted block sizes, Adv. in Appl. Math. 39 (2007), 283-292.

[5] R. EHRENBORG AND M. READDY, Exponential Dowling structures, European J. Combin. 30 (2009), 311-326.

[6] R. FORMAN, Morse theory for cell complexes, Adv. Math. 134 (1998), 90-145.

[7] R. FORMAN, A user's guide to discrete Morse theory, Sem. Lothar. Combin. 48 (2002), Article B48c.

[8] E. GOTTLIEB, On the homology of the h, k-equal Dowling lattice, SIAMJ. Discrete Math. 17 (2003), 50-71.

[9] E. GOTTLIEB AND M. L. WACHS, Cohomology of Dowling lattices and Lie (super)algebras, Adv. Appl. Math. 24 (2000), 301-336.

[10] D. KOZLOV, "Combinatorial Algebraic Topology," Springer, 2008.

[11] D. QUILLEN, Homotopy properties of the poset of nontrivial p-subgroups of a group, Adv. Math. 28 (1978), 101-128.

[12] B. E. SAGAN, "The Symmetric Group, Second Edition," Springer, 2000.

[13] R. P. STANLEY, Exponential structures, Stud. Appl. Math. 59 (1978), 73-82.

[14] R. P. STANLEY, "Enumerative Combinatorics, Vol. I," Wadsworth and Brooks/Cole, Pacific Grove, 1986.

[15] R. P. STANLEY, "Enumerative Combinatorics, Vol. II," Cambridge University Press, 1999.

[16] G. S. SYLVESTER, "Continuous-Spin Ising Ferromagnets," Doctoral dissertation, Massachusetts Institute of Technology, 1976.

[17] M. L. WACHS, A basis for the homology of the d-divisible partition lattice, Adv. Math. 117 (1996), 294-318.

[18] M. L. WACHS, Whitney homology of semipure shellable posets, J. Algebraic Combin. 9 (1999), 173-207.

[19] J. W. WALKER, Homotopy type and Euler characteristic of partially ordered sets, European J. Combin. 2 (1981), 373-384.

[20] R. WOODROOFE, Cubical convex ear decompositions, Electron. J. Combin. 16 (2009), 33 pp.

Richard Ehrenborg (1) ([dagger]) and JiYoon Jung (1)

(1) Department of Mathematics, University of Kentucky, Lexington, KY, USA

([dagger]) Both authors are partially supported by National Science Foundation grants 0902063.
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Ehrenborg, Richard; Jung, JiYoon
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2011
Words:6013
Previous Article:Critical groups of simplicial complexes.
Next Article:Allowed patterns of [beta]-shifts.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters