# Transitive generalized toggle groups containing a cycle

Jonathan S. Bloom
Dan Saracino

###### Abstract

In [9] Striker generalized Cameron and Fon-Der-Flaass’s notion of a toggle
group. In this paper we begin the study of transitive generalized toggle
groups that contain a cycle. We first show that if such a group has degree $n$
and contains a transposition or a 3-cycle then the group contains $A_{n}$.
Using the result about transpositions, we then prove that a transitive
generalized toggle group that contains a short cycle must be primitive.
Employing a result of Jones [8], which relies on the classification of the
finite simple groups, we conclude that any transitive generalized toggle group
of degree $n$ that contains a cycle with at least 3 fixed points must also
contain $A_{n}$. Finally, we look at imprimitive generalized toggle groups
containing a long cycle and show that they decompose into a direct product of
primitive generalized toggle groups each containing a long cycle.

##  1 Introduction

The study of toggle groups dates back to the 1995 work [1] of Cameron and Fon-
Der-Flaass on order ideals of posets. To provide a simpler proof of a result
from [4], Cameron and Fon-Der-Flaass associated to each element $p$ of a
finite poset $P$ a permutation $s_{p}$ of the set $J(P)$ of order ideals of
$P$. For each $I\in J(P)$, $s_{p}(I)$ was defined to be
$I\triangle\left\\{p\right\\}$ if $I\triangle\left\\{p\right\\}\in J(P)$, and
$s_{p}(I)=I$ otherwise. After using the $s_{p}$’s to achieve their proof, they
went on to study the subgroup $G(P)=\langle s_{p}\ |\ p\in P\rangle$ of the
symmetric group $S_{J(P)}$. They proved [1, Theorem 4] that if the Hasse
diagram of $P$ is connected then $G(P)$ contains the alternating group on
$J(P)$, while if $P$ is the disjoint union of posets $P_{1}$ and $P_{2}$ then
$G(P)\cong G(P_{1})\times G(P_{2})$.

In [10] Striker and Williams used the $s_{p}$’s in studying what they called
“promotion” and “rowmotion” on order ideals. They called the $s_{p}$’s
_toggles_ and $G(P)$ the _toggle group_. Several other papers soon followed
[3, 5, 6] that used analogues of the $s_{p}$’s in different contexts. In [9]
Striker noted that the definition of the $s_{p}$’s only relied on the order
ideals of $P$ being subsets of $P$, and generalized the definition of the
toggle group.

######  Definition 1.1.

Let $E$ be a finite set, which we refer to as the _ground set_. Let ${\cal L}$
be a set of subsets of $E$. For each $e\in E$, define the _toggle_
$\tau_{e}:{\cal L}\rightarrow{\cal L}$ by letting
$\tau_{e}(X)=X\triangle\left\\{e\right\\}$ if
$X\triangle\left\\{e\right\\}\in{\cal L}$ and $\tau_{e}(X)=X$ otherwise. The
_generalized toggle group_ $T({\cal L})$ is the subgroup of the symmetric
group $S_{{\cal L}}$ generated by $\left\\{\tau_{e}\,|\,e\in E\right\\}$.

Striker initiated the study of $T({\cal L})$ for a number of combinatorially
interesting choices of ${\cal L}$. In particular, she obtained analogs of [1,
Theorem 4], for several examples where ${\cal L}$ is a set of subsets of a
finite poset or graph.

In what follows, we head in a somewhat different direction. There is a long
history of results about primitive permutation groups that contain a
nontrivial cycle, dating back to the work of Jordan in the 1870’s. We will
prove some structure results for all transitive generalized toggle groups that
contain a nontrivial cycle. In Section 3 we will show that if $T({\cal L})$ is
transitive with degree $n$ and contains a transposition then $T({\cal L})$
must be the full symmetric group $S_{n}$, and if $T({\cal L})$ is transitive
with degree $n$ and contains a 3-cycle then $T({\cal L})$ must contain the
alternating group $A_{n}$. These results are analogues of standard results [2,
Theorem 3.3A] for primitive permutation groups, but we will obtain them for
transitive generalized toggle groups without assuming primitivity. Using the
result for transpositions, we will then show that if $T({\cal L})$ is
transitive with degree $n$ and contains a “short cycle” (i.e., a cycle of
length at most $n-1$), then $T({\cal L})$ is primitive. Using [8, Corollary
1.3] (a result that relies on the classification of the finite simple groups)
it will then follow that if $T({\cal L})$ contains a cycle with at least three
fixed points then $T({\cal L})$ contains $A_{n}$.

In Section 4 we will show that if $T({\cal L})$ is imprimitive and contains a
nontrivial cycle (necessarily a “long cycle” of length $n$) then $T({\cal L})$
is isomorphic to a direct product of primitive groups $T({\cal
L}_{1})\times\cdots\times T({\cal L}_{k})$ where each $T({\cal L}_{i})$ has
degree at least two and contains a long cycle whose length is the degree of
$T({\cal L}_{i})$.

In obtaining the results of Section 4 we will use what Striker [9] calls the
“toggle-disjoint Cartesian product” of sets ${\cal L}_{1}$ and ${\cal L}_{2}$.

######  Definition 1.2.

If $E_{1}$ and $E_{2}$ are disjoint ground sets and ${\cal L}_{i}\subseteq
2^{E_{i}}$ for $i=1,2$ then we say _${\cal L}$ is the toggle-disjoint
Cartesian product of ${\cal L}_{1}$ and ${\cal L}_{2}$_ and write ${\cal
L}={\cal L}_{1}\otimes{\cal L}_{2}$ if ${\cal L}=\left\\{X_{1}\cup
X_{2}\,|\,X_{i}\in{\cal L}_{i}\right\\}$.

