# The q = -1 phenomenon for bounded (plane) partitions via homology concentration.

1 Introduction

There is a rich history surrounding the enumeration of partitions in a rectangle or higher dimensional box, as well as the enumeration of classes of partitions possessing various symmetries (see e.g. (1), (10)). One reason for so much interest comes from connections to physics, while another is the important role they play in representation theory, specifically in the theory of canonical bases (see e.g. (11) and (12)). Richard Stanley used the Littlewood-Richardson rule in (10) to prove a recursive formula for the number of complementary plane partitions of bounded value. John Stembridge proved that semistandard domino tableaux are counted by this same formula, by showing that their enumeration formula satisfies the same recurrence. This proved that the set of fixed points in a fundamental involution of Lusztig on a type A canonical basis also has this same cardinality, by virtue of a bijection due to Berenstein and Zelevinsky between the elements of a canonical basis and semistandard Young tableaux (actually Gelfand-Tsetlin patterns) such that this bijection sends Lusztig's involution to evacuation. Stembridge examined this connection between self-complementary partitions and canonical bases more closely, unveiling in the process a phenomenon he dubbed the "q = -1 phenomenon".

In (12), Stembridge defines the q = -1 phenomenon as the following situation. One has a set of combinatorial objects B (such as tableaux), together with a generating function X(q) that enumerates the objects in B according to some weight depending on q. The q = -1 phenomenon occurs when there is a "natural" involution on B such that X (-1) is the number of fixed points of the involution. Stembridge established various instances of this phenomenon by interpreting X (-1) as the trace of a matrix which is conjugate to a permutation matrix for the involution.

It is natural to ask if the q = - 1 phenomenon can be explained by an Euler characteristic computation. To this end, we define a complex whose ranks of chain groups are the coefficients in the polynomial X (q) so that its Euler characteristic is X( - 1). On the other hand, the Euler characteristic is the alternating sum of ranks of homology groups, so whenever homology is concentrated in even dimensions with homology basis indexed by the fixed points of the involution, this would imply the phenomenon. Moreover, the homology generating function then offers a natural q-analogue of the integer which is the Euler characteristic. We carry out this plan in two quite central cases: the partitions in a rectangle and the plane partitions of bounded value in a rectangle, i.e., the partitions in a three dimensional box.

In [section]2 we associate to any action of a finite group G regarded as a subgroup of Sn four algebraic complexes over a field with 2 elements, and prove in Proposition 2.3 that their Euler characteristic is the number of fixed points of the complementation involution in the action of G on the subsets of [n]. The aforementioned case of partitions in a rectangle arises as the special case where G is a wreath product of symmetric groups. We prove acyclicity of these complexes for any G in which n is odd and also somewhat more generally. In [section]3 we give an algebraic Morse matching lemma, which is then applied in [section]4 and [section]5 to partitions in a rectangle and in a three dimensional box, respectively, establishing homology concentration in even dimensions and explicit homology bases. The results in [section]4 and [section]5 may be regarded as sign- reversing involutions with some extra topological structure. In [section]6, we conclude with an example showing that not all G give rise to complexes with homology concentrated in even dimensions, namely Example 6.1, and finally we propose in Conjecture 6.5 that homology concentration in even ranks nonetheless does hold for necklaces, i.e. the case where G is a cyclic group.

The authors are grateful to Vic Reiner for his numerous helpful suggestions.

2 The algebraic complexes

In this section we define the algebraic complexes, which are quotient complexes of the Boolean algebra over a field of two elements. The boundary map is closely related to the down operator introduced in (9). Let G be a subgroup of [[??].sub.n], so G acts on [n] := {1,2, ..., n}. Then G also permutes the elements of the Boolean algebra 2[n of all subsets of [n], and permutes the subsets ([n]) of a given cardinality i. Consider the following generating function that counts such G-orbits according to their cardinality, letting S be an element in the orbit [bar.S], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It has been well-studied historically via algebraic means, perhaps starting with Redfield and Polya.

Theorem 2.1 ((9; 5)) The polynomial X (G, q) has symmetric, unimodal coefficients.

The idea is to show that the coefficients in X (G, q) are the ranks of the weight spaces in a representation of [sl.sub.2] (C) by showing that the three operators D, U, DU - UD satisfy the appropriate relations.

See (6, Corollary 6.2) for the next result, which is due to de Bruijn.

Theorem 2.2 (de Bruijn) X(G, -1) is the number of G-orbits [bar.S] of subsets of [n] which are self-complementary in the sense that [bar.S] = [bar.[n]\S].

This was proven by finding two conjugate matrices, one having X(G, -1) as its trace and the other of which is a permutation matrix acting on the G-orbits of subsets of [n] by complementation. As an example, if G = ((12), (34)}, then S = {{1, 3}, {2,4}} is a self-complementary orbit. Theorem 2.2 may be applied to our first main example, namely the case of partitions in a rectangle, but does not seem to apply to our second example of plane partitions of bounded value in a rectangle.

One algebraic approach introduces, for any field F, the graded vector space C(F) := [[direct sum].sup.n.sub.i=0] [C.sub.i](F) in which [C.sub.i](F) has an F-basis [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is useful to identify C [congruent to] [V.sup.[cross product]n], where V [congruent to] [F.sub.2] has F-basis {[e.sub.0], [e.sub.1]}. Under this identification, the F-basis element [e.sub.s] in C(F) corresponds to the decomposable tensor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in which [i.sub.j] = 1 for [i.sub.j] [member of] S and [i.sub.j] = 0 otherwise.

Define the up and down maps U, D : C(F) [right arrow] C(F) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that U, D both commute with the G-action. As a consequence, they give well-defined maps on the graded vector spaces of G-invariants C(F)G and G-coinvariants. (i) C(F)G. Note that both C[(F).sup.G], C[(F).sub.G] will have F-bases indexed by G-orbits S of subsets of [n]: for C(F)G, a typical basis element es is a sum of [e.sub.S] as S varies over the elements of the orbit, while for C(F)G, a typical basis element is the image [[bar.e].sub.S] of [e.sub.S] in the quotient for any S [member of] [bar.S].

We let F = [F.sub.2] henceforth, in order to obtain a complex.

Proposition 2.3 The map D induced on C[([F.sub.2]).sup.G] or on C[([F.sub.2]).sub.G] make them algebraic chain complexes of [U.sup.2]-vector spaces, i.e., [D.sup.2] = 0 in each case. Likewise the map U makes them into cochain complexes, i.e., [U.sup.2] = 0.

Each of these four complexes has Euler characteristic, i.e. alternating sum of the ranks of its chain groups, equalling X(-1), or in other words the number of self-complementary G-orbits. In particular, each Euler characteristic is nonnegative.

Proof: Working over [F.sub.2], these maps D, U on C([F.sub.2]) coincide with the boundary and coboundary maps [[partial derivative].sub.i] and [[partial derivative].sub.i] in the usual simplicial chain complex for a simplex having vertex set [n]. Hence [D.sup.2] = [U.sup.2] = 0, and the same holds after taking G-invariants or G-coinvariants.

For the second assertion, note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

and now apply Theorem 2.2.

Given a G-orbit [bar.S], let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the basis element of [C.sup.G](F) corresponding to [bar.S]; let [[bar.e].sub.S] denote the basis element of C[(F).sub.G] corresponding to S

Proposition 2.4 The map sending [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] induces isomorphisms ofcochain complexes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

The map sending [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] induces isomorphisms of chain complexes

(C[([F.sub.2]).sup.G],D) [congruent to] [(C[([F.sub.2]).sup.G],U).sup.op]

(C[([F.sub.2]).sup.G],D) [congruent to] [C[([F.sub.2]).sub.G],U).sup.op],

where here [C.sub.op] for a cochain complex C denotes the opposite chain complex that one obtains by reindexing in the opposite order and reversing all the arrows.

Proof: Let [bar.S], [bar.T] be G-orbits of subsets with [absolute value of T] = [absolute value of S] + 1. Then the boundary map coefficient [D.sub.[bar.S],[bar.T]] in C[([F.sub.2]).sup.G] is the number of elements T' in the orbit T which contain the fixed set S in [bar.S]. Meanwhile the boundary coefficient [D.sub.[bar.S],[bar.T]] in C[([F.sub.2]).sub.G] is the number of elements S' in the orbit S which are contained in the fixed set T in [bar.T]. There are similar formulae for the coefficients [U.sub.[bar.S],[bar.T]] in the two complexes. The isomorphisms are not hard to verify, using the fact that set-complementation is an inclusion-reversing bijection.

In light of the previous proposition, one may consider any one of the four complexes, as its homology determines the homology of the others (either by turning it around in homological degree, or by taking dual [F.sub.2]-vector spaces, or both).

Proposition 2.5 The complex ([C.sub.G], D) is acyclic when n is odd. More generally, it is acyclic whenever G has at least one orbit in its action on [n] of odd cardinality. Whenever ([C.sup.G], D) is not acyclic, it must have [H.sub.0] = [F.sub.2] and [H.sub.1] = 0.

Proof: Let S [subset] [n] be G-stable (although not necessarily pointwise fixed by G). Then one forms S-masked versions of the up and down maps in C as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The G-stability of S implies that these S-masked up and down maps commute with the G-action: the crucial point in all these calculations is that g(S) = S, so that, for example,

S\g(T) = g(S\T)

S [intersection] g(T) = g(S [intersection] T),

Hence one gets induced S-masked up and down maps [U.sup.(S)], [D.sup.(S)] on the G-invariant and G-coinvariant complexes also.

An easy calculation, generalizing the commutator calculation DU - UD = (n - 2i)I on [C.sub.i] is the following:

(D x [U.sup.(S)] - [U.sup.(S)] x D)([e.sub.T]) = ([absolute value of S\T] - [bar.S [intersection] T]) x [e.sub.T] = ([absolute value of S] - 2[absolute value of S [intersection] T]) x [e.sub.T].

When working with [F.sub.2] coefficients, as in C([F.sub.2]), C[([F.sub.2]).sub.G], C[([F.sub.2]).sub.G], this gives

D x [U.sup.(S)] + [U.sup.(S)] x D) = [absolute value of S] x I.

