*The $q = -1$ phenomenon for bounded (plane) partitions via homology concentration*

P. Hersh$^{1,†}$, J. Shareshian$^{2‡}$ and D. Stanton$^{3§}$

$^{1}$North Carolina State University and Indiana University $^{2}$Washington University in St. Louis $^{3}$University of Minnesota

received 12 Nov 2008,

**Abstract.** Algebraic complexes whose “faces” are indexed by partitions and plane partitions are introduced, and their homology is proven to be concentrated in even dimensions with homology basis indexed by fixed points of an involution, thereby explaining topologically two quite important instances of Stembridge’s $q = -1$ phenomenon. A more general framework of invariant and coinvariant complexes with coefficients taken mod 2 is developed, and as a part of this story an analogous topological result for necklaces is conjectured.

**Résumé** Complexes algébriques dont les “faces” sont indexées par des partitions et des partitions planes sont introduits. Il est démontré que leur homologie est concentrée en dimensions paires, avec base de homologie indexée par des points fixes d’une involution. Ce résultat explique d’une manière topologique deux instances du phénomène $q = -1$ du a Stembridge. De plus, un cadre plus général des complexes invariants et coinvariants dont les coefficients sont pris modulo 2 est développé. Comme part de cette histoire, nous conjecturons un résultat analogue pour des colliers.

**Keywords:** plane partitions, discrete Morse theory, $q = -1$ phenomenon, homology basis, down operator

# 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

<footnote>†Supported by NSF grants DMS-0500638 and DMS-0757935.</footnote>

<footnote>‡Supported by NSF grant DMS-0604233.</footnote>

<footnote>§Supported by NSF grant DMS-0503660.</footnote>
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 §2 we associate to any action of a finite group $G$ regarded as a subgroup of $S_n$ 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 §3 we give an algebraic Morse matching lemma, which is then applied in §4 and §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 §4 and §5 may be regarded as sign-reversing involutions with some extra topological structure. In §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 $\mathfrak{S}_n$, so $G$ acts on $[n] := \{1, 2, \dots, n\}$. Then $G$ also permutes the elements of the Boolean algebra $2^{[n]}$ of all subsets of $[n]$, and permutes the subsets $\binom{[n]}{i}$ 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