Striker makes this definition under an assumption weaker than $E_{1}\cap
E_{2}=\emptyset$, but we will only use it when $E_{1}\cap E_{2}=\emptyset$. It
is straightforward to check [9, Theorem 2.18] that if ${\cal L}$ is the
toggle-disjoint Cartesian product of ${\cal L}_{1}$ and ${\cal L}_{2}$ then
$T({\cal L})\cong T({\cal L}_{1})\times T({\cal L}_{2})$.

######  Conventions.

It may happen that for some elements $e\in E$, $\tau_{e}$ is the identity
element of the symmetric group on ${\cal L}$. Since we will always be assuming
that $T({\cal L})$ is transitive in what follows, this can only happen if $e$
is in all or none of the sets in ${\cal L}$. We will always remove such $e$’s
from $E$. Doing this has no effect on $T({\cal L})$.

To simplify terminology we shall refer to generalized toggle groups simply as
toggle groups.

##  2 Block systems in toggle groups

Recall that if a group $G$ acts on a set $X$ then we say a subset ${\cal
B}\subseteq X$ is a _block_ for $G$ if, for all $g\in G$, either $g({\cal
B})={\cal B}$ or $g({\cal B})$ is disjoint from ${\cal B}$. If $G$ acts
transitively on $X$ and ${\cal B}$ is a block for $G$ then the sets
$\left\\{g({\cal B})\,|\,g\in G\right\\}$ form a partition of $X$. We call
such a partition a _block system_ for $G$. Clearly, the blocks in a given
block system must all have the same size. If there exists a block system for
which this size is strictly between 1 and $|X|$ then the group action is said
to be _imprimitive_ , and otherwise the action is said to be _primitive_. A
good source for background information on these ideas is [2, Chapter 1].

The purpose of this section is to explore how toggles behave on a block
system. In particular, the lemmas established in this section describe a rich
structure in the context of imprimitive toggle groups. We then exploit this
structure in the following sections.

Recall that, as in the introduction, $E$ is our finite ground set, ${\cal L}$
is a collection of subsets of $E$ and $T({\cal L})$ is the corresponding
toggle group. We assume throughout that $T({\cal L})$ acts transitively on
${\cal L}$, and we fix a system of blocks for $T({\cal L})$. We often denote
individual blocks by ${\cal B}$ or ${\cal C}$.

######  Definition 2.1.

We say that $g\in T({\cal L})$ is _type 2_ if $g({\cal B})={\cal B}$ for all
blocks ${\cal B}$, and that $g$ is _type 1_ otherwise.

######  Lemma 2.2.

Let $\tau_{y}$ be a type 1 toggle in $T({\cal L})$.

  1. i)

If $\tau_{y}({\cal B})={\cal B}$ for some block ${\cal B}$ then $\tau_{y}$ is
the identity on this block.

  2. ii)

$\tau_{y}$ commutes with all type 2 toggles in $T({\cal L})$.

  3. iii)

For any type 2 toggle $\tau$ and blocks ${\cal B},{\cal C}$, the cycle
structure of $\tau|_{{\cal B}}$ is the same as the cycle structure of
$\tau|_{{\cal C}}$.

###### Proof.

We prove i) by contradiction. Suppose that for some $A\in{\cal B}$ we have
$A,A\triangle\left\\{y\right\\}\in{\cal B}$. By definition of $\tau_{y}$ there
exists another block ${\cal C}\neq{\cal B}$. By transitivity there exist
toggles $\tau_{z_{1}},\ldots,\tau_{z_{k}}$ such that
$\tau_{z_{k}}\cdots\tau_{z_{1}}({\cal B})={\cal C}$. Let ${\cal B}_{0}={\cal
B}$ and ${\cal B}_{i}=\tau_{z_{i}}({\cal B}_{i-1})$. By omitting some
$\tau_{i}$’s we can assume that ${\cal B}_{i}\neq{\cal B}_{i-1}$. Then
$A\triangle\left\\{z_{1}\right\\},A\triangle\left\\{y,z_{1}\right\\}\in{\cal
B}_{1}$ and hence
$\tau_{y}(A\triangle\left\\{z_{1}\right\\})=A\triangle\left\\{z_{1},y\right\\}\in{\cal
B}_{1}$. So $\tau_{y}({\cal B}_{1})={\cal B}_{1}$. By iterating this argument
we can show that $\tau_{y}({\cal C})={\cal C}$. Since ${\cal C}$ was an
arbitrary block distinct from ${\cal B}$, it follows that $\tau_{y}$ is type
2, a contradiction.

To prove ii) let $\tau_{x}$ be a type 2 toggle and fix a block ${\cal B}$. If
$\tau_{y}({\cal B})={\cal B}$ then by i) it is clear that $\tau_{x}$ and
$\tau_{y}$ commute at all elements of ${\cal B}$. So we may assume that
$\tau_{y}({\cal B})={\cal C}$ where ${\cal B}\neq{\cal C}$. Fix $A\in{\cal B}$
so that $A\triangle\left\\{y\right\\}=\tau_{y}(A)\in{\cal C}$. If
$\tau_{x}(A)=A$ then $A\triangle\left\\{x\right\\}\not\in{\cal B}$ (since
$A\triangle\left\\{x\right\\}\not\in{\cal L}$) and hence
$A\triangle\left\\{x,y\right\\}\notin{\cal C}$. So

$\tau_{y}\tau_{x}(A)=\tau_{y}(A)=A\triangle\left\\{y\right\\}=\tau_{x}(A\triangle\left\\{y\right\\})=\tau_{x}\tau_{y}(A),$