Thus when [absolute value of S] is odd, the S-masked up map [U.sup.(S)] gives an algebraic chain-contraction, showing that the complex with D as boundary map is acyclic. We now analyze the consequences of this for the first few boundary maps in (C[([F.sub.2]).sup.G], D).

The boundary map D out of [C.sub.0][([F.sub.2]).sup.G] = [F.sub.2] is always the zero map, regardless of G. If all G- orbits have even cardinality, the boundary map D out of [C.sub.1][([F.sub.2]).sup.G] will also be the zero map, so the assertion about [H.sub.0] follows.

It remains to show that when all G-orbits have even cardinality, the map D out of [C.sub.2][([F.sub.2]).sup.G] is surjective. But for this we can work within each G-orbit X on [n]. That is, it suffices to show that there is some G-orbit Y = [bar.{i, j}] of pairs with i, j [member of] X for which D([e.sub.Y]) has coefficient 1 on [e.sub.X], not zero. However, fixing X, one can see that the sum of all of such boundary map coefficients incident to X and coming from G-orbits of pairs contained in X will be [absolute value of X] - 1, an odd number. Thus one of them must be non-zero in [F.sub.2], as desired.

Remark 2.6 Examples like G = ((123)(456)} in [[??].sub.6], where G has orbits on [n] of odd size but n is even and G is not a product [G.sub.1] x [G.sub.2] show that the Kunneth formula doesn't suffice to prove the previous proposition (or at least it's not obvious how to deduce it from Kunneth).

In light of Proposition 2.3 and the calculations of [H.sub.0], [H.sub.1] in Proposition 2.5, one might be tempted to make the conjecture (true up through n = 5) that the homology is always concentrated in even dimension. However, Section 6 gives a counterexample to this. Section 4 does confirm this behavior for wreath products of symmetric groups, and we conjecture it for cyclic groups in Section 6 as well.

3 An algebraic Morse matching lemma

In this section we give a general result, Lemma 3.2, on matchings in partially ordered sets, called Morse matchings. If the complex of [section]2 is supported by a partially ordered set, and the Morse matching is good enough, in a sense that will be made precise, it may be used to give a homology basis and prove homology concentration in even dimensions for the complex. In this case the basis is indexed by fixed points of the Morse matching, which must be equinumerous with X(G, -1).

Definition 3.1 Say that a graded poset P = [[??].sup.n.sub.i=0] [P.sub.i] supports an algebraic complex (C, d) of F- vector spaces if [C.sub.i] has an F-basis {[e.sub.p]} indexed by p [member of] [P.sub.i], and the differential [d.sub.i] has [([d.sub.i]).sub.p,q] = 0 unless q < P p.

As usual, say that a partial matching M of the Hasse diagram of a poset P is an acyclic matching, or Morse matching, if the digraph D, obtained by starting with the Hasse diagram directed downward and then reversing all the directions of the edges in M, is acyclic.

Given an acyclic matching M on P, let the subsets

[P.sup.M], [p.sup.unM], [P.sup.M.sub.i], [p.sup.unM.sub.i]

respectively denote the M-matched and M-unmatched elements in P, and the same sets restricted to rank i. The elements of [P.sup.unM] are called critical elements. Let q = M (p) denote that q is matched by M to p. Let [<.sub.D] be the partial order on P that results from taking the transitive closure of D.

Lemma 3.2 Let P be a graded poset supporting an algebraic complex (C d) and assume P has a Morse matching M such that for all q = M(p) with q < p, one has [d.sub.p,q] [member of] [F.sub.x]. Let [Q.sub.i] be the set of poset elements of rank i which are matched with elements of rank i - 1. Then

(i) dim [H.sub.i](C,d) [less than or equal to] [absolute value of [P.sup.unM.sub.i].

(ii) if [absolute value of [Q.sub.i]] = rank([d.sub.i]) for every i, then dim [H.sub.i] = [P.sup.unM.sub.i]. (For example, this condition is met whenever all unmatched poset elements live in ranks of the same parity.)

(iii) if [d.sub.q,p] = [d.sub.p,r] = 0 for all p [member of] [P.sup.unM] and all q, r [member of] P, then the homology H(C, d) has F-basis {[e.sub.p] : p [member of] [P.sup.unM]}.

Proof: To prove (i), we want to show that the boundary maps di have sufficiently large ranks, which we'll do by showing that they have some large, nonsingular square submatrices. We make the following claim: consider the subset [Q.sub.i] of [P.sup.M.sub.i] consisting of those elements matched below them into [P.sup.M.sub.i- 1]. Then ordering [Q.sub.i] as [q.sub.1], ..., [q.sub.r] by any linear extension of the partial order [<.sub.D], the square submatrix of [d.sub.i] having columns indexed [q.sub.1], ..., [q.sub.r] and rows indexed M([q.sub.1]), ..., M([q.sub.r]) will be invertible upper- triangular.

To prove the claim, note that the hypothesis [d.sub.p,q] [member of] [F.sup.x] for q < p implies that the diagonal entries of this square matrix are all in [F.sup.x], since q = M(p) implies q < p or p < q. Hence one only needs to verify upper-triangularity. So assume that the boundary map [d.sub.i] has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some k [not equal to] j. Since the complex C was supported on P, this implies that [q.sub.j] [>.sub.P] M([q.sub.k]) and hence D has an edge directed [q.sub.j] [right arrow] M ([q.sub.k]). There is also the matching edge in D, directed upward as M ([q.sub.k]) [right arrow] [q.sub.k], and thus by transitivity, [q.sub.j] [<.sub.D] [q.sub.k]. Hence j < k, yielding the claim.

The claim implies that rank([d.sub.i]) [greater than or equal to] [absolute value of [Q.sub.i]] for all i. As usual letting [Z.sub.i] = ker [d.sub.i] and [B.sub.i] = [imd.sub.i+1], note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as desired.

Now the hypothesis in (ii) makes the weak inequality into an equality in the above string of equalities and weak inequalities, implying the desired equality in (ii). To prove (iii), note that the hypothesis [d.sub.p,r] = 0 for all r < p ensures that {[e.sub.p]|p [member of] [P.sup.unM.sub.i]} spans a subspace of [H.sub.i](C, d) for each i, while [d.sub.q,p] = 0 for all q > p implies linear independence of the set. Since [absolute value of P.sup.unM.sub.i] [greater than or equal to] dim [H.sub.i](C, d), this set also must span [H.sub.i](C,d), hence is a homology basis. []

Lemma 3.2 is closely related to results of Jollenbeck-Welker, of Skoldberg, and of Kozlov (see (3), (8), and (4)) developing algebraic versions of discrete Morse theory.

4 Application to partitions in a rectangle

Consider the subgroup G = [[??].sub.l] [??] I [G.sub.k] inside [[??].sub.kl], acting on the cells of a rectangle with k rows and l columns, by permuting arbitrarily within each row, but also allowing wholesale swaps of one row for another. In this section, we will show how all three parts of Lemma 3.2 apply to the complex (C[([F.sub.2]).sub.G], D) for G = [[??].sub.l] [??] [[??].sub.k], yielding homology concentration in even dimensions. The G-orbits are indexed by partitions [lambda] = ([[lambda].sub.1], ..., [[lambda].sub.k]) with

l [greater than or equal to] [[lambda].sub.1] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.k] [greater than or equal to] 0.