$$X(G, q) := \sum_{G\text{-orbits } \bar{S} \text{ in } 2^{[n]}/G} q^{|S|}$$
$$= \sum_{i=0}^{n} \left| \begin{pmatrix} [n] \\ i \end{pmatrix} / G \right| q^i$$

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_2(\mathbb{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} = [n] \setminus \bar{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 = \langle (12), (34) \rangle$, then $\bar{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 $\mathbb{F}$, the graded vector space $C(\mathbb{F}) := \bigoplus_{i=0}^{n} C_i(\mathbb{F})$ in which $C_i(\mathbb{F})$ has an $\mathbb{F}$-basis $\{e_S : S \in \begin{pmatrix} [n] \\ i \end{pmatrix}\}$. It is useful to identify $C \cong V^{\otimes n}$, where $V \cong \mathbb{F}^2$ has $\mathbb{F}$-basis $\{e_0, e_1\}$. Under this identification, the $\mathbb{F}$-basis element $e_S$ in $C(\mathbb{F})$ corresponds to the decomposable tensor $e_{i_1} \otimes \dots \otimes e_{i_n}$ in which $i_j = 1$ for $i_j \in S$ and $i_j = 0$ otherwise.

Define the *up* and *down* maps $U, D : C(\mathbb{F}) \to C(\mathbb{F})$ by

$$U(e_S) = \sum_{i \in [n] \setminus S} e_{S \cup \{i\}}$$

$$D(e_S) = \sum_{j \in S} e_{S \setminus \{j\}}.$$

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(\mathbb{F})^G$ and $G$-coinvariants$^{(i)}$ $C(\mathbb{F})_G$. Note that both $C(\mathbb{F})^G, C(\mathbb{F})_G$ will have $\mathbb{F}$-bases indexed by $G$-orbits $\bar{S}$ of subsets of $[n]$: for $C(\mathbb{F})^G$, a typical basis element $e_{\bar{S}}$ is a sum of $e_S$ as $S$ varies over the elements of the orbit, while for $C(\mathbb{F})_G$, a typical basis element is the image $\overline{e_S}$ of $e_S$ in the quotient for any $S \in \bar{S}$.

We let $\mathbb{F} = \mathbb{F}_2$ henceforth, in order to obtain a complex.

**Proposition 2.3** The map $D$ induced on $C(\mathbb{F}_2)^G$ or on $C(\mathbb{F}_2)_G$ make them algebraic chain complexes of $\mathbb{F}_2$-vector spaces, i.e., $D^2 = 0$ in each case. Likewise the map $U$ makes them into cochain complexes, i.e., $U^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.

<footnote>(i) Recall that the coinvariant space $U_G$ for an $\mathbb{F}$-vector space $U$ with a linear $G$-action is the quotient space $U/\mathbb{F}\{u - g(u) : u \in U, g \in G\}$.</footnote>
**Proof:** Working over $\mathbb{F}_2$, these maps $D, U$ on $C(\mathbb{F}_2)$ coincide with the boundary and coboundary maps $\partial_i$ and $\partial^i$ in the usual simplicial chain complex for a simplex having vertex set $[n]$. Hence $D^2 = U^2 = 0$, and the same holds after taking $G$-invariants or $G$-coinvariants.

For the second assertion, note that

$$ \dim_{\mathbb{F}_2} C(\mathbb{F}_2)_i^G = \dim_{\mathbb{F}_2} C(\mathbb{F}_2)_G^i = \left| \begin{pmatrix} [n] \\ i \end{pmatrix} / G \right|. $$

and now apply Theorem 2.2. □

Given a $G$-orbit $\bar{S}$, let $e_{\bar{S}} := \sum_{S' \in \bar{S}} e_{S'}$ denote the basis element of $C^G(\mathbb{F})$ corresponding to $\bar{S}$; let $\overline{e_{\bar{S}}}$ denote the basis element of $C(\mathbb{F})_G$ corresponding to $\bar{S}$

**Proposition 2.4** The map sending $e_{\bar{S}} \mapsto \overline{e_{\bar{S}}}$ induces isomorphisms of cochain complexes

$$ (C(\mathbb{F}_2)^G, U) \cong \operatorname{Hom}_{\mathbb{F}_2}((C(\mathbb{F}_2)_G, D), \mathbb{F}_2) $$

$$ (C(\mathbb{F}_2)^G, D) \cong \operatorname{Hom}_{\mathbb{F}_2}((C(\mathbb{F}_2)_G, U), \mathbb{F}_2). $$

The map sending $e_{\bar{S}} \mapsto \overline{e_{[n] \setminus S}}$ induces isomorphisms of chain complexes

$$ (C(\mathbb{F}_2)^G, D) \cong (C(\mathbb{F}_2)^G, U)^{\mathrm{op}} $$

$$ (C(\mathbb{F}_2)_G, D) \cong (C(\mathbb{F}_2)_G, U)^{\mathrm{op}}, $$

where here $C^{\mathrm{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 $|T| = |S| + 1$. Then the boundary map coefficient $D_{\bar{S}, \bar{T}}$ in $C(\mathbb{F}_2)^G$ is the number of elements $T'$ in the orbit $\bar{T}$ which contain the fixed set $S$ in $\bar{S}$. Meanwhile the boundary coefficient $D_{\bar{S}, \bar{T}}$ in $C(\mathbb{F}_2)_G$ is the number of elements $S'$ in the orbit $\bar{S}$ which are contained in the fixed set $T$ in $\bar{T}$. There are similar formulae for the coefficients $U_{\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 $\mathbb{F}_2$-vector spaces, or both).

**Proposition 2.5** The complex $(C^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^G, D)$ is not acyclic, it must have $H_0 = \mathbb{F}_2$ and $H_1 = 0$.

**Proof:** Let $S \subseteq [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:

$$ U^{(S)}(e_T) := \sum_{i \in S \setminus T} e_T \cup \{i\} $$

$$ D^{(S)}(e_T) := \sum_{j \in S \cap T} e_T - \{j\}. $$
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,

$$
\begin{align*}
S \backslash g(T) &= g(S \backslash T) \\
S \cap g(T) &= g(S \cap T),
\end{align*}
$$

Hence one gets induced $S$-masked up and down maps $U^{(S)}$, $D^{(S)}$ on the $G$-invariant and $G$-coinvariant complexes also.

An easy calculation, generalizing the commutator calculation $DU - UD = (n - 2i)I$ on $C_i$ is the
following:

$$
\begin{align*}
(D \cdot U^{(S)} - U^{(S)} \cdot D)(e_T) &= (|S \backslash T| - |S \cap T|) \cdot e_T \\
&= (|S| - 2|S \cap T|) \cdot e_T.
\end{align*}
$$

When working with $\mathbb{F}_2$ coefficients, as in $C(\mathbb{F}_2)$, $C(\mathbb{F}_2)^G$, $C(\mathbb{F}_2)_G$, this gives

$$
D \cdot U^{(S)} + U^{(S)} \cdot D = |S| \cdot I.
$$

Thus when $|S|$ is odd, the $S$-masked up map $U^{(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(\mathbb{F}_2)^G, D)$.

The boundary map $D$ out of $C_0(\mathbb{F}_2)^G = \mathbb{F}_2$ is always the zero map, regardless of $G$. If all $G$-orbits have even cardinality, the boundary map $D$ out of $C_1(\mathbb{F}_2)^G$ will also be the zero map, so the assertion about $H_0$ follows.

It remains to show that when all $G$-orbits have even cardinality, the map $D$ out of $C_2(\mathbb{F}_2)^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 = \{i, j\}$ of pairs with $i, j \in X$ for which $D(e_Y)$ has coefficient 1 on $e_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 $|X| - 1$, an odd number. Thus one of them must be non-zero in $\mathbb{F}_2$, as desired. $\square$

**Remark 2.6** Examples like $G = \langle (123)(456) \rangle$ in $\mathfrak{S}_6$, where $G$ has orbits on $[n]$ of odd size but $n$ is even and $G$ is not a product $G_1 \times G_2$ show that the Künneth formula doesn't suffice to prove the previous proposition (or at least it's not obvious how to deduce it from Künneth).

In light of Proposition 2.3 and the calculations of $H_0, H_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 $\S^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 = \bigsqcup_{i=0}^n P_i$ supports an algebraic complex $(C, d)$ of $\mathbb{F}$-vector spaces if $C_i$ has an $\mathbb{F}$-basis $\{e_p\}$ indexed by $p \in P_i$, and the differential $d_i$ has $(d_i)_{p,q} = 0$ unless $q < P_i 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^M, P^{\text{unM}}, P_i^M, P_i^{\text{unM}}$$

respectively denote the $M$-matched and $M$-unmatched elements in $P$, and the same sets restricted to rank $i$. The elements of $P^{\text{unM}}$ are called critical elements. Let $q = M(p)$ denote that $q$ is matched by $M$ to $p$. Let $<_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_{p,q} \in \mathbb{F}^\times$. Let $Q_i$ be the set of poset elements of rank $i$ which are matched with elements of rank $i-1$. Then

(i) $\dim H_i(C, d) \le |P_i^{\text{unM}}|$.

(ii) if $|Q_i| = \text{rank}(d_i)$ for every $i$, then $\dim H_i = |P_i^{\text{unM}}|$. (For example, this condition is met whenever all unmatched poset elements live in ranks of the same parity.)

(iii) if $d_{q,p} = d_{p,r} = 0$ for all $p \in P^{\text{unM}}$ and all $q, r \in P$, then the homology $H(C, d)$ has $\mathbb{F}$-basis $\{e_p : p \in P^{\text{unM}}\}$.

**Proof:** To prove (i), we want to show that the boundary maps $d_i$ 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_i$ of $P_i^M$ consisting of those elements matched below them into $P_{i-1}^M$. Then ordering $Q_i$ as $q_1, \dots, q_r$ by any linear extension of the partial order $<_D$, the square submatrix of $d_i$ having columns indexed $q_1, \dots, q_r$ and rows indexed $M(q_1), \dots, M(q_r)$ will be invertible upper-triangular.

To prove the claim, note that the hypothesis $d_{p,q} \in \mathbb{F}^\times$ for $q < p$ implies that the diagonal entries of this square matrix are all in $\mathbb{F}^\times$, 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_i$ has $(d_i)_{q_j, M(q_k)} \ne 0$ for some $k \ne j$. Since the complex $C$ was supported on $P$, this implies that $q_j >_P M(q_k)$ and hence $D$ has an edge directed $q_j \to M(q_k)$. There is also the matching edge in $D$, directed upward as $M(q_k) \to q_k$, and thus by transitivity, $q_j <_D q_k$. Hence $j < k$, yielding the claim.

The claim implies that $\text{rank}(d_i) \ge |Q_i|$ for all $i$. As usual letting $Z_i = \ker d_i$ and $B_i = \text{im}d_{i+1}$, note that

$$ \begin{aligned} \dim H_i &= \dim Z_i - \dim B_i \\ &= |P_i| - (\text{rank}(d_i) + \text{rank}(d_{i+1})) \\ &\le |P_i| - (|Q_i| + |Q_{i+1}|) \\ &= |P_i| - |P_i^M| \\ &= |P_i^{\text{unM}}| \end{aligned} $$

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_{p,r} = 0$ for all $r < p$ ensures that $\{e_p|p \in P_i^{\text{unM}}\}$ spans a subspace of $H_i(C, d)$ for each $i$, while $d_{q,p} = 0$ for all $q > p$ implies linear independence of the set. Since $|P_i^{\text{unM}}| \ge \dim H_i(C, d)$, this set also must span $H_i(C, d)$, hence is a homology basis. $\square$

Lemma 3.2 is closely related to results of Jöllenbeck-Welker, of Sköldberg, 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 = \mathfrak{S}_\ell \wr \mathfrak{S}_k$ inside $\mathfrak{S}_{k\ell}$, acting on the cells of a rectangle with $k$ rows and $\ell$ 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(\mathbb{F}_2)_G, D)$ for $G = \mathfrak{S}_\ell \wr \mathfrak{S}_k$, yielding homology concentration in even dimensions. The $G$-orbits are indexed by partitions $\lambda = (\lambda_1, \dots, \lambda_k)$ with

$$ \ell \ge \lambda_1 \ge \dots \ge \lambda_k \ge 0. $$

The number $\lambda_i$ indicates the number of boxes in row $i$ not belonging to the set $S$ serving as orbit representative. Thus, the complex $C(\mathbb{F}_2)_G$ is supported on the Gaussian poset $P(k, \ell)$ 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_i$ to $\lambda_i - 1$, then

$$ d_{\lambda, \mu} = (\ell - \lambda_i + 1)(\text{mult}_{\lambda}(\lambda_{i-1}) + 1) \quad (1) $$

where $\text{mult}_{\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 $\lambda$ by one.

Here is the matching $M$ we will use. Given a partition $\lambda$, find the smallest part $\lambda_i$ which is either

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

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

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 \times 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 \times 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, \ell)$ is acyclic, with the partitions $\lambda$ in $P^{\text{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^{\text{unM}}$ directly from these descriptions and (1). Let us check acyclicity of $M$. Suppose one had a directed cycle $C$. If $\lambda_i$ is the smallest even value ever incremented in $C$, then there must be some downward step in $C$ decrementing the value $\lambda_i + 1$. However, since no smaller values ever change, this downward step is across a matching edge, a contradiction. $\square$

**Question 4.3** Is there some connection between the Poincaré series for the homology here and T. Eisenkőlbl’s recent (-1)-enumerations of self-complementary plane partitions which appears in (2)? In particular, what happens in her situation when the $k \times \ell \times 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 \times r \times 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 \times r \times 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)^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 \times 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,

$$dT = \sum_{T' \in d(T)} T'$$

for $d(T)$ the set of SSYT obtained by deleting one from a decrementable odd entry $\lambda_{i,j}$ 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^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 $|S| < |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 $P^{\text{unM}}$.

**Lemma 5.3** In any element of $P^{\text{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. $\square$

**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^{\text{unM}}$ are all in ranks of the same parity. They are also in bijection with the semistandard domino tableaux of $c \times r$ rectangular shape comprised of odd values between 0 and $t+r-1$.*

The idea is to show that our description of $P^{\text{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_\lambda$
• $(b) (-1)^{k(\lambda)} s_{\lambda}((-1)^0, (-1)^1, (-1)^2, \dots, (-1)^{(n-1)})$ for $k(\lambda) = \lambda_2 + \lambda_4 + \dots$

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 $\le 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 = PSL_2(\mathbb{F}_5)$ in $\mathfrak{S}_6$ via its action on the 6 points of the projective line over $\mathbb{F}_5$. To be explicit, one can start with these generators for $SL_2(\mathbb{F}_5)$

$$a = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, \quad b = \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix}, \quad c = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$$

and then if one numbers the points of the projective line over $\mathbb{F}_5$ as 1, 2, 3, 4, 5, 6 according their slopes 0, 1, 2, 3, 4, $\infty$, the images of $a, b, c$ in $PSL_2(\mathbb{F}_5)$ permute [6] as follows:

$$a = (16)(34)$$

$$b = (25)(34)$$

$$c = (12345).$$

One can check that this subgroup $G = \langle a, b, c \rangle$ of $\mathfrak{S}_6$ acts transitively on $\binom{[6]}{i}$ for $i = 0, 1, 2, 4, 5, 6$, and has these two orbits on $\binom{[6]}{3}$:

$$\{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(\mathbb{F}_2)^G$ has $H_0 = H_3 = \mathbb{F}_2$ and no other nonvanishing homology groups.

**Proposition 6.2** $G \le \mathfrak{S}_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^k d$ with $d$ odd then $g^d$ is a derangement of order $2^k$. Now if $g$ has no cycle of odd length then it is easy to construct $S \subseteq [n]$ with $Sg = [n] \setminus S$. On the other hand, say $Sg = [n] \setminus S$ and $(i_1 \dots i_k)$ is a cycle in $g$. We may assume that $i_1 \in S$. Then $i_j \in S$ if and only if $j$ is odd, and since $i_k g = i_1$, we must have $i_k \notin S$, so $k$ is even. $\square$
**Corollary 6.3** If $G$ is a transitive subgroup of $\mathfrak{S}_n$ with $n$ even, and $G$ contains no derangement in a Sylow 2-subgroup, then the homology of $\mathcal{C}(\mathbb{F}_2)^G$ is not concentrated in even dimensions.

**Proof:** By Theorem 2.2 and Proposition 6.2, the Euler characteristic of $\mathcal{C}(\mathbb{F}_2)^G$ is zero. On the other hand, by Proposition 2.5, we have $H_0(\mathcal{C}(\mathbb{F}_2)^G) \neq 0$. $\square$

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 Poincaré polynomial for the homology of, say $\mathcal{C}(\mathbb{F}_2)^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_n$ generated by an $n$-cycle in $\mathfrak{S}_n$. In this case the orbits are necklaces, as in (7). Here are homology calculations from *Mathematica* on $C_n$ for $n$ even; the case of $n$ odd already follows from Proposition 2.5.

<table><thead><tr><th>n</th><th>homology ranks</th></tr></thead><tbody><tr><td>2</td><td>1, 0, 0</td></tr><tr><td>4</td><td>1, 0, 1, 0, 0</td></tr><tr><td>6</td><td>1, 0, 0, 0, 1, 0, 0</td></tr><tr><td>8</td><td>1, 0, 1, 0, 1, 0, 1, 0, 0</td></tr><tr><td>10</td><td>1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0</td></tr><tr><td>12</td><td>1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 0</td></tr><tr><td>14</td><td>1, 0, 0, 0, 3, 0, 2, 0, 3, 0, 0, 0, 1, 0, 0</td></tr><tr><td>16</td><td>1, 0, 1, 0, 3, 0, 5, 0, 5, 0, 3, 0, 1, 0, 1, 0, 0</td></tr><tr><td>18</td><td>1, 0, 0, 0, 4, 0, 6, 0, 8, 0, 6, 0, 4, 0, 0, 0, 1, 0, 0</td></tr></tbody></table>

The following calculation of $X(C_n, q)$, $X(C_n, -1)$ may be done using Polya-Redfield theory or Burnside's lemma.

**Proposition 6.4** For $n > 2$,

$$X(C_n, q) = \frac{1}{n} \sum_{d:d|n} \varphi(d) (1 + q^d)^{\frac{n}{d}}$$
$$X(C_n, -1) = \frac{1}{n} \sum_{\substack{d:d|n \\ \text{deven}}} \varphi(d) 2^{\frac{n}{d}}$$

Note that the above homology data suggests that

* $H_i(\mathcal{C}^{C_{2n}}) = 0$ for $i$ odd, and for $i = 2n - 1, 2n$, and

* $H_{2j}(\mathcal{C}^{C_{2n}}) = H_{2n-2-2j}(\mathcal{C}^{C_{2n}})$.

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

$$X(C_{2n}, -1) = \frac{X(C_n, -1) + X(C_n, 1)}{2}$$
This recursion may be modified to a recursion predicting the homology Poincaré series. For notational convenience, define

$$A_n(q) := \sum_{i=1}^{n} \dim H_i(C(\mathbb{F}_2)^{C_n})q^i \quad \text{and} \quad X_n(q) := X(C_n, q).$$

**Conjecture 6.5** For any positive integer $n$, one has $H_i(C^{C_{2n}}) = 0$ if $i$ is odd, so that $A_{2n}(q)$ is a polynomial in $q^2$, and one has the recursion

$$A_{2n}(q^{1/2}) = \frac{qA_n(q) + X_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 $H_2(C^{C_{2n}})$.

## 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. Jöllenbeck, 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, \mathbb{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. Sköldberg, 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.