where the third equality follows from the fact that $\tau_{x}$ is type 2 so
that $\tau_{x}(A\triangle\left\\{y\right\\})$ must be in ${\cal C}$. So if
$\tau_{x}(A)=A$ then $\tau_{x}$ and $\tau_{y}$ commute at $A$. If
$\tau_{x}(A)=A\triangle\left\\{x\right\\}$ then
$A\triangle\left\\{x\right\\}\in{\cal B}$ and therefore
$\tau_{y}\tau_{x}(A)=A\triangle\left\\{x,y\right\\}=\tau_{x}\tau_{y}(A)$.

To prove iii) consider a type 2 toggle $\tau$ and blocks ${\cal B},{\cal C}$.
As in the proof of i) it suffices by transitivity to prove the claim in the
case where $\tau_{y}({\cal B})={\cal C}$. If we write $\tau$ as the product of
its block restrictions we have

$\tau=\cdots\tau|_{\cal B}\cdots\tau|_{\cal C}\cdots.$

Conjugating by $\tau_{y}$ gives

$\tau_{y}\tau\tau_{y}=\cdots(\tau_{y}\tau|_{\cal
B}\tau_{y})\cdots(\tau_{y}\tau|_{\cal C}\tau_{y})\cdots$

and we note that $\tau_{y}\tau|_{{\cal C}}\tau_{y}$ is a permutation of ${\cal
B}$. Consequently

$\tau_{y}\tau|_{{\cal C}}\tau_{y}=(\tau_{y}\tau\tau_{y})|_{{\cal
B}}=\tau|_{\cal B},$

where the last equality follows by part ii) and the fact that $\tau_{y}$ is
type 1. Since conjugation preserves cycle structure the result is now clear. ∎

######  Lemma 2.3.

Let $\rho\in T({\cal L})$ be a product of type 2 toggles. If $\rho$ fixes all
elements, pointwise, in some block ${\cal B}$ then $\rho=1$.

###### Proof.

If ${\cal B}$ is the only block we are done. Otherwise, transitivity implies
that there must be some type 1 toggle $\tau$ such that $\tau({\cal B})={\cal
C}$ with ${\cal B}\neq{\cal C}$. It follows by Lemma 2.2 that $\tau$ and
$\rho$ commute. Fix $C\in{\cal C}$ and let $B=\tau(C)\in{\cal B}$. Since
$\tau$ is an involution we have

$\rho(C)=\rho\tau(B)=\tau\rho(B)=\tau(B)=C.$

Hence $\rho$ fixes all elements in ${\cal C}$. As in the proof of the first
part of the preceding lemma, iterating this argument implies that $\rho=1$. ∎

######  Lemma 2.4.

Let $\sigma\in T({\cal L})$ be a product of type 1 toggles. For each block
${\cal B}$ there exists some set $X\subseteq E$ such that for each $A\in{\cal
B}$ we have

$\sigma(A)=A\triangle X.$

In particular, if $\sigma({\cal B})={\cal B}$ then $\sigma|_{{\cal B}}$ is
either the identity or an involution with no fixed points.

###### Proof.

Let $\sigma=\tau_{x_{k}}\cdots\tau_{x_{1}}$ where each $\tau_{x_{i}}$ is a
type 1 toggle. Set ${\cal B}_{0}={\cal B}$ and let ${\cal
B}_{i}=\tau_{x_{i}}({\cal B}_{i-1})$. By the first part of Lemma 2.2 we may
assume ${\cal B}_{i}\neq{\cal B}_{i-1}$. It then follows that

${\cal B}_{i}=\left\\{A\triangle\left\\{x_{i}\right\\}\,|\,A\in{\cal
B}_{i-1}\right\\}.$

Defining $X$ to be the set of all the $x_{i}$ that appear an odd number of
times in $x_{1},\ldots,x_{k}$ it further follows that $\sigma(A)=A\triangle X$
for every $A\in{\cal B}$. This proves our first claim. The second claim
follows since $\sigma$ is now seen to act by symmetric difference with a fixed
set $X$, on all of ${\cal B}$. ∎

######  Lemma 2.5.

Let $X$ and $Y$ be disjoint subsets of $E$ and define
$\sigma=\tau_{x_{1}}\cdots\tau_{x_{m}}$ and
$\rho=\tau_{y_{1}}\cdots\tau_{y_{\ell}}$ where $x_{i}\in X,\ y_{j}\in Y$. For
all $A\in{\cal L}$ we have $\sigma(A)=\rho(A)$ if and only if
$\sigma(A)=A=\rho(A)$.

###### Proof.

The reverse direction is clear. Now assume $\sigma(A)=\rho(A)$. For some
$S\subseteq X$ and $T\subseteq Y$ we have

$A\triangle S=\sigma(A)=\rho(A)=A\triangle T.$

(Note that the subsets $S$ and $T$ may be dependent on $A$.) As $X$ and $Y$
are disjoint this can only occur if $S=T=\emptyset$, and the forward direction
follows. ∎

######  Lemma 2.6.

Let $E_{1}=\left\\{x\in E\,|\,\tau_{x}\text{ is type 1}\right\\}$,
$E_{2}=\left\\{y\in E\,|\,\tau_{y}\text{ is type 2}\right\\}$ and set ${\cal
L}_{i}=\left\\{A\cap E_{i}\,|\,A\in{\cal L}\right\\}$.