The number [[lambda].sub.i] indicates the number of boxes in row i not belonging to the set S serving as orbit representative. Thus, the complex C[([F.sub.2]).sub.G] is supported on the Gaussian poset P(k, l) of all such [lambda] ordered by reverse inclusion of their Ferrers diagrams. One may check directly that the entries in the boundary maps d take the following form: if [mu] is obtained from [lambda] by reducing the part [[lambda].sub.i] to [[lambda].sub.i] - 1, then

[d.sub.[lambda],[mu]] = (l - [[lambda].sub.i] + 1)([mult.sub.[lambda]]([[lambda].sub.i-1]) + 1) (1)

where [mult.sub.[lambda]](s) is the multiplicity of the part s in [lambda] and [mu] covers [lambda] in the poset supporting the complex. In fact, d is derived from the down operator D which acts on faces of a simplex, by using the fact that D commutes with the group action. D deletes a box from the orbit representative S in all possible ways, each of which has the impact of lengthening some part of A by one.

Here is the matching M we will use. Given a partition [lambda], find the smallest part [[lambda].sub.i] which is either

* non-zero and of the same parity as I, in which case you should subtract 1 from it in order to obtain M([lambda]), or

* possibly zero and of opposite parity to I, but with odd multiplicity, in which case you should add 1 to it in order to obtain M(A).

It is not hard to check that this is indeed a well-defined matching.

Remark 4.1 The unmatched partitions also correspond to the lattice paths in a k x l rectangle delineating the shape [lambda], specifically those lattice paths from (l, k) to (0,0) comprised of steps (-2,0) and (0, -2) until either (i, 0) or (i, 1) is reached, after which there is a step (0, -1) in the latter case.

To see that these are equinumerous with self-complementary partitions in a k x l rectangle, notice that there is a bijection sending an unmatched path to a path fixed under 180 degree rotation by replacing each step of length 2 with a step in the same direction of length 1 to obtain the first half of the path with 180 degree rotational symmetry.

Theorem 4.2 The above matching on the Gaussian poset P (k, l) is acyclic, with the partitions [lambda] in [P.sup.unM] being those described in Remark 4.1. Moreover, the homology is concentrated in even dimensions.

Proof: It is easy to verify hypotheses (i), (ii), and (iii) of Lemma 3.2 and the description of [P.sub.unM] directly from these descriptions and (1). Let us check acyclicity of M. Suppose one had a directed cycle C. If [[lambda].sub.i] is the smallest even value ever incremented in C, then there must be some downward step in C decrementing the value [[lambda].sub.i] + 1. However, since no smaller values ever change, this downward step is across a matching edge, a contradiction.

Question 4.3 Is there some connection between the Poincare series for the homology here and T. Eisenkolbl's recent (-1)-enumerations of self-complementary plane partitions which appears in (2)? In particular, what happens in her situation when the k x l x m box in which the plane partitions live has m = 1?

5 Application to plane partitions of bounded value in a rectangle

In this section, we construct a mod 2 complex (C(c, r,t), d) whose i-dimensional cells are indexed by plane partitions of volume i in a c x r x t box. We prove homology concentration in Theorem 5.6 and also give a homology basis. Since we are not aware of a way to regard partitions in a c x r x t box as orbits of a group action permuting cells, we devised a different, though related construction.

It will be more convenient to use another indexing set of equal cardinality, namely the semistandard Young tableaux (SSYT) of shape [lambda] = [(c).sub.r] in which all entries have value between 0 and r + t - 1. The bijection comes from taking a Young tableaux filling with entries that weakly increase in rows and columns to a column strict one by adding i - 1 to each entry in row i.

We now define the complex (C(c, r, t), d), with coefficients taken mod 2, by letting the chain group generators be the SSYT of c x r rectangular shape with entries between 0 and t + r - 1. Let us call an odd value 2i + 1 in row R decrementable if it does not have the value 2i immediately above it in row R - 1. Define the boundary map d as follows. For T an SSYT, dT is a sum over SSYT obtained by subtracting one from the leftmost copy in some row R some odd value 2k + 1 having the following property: there are an odd number of decrementable copies of 2k + 1 in row R. In other words,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for d(T) the set of SSYT obtained by deleting one from a decrementable odd entry [[lambda].sub.i] of T located at position (i, j). One may verify:

Proposition 5.1 (C(c, r, t), d) is a chain complex, i.e., [d.sub.2] = 0.

Next we give an acyclic matching M on the set of such SSYT. M will have the property that for each pair S, T of matched tableaux with [absolute value S] < [absolute value of T], S appears with nonzero coefficient in dT.

Matching M: Let T be a SSYT satisfying our requirements on its entries. Consider the earliest row R in T having at least one of the following items:

1. an odd value i such that there are an odd number of decrementable copies of i in row R

2. an even value i in row R not having the value i + 1 immediately below it such that the number of decrementable copies of i + 1 in row R is even (possibly zero)

Match T to M(T) by choosing the smallest value i in the chosen row R meeting one of these conditions; now subtract one from the leftmost such copy of i in row R if i is odd, or add one to the rightmost such copy of i in row R if i is even.

Proposition 5.2 M is a matching and is acyclic, hence a Morse matching.

The proof is quite similar to the one discussed in the last section. One may also check that M meets the requirements of Lemma 3.2. Now we describe PunM.

Lemma 5.3 In any element of [P.sup.unM], every even value 2i with 2i < t + r - 1 has the odd value 2i + 1 just below it. For each odd value 2i + 1 with 2i +1 < t + r - 1, the number of decrementable copies of 2i + 1 in a given row is even.

Proof: Start with the top row, and proceed downward from row R to row R + 1 by induction as follows. In row 1, notice that each odd value 2i + 1 must occur with even multiplicity, since otherwise we could match by decrementing by one the leftmost copy of 2i +1. Thus, each even value 2i in row 1 will have an even number of copies (possibly 0) of 2i + 1 just to its right; therefore we could match by increasing the rightmost copy of 2i to 2i + 1 unless there were a 2i + 1 just below it. Since our fillings are semistandard, this implies we must have 2i + 1 just below all the other copies of 2i in that row, putting each 2i in row one in a vertical domino and each 2i + 1 in a horizontal domino.

The same argument works at row R + 1 once the claim has been proven through row R: we may have some odd values in row R + 1 which already belong to dominoes shared with row R, but all remaining spots to be filled in row R +1 will have odd values just above them. This ensures that each odd value 2i + 1 in row R + 1 must occur with even multiplicity (not counting those in dominoes shared with row R) to avoid matching by decrementing 2i +1. And again any even value 2i in row R +1 will have an even number of decrementable copies of 2i + 1 to its right, allowing matching by incrementing the rightmost 2i unless either it has a copy of 2i + 1 just below it or it is the absolute largest allowable value. []

Corollary 5.4 The first row has even sum. If row lengths are odd, then row sums alternate in parity. Otherwise, all row sums have even parity. Therefore the critical cells are concentrated in dimensions all of the same parity.

Proposition 5.5 The elements of [P.sub.unM] are all in ranks of the same parity. They are also in bijection with the semistandard domino tableaux of c x r rectangular shape comprised of odd values between 0 and t + r - 1.

The idea is to show that our description of [P.sub.unM] amounts to saying the shapes are tiled by two types of dominos: (1) horizontal dominos in which both entries of the domino have odd value 2i + 1, and (2) vertical dominos in which the top entry is 2i and the bottom entry is 2i + 1, along with perhaps some monominoes in the bottom row of maximal allowed value.

