% ################################################################# % ################################################################# % TITLE: Symmetric Chain Decompositions of Quotients by % Wreath Products % % AUTHORS: Dwight Duffus, Kyle Thayer % % FILE NAME: SCD-Rev-May2015-EJC-2.tex % % LAST MODIFIED: 05/04/2015 % % ################################################################# % ################################################################# \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.35}{22(2)}{2015} \usepackage{amsmath,amssymb,amsthm} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newtheorem{theorem}{Theorem}%[section] \newtheorem{lemma}{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}{Corollary} \newtheorem{claim}{Claim} \newtheorem{problem}{Problem} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\A}{\mathcal{A}} \newcommand{\ep}{\epsilon} \newcommand{\ul}{\underline} \newcommand{\C}{\mathcal{C}} \renewcommand{\labelenumi}{{\bf (\arabic{enumi})}} \renewcommand{\labelenumii}{{\bf (\alph{enumii})}} \newcommand{\bb}{\overline{b}_1} \newcommand{\bbr}{\overline{b}_1^r} \newcommand{\bfb}{\overline{b}_2} \newcommand{\bfbr}{\overline{b}_2^r} \newcommand{\Au}{\mathrm{Aut}} \parindent = 0cm \parskip = .3cm \title{\bf Symmetric Chain Decompositions\\ of Quotients by Wreath Products} \author {Dwight Duffus\\ \small Mathematics \& Computer Science\\[-0.8ex] \small Emory University\\[-0.8ex] \small Atlanta, GA 30322 U.S.A.\\ \small \tt dwight@mathcs.emory.edu\\ \and Kyle Thayer\\ \small Computer Science and Engineering\\[-0.8ex] \small The University of Washington, Seattle\\[-0.8ex] \small WA 98195 U.S.A.\\ \small \tt kthayer@cs.washington.edu} \date{\dateline{Mar 2, 2015}{May 9, 2015}{May 22, 2015}\\ \small Mathematics Subject Classifications: 06A07} \begin{document} \maketitle \begin{abstract} Subgroups of the symmetric group $S_n$ act on $C^n$ (the $n$-fold product $C \times \cdots \times C$ of a chain $C$) by permuting coordinates, and induce automorphisms of the power $C^n$. For certain families of subgroups of $S_n$, the quotients defined by these groups can be shown to have symmetric chain decompositions (SCDs). These SCDs allow us to enlarge the collection of subgroups $G$ of $S_n$ for which the quotient $\mathbf{2}^n/G$ on the Boolean lattice $\mathbf{2}^n$ is a symmetric chain order (SCO). The methods are also used to provide an elementary proof that quotients of powers of SCOs by cyclic groups are SCOs. \end{abstract} %%%%%%%%%%%%%%%%% \section{Introduction}\label{s:intro} %%%%%%%%%%%%%%%%% We are interested in a familiar symmetry property of finite partially ordered sets -- possessing a partition into symmetric chains. We want to determine circumstances under which having a symmetric chain decomposition is preserved by quotients. Here we restrict our attention to finite ordered sets $P$ with minimum element $0_P$ all of whose maximal chains have the same length. Such $P$ have a rank function $r= r_P$ defined as follows: for all $x \in P$, $r(x)$ is the maximum length $l(C) = |C| - 1$ over all chains $C \subseteq P$ with maximum element $x$. The {\it rank} $r(P)$ of $P$ is the maximum of $r(x)$ over all $x \in P$ and we call such $P$ {\it ranked} partial orders. In a ranked order $P$ a chain $x_1 < x_2 < \dots < x_k$ is {\it saturated} if for each $i$ there is no $z$ such that $x_i < z < x_{i + 1}$. Call the saturated chain \emph{symmetric} if $r(x_1) + r(x_k) = r(P)$. A \emph{symmetric chain decomposition}, an \emph{SCD}, of $P$ is a partition of $P$ into symmetric chains. If $P$ has an SCD, call $P$ a {\it symmetric chain order}, an {\it SCO}. Here, we are concerned with a particular family of SCOs, products of finite chains, and whether quotients of these are also SCOs. For any partially ordered set $P$ and any subgroup $G$ of $\Au (P)$ the automorphism group of $P$, let $P/G$ denote the quotient poset. That is, the elements of $P/G$ are the orbits induced by $G$, denoted by $[x]_G$, or just $[x]$ when no confusion should arise. And, $[x] \le [y]$ in $P/G$ if there are $x' \in [x]$ and $y' \in [y]$ such that $x' \le y'$ in $P$. Let $\mathbf{2}^n$ denote the Boolean lattice of all subsets of $[n] := \{1, 2, \ldots, n\}$, ordered by containment. Then $\Au (\mathbf{2}^n)$ is the group induced by the symmetric group $S_n$ acting on $[n]$. Canfield and Mason \cite{CM} conjectured that $\mathbf{2}^n / G$ is an SCO for all subgroups $G$ of $S_n$. In \S\ref{ss:Stanley}, we shall see that Stanley \cite{RPS} was first to ask if certain quotients of $\mathbf{2}^n$ are SCOs. A more general problem is to investigate conditions on an SCO $P$ and on subgroups $G$ of $\Au (P)$ under which $P/G$ an SCO. In studying Venn diagrams, Griggs, Killian and Savage \cite{GKS} explicitly constructed an SCD of the quotient $\mathbf{2}^n/G$ provided that $n$ is prime and $G$ is generated by a single $n$-cycle. They asked if this {\it necklace} poset is an SCO for arbitrary $n$. Jordan \cite{KKJ} proved that it is by constructing an SCD of the quotient based on SCDs of $\mathbf{2}^n$ obtained by Greene and Kleitman \cite{GK}. P. Hersh and A. Schilling \cite{HS} gave another proof of Jordan's result by devising a cyclic version of Greene and Kleitman's bracketing procedure. We \cite{DMT} showed that $\mathbf{2}^n/G$ is an SCO provided that $G$ is generated by powers of disjoint cycles. This result generalizes Jordan's result a bit, but the method of proof is likely more interesting in that we construct an SCD of the quotient by pruning the Greene-Kleitman SCD in a more direct way than Jordan. Dhand \cite{D} has shown that if $P$ is an SCO and $\mathbb{Z}_n$ acts on $P^n$ by permuting coordinates then $P^n/\mathbb{Z}_n$ is an SCO. His methods are algebraic. The base case of his argument is that for any chain $C$, $C^n/G$ is an SCO where $G$ generated by an $n$-cycle. In \cite{DMT}, a somewhat more general version of the base case is found: $C^n/G$ is an SCO provided $G$ is generated by powers of disjoint cycles. Here are our two main results. The required definitions and notation are provided in \S\ref{s:mainresult} and \S\ref{s:dhand}. \begin{theorem}\label{T:main} Let $n, k, t$ be positive integers and $n = kt$. Then $\mathbf{2}^n/G$ is a symmetric chain order for any subgroup $G$ of $\Au (\mathbf{2}^n)$ defined as follows: $G = K \wr T$, the wreath product of $K$ by $T$, where $K$ is a subgroup of $S_k$, $T$ is a subgroup of $S_t$, and both $K$ and $T$ are generated by powers of disjoint cycles. \end{theorem} The proof (in \S\ref{s:mainresult}) begins with the fact that certain quotients of products of chains are SCDs, proved in \cite{DMT}. The same proof strategy provides an elementary combinatorial proof of Dhand's result \cite{D} (\S\ref{s:dhand}), stated in somewhat more generality here. \begin{theorem}\label{T:dhand} Let $P$ be a symmetric chain order and let $G$ be a subgroup of $S_n$ generated by powers of disjoint cycles. Then $P^n/G$ is a symmetric chain order. \end{theorem} In \S\ref{s:examples}, a number of observations and problems are presented. First, we consider the implications of results-to-date for quotients of $\mathbf{2}^n$ by subgroups of $S_n$ for small values of $n$. Second, the original problem of Stanley is presented in the terminology of quotients (as he did \cite{RPS2}). Third, we consider whether quotients of $\mathbf{2}^n$ by abelian subgroups of $S_n$ are SCOs -- an obvious question since $\mathbf{2}^n/G$ is an SCO whenever $G$ is generated by disjoint cycles and each finite abelian group is a product of cyclic groups. Finally, we see that ordered sets of isomorphism types of graphs and hypergraphs can be viewed as quotients. Consequently, they possess several symmetry properties but are not known to be SCOs. %%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem \ref{T:main}}\label{s:mainresult} %%%%%%%%%%%%%%%%%%%% We start with the required terminology and notation. We use standard ordered set notation. See \cite {DM} for background on permutation groups. In this section, set $n = k t$ for positive integers $n, k, t$ and let $\mathbf{2}^n$ denote the Boolean lattice of subsets of the $n$-element set $[k] \times [t]$ of ordered pairs. Let $S_X$ denote the symmetric group on any set $X$. It is convenient to use $S_n$ in place of $S_{ [k] \times [t]}$, while using $S_k$ and $S_t$ for the symmetric groups on $[k]$ and $[t]$, respectively. Let \begin{equation}\label{e:partition} [k]\times[t] = N_1 \cup N_2 \cup \cdots \cup N_t \ \ \text{where} \ \ N_r = [k] \times \{r\}, \ (r = 1, 2, \ldots, t). \end{equation} Given subgroups $K$ of $S_k$ and $T$ of $S_t$, the wreath product $G = K \wr T$ of $K$ by $T$ is the set of all $\phi \in S_n$ defined as follows: given $\overline{\rho} = (\rho_1, \rho_2, \ldots, \rho_t ) \in K^t$ and $\tau \in T$, for all $(i, r) \in [k]\times[t]$, \begin{equation}\label{e:phi} \phi (i, r) = (\rho_r (i), \tau(r) ). \end{equation} The three subsections below are organized as follows. In \S\ref{ss:required}, we specify the properties of $K$ and $T$ that are needed in our proof that for $G = K \wr T$, $\mathbf{2}^n/G$ is an SCO. In \S\ref{ss:sufficiency}, we show that these properties do indeed suffice. In \S\ref{ss:powers}, we prove that if subgroups $K$ and $T$ are each generated by powers of disjoint cycles then they have the required properties; other sufficient conditions are given at the end of \S\ref{ss:powers}. %%%%%%%%%%%%%%%%%%%% \subsection{The required properties}\label{ss:required} %%%%%%%%%%%%%%%%%%%% We assume that $G = K \wr T$ is a subgroup of $S_n$ with $K$ a subgroup of $S_k$, $T$ a subgroup of $S_t$, and use the notation given above. We need notation for this situation: for a partially ordered set $P$ and subsets $P_1, P_2, \ldots P_m$, use $P = \sum_{i = 1}^m P_i$ to mean that $P$ is partitioned by the family of $P_i$'s and the order on each $P_i$ is that induced by the order on $P$, with no restriction on the order between elements of distinct $P_i$'s. This notation is non-standard but is very convenient here, particularly since direct products distribute over such sums. For a subposet $Q$ of a ranked partially ordered set $P$, $Q$ is said to be {\it saturated} if for all $x, y \in Q$, $x$ is covered by $y$ in $Q$ implies that $x$ is covered by $y$ in $P$. Given a saturated $Q \subseteq P$ with minimum $0_Q$ and maximum $1_Q$, say that $Q$ is {\it symmetric} in $P$ if $r_P( 0_Q ) + r_P(1_Q) = r_P(P).$\footnote{As is customary, we define ``symmetric" only for saturated subposets. However, we usually use the phrase ``saturated and symmetric" to emphasize the two aspects of the property.} Here is an immediate consequence of these definitions. \begin{lemma}\label{l:partition} Let $P$ be a partially ordered set, $P_1, P_2, \ldots, P_m$, subsets of $P$ and $P = \sum_{i = 1}^m P_i$. If each $P_i$ is a symmetric, saturated subposet of $P$ and is an SCO then $P$ is an SCO. \end{lemma} For all $X \subseteq [k] \times [t]$, let $X_r = X \cap N_r$, $r = 1, 2, \ldots, t$ (see equation (\ref{e:partition}) for this notation). With the notation in (\ref{e:phi}), let $K'$ be the subgroup of $G$ consisting of all $\phi$ for which $\tau$ is the identity on $[t]$. This is the base group of the wreath product and is isomorphic to $K^t$. Let $K_r$ denote the copy of $K$ acting on $N_r$ and for any set $N$, let $\mathbf{2}^N$ denote the Boolean lattice of all subsets of $N$. Then\\[-.6cm] \begin{equation}\label{e:inside} \mathbf{2}^n/K' \ \cong \ \prod_{r = 1}^t \mathbf{2}^{N_r}/K_r \ \cong \ (\mathbf{2}^k/K)^t . \end{equation} The first isomorphism, say $F$, in (\ref{e:inside}) is the map $[X]_{K'} \xrightarrow{F} ([X_1]_{K_1}, [X_2]_{K_2}, \ldots, [X_t]_{K_t})$, where $[X]_{K'}$ and $[X_r]_{K_r}$ denote the orbit of $X$ under $K'$ and the orbit of $X_r$ under $K_r$, respectively. Here is the property of the subgroup $K$ of $S_k$ needed in our proof:\\[-.3cm] \qquad\qquad {[{\bf K}]: $\mathbf{2}^k / K$ has an SCD.}\\[-.3cm] With an SCD guaranteed by [{\bf K}], let's derive the required property of $T$. Suppose that $C_1, C_2, \ldots, C_s$ constitute an SCD of $\mathbf{2}^k/K$ and that $C_1^r, C_2^r, \ldots, C_s^r$ is the corresponding SCD of $\mathbf{2}^{N_r}/K_r$, $r = 1, 2, \ldots, t$. Then these SCDs define a partition of the product $\prod_{r=1}^t \mathbf{2}^{N_r}/K_r$ into {\it grids}, that is, products of chains: \begin{equation}\label{e:grids} \prod_{r = 1}^t \mathbf{2}^{N_r}/K_r \ = \ \prod_{r = 1}^t \left( \sum_{j = 1}^s C_j^r \right) \ = \! \sum_{\overline{j} = (j_1, j_2, \ldots, j_t ) \in [s]^t} C_{j_1}^1 \times C_{j_2}^2 \ldots \times C_{j_t}^t . \end{equation} Note that each grid $C(\overline{j}) = C_{j_1}^1 \times C_{j_2}^2 \ldots \times C_{j_t}^t$ is itself an SCO (\cite {BTK}) and is a symmetric, saturated subset of $\prod_{r = 1}^t \mathbf{2}^{N_r}/K_r$. Following Lemma \ref{l:partition}, the family of all chains from the SCDs of the $C(\overline{j})$s and the first isomorphism in (\ref{e:inside}) yield an SCD for $\mathbf{2}^n/K' $. The group $T$ acts on $[s]^t$ as follows: for $\tau \in T$ and $\overline{j} = (j_1, j_2, \ldots, j_t ) \in [s]^t$, $$\tau(\overline{j}) = (j_{\tau^{-1}(1)}, j_{\tau^{-1}(2)}, \ldots, j_{\tau^{-1}(t)} ).$$ Let $T_{\overline{j}}$ denote the stabilizer of ${\overline{j}}$ -- the subgroup of all $\tau \in T$ such that $\tau(\overline{j}) = {\overline{j}}$. Each $\tau \in T$ induces a permutation of the family of all $C(\overline{j})$, $\overline{j} \in [s]^t$, via $C(\overline{j}) \to C(\tau(\overline{j}))$. In fact, each $\tau \in T$ induces ``local isomorphisms" among the grids $C(\overline{j})$, $\overline{j} \in [s]^t$, as follows. Given $X \subseteq [k] \times [t]$ and $X_r = X \cap N_r$, let $X_{r,p} = \{ (i, p) | (i, r) \in X_r \}$. Thus, $X_r$ and $X_{r,p}$ have the same first projection into $[k]$. Also, for brevity, let $[X_r]$ replace $[X_r]_{K_r}$, $[X_{r,p}]$ replace $[X_{r,p}]_{K_p}$, and $\overline{X} = ([X_1], [X_2], \ldots , [X_t])$. Define $\widehat{\tau}: C(\overline{j}) \to C(\tau(\overline{j}))$ by \begin{equation}\label{e:tau} \widehat{\tau} ([X_1], [X_2], \ldots , [X_t]) = ([X_{{\tau}^{-1}(1), 1}], [X_{{\tau}^{-1}(2), 2}], \ldots, [X_{{\tau}^{-1}(t), t}]) . \end{equation} Then $\widehat{\tau}$ is well-defined and is an order isomorphism because: \begin{align*} \widehat{\tau}(\overline{X}) = \widehat{\tau} ([X_1], [X_2], \ldots , [X_t]) \le \widehat{\tau} ([Y_1], [Y_2], \ldots , [Y_t]) =\widehat{\tau}(\overline{Y})\ \text{in} \ C(\tau(\overline{j})) &\iff \\ [X_{{\tau}^{-1}(r), r}] \le [Y_{{\tau}^{-1}(r), r}] \ \text{in} \ C_{j_{\tau^{-1} (r)}}^r \ (r = 1, 2, \ldots, t) &\iff \\ [X_{{\tau}^{-1}(r)}] \le [Y_{{\tau}^{-1}(r)}] \ \text{in} \ C_{j_{\tau^{-1} (r)}}^{\tau^{-1} (r)} \ (r = 1, 2, \ldots, t) &\iff \\ \overline{X} = ([X_1], [X_2], \ldots , [X_t]) \le ([Y_1], [Y_2], \ldots , [Y_t]) = \overline{Y} \ \text{in} \ C(\overline{j}). \end{align*} Whenever $\tau \in T_{\overline{j}}$, $\widehat{\tau}: C(\overline{j}) \to C(\overline{j})$ is an automorphism of $C(\overline{j})$. Finally, we can state the property of $T$ we need. [{\bf T}]: With the SCD $C_1, C_2, \ldots, C_s$ of $\mathbf{2}^k/K$, for each $\overline{j} \in [s]^t$, $C(\overline{j})/T_{\overline{j}}$ is an SCO. %%%%%%%%%%%%%%%%%%%% \subsection{Proof of Theorem \ref{T:main} from [K] and [T]}\label{ss:sufficiency} %%%%%%%%%%%%%%%%%%%% In this subsection, we assume that the subgroups $K$ and $T$ of $S_k$ and $S_t$, respectively, satisfy [{\bf K}] and [{\bf T}]. We have the partition of $\prod_{r = 1}^t \mathbf{2}^{N_r}/K_r$ into symmetric, saturated grids $C(\overline{j}), \ \overline{j} \in [s]^t$, given in (\ref{e:grids}) and know that the union of the SCDs of these grids gives an SCD of $\prod_{r = 1}^t \mathbf{2}^{N_r}/K_r$. Select a representative from each orbit in $[s]^t$ under $T$, say the lexicographically least, and let $J$ be the set of these representatives. The family $\{ C(\overline{j}) \ | \ \overline{j} \in J \}$ seems to be a promising source of an SCD of $\mathbf{2}^n/G$. Indeed, for $X = \cup_{r = 1}^t X_r \subseteq [n]$, each $X_r$ determines an index $j_r$ via $[X_r] \in C_{j_r}^r$ in the SCD of $\mathbf{2}^{N_r}/K_r$. There is a unique $\overline{j} \in [s]^t$ such that $\overline {X} = ([X_1], [X_2], \ldots , [X_t]) \in C(\overline{j})$. Thus, there is exactly one $\overline{j'} \in J$ such that $\widehat{\tau} (\overline{X}) \in C(\overline{j'})$ for some $\tau \in T$. Creating an SCD for $\mathbf{2}^n/G$ begins with verifying this claim. \begin{claim}\label{cl:bijection} Let $\Phi: \mathbf{2}^n/G \to \sum_{\overline{j} \in J} C(\overline{j})/T_{\overline{j}}$ be defined by $$\Phi([Y]_G) = [\overline{X}]_{T_{\overline{j}}}$$ where $X \in [Y]_G$ and $\overline{X} \in C(\overline{j})$ for some $\overline{j} \in J$. Then $\Phi$ is a bijection. \end{claim} \begin{proof} Let's begin by verifying the following equivalence: for all $U, V \subseteq [k] \times [t]$, \begin{equation}\label{e:mainpoint} \phi(U) = V \ \text{for some} \ \phi \in G \ \text{if and only if} \ \widehat{\tau}(\overline{U}) = \overline{V} \ \text{for some} \ \tau \in T . \end{equation} Suppose that $\phi \in G$ corresponds to $\overline{\rho} \in K^t$ and $\tau \in T$ as in (\ref{e:phi}). We need a description of $\phi(W)$ for any $W \subseteq [k] \times [t]$: with $W_r' = \{ i \in [k] \ | \ (i,r) \in W_r \}$, $$\phi(W) \ = \ \bigcup_{r = 1}^t \left( \rho_{\tau^{-1}(r )}( W_{\tau^{-1}(r)}') \times \{ r \} \right) .$$ With this notation we have \begin{align*} \phi(U) = V \ &\iff \bigcup_{r = 1}^t \left( \rho_{\tau^{-1}(r )}( U_{\tau^{-1}(r)}') \times \{ r \} \right) = \bigcup_{r = 1}^t V_r \\ &\iff \ \rho_{\tau^{-1} (r)}(U_{{\tau}^{-1}(r)}') \times \{ r \} = V_r , \ r = 1, 2, \ldots, t \\ &\iff \ [U_{\tau^{-1}(r), r}] = [V_r], \ r = 1, 2, \ldots, t\\ &\iff \ \widehat{\tau}(\overline{U}) = \overline{V} . \end{align*} The first equivalence is from the description of the wreath product in (\ref{e:phi}). The second is obvious. The third is the definition of the $K_r$-orbit. The last is the definition of $\widehat{\tau}$ in (\ref{e:tau}). Let us see that $\Phi$ is well-defined and injective. Suppose that $X$ and $Y$ are as in the statement of the claim and that $V \in [U]_G$, $V \in C_{\overline{j'}}$ for some $\overline{j'} \in J$ and $\Phi([U]_G) = [\overline{V}]_{T_{\overline{j'}}}$. Suppose that $[U]_G = [Y]_G$. Then $\phi(X) = V$ for some $\phi \in G$ so, by (\ref{e:mainpoint}), $\widehat{\tau}(\overline{X}) = \overline{V}$ for some $\tau \in T$. Then $\tau(\overline{j}) = \overline{j'}$. Since $\overline{j},\overline{j'} \in J$, a system of representatives of the $T$-orbits in $[s]^t$, $\overline{j} = \overline{j'}$ and $\tau \in T_{\overline{j}}$. Hence, $ [\overline{X}]_{T_{\overline{j}}} = [\overline{V}]_{T_{\overline{j}}}$, that is, $\Phi([U]_G) = \Phi([Y]_G).$ Thus, $\Phi$ is well-defined. The converse is easily argued, also based on (\ref{e:mainpoint}), establishing that $\Phi$ is injective. It is obvious that $\Phi$ is surjective: any element of $\sum_{\overline{j} \in J} C(\overline{j})/T_{\overline{j}}$ is the form $[\overline{X}]_{T_{\overline{j}}}$, for some $\overline{X} \in C({\overline{j}})$, ${\overline{j}} \in J$. Then $X \subseteq [k] \times [t]$ and $\Phi([X]_G) = [\overline{X}]_{T_{\overline{j}}}$. \end{proof} We began this subsection assuming that [{\bf T}]: With the SCD $C_1, C_2, \ldots, C_s$ of $\mathbf{2}^k/K$, for each $\overline{j} \in [s]^t$, $C(\overline{j})/T_{\overline{j}}$ is an SCO. Let $\overline{j} \in J$ and let $\mathcal{C}$ be a symmetric chain in an SCO of $C(\overline{j})/T_{\overline{j}}$. \begin{claim}\label{cl:quotient} The inverse image $\Phi^{-1} (\mathcal{C})$ of $\mathcal{C}$ under $\Phi$ is a symmetric, saturated chain in $\mathbf{2}^n/G$. \end{claim} \begin{proof} Observe that for all ranked orders $P$, and all subgroups $G$ of $\Au(P)$, and all $x \in P$, $r_{P/G} ([x]_G) = r_P(x)$. Thus, for all $[\overline{X}]_{T_{\overline{j}}} \in C(\overline{j})/T_{\overline{j}}$, $$r_{C(\overline{j})/T_{\overline{j}}} ([\overline{X}]_{T_{\overline{j}}}) = r_{C(\overline{j})} (\overline{X}) \ \text {and} \ r_{\mathbf{2}^n/K'} ([X]_{K'}) = r_{\mathbf{2}^n/G} ([X]_{G}) .$$ Recall $C(\overline{j})$ is a symmetric, saturated subset of $\prod_{r = 1}^t \mathbf{2}^{N_r}/K_r \cong \mathbf{2}^n/K'$ and that $r_{\mathbf{2}^n/K'} = r(\mathbf{2}^n) = n$. If $r_{C(\overline{j})} = n_{\overline{j}}$ then we have $$ r_{\mathbf{2}^n/K'} ([X]_{K'}) = 1/2(n - n_{\overline{j}}) + r_{C(\overline{j})} (\overline{X}).$$ Since $\mathcal{C}$ is a symmetric saturated chain in an SCD of $C_{\overline{j}}/T_{\overline{j}}$, the ranks of its elements form an interval $k, k+1, \dots, n_{\overline{j}} - k$, for some $k$. Thus, the ranks of the elements of $\Phi^{-1} (\mathcal{C})$ in $\mathbf{2}^n/G$ form the interval $$1/2(n - n_{\overline{j}}) + k, 1/2(n - n_{\overline{j}}) + k + 1, \ldots, 1/2(n - n_{\overline{j}}) + n_{\overline{j}} - k = n - (1/2(n - n_{\overline{j}}) + k),$$ a symmetric interval of ranks in $\mathbf{2}^n/G$. Suppose that $[\overline{X}]_{T_{\overline{j}}} \le [\overline{Y}]_{T_{\overline{j}}}$ in $\mathcal{C}$. Then there is some $\overline{Y'} = \widehat{\tau}(\overline{Y})$, for some $\tau \in T_{\overline{j}}$ such that $\overline{X} \le \overline{Y'}$ in $\prod_{r = 1}^t \mathbf{2}^{N_r}/K_r$. Then $[X]_{K'} \le [Y']_{K'}$ and, so, $[X]_{G} \le [Y']_{G} = [Y]_G$. Hence, $\Phi^{-1} (\mathcal{C})$ is a symmetric saturated chain in $\mathbf{2}^n/G$. \end{proof} The collection of the symmetric, saturated chains $\Phi^{-1} (\mathcal{C})$, over all $\mathcal{C}$ in the given SCDs of all $C(\overline{j})/T_{\overline{j}}$, $\overline{j} \in J$, provides an SCD of $\mathbf{2}^n/G$. %%%%%%%%%%%%%%%%%%%% \subsection{Powers of disjoint cycles suffice}\label{ss:powers} %%%%%%%%%%%%%%%%%%%% Let's see that if both $K$ and $T$ are generated by powers of disjoint cycles in $S_k$ and $S_t$, respectively, then both {\bf [K]} and {\bf [T]} hold. First, this result from \cite{DMT} (Corollary 7) and \cite{D} establishes {\bf [K]}. \begin{lemma}\label{l:cycles} Let $P$ be a product of chains and let $K$ be a subgroup of $\Au(P)$ that is generated by powers of disjoint cycles. Then $P/K$ is an SCO. \end{lemma} Lemma \ref{l:cycles} plus the following lemma yield {\bf [T]}, assuming $T$, too, is generated by powers of disjoint cycles. \begin{lemma}\label{L:stabilizer} Let $s, t$ be positive integers and let $T$ be a subgroup of $S_t$ that is generated by powers of disjoint cycles. Then for all $\overline{j} \in [s]^t$, the stabilizer $T_{\overline{j}}$ of $\overline{j}$ in the action of $T$ on $[s]^t$ is also generated by powers of disjoint cycles. \end{lemma} \begin{proof} Let $\overline{j} \in [s]^t$ and $\tau \in T$. Then $\tau \in T_{\overline{j}}$ if and only if for all $u, v \in [t]$, $\tau (u) = v$ implies that $j_u = j_v$. In other words, the partition of $[t]$ defined by the orbits of $[t]$ under $\tau$ refines the partition of $[t]$ defined $\overline{j}$. For each $\tau \in T$ there is a minimum $d$, at most the order of $\tau$, such that $\tau^d \in T_{\overline{j}}$. Suppose that $T = \langle \sigma_1^{r_1}, \sigma_2^{r_2}, \ldots, \sigma_m^{r_m} \rangle$ where $\sigma_i$ acts on $N_i$, $[t] = \bigcup N_i$, and $d_i$ is minimum such that $(\sigma_i^{r_i})^ {d_i} \in T_{\overline{j}}$ for $i = 1, 2, \ldots, m$. Then $T_{\overline{j}} \supseteq \langle \sigma_1^{r_1 d_1}, \sigma_2^{r_2 d_2}, \ldots, \sigma_m^{r_m d_m} \rangle$. Let $\tau \in T_{\overline{j}}$. Then for each $i$, $\tau_{|N_i}$ is a power of $\sigma_i^{r_i}$ and the $\tau$-orbits in $N_i$ refine the $\overline{j}$-partition of $[t]$ restricted to $N_i$. By definition of $d_i$, $\tau_{|N_i}$ is a power of $\sigma_i^{r_i d_i}$. Thus, $T_{\overline{j}} \subseteq \langle \sigma_1^{r_1 d_1}, \sigma_2^{r_2 d_2}, \ldots, \sigma_m^{r_m d_m} \rangle.$ \end{proof} This completes the proof of Theorem \ref{T:main}. The proof strategy gives other circumstances under which quotients by a wreath product are symmetric chain orders. As long as we know that $n = kt$, $G = K \wr T$ for $K$ a subgroup of $S_k$ such that $\mathbf{2}^k/K$ is an SCO and $T$ a subgroup of $S_t$ generated by powers of disjoint cycles, then $\mathbf{2}^n/G$ is an SCO. For instance, if $K = S_k$ or $K = A_k$, the alternating group, then $K$ is transitive on the family of $m$-element subsets of $[k]$ for all $m$, so the quotient $\mathbf{2}^k/K$ is a $(k\!+\!1)$-element chain. As long as $T$ is generated by powers of disjoint cycles, $G = K \wr T$ produces quotients that are SCOs. \begin{corollary}\label{c:iterate} Let $\mathcal{P}$ be the family of permutation groups constructed as follows. For all positive integers $k$, $t$ and $n$, \vspace{-.2cm} \begin{enumerate} \item if $G = S_k, A_k$ or $G$ is a subgroup of $S_k$ generated by powers of disjoint cycles, then $G \in \mathcal{P}$;\\[-.2cm] \item if $n = kt$ and $G$ is a subgroup of $S_n$ such that $G = K \wr T$, with $K$ a subgroup of $S_k$ that belongs to $\mathcal{P}$ and $T$ a subgroup of $S_t$ generated by powers of disjoint cycles, then $G \in \mathcal{P}$. \end{enumerate} \vspace{-.2cm} For all subgroups $G$ of $S_n$ that belong to $\mathcal{P}$, $\mathbf{2}^n/G$ is a symmetric chain order. \end{corollary} Here is an example of an infinite family in $\mathcal{P}$. For a prime $p$, the Sylow $p$-subgroup of $S_{p^n}$ is an iterated wreath product $W_n = W_{n-1} \wr \mathbb{Z}_p$, with $W_1 = \mathbb{Z}_p$ \cite{Kal}. %%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem \ref{T:dhand}}\label{s:dhand} %%%%%%%%%%%%%%%%%%%% Let $C_1, C_2, \ldots, C_s$ form an SCD of $P$. As noted after (\ref{e:grids}) in \S2.1, the family of grids $$C(\overline{j}) = C_{j_1} \times C_{j_2} \times \cdots \times C_{j_n}, \ \overline{j} = (j_1, j_2, \ldots , j_n) \in [s]^n$$ provides a partition of $P^n$ into symmetric, saturated subsets. The group $G$ acts on $[s]^n$ as before, $\sigma(j_1, j_2, \ldots, j_n) = (j_{\sigma^{-1}(1)}, j_{\sigma^{-1}(2)}, \ldots, j_{\sigma^{-1}(n)})$, and defines these mappings: \qquad $\sigma$ permutes the members of the family $\{ C(\overline{j}) \ | \ \overline{j} \in [s]^n \}$; \qquad $\sigma: P^n \to P^n$, $\sigma(\overline{p}) = (p_{\sigma^{-1}(1)}, p_{\sigma^{-1}(2)}, \ldots, p_{\sigma^{-1}(n)}, )$, $\overline{p} = (p_1, p_2, \ldots, p_n) \in P^n$, \qquad\qquad is an automorphism; and, \qquad for each $\overline{j} \in [s]^n$, the restriction of $\sigma$ is a local isomorphism of $C(\overline{j})$ to $C(\sigma(\overline{j}))$. Let $J \subseteq [s]^n$ be a system of representatives of the $G$-orbits of $[s]^n$. Note that for each $\overline{j} \in [s]^n$ and $\sigma \in G_{\overline{j}}$, the restriction of $\sigma$ is an automorphism of $C(\overline{j})$. \begin{claim}\label{cl:bijection2} Let $\Psi: P^n/G \to \sum_{\overline{j} \in J} C(\overline{j})/G_{\overline{j}}$ be defined by $$\Psi([\overline{y}]_G) = [\overline{x}]_{G_{\overline{j}}}$$ where $\overline{x} \in [\overline{y}]_G$ and $\overline{x} \in C(\overline{j})$ for some $\overline{j} \in J$. Then $\Psi$ is a bijection. \end{claim} The proof of this claim is analogous to that of Claim \ref{cl:bijection}, with simpler notation. If $[\overline{y'}]_G = [\overline{y}]_G$, $\overline{x'} \in [\overline{y'}]_G$ with $\overline{x'} \in C(\overline{j'})$ for some $\overline{j'} \in J$, and $\overline{x}, \overline{y}$ are as in the statement of Claim \ref{cl:bijection2}, then there exist $\sigma_1, \sigma_2, \sigma_3 \in G$ such that $$\sigma_1(\overline{x}) = \overline{y}, \sigma_2(\overline{y'}) = \overline{y}, \ \text{and} \ \sigma_3(\overline{x'}) = \overline{y'}.$$ Thus, $\sigma_1^{-1} \sigma_2 \sigma_3 (\overline{x'}) = \overline{x}$. Since $\overline{x} \in C_{\overline{j}}$, $\overline{x'} \in C_{\overline{j'}}$, and $\overline{j}, \overline{j'} \in J$, we have $\overline{j} = \overline{j'}$ and, thus, $\sigma_1^{-1} \sigma_2 \sigma_3 \in G_{\overline{j}}$. This shows that $\Psi$ is well-defined. It is easily shown to be bijective. By Lemma \ref{L:stabilizer} and the hypothesis that $G$ is generated by powers of disjoint cycles, we have that the same is true for each $G_{\overline{j}}$. By Lemma \ref{l:cycles}, each $C(\overline{j})/G_{\overline{j}}$ has an SCD. Let $\overline{j} \in J$ and let $\mathcal{C}$ be a symmetric chain in an SCO of $C(\overline{j})/G_{\overline{j}}$. That $P^n/G$ has an SCD follows from \begin{claim}\label{cl:quotient2} The inverse image $\Psi^{-1} (\mathcal{C})$ of $\mathcal{C}$ under $\Psi$ is a symmetric, saturated chain in $P^n/G$. \end{claim} Follow the proof of Claim \ref{cl:quotient} in the obvious way to establish that the set of ranks of elements of $\Psi^{-1} (\mathcal{C})$ is a symmetric interval in the ranks of $P^n/G$ and that if $\Psi([\overline{y}]_G) \le \Psi([\overline{u}]_G)$ in $\mathcal{C}$ then $[\overline{y}]_G \le [\overline{u}]_G$ in $P^n/G$. %%%%%%%%%%%%%%%%%%%% \section{Observations, Examples and Problems}\label{s:examples} %%%%%%%%%%%%%%%%%%%% As noted at the end of \S\ref{s:mainresult}, the proof of Theorem \ref{T:main} and the results of \cite{DMT} allow the recursive construction of a family of groups defining quotients that are SCOs. We do not have an easy characterization of this family, but we can provide a catalog of those subgroups of $S_n$ that, by these results, do generate quotients of $\mathbf{2}^n$ with SCDs for some small values of $n$. We display the collection for $n = 6$ in Table~\ref{table1}. %%%%%%%%%%%%%%%%%%%%% \subsection{The case $n= 6$ and some specific groups}\label{ss:examples} Here are the applicable facts: \begin{enumerate} \item if $[n] = X_1 \cup X_2 \cup \cdots \cup X_m$ is a partition and $G = G_1 \times G_2 \times \cdots \times G_m$ where $G_i = G_{|X_i}$ then $\mathbf{2}^n/G$ is an SCO provided that each $\mathbf{2}^{X_i}/G_i$ is an SCO;\\[-.2cm] \item if $G = \langle \sigma^r \rangle$ for some cycle $\sigma \in S_n$ then $\mathbf{2}^n/G$ is an SCO; and\\[-.2cm] \item Theorem \ref{T:main}. \end{enumerate} We list the groups in Table~\ref{table1} according to the partitions of 6 given by their orbit sizes, then refine with the cycle structure. These are all the subgroups, up to conjugation, that are handled by {\bf (1) - (3)} and the fact that the quotient of $\mathbf{2}^n$ by either the symmetric group $S_n$ or the alternating group $A_n$ is an $(n\!+\!1)$-element chain. \begin{table}[ht!] \begin{tabular}{l l l r} \hline \\[-.1cm] {\bf Partition of 6} & \qquad {\bf Generators} & \qquad {\bf Description} & \qquad {\bf Order} \\[.05cm] \hline \\ 1 + 1 + 2 + 2 & \qquad (1 2 ), (3 4) & \qquad $ \Z_2 \times \Z_2$ & \qquad 4 \\[.05cm] & \qquad (1 2 )(3 4) & \qquad$ \Z_2$ & \qquad 2 \\[.1cm] \hline \\[-.1cm] 1 + 1 + 4 & \qquad (1 2 3 4) & \qquad $ \Z_4 $ & \qquad 4 \\[.05cm] & \qquad (1 2 3 4), (1 2) & \qquad$ S_4$ & \qquad 24 \\[.05cm] & \qquad (1 2 3), (2 3 4) & \qquad$A_4$ & \qquad 12 \\[.05cm] & \qquad (1 2 3 4), (1 3) & \qquad$ \Z_2 \wr \Z_2 \cong D_8$ & \qquad 8 \\[.1cm] \hline \\[-.1cm] 1 + 2 + 3 & \qquad (1 2), (3 4 5) & \qquad $ \Z_2 \times \Z_3 $ & \qquad 6 \\[.05cm] & \qquad (1 2), (3 4 5), (3 4) & \qquad$ \Z_2 \times S_3$ & \qquad 12 \\[.1cm] \hline \\[-.1cm] 2 + 2 + 2 & \qquad (1 2), (3 4), (5 6) & \qquad $ \Z_2 \times \Z_2 \times \Z_2 $ & \qquad 8 \\[.05cm] & \qquad (1 2)(3 4), (5 6) & \qquad$ \Z_2 \times \Z_2$ & \qquad 4 \\[.05cm] & \qquad (1 2)(3 4)(5 6) & \qquad$ \Z_2$ & \qquad 2 \\[.1cm] \hline \\[-.1cm] 3 + 3 & \qquad (1 2 3), ( 4 5 6) & \qquad $ \Z_3 \times \Z_3$ & \qquad 9 \\[.05cm] & \qquad (1 2 3), (1 2), (4 5 6) & \qquad$ S_3 \times \Z_3$ & \qquad 18\\[.05cm] & \qquad (1 2 3), (1 2), ( 4 5 6), (4 5) & \qquad$ S_3 \times S_3$ & \qquad 36 \\[.1cm] \hline \\[-.05cm] 2 + 4 & \qquad (1 2), (3 4 5 6) & \qquad $ \Z_2 \times \Z_4 $ & \qquad 8 \\[.05cm] & \qquad (1 2), (3 4 5 6), (3 4) & \qquad$ \Z_2 \times S_4$ & \qquad 48 \\[.05cm] & \qquad (1 2), (3 4 5), (4 5 6) & \qquad$ \Z_2 \times A_4$ & \qquad 24 \\[.05cm] & \qquad (1 2), (3 4 5 6), (3 5) & \qquad$ \Z_2 \times (\Z_2 \wr \Z_2)$ & \qquad 16 \\[.1cm] \hline \\[-.1cm] 1 + 5 & \qquad (1 2 3 4 5) & \qquad $ \Z_5$ & \qquad 5 \\[.05cm] & \qquad (1 2 3 4 5), (1 2 3) & \qquad$ A_5$ & \qquad 60 \\[.05cm] & \qquad (1 2 3 4 5), (1 2) & \qquad$ S_5$ & \qquad 120 \\[.1cm] \hline \\[-.1cm] 6 & \qquad (1 2 3 4 5 6) & \qquad $ \Z_6$ & \qquad 6 \\[.05cm] & \qquad (1 2 3 4 5), (1 2 3), (1 2)(5 6) & \qquad $ A_6$ & \qquad 360 \\[.05cm] & \qquad (1 2 3 4 5 6), (1 2) & \qquad $ S_6$ & \qquad 720 \\[.05cm] & \qquad (1 2 3)(4 5 6), (1 4) & \qquad $\Z_2 \wr \Z_3$ & \qquad 24 \\[.05cm] & \qquad (1 2 3), (1 4)(2 5)(3 6) & \qquad $\Z_3 \wr \Z_2$ & \qquad 18 \\[.05cm] & \qquad (1 2 3), (1 2), (1 4)(2 5)(3 6) & \qquad $ S_3 \wr \Z_2$ & \qquad 72 \\[.1cm] \hline \end{tabular} \label{table1} \caption{Catalog of subgroups of $S_6$ that generate quotients of $\mathbf{2}^6$ with SCDs.} \end{table} The partitions $6 = 1 + 1 + \cdots + 1$ and $6 = 1 + \cdots + 1 + 2$ each give only one group, $(1)$ and $\mathbb{Z}_2 \cong \langle (12) \rangle$, respectively. Also, $6 = 1 + 1 + 1 + 3$ yields two: $\mathbb{Z}_3 \cong \langle (1\ 2 \ 3) \rangle$ and $S_3 \cong \langle (1\ 2 \ 3), (1 2) \rangle$. The rest are listed in Table~\ref{table1}. This is far from all the groups of degree 6. In \cite{DM}, there are 16 transitive subgroups of $S_6$ listed. Our table contains 6. One familiar transitive subgroup of $S_6$ missing from our list is the dihedral group $D_{12}$. The dihedral groups seem to be the next interesting case. \begin{problem}\label{p:dihedral} For all $n \ge 1$, let $D_{2n}$ denote the dihedral group of symmetries of a regular $n$-gon. Show that $\mathbf{2}^n/D_{2n}$ is an SCO. \end{problem} We know this only for the trivial cases $n = 1, 2, 3$ and, as noted in the table, $n = 4$, since $D_8$ is a wreath product $\Z_2 \wr \Z_2$. Note that $D_{2n}$ is the semidirect product $\Z_n \rtimes \Z_2$. However the dihedral groups are not wreath products for $n \ge 5$. This is easy to see: each permutation in $D_{2n}$ has either no fixed points, or one (for odd $n$) or two (for even $n$), or $n$ fixed points. However, a wreath product $K \wr T$ has maps with $k, 2k, \ldots, tk$ fixed points, where $K$ is a subgroup of $S_k$ and $T$ is a subgroup of $S_t$. The approach presented above can be extended in some other special cases. Here is an example. Let \qquad $G$ be the subgroup of $S_8$ generated by $\{ (1 5)(2 6)(3 7)(4 8) , (1 4)(2 3) \}$, and \qquad $H$ be the subgroup of $G$ generated by $\{ (1 5)(2 6)(3 7)(4 8) , (1 4)(2 3)(5 8)(6 7) \}$. Then $G =K \wr T$ where \qquad $K = \langle (1 2 4 3)^2 \rangle$ is a subgroup of $S_4$ and $T = \langle (12) \rangle$ is a subgroup of $S_2$. Thus $\mathbf{2}^8 / G$ is an SCO. One can describe how to refine the $G$-orbits to obtain $H$-orbits and how to produce the additional symmetric chains required for an SCD of $\mathbf{2}^8 / H$. Unfortunately, this sort of argument does not appear to yield anything for $D_{2n}$ since it is not a ``manageable" subgroup of any group we can handle, such as $Z_n \wr Z_2$ or $Z_2 \wr Z_n$. %%%%%%%%%%%%%%%%%%%%%%% \subsection{The lattice $L(k, t)$}\label{ss:Stanley} %%%%%%%%%%%%%%%%%%%%%%% Stanley \cite{RPS} raised the question of whether the distributive lattice $L(k, t)$, the poset with elements all integer sequences $\overline{a} = (a_1, a_2, \ldots, a_t)$ such that $0 \le a_1 \le \cdots \le a_t \le k$ and componentwise order, is an SCO for all $k$ and $t$. He noted \cite{RPS2, RPS3} that $L(k, t)$ is obtained as a quotient of the Boolean lattice $\mathbf{2}^{kt}$ by the group $S_k \wr S_t$ with its natural action on $[k] \times [t]$. (This is the action described at the beginning of Section \ref{s:mainresult}.) It is easiest to see this if we think of $L(k, t)$ as the set of down sets of the grid $\mathbf{k} \times \mathbf{t}$ ordered by containment (using $\mathbf{m}$ to denote the $m$-element chain). The wreath product $S_k \wr S_t$ acts on the elements of $\mathbf{k} \times \mathbf{t}$ by permuting the elements of $C_j = \{ (1, j), (2, j), \ldots, (k,j) \}$ independently under $S_k$ for each $j = 1, 2, \ldots, t$, then permuting $C_1, C_2, \ldots, C_t$. Each equivalence class under this action contains a unique down set of $\mathbf{k} \times \mathbf{t}$. If we break this action into two steps then the independent permutations of the elements in each $C_j$ produce the quotient $(\mathbf{2}^k/S_k)^t$, just as in (\ref{e:inside}) in Section \ref{s:mainresult}. Since $\mathbf{2}^k/S_k \cong \mathbf{k\!+\!1}$, the second part of the action is just $S_t$ acting on the coordinates of $(\mathbf{k\!+\!1})^t$. We restate Stanley's problem. \begin{problem}\label{p:Stanley} Show that for all $k, t$, $L(k, t)$ is an SCO. Equivalently, show that this quotient is an SCO: $$ \mathbf{2}^{kt} / (S_k \wr S_t ) \ \cong \ (\mathbf{k\!+\!1})^t / S_t .$$ \end{problem} \vspace{-.2cm} In thinking about Dhand's result, one can ask several types of questions. If we focus on groups acting by permuting coordinates, we can pose this problem. \begin{problem}\label{p:Dhand} Determine whether $P^n/G$ is an SCO, assuming that $P$ is an SCO and the subgroup $G$ of $S_n$ acts on $P^n$ by permuting coordinates. \end{problem} \vspace{-.2cm} One approach to this follows the strategy given in \S2.1 and the proof of Theorem \ref{T:dhand}. With an SCD $C_1, C_2, \ldots, C_s$ of $P$, the family of grids $C(\overline{j})$, $\overline{j} \in [s]^t$, forms a partition of $P^n$ into symmetric, saturated subsets. Every $\sigma \in G$ permutes the members of the family $\{ C(\overline{j}) \ | \ \overline{j} \in [s]^n \}$ and the restriction of $\sigma$ defines a local isomorphism of $C(\overline{j})$ to $C(\sigma(\overline{j}))$. We have an SCD for $P^n/G$ if we can obtain an SCD of each $C(\overline{j})/G_{\overline{j}}$ for a set $J$ of representatives of the $G$-orbits of $[s]^n$. If we follow this line, quotients of products of chains could be the key to Problem 3. Of course, in the case that $G = S_n$, the stabilizers $G_{\overline{j}}$ are themselves products of symmetric groups acting on disjoint subsets of $[n]$, so we are back to Stanley's problem. %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Abelian subgroups of $S_n$}\label{ss:Abelian} %%%%%%%%%%%%%%%%%%%%%%%%%%%%% Any abelian group $A$ is the direct product of cyclic groups of prime power order -- this is just the basis theorem. If we begin with an isomorphism such as $A \cong \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_5$ then the subgroups $$A_1 = \langle (1 \ 2), (3 \ 4), (5 \ 6 \ 7 \ 8 \ 9) \rangle \ \text{in} \ S_{9} \ \text{and} \ A_2 = \langle (1 \ 2), (3 \ 4 \ \cdots \ 12) \rangle \ \text{in} \ S_{12}$$ are both isomorphic to $A$ and produce SCOs $\mathbf{2}^9/A_1$ and $\mathbf{2}^{12}/A_2$, respectively, by Theorem 1 in \cite{DMT}. However, if we take the usual regular representation of $A$, say $A_3$, we obtain a subgroup of $S_{20}$ and our results do not show that $\mathbf{2}^{20}/A_3$ is an SCO. \begin{problem}\label{p:regular} Given a finite abelian group $A$ with its regular representation in $S_A$ determine whether $\mathbf{2}^A/A$ is an SCO. \end{problem} \vspace{-.2cm} One can argue easily, using Dixon \cite{D2}, that if this can be settled positively then the same is true for all maximal abelian subgroups of $S_n$. It is not difficult to describe, up to permutational equivalence, how to obtain all embeddings of a finite abelian group $A$ in a finite permutation group. Let $H_i$, $i = 1, 2, \ldots, k$, be subgroups of $A$ (repetition allowed) with $[A:H_i] = n_i$ and $\bigcap H_i = \{ 1 \}$; set $n = \sum n_i$. For each $i$, $A$ acts on $A/H_i$, the quotient group of (left) cosets of $H_i$ in $A$, by (left) multiplication. This defines a homomorphism ${\eta}_i: A \to S_{A/H_i}$ with kernel $H_i$. Identify $[n]$ with $\bigcup A/H_i$ and extend each of these homomorphisms to ${\phi}_i: A \to S_n$ by ${\phi_i} = \eta_i $ on $A/H_i$ and otherwise is the identity. Then $\phi = \phi_1\phi_2 \cdots \phi_k$ is an embedding of $A$ in $S_n$, since $\bigcap H_i = \{ 1 \}$. Note that the orbits induced by $\widehat{A} = \phi(A)$ refine the partition $[n] = \bigcup A/H_i$. L. Babai pointed out that this construction produces all embeddings of $A$, up to permutational equivalence. And he noted that this suggests a good test case. Let $A$ be an elementary abelian $p$-group, say $A = (\mathbb{Z}_p)^t$ with $p$ prime and $t$ any positive integer. If we use the cycle decomposition of $A$ then we have independent actions on each orbit and, with $n = pt$, $\mathbf{2}^n/(\mathbb{Z}_p)^t$ is an SCO since the group is generated by $t$ disjoint $p$-cycles. So, let's consider a case where the actions on the orbits are highly correlated. Let $H_i$, $i = 1, 2, \ldots, k$, be the maximal subgroups of $A$. Then $k = (p^t - 1)/(p - 1)$ and each $[A:H_i] = p$, with $A/H_i$ a cyclic group of order $p$. With the notation above and ${\widehat{A}}_i = {\phi}_i (A)$, the subgroups ${\widehat{A}}_i$, $i = 1, 2, \ldots, k$, are cyclic, of order $p$, and generated by disjoint cycles in $S_n$. Also, $\widehat{A}$ is the diagonal subgroup of all $p^t$ elements $\phi_1(a) \phi_2 (a) \cdots \phi_k (a)$, $a \in A$, of the $p^k$-element subgroup ${\widehat{A}}_1 \times {\widehat{A}}_2 \times \cdots \times{\widehat{A}}_k$ of $S_n$. For brevity, let $G = {\widehat{A}}_1 \times {\widehat{A}}_2 \times \cdots \times{\widehat{A}}_k$, $[n] = N_1 \cup N_2 \cup \cdots \cup N_k$ where $N_i = G/H_i$. Since $G$ is a subgroup of $S_n$ generated by disjoint cycles, $\mathbf{2}^n/G$ has a symmetric chain decomposition, by Theorem 1, \cite{DMT}. Also, $\widehat{A}$ is a subgroup of $G$ so its orbits refine those in $\mathbf{2}^n/G$. However, the refinements are not of uniform cardinality, though they are for each $X \subset [n]$ which intersects each $N_i$ properly. On the other hand, we can view the maximal subgroups $H_i$ as hyperplanes and explicitly describe the action of $\widehat{A}$ and $G$. \begin{problem}\label{p:p-group} With the notation defined above, show that $\mathbf{2}^n/\widehat{A}$ is an SCO. \end{problem} \vspace{-.2cm} The obvious inductive strategy for showing that all abelian subgroups of $S_n$ produce quotients which are SCOs leads to the same difficulty. Take $A$ to be an abelian subgroup of $S_n$. If $|A| = p$, $p$ prime, then $A$ is generated by a product of $p$-cycles, so is a power of a cycle, hence $\mathbf{2}^n/A$ is an SCO. If $|A| = m$ then $A$ has a subgroup $B$ of index $p$ and $A$ acts on the orbits $[X]_B$ in the obvious way, permuting them within the $A$-orbits. If nontrivial, this action amounts to a cyclic $p$-element group acting on $\mathbf{2}^n/B$, producing a quotient isomorphic to $\mathbf{2}^n/A$. However, it is not obvious how to use an inductively-obtained SCD of $\mathbf{2}^n/B$ to obtain one for $\mathbf{2}^n/A$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Graphs and hypergraphs ordered by embeddibility}\label{ss:Graphs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%% Finally, consider the set of graphs (loopless, undirected) on the vertex set $[n]$. Ordered by containment, this is the Boolean lattice $\mathbf{2}^M$, where $M = {\binom{[n]}{2}}$ is the set of $2$-element subsets of $[n]$. Let $S_n^{(2)}$ denote the subgroup of $S_M$ induced by $S_n$ on $[n]$. Then $\mathcal{G}_n = \mathbf{2}^M/S_n^{(2)}$ is the family of unlabelled graphs on $n$ vertices, ordered by embedding. Pouzet and Rosenberg \cite{PR} used this description of $\mathcal{G}_n$ to find the maximum size of an antichain in $\mathcal{G}_n$. Stanley's results on quotients \cite{RPS3} give several symmetry properties of $\mathcal{G}_n$ -- it is rank-symmetric, rank-unimodal and strongly Sperner. \begin{problem}\label{p:graphs} Determine whether the set of unlabelled graphs on $n$ vertices, ordered by embedding, is a symmetric chain order. \end{problem} \vspace{-.2cm} The same problem can be posed for the family of $k$-uniform $n$-vertex hypergraphs. \begin{thebibliography}{99} \bibitem{BTK} N. G. de Bruijn, C. Tengbergen and D. Kruyswijk. \newblock On the set of divisors of a number. \newblock {\it Nieuw Arch. Wiskd.}, 23: 191 -- 193, 1951. \bibitem{CM} E. R. Canfield and S. Mason. \newblock When is a quotient of the Boolean lattice a symmetric chain order? \newblock Preprint, 2006. \bibitem{CJT} C. C. Chang, B. J\'onsson and A. Tarski. \newblock Refinement properties for relational structures. \newblock {\it Fund. Math.}, 55: 249 -- 281, 1964. \bibitem{D} V. Dhand. \newblock Symmetric chain decomposition of necklace posets. \newblock {\it Electron. J. Combin.}, 19: \#P26, 2012. \bibitem{D2} J. D. Dixon. \newblock Maximal abelian subgroups of the symmetric group. \newblock {\it Canad. J. Math.}, 23: 426 -- 438, 1971. \bibitem{DM} J. D. Dixon and B. Mortimer. \newblock {\it Permutation Groups}. \newblock Springer, New York, 1996. \bibitem{DMT} D. Duffus, J. McKibben-Sanders and Kyle Thayer. \newblock Some quotients of the Boolean lattice are symmetric chain orders. \newblock {\it Electron. J. Combin.}, 19(2): P46, 2012. \bibitem{E} K. Engel, {\it Sperner Theory}. \newblock Cambridge University Press. \newblock Cambridge UK, 1997. \bibitem{GK} C. Greene and D. J. Kleitman. \newblock Strong versions of Sperner's theorem. \newblock \textit{J. Combinatorial Theory A}, 20: 80 -- 88, 1976. \bibitem{JRG} J. R. Griggs. \newblock Sufficient conditions for a symmetric chain order. \newblock {\it SIAM J. Appl. Math.}, 32: 807 -- 809, 1977. \bibitem{HS} P. Hersh and A. Schilling. \newblock Symmetric chain decomposition for cyclic quotients of Boolean algebras and relation to cyclic crystals. \newblock {\em Internat. Math. Res. Notices}, 2013(2):463--473, 2012. \doi{10.1093/imrn/rnr254} \bibitem{GKS} J. R. Griggs, C. E. Killian and C. D. Savage. \newblock Venn diagrams and symmetric chain decompositions in the Boolean lattice. \newblock {\it Electronic J. Combinatorics}, 11: R2, 2004. \bibitem{KKJ} K. K. Jordan.\newblock The necklace poset is a symmetric chain order. \newblock \textit{J. Combinatorial Theory A}, 117: 625 -- 641, 2010. \bibitem{Kal} L. Kaloujnine. \newblock La structure des p-groupes de Sylow des groupes sym{\' e}triques finis. \newblock \textit{Annales Scientifiques de l'{\' E}cole Normale Sup{\' e}rieure}, Troisi\`eme S\'erie, 65: 239 -- 276, 1948. \bibitem{K} G. O. H. Katona. \newblock A generalization of some generalizations of Sperner's theorem. \newblock \textit{J. Combinatorial Theory B}, 12: 72 -- 81, 1972. \bibitem{PR} M. Pouzet and I. G. Rosenberg. \newblock Sperner properties for groups and relations. \newblock {\it Europ. J. Combinatorics}, 7: 349 -- 370, 1986. \bibitem{RPS} R. P. Stanley. \newblock Weyl groups, the hard Lefschetz theorem, and the Sperner property. \newblock {\it SIAM J. Alg. Disc. Meth.}, 1: 168 -- 184, 1980. \bibitem{RPS2} R. P. Stanley. \newblock Some aspects of groups acting on finite posets. \newblock {\it J. Combinatorial Theory A}, 32: 132 -- 161, 1982. \bibitem{RPS3} R. P. Stanley. \newblock Quotients of Peck posets. \newblock {\it Order}, 1: 29 -- 34, 1984. \end{thebibliography} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%