Suppose $T({\cal L})$ is such that any product $\sigma$ of type 1 toggles has
the property that if $\sigma({\cal B})={\cal B}$, for some block ${\cal B}$,
then $\sigma(A)=A$ for all $A\in{\cal B}$. Then ${\cal L}={\cal
L}_{1}\otimes{\cal L}_{2}$ where $|{\cal L}_{1}|$ is the number of blocks and
$|{\cal L}_{2}|$ is the size of each block.

###### Proof.

Fix $A\in{\cal L}$ and define ${\cal O}(A)$ to be the orbit containing $A$
under the group generated by all type 1 toggles. As $T({\cal L})$ is
transitive it follows that for any two blocks there is a product of type 1
toggles that maps one to the other. As a result ${\cal O}(A)$ contains at
least one set from each block. On the other hand if $B,B^{\prime}\in{\cal
O}(A)$ are in the same block it follows by our assumption about type 1 toggles
that $B=B^{\prime}$. So ${\cal O}(A)$ contains exactly one set from each
block. Consequently for a fixed block ${\cal B}$ we have the disjoint union

${\cal L}=\bigcup_{A\in{\cal B}}{\cal O}(A).$

We call the sets ${\cal O}(A)$ _layers_.

If $A\neq B$ are elements of the same block ${\cal B}$ then by transitivity,
the second part of Lemma 2.2 and the fact that ${\cal O}(A)$ contains exactly
one set from each block, it follows that for some product $\rho$ of type 2
toggles we have $\rho(A)=B$. From this we see that

$A\cap E_{1}=B\cap E_{1}\text{ and }A\cap E_{2}\neq B\cap E_{2}.$

On the other hand, if $A\neq C$ are elements in the same layer then

$A\cap E_{1}\neq C\cap E_{1}\text{ and }A\cap E_{2}=C\cap E_{2}.$

So all the sets in ${\cal O}(A)$ have different intersections with $E_{1}$ and
every set $D\in{\cal L}$ has the same intersection with $E_{1}$ as some set in
${\cal O}(A)$ since $D$ is in the same block as some set in ${\cal O}(A)$.
Thus $|{\cal L}_{1}|=|{\cal O}(A)|$ is the number of blocks ${\cal B}_{i}$,
since ${\cal O}(A)$ contains exactly one set from each block. Since all sets
in ${\cal O}(A)$ have the same intersection with $E_{2}$ we have

${\cal O}(A)={\cal L}_{1}\otimes\\{A\cap E_{2}\\}.$

So we have

${\cal L}=\bigcup_{A\in{\cal B}}{\cal O}(A)=\bigcup_{A\in{\cal B}}{\cal
L}_{1}\otimes\\{A\cap E_{2}\\}={\cal L}_{1}\otimes{\cal L}_{2},$

since every set in ${\cal L}$ is in the same layer as some set in ${\cal B}$,
hence has the same intersection with $E_{2}$. The last equality further shows
that $|{\cal L}_{2}|$ is the size of each block as claimed. ∎

######  Lemma 2.7.

Let $T({\cal L})$ be imprimitive with a system of blocks of imprimitivity
${\cal B}_{i}$. If the block size is odd, then ${\cal L}$ is a toggle-disjoint
Cartesian product of sets each of which has at least two elements.

###### Proof.

To apply Lemma 2.6, suppose $\sigma$ is a product of type 1 toggles such that
$\sigma({\cal B}_{i})={\cal B}_{i}$ for some $i$. By Lemma 2.4 it follows that
$\sigma|_{{\cal B}_{i}}$ is either an involution with no fixed points or the
identity. Since the blocks ${\cal B}_{i}$ have odd size we see that
$\sigma|_{{\cal B}_{i}}$ is the identity. Lemma 2.6 completes the proof. ∎

######  Lemma 2.8.

Let $T({\cal L})$ be imprimitive with a system of blocks of imprimitivity
${\cal B}_{i}$. Assume there exists some $\sigma$, a product of type 1
toggles, such that $\sigma({\cal B}_{i})={\cal B}_{i}$ and $\sigma|_{{\cal
B}_{i}}\neq 1$ for some ${\cal B}_{i}$. Then $\tau|_{{\cal B}_{j}}$ is an even
permutation for all type 2 toggles $\tau$ and all blocks ${\cal B}_{j}$.

Consequently, if for some ${\cal B}_{i}$ there exists a type 2 toggle $\tau$
such that $\tau|_{{\cal B}_{i}}$ is odd, then ${\cal L}$ is a toggle-disjoint
Cartesian product of two sets each of which has at least two elements.

###### Proof.

Let ${\cal B}_{i}$ and $\sigma$ be as stated. As $\sigma|_{{\cal B}_{i}}\neq
1$, Lemma 2.4 implies that $\sigma|_{{\cal B}_{i}}$ is an involution with no
fixed points. Define a partition on ${\cal B}_{i}$ so that elements $A$ and
$B$ are in the same class if and only if $\sigma(A)=B$. Denote the classes in
this partition by ${\cal C}_{j}$ and observe that $|{\cal C}_{j}|=2$. As
$\sigma$ is a product of type 1 toggles, it follows from Lemma 2.2 that any
type 2 toggle commutes with $\sigma$. Consequently, the ${\cal C}_{j}$ form a
block system for the restriction to ${\cal B}_{i}$ of the group $G$ generated
by all the type 2 toggles. By Lemma 2.5 we see that any type 2 toggle $\tau$
restricted to ${\cal B}_{i}$ can either have $\tau({\cal C}_{j})={\cal C}_{k}$
with $j\neq k$ or $\tau|_{{\cal C}_{j}}=1$. As each $C_{j}$ has size 2 this
implies that the restriction to ${\cal B}_{i}$ of any type 2 toggle is an even
permutation. By the third part of Lemma 2.2, this proves our first claim.