Theorem 5.6 The complex (C(c,r,t),d). has homology concentration in ranks all of the same parity. Moreover, a basis is given by Lemma 5.3.

Now we will use the following result from (12):

Theorem 5.7 (Stembridge, Theorem 3.1) The following quantities are equal.

* (a) The number of self-evacuating tableaux in [S.sub.[lambda]]

* (b) [(-1).sup.k([lambda])][s.sub.[lambda]][s.sub.[lambda]]([(-1).sup.0], [(-1).sup.1], [(-1).sup.2], ..., [(- 1).sup.(n-1)] for k([lambda]) = [[lambda].sub.2] + [[lambda].sub.4] + ...

Moreover, if n is even, or more generally if we allow monominos of maximal value in a domino tableau, then these quantities also equal

* (c) The number of semistandard domino tableaux with entries [less than or equal to] n/2 and shape [lambda]

Since the map sending a plane partition in a rectangle to a SSYT by adding i - 1 to each entry of row i has the effect of sending the self-complementary partitions exactly to the self-evacuating tableaux of the same rectangular shape, we may use Stembridge's result to deduce that our homology basis has the same cardinality as the self-complementary plane partitions with entries of value at most t.

Our matching, together with a straightforward verification that quantity (b) has positive sign, also gives a combinatorial proof that (b) equals (c) by a sign-reversing involution on the SSYT counted by (b) which has as its fixed points a set that is in trivial bijection with the objects counted by (c).

6 A counterexample and a conjecture

Example 6.1 Embed G = PSL2(F5) in S6 via its action on the 6 points of the projective line over F5. To be explicit, one can start with these generators for SL2 (F5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and then if one numbers the points of the projective line over [F.sub.5] as 1, 2, 3, 4, 5, 6 according their slopes 0, 1, 2, 3, 4, [infinite], the images of a, b, c in [PSL.sub.2] (F5) permute [6] as follows:

a = (16)(34)

b = (25)(34)

c = (12345).

One can check that this subgroup G = (a, b, c) of [[??].sub.6] acts transitively on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i = 0,1,2,4,5, 6, and has these two orbits on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

{123, 234, 345,145,125,136, 246, 356,146, 256}, {124, 235,134, 245,135,126, 236, 346, 456,156}.

An easy computation then shows that C (F2)G has H0 = H3 = F2 and no other nonvanishing homology groups.

Proposition 6.2 G [less than or equal to] [[??].sub.n] has a self-complementary orbit if and only if a Sylow 2-subgroup of G contains a derangement.

Proof: Note first that a Sylow 2-subgroup of G contains a derangement if and only if some element of g contains no cycle of odd length in its cycle decomposition. Indeed, a derangement of 2-power order is such an element, while if g has no cycle of odd length and order [2.sup.k]d with d odd then [g.sup.d] is a derangement of order [2.sup.k]. Now if g has no cycle of odd length then it is easy to construct S [subset] [n] with Sg = [n] \ S. On the other hand, say Sg = [n] \ S and (i1... ik) is a cycle in g. We may assume that [i.sub.1] [member of] S. Then [i.sub.j] [member of] S if and only if j is odd, and since [i.sub.kg] = [i.sub.1], we must have [i.sub.k] [not member of] S, so k is even. []

Corollary 6.3 If G is a transitive subgroup of [[??].sub.n] with n even, and G contains no derangement in a Sylow 2-subgroup, then the homology of C[([F.sub.2]).sub.G] is not concentrated in even dimensions.

Proof: By Theorem 2.2 and Proposition 6.2, the Euler characteristic of C[([F.sub.2]).sup.G] is zero. On the other hand, by Proposition 2.5, we have H0 (C[([F.sub.2]).sub.G]) = 0. ?

Although the homology of our mod 2 complexes is not always concentrated in even dimensions, we are still interested in interesting families of groups G for which this concentration does occur. In this situation, the Poincare polynomial for the homology of, say C[([F.sub.2]).sub.G], can be interpreted as giving a grading on the set of self-complementary G-orbits.

We conclude with evidence that this holds for G a cyclic group [C.sub.n] generated by an n-cycle in Sn. In this case the orbits are necklaces, as in (7). Here are homology calculations from Mathematica on [C.sub.n] for n even; the case of n odd already follows from Proposition 2.5.

The following calculation of X([C.sub.n], q), X([C.sub.n], -1) may be done using Polya-Redfield theory or Burnside's lemma.

Proposition 6.4 For n > 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the above homology data suggests that

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i odd, and for i = 2n - 1, 2n, and

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But one can be much more precise. Note that using the formula in Proposition 6.4 for X([C.sub.n], -1), one can easily check that it satisfies the recursion

X ([C.sub.2n], -1) = X([C.sub.n], -1) + X([C.sub.n], 1)/2

This recursion may be modified to a recursion predicting the homology Poincare series. For notational convenience, define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Conjecture 6.5 For any positive integer n, one has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if i is odd, so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a polynomial in [q.sup.2], and one has the recursion

[A.sub.2n]([q.sup.1/2]) = q[A.sub.n](q)+ [X.sub.n](q)/1 + q

Conjecture 6.5 has some strong evidence. It is correct at q = 1. It holds through n = 18, as shown earlier. We have proven it for n odd, although we do not include a proof here. In addition, it is correct with regard to its prediction about [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

received 12 Nov 2008

References

[1] M. Ciucu, The equivalence between enumerating cyclically symmetric, self-complementary and totally symmetric self-complementary plane partitions, J. Comb. Theory, Ser. A 86 (1999), no. 2, 382-389.

[2] T. Eisenkoelbl, (-1)-enumeration of self-complementary plane partitions, Electronic J. Combinatorics, 12(1), (2005), #R7, 22 pages.

[3] M. Jollenbeck, and V. Welker, Resolution of the residue field via algebraic discrete Morse theory, To appear in Mem. Amer. Math. Soc.

[4] D. Kozlov, Discrete Morse theory for free chain complexes, C. R. Math. Acad. Sci. Paris, 340 (2005), no. 12, 867-872.

[5] R. Proctor, Representations of sl(2, C) on posets and the Sperner property, SIAM J. Algebraic Discrete Methods, 3 275-280.

[6] V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), 17-50.

[7] C. Reutenauer, Free Lie Algebras, London Mathematical Society Monographs. New Series, 7. Oxford Science Publications. The Clarendon Press. Oxford University Press, New York, 1993. xviii + 269 pp.

[8] E. Skoldberg, Morse theory from an algebraic viewpoint, Trans. Amer. Math. Soc., 358 (2006), no. 1, 115-129.

[9] R. P. Stanley, Some aspects of groups acting on finite posets, J. Comb. Theory, Ser. A, 32 (1982), no. 2, 132-161.

[10] R. P. Stanley, Symmetries of plane partitions, J. Comb. Theory, Ser. A, 43 (1986), no. 1, 103-113.

[11] J. Stembridge, On miniscule representations, plane partitions and involutions in complex Lie groups, Duke Mathematical Journal 73 (1996), no. 2, 469-490.

[12] J. Stembridge, Canonical bases and self-evacuating tableaux, Duke Mathematical Journal 82 (1996), no. 3, 585-606.

P. Hersh 1, ([dagger]) J. Shareshian (2) ([double dagger]) and D. Stanton (3) ([section])

(1) North Carolina State University and Indiana University (2) Washington University in St. Louis (3) University of Minnesota

([dagger]) Supported by NSF grants DMS-0500638 and DMS-0757935.

([double dagger]) Supported by NSF grant DMS-0604233.

([section]) Supported by NSF grant DMS-0503660.

(i) Recall that the coinvariant space [U.sub.G] for an F-vector space U with a linear G-action is the quotient space U/F{u - g(u) : u [member of] U, g [member of] G}.

There is a rich history surrounding the enumeration of partitions in a rectangle or higher dimensional box, as well as the enumeration of classes of partitions possessing various symmetries (see e.g. (1), (10)). One reason for so much interest comes from connections to physics, while another is the important role they play in representation theory, specifically in the theory of canonical bases (see e.g. (11) and (12)). Richard Stanley used the Littlewood-Richardson rule in (10) to prove a recursive formula for the number of complementary plane partitions of bounded value. John Stembridge proved that semistandard domino tableaux are counted by this same formula, by showing that their enumeration formula satisfies the same recurrence. This proved that the set of fixed points in a fundamental involution of Lusztig on a type A canonical basis also has this same cardinality, by virtue of a bijection due to Berenstein and Zelevinsky between the elements of a canonical basis and semistandard Young tableaux (actually Gelfand-Tsetlin patterns) such that this bijection sends Lusztig's involution to evacuation. Stembridge examined this connection between self-complementary partitions and canonical bases more closely, unveiling in the process a phenomenon he dubbed the "q = -1 phenomenon".

In (12), Stembridge defines the q = -1 phenomenon as the following situation. One has a set of combinatorial objects B (such as tableaux), together with a generating function X(q) that enumerates the objects in B according to some weight depending on q. The q = -1 phenomenon occurs when there is a "natural" involution on B such that X (-1) is the number of fixed points of the involution. Stembridge established various instances of this phenomenon by interpreting X (-1) as the trace of a matrix which is conjugate to a permutation matrix for the involution.

It is natural to ask if the q = - 1 phenomenon can be explained by an Euler characteristic computation. To this end, we define a complex whose ranks of chain groups are the coefficients in the polynomial X (q) so that its Euler characteristic is X( - 1). On the other hand, the Euler characteristic is the alternating sum of ranks of homology groups, so whenever homology is concentrated in even dimensions with homology basis indexed by the fixed points of the involution, this would imply the phenomenon. Moreover, the homology generating function then offers a natural q-analogue of the integer which is the Euler characteristic. We carry out this plan in two quite central cases: the partitions in a rectangle and the plane partitions of bounded value in a rectangle, i.e., the partitions in a three dimensional box.

In [section]2 we associate to any action of a finite group G regarded as a subgroup of Sn four algebraic complexes over a field with 2 elements, and prove in Proposition 2.3 that their Euler characteristic is the number of fixed points of the complementation involution in the action of G on the subsets of [n]. The aforementioned case of partitions in a rectangle arises as the special case where G is a wreath product of symmetric groups. We prove acyclicity of these complexes for any G in which n is odd and also somewhat more generally. In [section]3 we give an algebraic Morse matching lemma, which is then applied in [section]4 and [section]5 to partitions in a rectangle and in a three dimensional box, respectively, establishing homology concentration in even dimensions and explicit homology bases. The results in [section]4 and [section]5 may be regarded as sign- reversing involutions with some extra topological structure. In [section]6, we conclude with an example showing that not all G give rise to complexes with homology concentrated in even dimensions, namely Example 6.1, and finally we propose in Conjecture 6.5 that homology concentration in even ranks nonetheless does hold for necklaces, i.e. the case where G is a cyclic group.

The authors are grateful to Vic Reiner for his numerous helpful suggestions.

2 The algebraic complexes

In this section we define the algebraic complexes, which are quotient complexes of the Boolean algebra over a field of two elements. The boundary map is closely related to the down operator introduced in (9). Let G be a subgroup of [[??].sub.n], so G acts on [n] := {1,2, ..., n}. Then G also permutes the elements of the Boolean algebra 2[n of all subsets of [n], and permutes the subsets ([n]) of a given cardinality i. Consider the following generating function that counts such G-orbits according to their cardinality, letting S be an element in the orbit [bar.S], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It has been well-studied historically via algebraic means, perhaps starting with Redfield and Polya.

Theorem 2.1 ((9; 5)) The polynomial X (G, q) has symmetric, unimodal coefficients.

The idea is to show that the coefficients in X (G, q) are the ranks of the weight spaces in a representation of [sl.sub.2] (C) by showing that the three operators D, U, DU - UD satisfy the appropriate relations.

See (6, Corollary 6.2) for the next result, which is due to de Bruijn.

Theorem 2.2 (de Bruijn) X(G, -1) is the number of G-orbits [bar.S] of subsets of [n] which are self-complementary in the sense that [bar.S] = [bar.[n]\S].

This was proven by finding two conjugate matrices, one having X(G, -1) as its trace and the other of which is a permutation matrix acting on the G-orbits of subsets of [n] by complementation. As an example, if G = ((12), (34)}, then S = {{1, 3}, {2,4}} is a self-complementary orbit. Theorem 2.2 may be applied to our first main example, namely the case of partitions in a rectangle, but does not seem to apply to our second example of plane partitions of bounded value in a rectangle.

One algebraic approach introduces, for any field F, the graded vector space C(F) := [[direct sum].sup.n.sub.i=0] [C.sub.i](F) in which [C.sub.i](F) has an F-basis [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is useful to identify C [congruent to] [V.sup.[cross product]n], where V [congruent to] [F.sub.2] has F-basis {[e.sub.0], [e.sub.1]}. Under this identification, the F-basis element [e.sub.s] in C(F) corresponds to the decomposable tensor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in which [i.sub.j] = 1 for [i.sub.j] [member of] S and [i.sub.j] = 0 otherwise.

Define the up and down maps U, D : C(F) [right arrow] C(F) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that U, D both commute with the G-action. As a consequence, they give well-defined maps on the graded vector spaces of G-invariants C(F)G and G-coinvariants. (i) C(F)G. Note that both C[(F).sup.G], C[(F).sub.G] will have F-bases indexed by G-orbits S of subsets of [n]: for C(F)G, a typical basis element es is a sum of [e.sub.S] as S varies over the elements of the orbit, while for C(F)G, a typical basis element is the image [[bar.e].sub.S] of [e.sub.S] in the quotient for any S [member of] [bar.S].

We let F = [F.sub.2] henceforth, in order to obtain a complex.

Proposition 2.3 The map D induced on C[([F.sub.2]).sup.G] or on C[([F.sub.2]).sub.G] make them algebraic chain complexes of [U.sup.2]-vector spaces, i.e., [D.sup.2] = 0 in each case. Likewise the map U makes them into cochain complexes, i.e., [U.sup.2] = 0.

Each of these four complexes has Euler characteristic, i.e. alternating sum of the ranks of its chain groups, equalling X(-1), or in other words the number of self-complementary G-orbits. In particular, each Euler characteristic is nonnegative.

Proof: Working over [F.sub.2], these maps D, U on C([F.sub.2]) coincide with the boundary and coboundary maps [[partial derivative].sub.i] and [[partial derivative].sub.i] in the usual simplicial chain complex for a simplex having vertex set [n]. Hence [D.sup.2] = [U.sup.2] = 0, and the same holds after taking G-invariants or G-coinvariants.

For the second assertion, note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

and now apply Theorem 2.2.

Given a G-orbit [bar.S], let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the basis element of [C.sup.G](F) corresponding to [bar.S]; let [[bar.e].sub.S] denote the basis element of C[(F).sub.G] corresponding to S

Proposition 2.4 The map sending [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] induces isomorphisms ofcochain complexes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

The map sending [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] induces isomorphisms of chain complexes

(C[([F.sub.2]).sup.G],D) [congruent to] [(C[([F.sub.2]).sup.G],U).sup.op]

(C[([F.sub.2]).sup.G],D) [congruent to] [C[([F.sub.2]).sub.G],U).sup.op],

where here [C.sub.op] for a cochain complex C denotes the opposite chain complex that one obtains by reindexing in the opposite order and reversing all the arrows.

Proof: Let [bar.S], [bar.T] be G-orbits of subsets with [absolute value of T] = [absolute value of S] + 1. Then the boundary map coefficient [D.sub.[bar.S],[bar.T]] in C[([F.sub.2]).sup.G] is the number of elements T' in the orbit T which contain the fixed set S in [bar.S]. Meanwhile the boundary coefficient [D.sub.[bar.S],[bar.T]] in C[([F.sub.2]).sub.G] is the number of elements S' in the orbit S which are contained in the fixed set T in [bar.T]. There are similar formulae for the coefficients [U.sub.[bar.S],[bar.T]] in the two complexes. The isomorphisms are not hard to verify, using the fact that set-complementation is an inclusion-reversing bijection.

In light of the previous proposition, one may consider any one of the four complexes, as its homology determines the homology of the others (either by turning it around in homological degree, or by taking dual [F.sub.2]-vector spaces, or both).

Proposition 2.5 The complex ([C.sub.G], D) is acyclic when n is odd. More generally, it is acyclic whenever G has at least one orbit in its action on [n] of odd cardinality. Whenever ([C.sup.G], D) is not acyclic, it must have [H.sub.0] = [F.sub.2] and [H.sub.1] = 0.

Proof: Let S [subset] [n] be G-stable (although not necessarily pointwise fixed by G). Then one forms S-masked versions of the up and down maps in C as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The G-stability of S implies that these S-masked up and down maps commute with the G-action: the crucial point in all these calculations is that g(S) = S, so that, for example,

S\g(T) = g(S\T)

S [intersection] g(T) = g(S [intersection] T),

Hence one gets induced S-masked up and down maps [U.sup.(S)], [D.sup.(S)] on the G-invariant and G-coinvariant complexes also.

An easy calculation, generalizing the commutator calculation DU - UD = (n - 2i)I on [C.sub.i] is the following:

(D x [U.sup.(S)] - [U.sup.(S)] x D)([e.sub.T]) = ([absolute value of S\T] - [bar.S [intersection] T]) x [e.sub.T] = ([absolute value of S] - 2[absolute value of S [intersection] T]) x [e.sub.T].

When working with [F.sub.2] coefficients, as in C([F.sub.2]), C[([F.sub.2]).sub.G], C[([F.sub.2]).sub.G], this gives

D x [U.sup.(S)] + [U.sup.(S)] x D) = [absolute value of S] x I.

Thus when [absolute value of S] is odd, the S-masked up map [U.sup.(S)] gives an algebraic chain-contraction, showing that the complex with D as boundary map is acyclic. We now analyze the consequences of this for the first few boundary maps in (C[([F.sub.2]).sup.G], D).

The boundary map D out of [C.sub.0][([F.sub.2]).sup.G] = [F.sub.2] is always the zero map, regardless of G. If all G- orbits have even cardinality, the boundary map D out of [C.sub.1][([F.sub.2]).sup.G] will also be the zero map, so the assertion about [H.sub.0] follows.

It remains to show that when all G-orbits have even cardinality, the map D out of [C.sub.2][([F.sub.2]).sup.G] is surjective. But for this we can work within each G-orbit X on [n]. That is, it suffices to show that there is some G-orbit Y = [bar.{i, j}] of pairs with i, j [member of] X for which D([e.sub.Y]) has coefficient 1 on [e.sub.X], not zero. However, fixing X, one can see that the sum of all of such boundary map coefficients incident to X and coming from G-orbits of pairs contained in X will be [absolute value of X] - 1, an odd number. Thus one of them must be non-zero in [F.sub.2], as desired.

Remark 2.6 Examples like G = ((123)(456)} in [[??].sub.6], where G has orbits on [n] of odd size but n is even and G is not a product [G.sub.1] x [G.sub.2] show that the Kunneth formula doesn't suffice to prove the previous proposition (or at least it's not obvious how to deduce it from Kunneth).

In light of Proposition 2.3 and the calculations of [H.sub.0], [H.sub.1] in Proposition 2.5, one might be tempted to make the conjecture (true up through n = 5) that the homology is always concentrated in even dimension. However, Section 6 gives a counterexample to this. Section 4 does confirm this behavior for wreath products of symmetric groups, and we conjecture it for cyclic groups in Section 6 as well.

3 An algebraic Morse matching lemma

In this section we give a general result, Lemma 3.2, on matchings in partially ordered sets, called Morse matchings. If the complex of [section]2 is supported by a partially ordered set, and the Morse matching is good enough, in a sense that will be made precise, it may be used to give a homology basis and prove homology concentration in even dimensions for the complex. In this case the basis is indexed by fixed points of the Morse matching, which must be equinumerous with X(G, -1).

Definition 3.1 Say that a graded poset P = [[??].sup.n.sub.i=0] [P.sub.i] supports an algebraic complex (C, d) of F- vector spaces if [C.sub.i] has an F-basis {[e.sub.p]} indexed by p [member of] [P.sub.i], and the differential [d.sub.i] has [([d.sub.i]).sub.p,q] = 0 unless q < P p.

As usual, say that a partial matching M of the Hasse diagram of a poset P is an acyclic matching, or Morse matching, if the digraph D, obtained by starting with the Hasse diagram directed downward and then reversing all the directions of the edges in M, is acyclic.

Given an acyclic matching M on P, let the subsets

[P.sup.M], [p.sup.unM], [P.sup.M.sub.i], [p.sup.unM.sub.i]

respectively denote the M-matched and M-unmatched elements in P, and the same sets restricted to rank i. The elements of [P.sup.unM] are called critical elements. Let q = M (p) denote that q is matched by M to p. Let [<.sub.D] be the partial order on P that results from taking the transitive closure of D.

Lemma 3.2 Let P be a graded poset supporting an algebraic complex (C d) and assume P has a Morse matching M such that for all q = M(p) with q < p, one has [d.sub.p,q] [member of] [F.sub.x]. Let [Q.sub.i] be the set of poset elements of rank i which are matched with elements of rank i - 1. Then

(i) dim [H.sub.i](C,d) [less than or equal to] [absolute value of [P.sup.unM.sub.i].

(ii) if [absolute value of [Q.sub.i]] = rank([d.sub.i]) for every i, then dim [H.sub.i] = [P.sup.unM.sub.i]. (For example, this condition is met whenever all unmatched poset elements live in ranks of the same parity.)

(iii) if [d.sub.q,p] = [d.sub.p,r] = 0 for all p [member of] [P.sup.unM] and all q, r [member of] P, then the homology H(C, d) has F-basis {[e.sub.p] : p [member of] [P.sup.unM]}.

Proof: To prove (i), we want to show that the boundary maps di have sufficiently large ranks, which we'll do by showing that they have some large, nonsingular square submatrices. We make the following claim: consider the subset [Q.sub.i] of [P.sup.M.sub.i] consisting of those elements matched below them into [P.sup.M.sub.i- 1]. Then ordering [Q.sub.i] as [q.sub.1], ..., [q.sub.r] by any linear extension of the partial order [<.sub.D], the square submatrix of [d.sub.i] having columns indexed [q.sub.1], ..., [q.sub.r] and rows indexed M([q.sub.1]), ..., M([q.sub.r]) will be invertible upper- triangular.

To prove the claim, note that the hypothesis [d.sub.p,q] [member of] [F.sup.x] for q < p implies that the diagonal entries of this square matrix are all in [F.sup.x], since q = M(p) implies q < p or p < q. Hence one only needs to verify upper-triangularity. So assume that the boundary map [d.sub.i] has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some k [not equal to] j. Since the complex C was supported on P, this implies that [q.sub.j] [>.sub.P] M([q.sub.k]) and hence D has an edge directed [q.sub.j] [right arrow] M ([q.sub.k]). There is also the matching edge in D, directed upward as M ([q.sub.k]) [right arrow] [q.sub.k], and thus by transitivity, [q.sub.j] [<.sub.D] [q.sub.k]. Hence j < k, yielding the claim.

The claim implies that rank([d.sub.i]) [greater than or equal to] [absolute value of [Q.sub.i]] for all i. As usual letting [Z.sub.i] = ker [d.sub.i] and [B.sub.i] = [imd.sub.i+1], note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as desired.

Now the hypothesis in (ii) makes the weak inequality into an equality in the above string of equalities and weak inequalities, implying the desired equality in (ii). To prove (iii), note that the hypothesis [d.sub.p,r] = 0 for all r < p ensures that {[e.sub.p]|p [member of] [P.sup.unM.sub.i]} spans a subspace of [H.sub.i](C, d) for each i, while [d.sub.q,p] = 0 for all q > p implies linear independence of the set. Since [absolute value of P.sup.unM.sub.i] [greater than or equal to] dim [H.sub.i](C, d), this set also must span [H.sub.i](C,d), hence is a homology basis. []

Lemma 3.2 is closely related to results of Jollenbeck-Welker, of Skoldberg, and of Kozlov (see (3), (8), and (4)) developing algebraic versions of discrete Morse theory.

4 Application to partitions in a rectangle

Consider the subgroup G = [[??].sub.l] [??] I [G.sub.k] inside [[??].sub.kl], acting on the cells of a rectangle with k rows and l columns, by permuting arbitrarily within each row, but also allowing wholesale swaps of one row for another. In this section, we will show how all three parts of Lemma 3.2 apply to the complex (C[([F.sub.2]).sub.G], D) for G = [[??].sub.l] [??] [[??].sub.k], yielding homology concentration in even dimensions. The G-orbits are indexed by partitions [lambda] = ([[lambda].sub.1], ..., [[lambda].sub.k]) with

l [greater than or equal to] [[lambda].sub.1] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.k] [greater than or equal to] 0.

The number [[lambda].sub.i] indicates the number of boxes in row i not belonging to the set S serving as orbit representative. Thus, the complex C[([F.sub.2]).sub.G] is supported on the Gaussian poset P(k, l) of all such [lambda] ordered by reverse inclusion of their Ferrers diagrams. One may check directly that the entries in the boundary maps d take the following form: if [mu] is obtained from [lambda] by reducing the part [[lambda].sub.i] to [[lambda].sub.i] - 1, then

[d.sub.[lambda],[mu]] = (l - [[lambda].sub.i] + 1)([mult.sub.[lambda]]([[lambda].sub.i-1]) + 1) (1)

where [mult.sub.[lambda]](s) is the multiplicity of the part s in [lambda] and [mu] covers [lambda] in the poset supporting the complex. In fact, d is derived from the down operator D which acts on faces of a simplex, by using the fact that D commutes with the group action. D deletes a box from the orbit representative S in all possible ways, each of which has the impact of lengthening some part of A by one.

Here is the matching M we will use. Given a partition [lambda], find the smallest part [[lambda].sub.i] which is either

* non-zero and of the same parity as I, in which case you should subtract 1 from it in order to obtain M([lambda]), or

* possibly zero and of opposite parity to I, but with odd multiplicity, in which case you should add 1 to it in order to obtain M(A).

It is not hard to check that this is indeed a well-defined matching.

Remark 4.1 The unmatched partitions also correspond to the lattice paths in a k x l rectangle delineating the shape [lambda], specifically those lattice paths from (l, k) to (0,0) comprised of steps (-2,0) and (0, -2) until either (i, 0) or (i, 1) is reached, after which there is a step (0, -1) in the latter case.

To see that these are equinumerous with self-complementary partitions in a k x l rectangle, notice that there is a bijection sending an unmatched path to a path fixed under 180 degree rotation by replacing each step of length 2 with a step in the same direction of length 1 to obtain the first half of the path with 180 degree rotational symmetry.

Theorem 4.2 The above matching on the Gaussian poset P (k, l) is acyclic, with the partitions [lambda] in [P.sup.unM] being those described in Remark 4.1. Moreover, the homology is concentrated in even dimensions.

Proof: It is easy to verify hypotheses (i), (ii), and (iii) of Lemma 3.2 and the description of [P.sub.unM] directly from these descriptions and (1). Let us check acyclicity of M. Suppose one had a directed cycle C. If [[lambda].sub.i] is the smallest even value ever incremented in C, then there must be some downward step in C decrementing the value [[lambda].sub.i] + 1. However, since no smaller values ever change, this downward step is across a matching edge, a contradiction.

Question 4.3 Is there some connection between the Poincare series for the homology here and T. Eisenkolbl's recent (-1)-enumerations of self-complementary plane partitions which appears in (2)? In particular, what happens in her situation when the k x l x m box in which the plane partitions live has m = 1?

5 Application to plane partitions of bounded value in a rectangle

In this section, we construct a mod 2 complex (C(c, r,t), d) whose i-dimensional cells are indexed by plane partitions of volume i in a c x r x t box. We prove homology concentration in Theorem 5.6 and also give a homology basis. Since we are not aware of a way to regard partitions in a c x r x t box as orbits of a group action permuting cells, we devised a different, though related construction.

It will be more convenient to use another indexing set of equal cardinality, namely the semistandard Young tableaux (SSYT) of shape [lambda] = [(c).sub.r] in which all entries have value between 0 and r + t - 1. The bijection comes from taking a Young tableaux filling with entries that weakly increase in rows and columns to a column strict one by adding i - 1 to each entry in row i.

We now define the complex (C(c, r, t), d), with coefficients taken mod 2, by letting the chain group generators be the SSYT of c x r rectangular shape with entries between 0 and t + r - 1. Let us call an odd value 2i + 1 in row R decrementable if it does not have the value 2i immediately above it in row R - 1. Define the boundary map d as follows. For T an SSYT, dT is a sum over SSYT obtained by subtracting one from the leftmost copy in some row R some odd value 2k + 1 having the following property: there are an odd number of decrementable copies of 2k + 1 in row R. In other words,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for d(T) the set of SSYT obtained by deleting one from a decrementable odd entry [[lambda].sub.i] of T located at position (i, j). One may verify:

Proposition 5.1 (C(c, r, t), d) is a chain complex, i.e., [d.sub.2] = 0.

Next we give an acyclic matching M on the set of such SSYT. M will have the property that for each pair S, T of matched tableaux with [absolute value S] < [absolute value of T], S appears with nonzero coefficient in dT.

Matching M: Let T be a SSYT satisfying our requirements on its entries. Consider the earliest row R in T having at least one of the following items:

1. an odd value i such that there are an odd number of decrementable copies of i in row R

2. an even value i in row R not having the value i + 1 immediately below it such that the number of decrementable copies of i + 1 in row R is even (possibly zero)

Match T to M(T) by choosing the smallest value i in the chosen row R meeting one of these conditions; now subtract one from the leftmost such copy of i in row R if i is odd, or add one to the rightmost such copy of i in row R if i is even.

Proposition 5.2 M is a matching and is acyclic, hence a Morse matching.

The proof is quite similar to the one discussed in the last section. One may also check that M meets the requirements of Lemma 3.2. Now we describe PunM.

Lemma 5.3 In any element of [P.sup.unM], every even value 2i with 2i < t + r - 1 has the odd value 2i + 1 just below it. For each odd value 2i + 1 with 2i +1 < t + r - 1, the number of decrementable copies of 2i + 1 in a given row is even.

Proof: Start with the top row, and proceed downward from row R to row R + 1 by induction as follows. In row 1, notice that each odd value 2i + 1 must occur with even multiplicity, since otherwise we could match by decrementing by one the leftmost copy of 2i +1. Thus, each even value 2i in row 1 will have an even number of copies (possibly 0) of 2i + 1 just to its right; therefore we could match by increasing the rightmost copy of 2i to 2i + 1 unless there were a 2i + 1 just below it. Since our fillings are semistandard, this implies we must have 2i + 1 just below all the other copies of 2i in that row, putting each 2i in row one in a vertical domino and each 2i + 1 in a horizontal domino.

The same argument works at row R + 1 once the claim has been proven through row R: we may have some odd values in row R + 1 which already belong to dominoes shared with row R, but all remaining spots to be filled in row R +1 will have odd values just above them. This ensures that each odd value 2i + 1 in row R + 1 must occur with even multiplicity (not counting those in dominoes shared with row R) to avoid matching by decrementing 2i +1. And again any even value 2i in row R +1 will have an even number of decrementable copies of 2i + 1 to its right, allowing matching by incrementing the rightmost 2i unless either it has a copy of 2i + 1 just below it or it is the absolute largest allowable value. []

Corollary 5.4 The first row has even sum. If row lengths are odd, then row sums alternate in parity. Otherwise, all row sums have even parity. Therefore the critical cells are concentrated in dimensions all of the same parity.

Proposition 5.5 The elements of [P.sub.unM] are all in ranks of the same parity. They are also in bijection with the semistandard domino tableaux of c x r rectangular shape comprised of odd values between 0 and t + r - 1.

The idea is to show that our description of [P.sub.unM] amounts to saying the shapes are tiled by two types of dominos: (1) horizontal dominos in which both entries of the domino have odd value 2i + 1, and (2) vertical dominos in which the top entry is 2i and the bottom entry is 2i + 1, along with perhaps some monominoes in the bottom row of maximal allowed value.

Theorem 5.6 The complex (C(c,r,t),d). has homology concentration in ranks all of the same parity. Moreover, a basis is given by Lemma 5.3.

Now we will use the following result from (12):

Theorem 5.7 (Stembridge, Theorem 3.1) The following quantities are equal.

* (a) The number of self-evacuating tableaux in [S.sub.[lambda]]

* (b) [(-1).sup.k([lambda])][s.sub.[lambda]][s.sub.[lambda]]([(-1).sup.0], [(-1).sup.1], [(-1).sup.2], ..., [(- 1).sup.(n-1)] for k([lambda]) = [[lambda].sub.2] + [[lambda].sub.4] + ...

Moreover, if n is even, or more generally if we allow monominos of maximal value in a domino tableau, then these quantities also equal

* (c) The number of semistandard domino tableaux with entries [less than or equal to] n/2 and shape [lambda]

Since the map sending a plane partition in a rectangle to a SSYT by adding i - 1 to each entry of row i has the effect of sending the self-complementary partitions exactly to the self-evacuating tableaux of the same rectangular shape, we may use Stembridge's result to deduce that our homology basis has the same cardinality as the self-complementary plane partitions with entries of value at most t.

Our matching, together with a straightforward verification that quantity (b) has positive sign, also gives a combinatorial proof that (b) equals (c) by a sign-reversing involution on the SSYT counted by (b) which has as its fixed points a set that is in trivial bijection with the objects counted by (c).

6 A counterexample and a conjecture

Example 6.1 Embed G = PSL2(F5) in S6 via its action on the 6 points of the projective line over F5. To be explicit, one can start with these generators for SL2 (F5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and then if one numbers the points of the projective line over [F.sub.5] as 1, 2, 3, 4, 5, 6 according their slopes 0, 1, 2, 3, 4, [infinite], the images of a, b, c in [PSL.sub.2] (F5) permute [6] as follows:

a = (16)(34)

b = (25)(34)

c = (12345).

One can check that this subgroup G = (a, b, c) of [[??].sub.6] acts transitively on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i = 0,1,2,4,5, 6, and has these two orbits on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

{123, 234, 345,145,125,136, 246, 356,146, 256}, {124, 235,134, 245,135,126, 236, 346, 456,156}.

An easy computation then shows that C (F2)G has H0 = H3 = F2 and no other nonvanishing homology groups.

Proposition 6.2 G [less than or equal to] [[??].sub.n] has a self-complementary orbit if and only if a Sylow 2-subgroup of G contains a derangement.

Proof: Note first that a Sylow 2-subgroup of G contains a derangement if and only if some element of g contains no cycle of odd length in its cycle decomposition. Indeed, a derangement of 2-power order is such an element, while if g has no cycle of odd length and order [2.sup.k]d with d odd then [g.sup.d] is a derangement of order [2.sup.k]. Now if g has no cycle of odd length then it is easy to construct S [subset] [n] with Sg = [n] \ S. On the other hand, say Sg = [n] \ S and (i1... ik) is a cycle in g. We may assume that [i.sub.1] [member of] S. Then [i.sub.j] [member of] S if and only if j is odd, and since [i.sub.kg] = [i.sub.1], we must have [i.sub.k] [not member of] S, so k is even. []

Corollary 6.3 If G is a transitive subgroup of [[??].sub.n] with n even, and G contains no derangement in a Sylow 2-subgroup, then the homology of C[([F.sub.2]).sub.G] is not concentrated in even dimensions.

Proof: By Theorem 2.2 and Proposition 6.2, the Euler characteristic of C[([F.sub.2]).sup.G] is zero. On the other hand, by Proposition 2.5, we have H0 (C[([F.sub.2]).sub.G]) = 0. ?

Although the homology of our mod 2 complexes is not always concentrated in even dimensions, we are still interested in interesting families of groups G for which this concentration does occur. In this situation, the Poincare polynomial for the homology of, say C[([F.sub.2]).sub.G], can be interpreted as giving a grading on the set of self-complementary G-orbits.

We conclude with evidence that this holds for G a cyclic group [C.sub.n] generated by an n-cycle in Sn. In this case the orbits are necklaces, as in (7). Here are homology calculations from Mathematica on [C.sub.n] for n even; the case of n odd already follows from Proposition 2.5.

n homologyranks 2 1, 0, 0 4 1, 0, 1, 0, 0 6 1, 0, 0, 0, 1, 0, 0 8 1, 0, 1, 0, 1, 0, 1, 0, 0 10 1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0 12 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 0 14 1, 0, 0, 0, 3, 0, 2, 0, 3, 0, 0, 0, 1, 0, 0 16 1, 0, 1, 0, 3, 0, 5, 0, 5, 0, 3, 0, 1, 0, 1, 0, 0 18 1, 0, 0, 0, 4, 0, 6, 0, 8, 0, 6, 0, 4, 0, 0, 0, 1, 0, 0

The following calculation of X([C.sub.n], q), X([C.sub.n], -1) may be done using Polya-Redfield theory or Burnside's lemma.

Proposition 6.4 For n > 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the above homology data suggests that

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for i odd, and for i = 2n - 1, 2n, and

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But one can be much more precise. Note that using the formula in Proposition 6.4 for X([C.sub.n], -1), one can easily check that it satisfies the recursion

X ([C.sub.2n], -1) = X([C.sub.n], -1) + X([C.sub.n], 1)/2

This recursion may be modified to a recursion predicting the homology Poincare series. For notational convenience, define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Conjecture 6.5 For any positive integer n, one has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if i is odd, so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a polynomial in [q.sup.2], and one has the recursion

[A.sub.2n]([q.sup.1/2]) = q[A.sub.n](q)+ [X.sub.n](q)/1 + q

Conjecture 6.5 has some strong evidence. It is correct at q = 1. It holds through n = 18, as shown earlier. We have proven it for n odd, although we do not include a proof here. In addition, it is correct with regard to its prediction about [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

received 12 Nov 2008

References

[1] M. Ciucu, The equivalence between enumerating cyclically symmetric, self-complementary and totally symmetric self-complementary plane partitions, J. Comb. Theory, Ser. A 86 (1999), no. 2, 382-389.

[2] T. Eisenkoelbl, (-1)-enumeration of self-complementary plane partitions, Electronic J. Combinatorics, 12(1), (2005), #R7, 22 pages.

[3] M. Jollenbeck, and V. Welker, Resolution of the residue field via algebraic discrete Morse theory, To appear in Mem. Amer. Math. Soc.

[4] D. Kozlov, Discrete Morse theory for free chain complexes, C. R. Math. Acad. Sci. Paris, 340 (2005), no. 12, 867-872.

[5] R. Proctor, Representations of sl(2, C) on posets and the Sperner property, SIAM J. Algebraic Discrete Methods, 3 275-280.

[6] V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), 17-50.

[7] C. Reutenauer, Free Lie Algebras, London Mathematical Society Monographs. New Series, 7. Oxford Science Publications. The Clarendon Press. Oxford University Press, New York, 1993. xviii + 269 pp.

[8] E. Skoldberg, Morse theory from an algebraic viewpoint, Trans. Amer. Math. Soc., 358 (2006), no. 1, 115-129.

[9] R. P. Stanley, Some aspects of groups acting on finite posets, J. Comb. Theory, Ser. A, 32 (1982), no. 2, 132-161.

[10] R. P. Stanley, Symmetries of plane partitions, J. Comb. Theory, Ser. A, 43 (1986), no. 1, 103-113.

[11] J. Stembridge, On miniscule representations, plane partitions and involutions in complex Lie groups, Duke Mathematical Journal 73 (1996), no. 2, 469-490.

[12] J. Stembridge, Canonical bases and self-evacuating tableaux, Duke Mathematical Journal 82 (1996), no. 3, 585-606.

P. Hersh 1, ([dagger]) J. Shareshian (2) ([double dagger]) and D. Stanton (3) ([section])

(1) North Carolina State University and Indiana University (2) Washington University in St. Louis (3) University of Minnesota

([dagger]) Supported by NSF grants DMS-0500638 and DMS-0757935.

([double dagger]) Supported by NSF grant DMS-0604233.

([section]) Supported by NSF grant DMS-0503660.

(i) Recall that the coinvariant space [U.sub.G] for an F-vector space U with a linear G-action is the quotient space U/F{u - g(u) : u [member of] U, g [member of] G}.

Printer friendly Cite/link Email Feedback | |

Author: | Hersh, P.; Shareshian, J.; Stanton, D. |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Jan 1, 2009 |

Words: | 6541 |

Previous Article: | Counting quiver representations over finite fields via graph enumeration. |

Next Article: | Colored Tutte polynomials and composite knots. |

Topics: |