The proof of our second claim is now immediate by Lemma 2.6. ∎

##  3 Transitive toggle groups containing short cycles

Throughout this section we continue to assume that $T({\cal L})$ is
transitive. The _degree_ of $T({\cal L})$ is the number of elements in the set
${\cal L}$.

The first two theorems of this section state that if $T({\cal L})$ has degree
$n$ and contains a transposition then $T({\cal L})$ is $S_{n}$, and if
$T({\cal L})$ has degree $n$ and contains a 3-cycle then $T({\cal L})$
contains $A_{n}$. These two theorems echo well-known results of Jordan for
primitive permutation groups (see [2, Theorem 3.3A] or [7, Theorem 8.17,
Corollary 8.19]). Interestingly, in the toggle-group case we do not need to
assume the groups are primitive but instead we obtain that as a consequence.

######  Theorem 3.1.

Assume that $T({\cal L})$ has degree $n$ and contains a transposition. Then
$T({\cal L})\cong S_{n}$.

###### Proof.

We define an equivalence relation $\sim$ on ${\cal L}$ by letting $A\sim B$ if
and only if either $A=B$ or else $(A,B)\in T({\cal L})$. Since conjugating
$(A,B)$ by $(B,C)$ yields $(A,C)$, it is easy to check that $\sim$ is an
equivalence relation. Likewise, conjugating $(A,B)$ by any $g\in T({\cal L})$
yields $(g(A),g(B))$, so the equivalence classes of $\sim$ constitute a system
of blocks for $T({\cal L})$. For the remainder of the proof we fix this system
of blocks and denote the blocks by ${\cal B}_{1},\ldots,{\cal B}_{m}$.

We prove the theorem by showing that $m=1$ (which implies that $T({\cal L})$
contains all transpositions). By assumption we have $(A,B)\in T({\cal L})$ for
some $A,B\in{\cal L}$, and we can suppose without loss of generality that
$A,B\in{\cal B}_{1}$. By the second part of Lemma 2.2 we can express

$(A,B)=\underbrace{\tau_{y_{1}}\cdots\tau_{y_{k}}}_{\sigma}\underbrace{\tau_{x_{1}}\cdots\tau_{x_{\ell}}}_{\rho}$

where the $\tau_{y_{j}}$ are type 1 and the $\tau_{x_{i}}$ are type 2. By
squaring both sides we obtain

$1=\sigma^{2}\rho^{2}.$

As $\\{x_{1},\ldots,x_{m}\\}\cap\\{y_{1},\ldots,y_{\ell}\\}=\emptyset$, Lemma
2.5 implies that $\sigma^{2}=\rho^{2}=1$.

Assume for a contradiction that $m>1$, and let $C\in{\cal B}_{2}$. As
$(A,B)=\sigma\rho$ we must have $\sigma\rho(C)=C$. As $\sigma^{2}=1$ it
follows that $\rho(C)=\sigma(C)$. By Lemma 2.5 then $\rho(C)=C=\sigma(C)$ for
all $C\in{\cal B}_{2}$. So $\rho$, a product of type 2 toggles, fixes ${\cal
B}_{2}$ pointwise. Hence by Lemma 2.3, $\rho=1$ and $\sigma=(A,B)$. Now if
each block has even size then it follows from the first part of Lemma 2.2 that
each $\tau_{y_{i}}$ is an even permutation, contradicting $\sigma=(A,B)$. So
each block has odd size. As $\sigma({\cal B}_{1})={\cal B}_{1}$ it follows by
the second claim in Lemma 2.4 that $\sigma|_{{\cal B}_{1}}=1$, contradicting
the fact that $\sigma=(A,B)$. We conclude that $m=1$ as needed. ∎

######  Theorem 3.2.

Assume $T({\cal L})$ has degree $n$ and contains a 3-cycle. Then $A_{n}\leq
T({\cal L})$.

###### Proof.

We define an equivalence relation $\sim$ on ${\cal L}$ by letting $A\sim B$ if
and only if either $A=B$ or else $(A,B,C)\in T({\cal L})$ for some $C$. Using
the fact that $(A,B,C)^{2}=(B,A,C)$, it is easy to check, as in the preceding
proof, that $\sim$ is an equivalence relation, and that the equivalence
classes of $\sim$ constitute a system of blocks for $T({\cal L})$. We again
denote the blocks by ${\cal B}_{1},\ldots,{\cal B}_{m}$.

To prove the theorem it suffices to show that $T({\cal L})$ must contain all
3-cycles or, equivalently, that $m=1$. To see that this suffices, suppose
$m=1$ and let $A,B,C$ be distinct elements of ${\cal L}$. We claim that
$(A,B,C)\in T({\cal L})$. Since $m=1$ we have $A\sim B$, so $(A,B,D)\in
T({\cal L})$ for some $D\neq A,B$. If $D=C$ we are done. Otherwise, $D\neq C$
and since $m=1$ we must have a 3-cycle $(D,C,E)\in T({\cal L})$. If $E\neq
A,B$ we are done by conjugating $(A,B,D)$ by $(D,C,E)$. If $E=A$ then we have
$(A,B,C)=(D,C,A)(A,B,D)\in T({\cal L})$. If $E=B$ we have
$(A,B,C)=(A,B,D)(D,C,B)^{2}\in T({\cal L})$.

We now show that $m=1$. By assumption we have a 3-cycle $(A,B,C)$ in $T({\cal
L})$, and without loss of generality we can suppose that $A,B\in{\cal B}_{1}$
and therefore $C\in{\cal B}_{1}$ since $(A,B,C)$ maps $A$ and $B$ into the
same block. By Lemma 2.2 we can write

$(A,B,C)=\underbrace{\tau_{y_{1}}\cdots\tau_{y_{k}}}_{\sigma}\underbrace{\tau_{x_{1}}\cdots\tau_{x_{\ell}}}_{\rho}$

where the $\tau_{y_{j}}$ are type 1 and the $\tau_{x_{i}}$ are type 2.

For a contradiction assume $m>1$ and let $D\in{\cal B}_{i}$ where $i\neq 1$.
As $(A,B,C)=\sigma\rho$ we have $\sigma\rho(D)=D$ and hence
$\rho(D)=\sigma^{-1}(D)$. By Lemma 2.5 we conclude that $\rho(D)=D$. As $D$ is
an arbitrary element of ${\cal B}_{i}$ then $\rho$ is the identity on ${\cal
B}_{i}$. By Lemma 2.3 it follows that $\rho=1$. So $\sigma=(A,B,C)$. But then
Lemma 2.4 forces $\sigma^{2}=1$, a contradiction. We conclude that $m=1$ as
needed. ∎

In addition to the results that motivated Theorem 3.1 and Theorem 3.2, Jordan
also proved that if a primitive permutation group $G$ of degree $n$ contains a
cycle of prime length $p\leq n-3$ then $A_{n}\leq G$ (see [2, Theorem 3.3E] or
[7, Theorem 8.23]). Much more recently, Jones, in [8, Corollary 1.3], removed
the assumption that the length of the cycle be prime in Jordan’s result. To
obtain an analogue of Jones’ result for toggle groups (as opposed to primitive
permutation groups), we will combine Jones’ result with the following.

######  Theorem 3.3.

Suppose $T({\cal L})$ has degree $n$ and contains a nontrivial cycle $\gamma$
of length $\leq n-1$. Then $T({\cal L})$ is primitive.

###### Proof.

Suppose not, and take a system of blocks of imprimitivity for $T({\cal L})$.
Note that if two points of ${\cal L}$ are in the same block then so are their
images under $\gamma$, so if one point moved by $\gamma$ is in the same block
as a fixed point of $\gamma$ then all points moved by $\gamma$ are in that
block.

We first consider the case when all points moved by $\gamma$ are in a block
${\cal B}$ that contains a fixed point of $\gamma$. We know there are blocks
other than ${\cal B}$, and each of these other blocks consists entirely of
fixed points of $\gamma$. Let ${\cal C}$ be any one of these other blocks. If
we write $\gamma=\sigma\rho$ with $\sigma$ a product of type 1 toggles and
$\rho$ a product of type 2 toggles, then we can argue as we have before that
$\rho$ must fix every point of ${\cal C}$, and therefore $\rho=1$ by Lemma
2.3. Therefore $\gamma=\sigma$, and $\gamma$ maps ${\cal B}$ to itself. By
Lemma 2.4, $\gamma^{2}=1$, so $\gamma$ is a transposition. By Theorem 3.1,
$T({\cal L})$ is $S_{n}$, so since $T({\cal L})$ has degree $n$, $T({\cal L})$
is primitive.

We now consider the case when no points moved by $\gamma$ are in the same
block as any fixed point of $\gamma$. We first show that in this case each
block has even size. If not, then there is a block ${\cal B}$ of odd size
$|{\cal B}|>1$ consisting of points moved by $\gamma$, and there is a block
${\cal C}$ consisting of fixed points of $\gamma$ (since $\gamma$ has length
$\leq n-1$). As in the first case, we write $\gamma=\sigma\rho$ and use the
existence of the block ${\cal C}$ to show that $\rho=1$ and $\gamma=\sigma$.
If we choose $A\neq B$ in ${\cal B}$ then there exists a positive integer $m$
such that $\gamma^{m}(A)=B$, and therefore $\gamma^{m}$ maps ${\cal B}$ to
${\cal B}$. Since $\gamma^{m}=\sigma^{m}$, a product of type 1 toggles, Lemma
2.4 implies that $\gamma^{m}|_{{\cal B}_{i}}$ is either an involution with no
fixed points or the identity. Since the blocks have odd size we see that
$\sigma|_{{\cal B}_{i}}$ is the identity. But this is impossible, since
$\gamma^{m}(A)=B$ where $A\neq B$.

So we know the blocks have even size. Since the elements moved by $\gamma$
comprise a set of blocks, $\gamma$ has even length, hence is an odd
permutation. But the fact that the blocks have even size also implies, by the
first part of Lemma 2.2, that every type 1 toggle is an even permutation.
Since $\gamma=\sigma$ is a product of type 1 toggles, $\gamma$ is an even
permutation. This contradiction concludes the proof.

∎

######  Corollary 3.4.

If $T({\cal L})$ has degree $n$ and contains a nontrivial cycle of length
$\leq n-3$ then $A_{n}\leq T({\cal L})$.

###### Proof.

By Theorem 3.3, $T({\cal L})$ is primitive, so the corollary follows from [8,
Corollary 1.3], which states, among other things, that if $G$ is a primitive
permutation group of degree $n$ that contains a nontrivial cycle with at least
three fixed points, then $A_{n}\leq G$.

∎

Corollary 3.4 provides an alternate proof of Theorem 3.2 if we check
separately the cases $n\leq 5$. But Corollary 3.4 relies on [8, Corollary
1.3], which depends on the classification of the finite simple groups.

##  4 Imprimitive toggle groups containing long cycles

We have shown that a toggle group that contains a short cycle must be
primitive. Therefore, if an imprimitive toggle group contains a cycle that
cycle can only be a long cycle. In this section we study imprimitive toggle
groups that contain a long cycle.

######  Lemma 4.1.

Let $E_{1},E_{2}$ be disjoint ground sets and let ${\cal L}_{i}\subseteq
2^{E_{i}}$ be such that $|{\cal L}_{i}|\geq 2$ for $i=1,2$. Set $\ell=|{\cal
L}_{1}|$ and $m=|{\cal L}_{2}|$ and ${\cal L}={\cal L}_{1}\otimes{\cal
L}_{2}$. Then $T({\cal L})$ contains a long cycle if and only if $(\ell,m)=1$
and both $T({\cal L}_{1})$ and $T({\cal L}_{2})$ contain long cycles.

###### Proof.

Let ${\cal L}_{1}=\\{A_{1},\ldots,A_{\ell}\\}$ and ${\cal
L}_{2}=\\{B_{1},\ldots,B_{m}\\}$. Consider the block system given by the
blocks

${\cal C}_{i}=\left\\{A_{i}\cup B_{j}\,|\,B_{j}\in{\cal L}_{2}\right\\},$

so that the type 1 toggles are precisely $\tau_{x}$ for $x\in E_{1}$ and the
type 2 toggles are precisely $\tau_{y}$ for $y\in E_{2}$. (Recall that, by the
convention we adopted at the outset, no $\tau_{x}$ or $\tau_{y}$ is the
identity.) Note that $|{\cal C}_{i}|\geq 2$ for all ${\cal C}_{i}$.

Suppose $T({\cal L})$ contains a long cycle $\gamma$. Fix a block ${\cal C}$.
Since $|{\cal C}|\geq 2$ and $\gamma$ is a long cycle, there exists a smallest
positive integer $a$ such that $\gamma^{a}$ maps a point of ${\cal C}$ into
${\cal C}$. Choose $X\in{\cal C}$ such that $\gamma^{a}(X)\in{\cal C}$. By our
choice of $a$, it follows that
$X,\gamma(X),\gamma^{2}(X),\ldots,\gamma^{(a-1)}(X)$ must all be in distinct
blocks and so $a\leq\ell$. Further observe that $\gamma^{ka}(X)\in{\cal C}$
for all $k$. If we write $\ell m=ka+r$, with $0\leq r<a$, then
$\gamma^{r}(\gamma^{ka}(X))=X\in{\cal C}$ since $\gamma$ is an $\ell m$-cycle.
Since $0\leq r<a$ we must have $r=0$ by our choice of $a$. So $a|\ell m$.
Again since $\gamma$ is an $\ell m$-cycle, we see that
$\gamma^{a}(X),\gamma^{2a}(X)\ldots,\gamma^{\ell m}(X)$ are distinct and in
${\cal C}$. As $|{\cal C}|=m$ have $\ell m/a\leq m$, so $\ell\leq a$ and
therefore $\ell=a$ and we have

$\gamma^{\ell}=\gamma_{1}\cdots\gamma_{\ell},$

where $\gamma_{i}$ is a long cycle on block ${\cal C}_{i}$.

Now, using Lemma 2.2, write $\gamma=\sigma\rho$ where $\sigma$ is a product of
type 1 toggles and $\rho$ is a product of type 2 toggles. Since $\sigma$ and
$\rho$ commute we have $\gamma^{\ell}=\sigma^{\ell}\rho^{\ell}$, and since
$\gamma^{\ell}$ and $\rho^{\ell}$ are type 2 permutations so is
$\sigma^{\ell}$. Since $\sigma^{\ell}$ is a product of type 1 toggles and
${\cal L}$ is a toggle-disjoint Cartesian product it follows that
$\sigma^{\ell}=1$. So

$\gamma_{1}\cdots\gamma_{\ell}=\rho^{\ell}.$

Restricting our attention to a fixed block ${\cal C}_{i}$ we see that
$\rho^{\ell}|_{{\cal C}_{i}}=\gamma_{i}$. Since $\gamma_{i}$ is a long cycle
on this block it follows that $\rho|_{{\cal C}_{i}}$ must be a long cycle on
${\cal C}_{i}$ and that $(m,\ell)=1$. It is now immediate that $T({\cal
L}_{2})$ must contain a long cycle as well. By repeating this argument with
the block system

${\cal C}_{i}^{\prime}=\left\\{B_{i}\cup A_{j}\,|\,A_{j}\in{\cal
L}_{1}\right\\}$

we conclude that $T({\cal L}_{1})$ must also have a long cycle as claimed.

Let us now consider the converse. Suppose $(m,\ell)=1$ and $T({\cal L}_{1})$
and $T({\cal L}_{2})$ have long cycles $\gamma$ and $\delta$, respectively.
Note that $\gamma$ and $\delta$ have orders $\ell$ and $m$, respectively.
Label the sets in ${\cal L}$ by $(i,j)$ for $1\leq i\leq\ell,\ 1\leq j\leq m$
and observe that $T({\cal L})$ contains permutations

$\gamma^{\prime}(i,j):=(\gamma(i),j)$

and

$\delta^{\prime}(i,j):=(i,\delta(j))$

with orders $\ell$ and $m$, respectively. The element
$\gamma^{\prime}\sigma^{\prime}$ is a long cycle in $T({\cal L})$, because
$\gamma^{\prime}\sigma^{\prime}(1,1),\ldots,(\gamma^{\prime}\sigma^{\prime})^{\ell
m}(1,1)$ gives us all the elements of ${\cal L}$. ∎

######  Theorem 4.2.

Assume $T({\cal L})$ is imprimitive and contains a long cycle. Then ${\cal
L}={\cal L}_{1}\otimes{\cal L}_{2}$ for some ${\cal L}_{1}$ and ${\cal L}_{2}$
such that $|{\cal L}_{1}|\geq 2,\ |{\cal L}_{2}|\geq 2,\ (|{\cal
L}_{1}|,|{\cal L}_{2}|)=1$, and each of $T({\cal L}_{1})$ and $T({\cal
L}_{2})$ contains a long cycle.

###### Proof.

As $T({\cal L})$ is imprimitive, let ${\cal B}_{1},\ldots,{\cal B}_{\ell}$ be
a system of blocks of imprimitivity. Set $|{\cal B}_{i}|=m$. If $m$ is odd,
then the result follows from Lemma 2.7 and Lemma 4.1.

Now assume $m$ is even. If we replace the blocks ${\cal C}_{i}$ in the proof
of Lemma 4.1 by the ${\cal B}_{i}$’s and define $a$ as we did before, we
obtain

$\gamma^{\ell}=\gamma_{1}\cdots\gamma_{\ell},$

where $\gamma_{i}$ is a long cycle on block ${\cal B}_{i}$. We write
$\gamma=\sigma\rho$ as before and have

$\gamma_{1}\cdots\gamma_{\ell}=\gamma^{\ell}=\sigma^{\ell}\rho^{\ell}.$

Since $\gamma^{\ell}$ and $\rho^{\ell}$ are type 2 permutations, so is
$\sigma^{\ell}$.

We claim that $\sigma^{\ell}=1$. For a contradiction, assume otherwise. Lemma
2.8 then implies that every type 2 toggle is even. Since $m$ is even we also
have (using the first part of Lemma 2.2) that every type 1 toggle is even.
Therefore since $\gamma$ is product of toggles it must be even, but $\gamma$
is an $\ell m$-cycle which is odd because $m$ is even. We conclude that
$\sigma^{\ell}=1$ as claimed.

Since $\sigma^{\ell}=1$ we see that $\rho^{\ell}=\gamma^{\ell}$ which is the
long cycle $\gamma_{i}$ on each block ${\cal B}_{i}$. So $\rho$ must be a long
cycle on each block ${\cal B}_{i}$. As each block has even size $\rho|_{{\cal
B}_{i}}$ must be odd. Since $\rho$ is a product of type 2 toggles we must
have, for each ${\cal B}_{i}$, some type 2 toggle $\tau$ such that
$\tau|_{{\cal B}_{i}}$ is odd. Lemma 2.8 and Lemma 4.1 now complete the proof.
∎

######  Corollary 4.3.

Assume $T({\cal L})$ is imprimitive and contains a long cycle. Then

$T({\cal L})\cong T({\cal L}_{1})\times\cdots\times T({\cal L}_{k}),$

where each $T({\cal L}_{i})$ is primitive and contains a long cycle, their
degrees are larger than 1 and pairwise coprime, and $|{\cal L}|=|{\cal
L}_{1}|\cdots|{\cal L}_{k}|$.

###### Proof.

Apply Theorem 4.2 repeatedly.

∎

######  Corollary 4.4.

If $T({\cal L})$ is transitive, has prime-power degree, and contains a long
cycle, then $T({\cal L})$ is primitive.

###### Proof.

This is immediate from Corollary 4.3.

∎

Corollary 4.4 expresses a special property of toggle groups. For example, the
dihedral group of order eight, in its natural action on a set of order four,
contains a 4-cycle but is not primitive by [2, Theorem 4.2A(vi)], since it has
nontrivial center and is nonabelian.

In view of Theorem 3.3, Corollary 3.4 and Corollary 4.3 it would be very
interesting to have an answer to the following question: Which primitive
toggle groups of degree $n$ contain a cycle of length at least $n-2$ but do
not contain $A_{n}$? A list of all the primitive permutation groups that
contain a cycle of length at least $n-2$ but do not contain $A_{n}$ is given
in [8, Theorem 1.2]. The first groups on the list are the subgroups of the
affine group $AGL_{1}(p)$ that contain a cyclic subgroup of order $p$, and we
can show that these are not toggle groups. But at this point we do not know
the status of the other groups on the list.

## References

  * [1] Cameron, P. J., and Fon-der Flaass, D. G. Orbits of antichains revisited.  European Journal of Combinatorics 16, 6 (1995), 545–554.
  * [2] Dixon, J. D., and Mortimer, B. Permutation groups, vol. 163.  Springer Science & Business Media, 1996.
  * [3] Einstein, D., and Propp, J. Piecewise-linear and birational toggling.  Discrete Mathematics & Theoretical Computer Science, FPSAC 2014, 513–524.
  * [4] Fon-der Flaass, D. G. Orbits of antichains in ranked posets.  European journal of combinatorics 14, 1 (1993), 17–22.
  * [5] Grinberg, D., and Roby, T. Iterative properties of birational rowmotion i: generalities and skeletal posets.  The Electronic Journal of Combinatorics 23, 1 (2016), P1–33.
  * [6] Gringberg, D., and Roby, T. Iterative properties of birational rowmotion ii: rectangles and triangles.
  * [7] Isaacs, I. Finite Group Theory.  Graduate studies in mathematics. American Mathematical Society, 2008.
  * [8] Jones, G. A. Primitive permutation groups containing a cycle.  Bulletin of the Australian Mathematical Society 89, 1 (2014), 159–165.
  * [9] Striker, J. Rowmotion and generalized toggle groups.  Discrete Mathematics & Theoretical Computer Science 20, Combinatorics (2018).
  * [10] Striker, J., and Williams, N. Promotion and rowmotion.  European Journal of Combinatorics 33, 8 (2012), 1919–1942.