Schur-positive Sets

Yuval Khachatryan-Raziel
Department of Mathematics

Ph.D. Thesis
Submitted to the Senate of Bar-Ilan University

Ramat-Gan, Israel October, 2021

This work was carried out under the guidance and supervision of

Prof. Ron Adin and Prof. Yuval Roichman

Department of Mathematics

Bar-Ilan University

## Acknowledgments

I wish to express my deepest gratitude to several individuals whose
contributions have been indispensable in the completion of this journey.

Foremost, my sincere thanks go to my academic supervisors, Ron Adin and Yuval
Roichman, who guided me from the midst of my undergraduate studies up to the
completion of this PhD. They have been extremely supportive and patient,
fostering my growth both as a person and a mathematician. Their help, support
and patience have been nothing short of unparalleled, and far exceeded my
expectations.

I would also like to extend my appreciation to the professors and faculty
members at Bar-Ilan University, whose contributions were pivotal to my
development as a mathematician. Special thanks go to Uzi Vishne, Michael
Schein, Nathen Keller, Reuven Cohen, and Gidi Amir. A note of profound
gratitude must be made to the late Shmuel Dahari, who encouraged me to pursue
an advanced degree and infused me with confidence. His readiness to answer
every question will never be forgotten.

Special mention must also go to the participants of the Combinatorics Seminar
at Bar Ilan University. I am particularly grateful to Eli Bagno, Yonah
Cherniavsky, and Chaya Keller for their advice and help.

The journey would have been impossible without my friends from studies.
Special gratitude is extended to Achya Baron, Tamar Baron, Ariel Weizman,
Shira Gilat, and Adi Ben-Tsvi. A shout out to Tomer Bauer for his invaluable
assistance with TeX and Sage.

To the secretaries - Malka Bachar, Yael Madar, and Michal Davidov - for their
willingness to provide help whenever needed.

My deepest thanks go to my parents, Vardan and Varsenik Khachatryan, and my
brother, Edward Khachatryan, for their unwavering support and belief in me.

I wish to express my deepest gratitude to my wife’s family, especially my
parents-in-law, Naomi and Amram Mashraky, for their help and support during my
studies.

Lastly, but most importantly, I would like to express my deepest gratitude to
my wife, Alona. Her steadfast support and patience throughout these long years
of study have been a beacon of hope and endurance. To our children, Elisheva
Miryam, David, Tamar, Ruth Tchiya, and Yochai Meir, your presence has filled
my life with joy and purpose, motivating me to strive for success.

To anyone I may have inadvertently overlooked, please accept my sincere
apologies.

Lastly, I dedicate my thesis to the memory of my grandparents Miryam and
Edward Zilbershtein, and my uncle Andrei Zilberstein, who inspired me to
foster a love for mathematics and science from a young age.

###### Contents

  1. Abstract
  2. 1 Introduction
  3. 2 Background
    1. 2.1 Basic notation and definitions
      1. 2.1.1 Compositions and partitions
      2. 2.1.2 Permutations
    2. 2.2 Representations
    3. 2.3 Shapes and Standard Young Tableaux
    4. 2.4 Statistics on permutations and Young tableaux
    5. 2.5 Symmetric and quasi-symmetric functions
      1. 2.5.1 Symmetric functions
      2. 2.5.2 Quasisymmetric functions
      3. 2.5.3 Examples of Schur-positive sets
  4. 3 Schur-positivity of convex caterpillars
    1. 3.1 Introduction
    2. 3.2 Background
      1. 3.2.1 Maximal chains in the non-crossing partition lattice
      2. 3.2.2 The Goulden-Yong partial order
    3. 3.3 Convex caterpillars
      1. 3.3.1 Basic properties of convex caterpillars
      2. 3.3.2 A labeling of maximal chains
      3. 3.3.3 Descents of convex caterpillars
      4. 3.3.4 Schur-positivity of convex caterpillars
  5. 4 Cyclic descent extensions
    1. 4.1 Introduction
    2. 4.2 Inverse descent classes and their cyclic descent extensions
    3. 4.3 Permutations with given inversion number
  6. 5 On cyclic descents of roots of unity
    1. 5.1 Background and main results
    2. 5.2 Basic propositions
    3. 5.3 Reduction to unimodal permutations
    4. 5.4 The case of prime $n$
    5. 5.5 Gluing unimodal permutations
    6. 5.6 Proof of Theorem 5.1.6

## Abstract

The notion of descent set for permutations and standard Young tableaux
(abbreviated to SYT) is classical. A significant problem in contemporary
algebraic combinatorics is determining whether the associated quasisymmetric
function is symmetric and Schur-positive. Gessel proved that Knuth classes of
permutations and inverse descent classes are Schur-positive. Other examples of
Schur-positive permutation sets follow from seminal works by Foata-
Schützenberger and Gessel-Reutenauer: permutations of fixed Coxeter length,
conjugacy classes, and $d$-roots of unity.

Sometimes it is possible to define descents on maximal chains of certain
posets using an $EL$-labeling of the edges in the Hasse diagram. A classic
example of a Schur-positive set of this type is the set of all maximal chains
in the non-crossing partition lattice of type $A$, which was given by Stanley.
In this case, the maximal chains can be realized by edge-labeled trees. A
long-standing problem is to find other Schur-positive sets of maximal chains
or trees.

In Chapter 3, we present an appealing set of maximal chains in the non-
crossing partition lattice (equivalently: a set of edge-labeled trees) that is
Schur-positive: we show that the subset of maximal chains in the non-crossing
partition lattice, which may be realized by convex caterpillars, is Schur
positive. We prove the following.

######  Theorem (3.1.4).

The set of linearly ordered factorizations of the $n$-cycle $(1,2,\dots,n)$
satisfies

$\mathcal{Q}(\mathcal{L}_{n})=\sum_{k=0}^{n-1}(k+1)s_{(n-k,1^{k})},$

where the descent set of any $u\in\mathcal{L}_{n}$ is defined by the edge
labeling of [9]. In particular, $\mathcal{L}_{n}$ is Schur-positive.

The proof uses the Goulden-Yong partial order on the edges together with a
variant of an $EL$-labeling due to Björner.

The rest of our work studies cyclic descent extensions (CDE) of Schur-positive
sets of permutations. The study of cyclic descent extensions has been an
active research area in recent years. Klyachko and Cellini introduced a
natural notion of cyclic descent set for permutations. This notion was further
studied by Dilks, Petersen, Stembridge, and many others. An analogous notion
for standard Young tableaux, using an axiomatic approach, was presented by
Rhoades, Adin-Reiner-Roichman, and others.

A significant problem in this field is whether a given set of permutations
admits a cyclic descent extension. The existence of cyclic extensions is
related to significant problems in various fields, in particular, to the non-
negativity of the coefficients of the Postnikov toric Schur functions and a
long-standing open problem of Thrall on higher Lie characters. Adin, Hegedüs
and Roichman, in [3], gave an algebraic characterization for Schur-positive
sets that admit a CDE.

In Chapter 4, we study an important Schur-positive subset of the symmetric
group, the set of all permutations of fixed Coxeter length. We obtain
sufficient conditions for the positive integer $m$, under which there is a CDE
for permutations of length $m$ in the symmetric group $\mathfrak{S}_{n}$, for
almost all $n$. The result involves surprising connections to generalized
pentagonal numbers. We prove the following.

######  Theorem (4.3.11).

For $k<n$, the set of permutations in $\mathfrak{S}_{n}$ with $k$ inversions
has a cyclic descent extension if and only if $k$ is not a generalized
pentagonal number.

In Chapter 5, we state a conjectured necessary and sufficient condition for
$d$-roots of unity in $\mathfrak{S}_{n}$ to carry a cyclic descent extension.

######  Conjecture.

The set of roots of unity of order $d$ in $\mathfrak{S}_{n}$ has a cyclic
descent extension if and only if $d$ and $n$ are not coprime.

We prove the following results, towards this conjecture.

######  Theorem (5.1.6).

The set of roots of unity of order $d$ in $\mathfrak{S}_{n}$:

  1. 1.

Does not have a cyclic descent extension if $n$ and $d$ are coprime.

  2. 2.

Has a cyclic descent extension when $d$ is a prime power and $d$ and $n$ are
not coprime.

##  Chapter 1 Introduction

Given a set $A$ of combinatorial objects equipped with a descent function
$Des:A\to 2^{[n-1]}$, define the quasi-symmetric function

$\mathcal{Q}(A)\coloneqq\sum_{a\in A}\mathcal{F}_{n,\operatorname{Des}(a)}$

where $\mathcal{F}_{n,D}$ are Gessel’s fundamental quasi-symmetric functions;
see Subsection 2.5.2 for more details. The following long-standing problem was
posed by Gessel and Reutenauer in [22].

######  Problem.

For which sets $A$ is $\mathcal{Q}(A)$ symmetric?

A symmetric function is called Schur-positive if all the coefficients in its
expansion in the basis of Schur functions are non-negative; see Subsection
2.5.1 for definitions. Determining whether a given symmetric function is
Schur-positive is a significant problem in contemporary algebraic
combinatorics; see Stanley’s article [45]. We say that the set $A$ of
combinatorial objects is Schur-positive if $\mathcal{Q}(A)$ is Schur-positive;
for details and examples, see Sections 2.5.1 and 2.5.3.

Another approach to Schur-positivity is via a significant problem in
combinatorial representation theory: Provide explicit formulas that express
the character values of interesting representations as a weighted enumeration
of combinatorial objects. The reader is referred to the survey article by
Barcelo and Ram [11]. Many such formulas have been found; examples include the
Murnaghan-Nakayama rule [44, Section 7.17], characters of Specht modules of
ribbon shapes [21], Lie characters [22], Gelfand models [5], characters of
homogeneous components of the coinvariant algebra [4], characters induced from
a lower ranked exterior algebra [17] and k-root enumerators [37], among
others. It turns out that the sets that appear in these formulas are Schur-
positive sets. An abstract framework for this phenomenon was proposed in [8].
In particular, it was shown in [8] that the equality of the characters of two
Schur-positive sets is equivalent to the equidistribution of their descent
sets, implying the equivalence of classical theorems in representation theory,
for example, the equivalence of theorems of Lusztig-Stanley in invariant
theory [42] and Foata-Schützenberger in permutation statistics [19]. Their
work is a development of the ideas of Gessel and Reutenauer in [22].

Note that equivalent - but different terminology is used in the literature in
this field. In particular, Schur-positive sets are also called fine sets. In
this work, we use only the term Schur-positive.

Schur-positive sets are often subsets of the symmetric group
$\mathfrak{S}_{n}$. However, there are important examples that are not of this
form. In particular, a part of our work deals with Schur-positive sets of
maximal chains in posets. Maximal chains in a labeled poset $P$ are equipped
with a natural descent map. A well-known conjecture of Stanley [40, III, Ch.
21] implies that all examples of Schur-positive labeled posets, in this sense
correspond to intervals in the Young lattice.

Another way to equip the set of maximal chains with a descent map is by
labeling the edges in the Hasse diagram. A classic example of a Schur-positive
set of this type, the set of all maximal chains in the non-crossing partition
lattice of type $A$, was given by Stanley [41]. An $EL$ edge-labeling of this
poset was presented in an earlier work of Björner [12]; see also [14, 31, 9].

Adin and Roichman presented in [9] a variant of the EL-labeling that was
defined by Björner, using the fact that every maximal chain bijectively
corresponds to a factorization of the cycle $(1\ \dots\ n)$ in
$\mathfrak{S}_{n}$ into a product of $n-1$ transpositions. This variant will
be used in our work.

Goulden and Yong in [23] showed that every maximal chain in the non-crossing
partition lattice can be interpreted as a geometric non-crossing tree with an
ordering of the edges (see Chapter 3 for more details). In particular, their
construction defines a poset structure on the edges of a non-crossing
geometric tree. It is natural to ask when this order is a linear order. In
Chapter 3, we provide a detailed description of these trees, named convex
caterpillars. We show that the set $\mathcal{L}_{n}$ of maximal chains that
correspond to these trees is Schur-positive and calculate the corresponding
quasisymmetric function. We prove the following result:

######  Theorem (3.1.4).

The set of linearly ordered factorizations of the $n$-cycle $(1,2,\dots,n)$
satisfies

$\mathcal{Q}(\mathcal{L}_{n})=\sum_{k=0}^{n-1}(k+1)s_{(n-k,1^{k})},$

where the descent set of any $u\in\mathcal{L}_{n}$ is defined by the edge
labeling of [9]. In particular, $\mathcal{L}_{n}$ is Schur-positive.

Here and elsewhere, $s_{\lambda}$ denotes the Schur function indexed by a
partition $\lambda$. See Subsection 2.5.1.

The rest of our work is dedicated to studying cyclic descent extensions for
several classes of Schur-positive sets in $\mathfrak{S}_{n}$. The study of
cyclic descent extensions has been an active research area in recent years.

One of the first works studying cyclic descents was a paper by Cellini [15],
who introduced a natural notion of cyclic descent on permutations as follows:

${\rm CDES}(\pi)\coloneqq\left\\{1\leq i\leq
n:\pi_{i}>\pi_{i+1}\right\\}\subseteq\left[n\right]\ \text{for all}\
\pi\in\mathfrak{S}_{n}.$

with the convention $\pi_{n+1}\coloneqq\pi_{1}$. A more restricted notion of a
cyclic descent number was used by Klyachko in [28]. Cyclic descent sets were
further studied by Dilks, Petersen and Stembridge in [16].

A well-established notion of descent also exists for standard Young tableaux
(SYT); however, there is no apparent cyclic analog. A significant milestone on
the way to defining a cyclic descent set on SYT was the work of Rhoades [35],
who described a notion of cyclic descent set for SYT of rectangular shape.
Some properties common to Cellini’s definition for permutations and Rhoades’
construction for SYT appeared in other combinatorial settings [33, 32, 18, 1].
These properties led to an axiomatic definition of a cyclic descent extension
in [6]:

######  Definition (4.1.3).

Let $\mathcal{T}$ be a finite set, equipped with a descent map
$\operatorname{Des}:\mathcal{T}\longrightarrow 2^{[n-1]}$. A cyclic extension
of $\operatorname{Des}$ is a pair $(\operatorname{\mathrm{cDes}},p)$, where
$\operatorname{\mathrm{cDes}}:\mathcal{T}\longrightarrow 2^{[n]}$ is a map and
$p:\mathcal{T}\longrightarrow\mathcal{T}$ is a bijection, satisfying the
following axioms: for all $T$ in $\mathcal{T}$,

$\begin{array}[]{rl}\text{(extension)}&\operatorname{\mathrm{cDes}}(T)\cap[n-1]=\operatorname{Des}(T),\\\
\text{(equivariance)}&\operatorname{\mathrm{cDes}}(p(T))={\rm
sh}(\operatorname{\mathrm{cDes}}(T)),\\\ \text{(non-
Escher)}&\varnothing\subsetneq\operatorname{\mathrm{cDes}}(T)\subsetneq[n].\\\
\end{array}$

Here $\mathrm{sh}$ denotes the cyclic shift of a subset of $[n]$, as in
Definition 4.1.1.

Cellini’s and Rhoades’ constructions are special cases of Definition 4.1.3. A
naturally arising question is the existence of such an extension for specific
subsets of the symmetric group $\mathfrak{S}_{n}$(see Chapter 4 and the
discussion at the beginning of [3]). It is also not apparent whether a cyclic
descent set similar to Rhoades’ can be defined for the set of SYT of every
shape. The question for SYT was solved by Adin, Reiner and Roichman in [6].
They proved that a cyclic descent extension exists for the set of SYT of skew
shape $\lambda/\mu$ if and only if $\lambda/\mu$ is not a connected ribbon.
They used Postnikov’s toric symmetric functions. A constructive proof was
found later by Huang in [25].

Adin, Hegedüs and Roichman provided in [3] an algebraic necessary and
sufficient condition for the existence of a cyclic descent extension on Schur-
positive sets. In addition, they characterized the conjugacy classes in
$\mathfrak{S}_{n}$ that possess a cyclic descent extension. Their proof was
not constructive - providing a combinatorial construction of a cyclic descent
extension for conjugacy classes is a significant work in progress. An explicit
construction for involutions with fixed points was described in [7]. Explicit
constructions of a cyclic descent extension for Dyck paths appear in [33].
This construction was extended to Motzkin paths by B. Han in [24]. Another
recent development is a cyclic analog of quasi-symmetric functions by Adin,
Gessel, Reiner and Roichman in [2].

In Chapter 4, we study the existence of cyclic descent extensions on inverse
descent classes and their generalizations. In particular, we obtain the
following result:

######  Theorem (Theorem 4.2.6).

The following sets in $\mathfrak{S}_{n}$ have cyclic descent extensions:

  1. 1.

$D_{2^{J},n}^{-1}$ if and only if $J\neq\emptyset$.

  2. 2.

$D_{[I,J],n}^{-1}$ for an interval

$[I,J]=\left\\{K:I\subseteq K\ and\ K\subseteq J\right\\}$

(in the poset $2^{[n-1]}$ ordered by inclusion), if and only if $I\subsetneq
J$.

  3. 3.

For every maximal chain $C$ in the poset $[I,J]$, $D_{C,n}^{-1}$ has a cyclic
descent extension if and only if $I\subsetneq J$ and $2\not|(|J|-|I|)$. In
particular, $D_{C,n}^{-1}$ for a maximal chain $C$ in $2^{[n-1]}$ has a cyclic
descent extension if and only if $n-1$ is odd, or equivalently $n$ is even.

Here $D_{S,n}^{-1}$ denotes, for a set $S$ of subsets of $[n]$, a generalized
inverse descent class, as in Definition 4.2.2.

In the last part of Chapter 4, we use this result to describe conditions for
the existence of cyclic descent extensions for permutations with a given
number of inversions. We determine necessary and sufficient conditions for
permutations with a given inversion number in $\mathfrak{S}_{n}$ for
sufficiently large $n$. Our result has a surprising connection to Euler’s
pentagonal number theorem. We prove the following.

######  Theorem (4.3.11).

For $k<n$, the set of permutations in $\mathfrak{S}_{n}$ with $k$ inversions
has a cyclic descent extension if, and only if, $k$ is not a generalized
pentagonal number.

In the last chapter, we study roots of unity in $\mathfrak{S}_{n}$ and
conditions for the existence of a cyclic descent extension, which can be seen
as a generalization of the criterion given in [3].

In particular, we obtain the following result:

######  Theorem (5.1.6).

The set of roots of unity of order $d$ in $\mathfrak{S}_{n}$:

  1. 1.

Does not have a cyclic descent extension if $n$ and $d$ are co-prime.

  2. 2.

Has a cyclic descent extension when $d$ is a prime power and $d$ and $n$ are
not co-prime.

Finally, we present the following conjecture, a subject for future work.

######  Conjecture.

The set of roots of unity of order $d$ in $\mathfrak{S}_{n}$ has a cyclic
descent extension if and only if $d$ and $n$ are not co-prime.

##  Chapter 2 Background

###  2.1 Basic notation and definitions

This section quickly reviews some notation and basic facts about permutations,
partitions, and related structures.

We use $[n]$ to denote the set $\left\\{1,\dots,n\right\\}$. Unless explicitly
stated, the arithmetic on $[n]$ is performed modulo $n$. For a set $X$, the
power set of $X$, consisting of all subsets of $X$, will be denoted $2^{X}$.
For sets $X$ and $Y$, the set of all functions from $X$ to $Y$ is denoted
$Y^{X}$.

####  2.1.1 Compositions and partitions

######  Definition 2.1.1.

A weak composition of $n$ is a sequence
$\alpha=\left(\alpha_{1},\alpha_{2},\dots\right)$ of non-negative integers
such that $\sum_{k=1}^{\infty}\alpha_{k}=n$.

######  Definition 2.1.2.

A partition of $n$ is a weakly decreasing sequence of non-negative integers
$\lambda=(\lambda_{1},\lambda_{2},\dots)$ such that
$\sum_{k=1}^{\infty}\lambda_{k}=n$. We denote $\lambda\vdash n$.

######  Definition 2.1.3.

The length of a partition
$\lambda=\left(\lambda_{1},\lambda_{2},\dots\right)$, denoted $l(\lambda)$, is
the number of non-zero parts $\lambda_{i}$. The non-zero $\lambda_{i}$ are
called the parts of $\lambda$.

######  Remark 2.1.4.

Sometimes we use the notation $\lambda=(a_{1}^{i_{1}},\dots,a_{k}^{i_{k}})$
where $i_{k}$ is the number of parts of $\lambda$ equal to $a_{k}$.

####  2.1.2 Permutations

######  Definition 2.1.5.

The symmetric group or the group of permutations is the group of bijections
from $[n]$ to itself. We denote the symmetric group $\mathfrak{S}_{n}$.

For a permutation $\pi\in\mathfrak{S}_{n}$ we often write $\pi_{i}$ instead of
$\pi(i)$. In some cases, we will use cycle decomposition representation, which
we now describe.

######  Definition 2.1.6.

A cycle $\pi=\left(i_{1}\ \dots\ i_{l}\right)$ is a permutation in
$\mathfrak{S}_{n}$ such that $\pi(i_{k})=i_{k+1}$ for all $1\leq k\leq l-1$,
$\pi(i_{l})=i_{1}$ and $\pi(m)=m$ if
$m\notin\left\\{i_{1},\dots,i_{l}\right\\}$. The number $l$ is called the
length of the cycle. We say that cycles $(i_{1},\dots,i_{l})$ and
$(i^{\prime}_{1},\dots,i^{\prime}_{l^{\prime}})$ are disjoint if
$i_{k}\neq{j_{k^{\prime}}}$ for all $1\leq k\leq l$ and $1\leq k^{\prime}\leq
l^{\prime}$.

Recall the basic fact from group theory.

######  Theorem 2.1.7.

Every $\pi\in\mathfrak{S}_{n}$ can be represented as a product of disjoint
cycles

$\pi=\left(a_{1}\ \dots\ a_{l_{1}}\right)\left(a_{l_{1}+1}\dots
a_{l_{1}+l_{2}}\right)\dots\left(a_{l_{1}+\dots+l_{k-1}+1}\ \dots\
a_{n}\right).$

Furthermore:

  1. 1.

The representation is unique, up to the order of the cycles.

  2. 2.

Two permutations $\pi,\sigma\in\mathfrak{S}_{n}$ with

$\pi=\left(a_{1}\dots\right)\dots\left(\dots a_{n}\right)$

are conjugate in $\mathfrak{S}_{n}$ if and only if there is
$\tau\in\mathfrak{S}_{n}$ such that

$\sigma=\left(\tau(a_{1})\dots\right)\dots\left(\dots\tau(a_{n})\right).$

In such case we have $\sigma=\tau\pi\tau^{-1}$.

######  Definition 2.1.8.

The cycle type of a permutation

$\pi=\left(a_{1}\ \dots\ a_{l_{1}}\right)\left(a_{l_{1}+1}\dots
a_{l_{1}+l_{2}}\right)\dots\left(a_{l_{1}+\dots+l_{k-1}+1}\ \dots\
a_{n}\right)$

is the partition of $n$ obtained by writing the lengths of cycles in the cycle
decomposition of $\pi$ in weakly decreasing order. The cycle type of $\pi$ is
denoted by $\mathbf{type}\,\pi$.

Part 2 of theorem 2.1.7 is equivalent to the statement that two permutations
in $\mathfrak{S}_{n}$ are conjugate if and only if they have the same cycle
type. The conjugacy class of all permutations $\pi$ with
$\mathbf{type}\,\pi=\lambda$ will be denoted by $\mathcal{C}_{\lambda}$.

###  2.2 Representations

Representations and their characters play an essential role in understanding
objects’ symmetries and studying the structures of groups. We recall the basic
definitions and theorems we need from representation theory.

######  Definition 2.2.1.

An action of a group $G$ on a set $X$ is a function from $G\times X$ to $X$,
written as $g\cdot x$ or simply $gx$ for all $g\in G$ and $x\in X$ with the
following properties:

  1. 1.

$g_{1}\cdot(g_{2}\cdot x)=(g_{1}g_{2})\cdot x$ for all $g_{1},g_{2}\in G$ and
$x\in X$.

  2. 2.

For the identity element $e$ of $G$ we have $e\cdot x=x$ for all $x\in X$.

For a vector space $V$, we often identify a linear map $T:V\to V$ with its
representation matrix relative to the standard basis. Let $GL(V)$ denote the
general linear group of invertible linear transformations from $V$ to itself.
For a field $\mathbb{F}$, let $GL_{n}(\mathbb{F})$ denote group of invertible
matrices of size $n\times n$ with elements in $\mathbb{F}$. If $V$ is an
$n$-dimensional vector space over $\mathbb{F}$, then $GL(V)$ and
$GL_{n}(\mathbb{F})$ are isomorphic; therefore, unless stated explicitly, no
distinction will be made between them.

######  Definition 2.2.2.

Let $G$ be a finite group, $\mathbb{F}$ a field, and $V$ a vector space over
$\mathbb{F}$. A linear representation of $G$ is a group homomorphism

$\rho:G\to GL(V).$

######  Observation 2.2.3.

Every linear group representation $\rho:G\to GL(V)$ defines an action of $G$
on $V$ by $g\cdot v=\rho(g)v$.

######  Definition 2.2.4.

For a set $X$ and field $\mathbb{F}$, the free vector space $\mathbb{F}^{(X)}$
generated by $X$ over $F$ is the direct sum of copies of $F$ indexed by $X$

$\mathbb{F}^{(X)}=\bigoplus_{x\in X}\mathbb{F}$

which is the subspace of the cartesian product $\prod\limits_{x\in X}F$ of
elements with finitely many nonzero components. It can be equivalently viewed
as the vector space of formal linear combinations $\sum\limits_{x\in X}a_{x}x$
with coefficients in $F$ with finitely many $x\in X$ with non-zero $a_{x}$. If
we replace field $\mathbb{F}$ in the definition with a commutative ring $R$,
then $R^{(X)}$ is the a $R$-module over $X$.

If the set $X$ in the previous definition is the group $G$ itself, then
$R^{(G)}$ can be given a ring structure as follows.

######  Definition 2.2.5.

Let $G$ be a finite group and $R$ a commutative ring. Then $R\left[G\right]$,
the group ring or the group algebra of $G$ over $R$ is the free $R$-module
over $G$, together with multiplication between two elements defined as
follows:

$\sum_{g\in G}a_{g}g\sum_{h\in G}b_{h}h=\sum_{k\in
G}\left(\sum_{gh=k}a_{g}b_{h}\right)k.$

Note that for every finite group $G$ and finite set $X$, if $G$ acts on $X$,
then this action can be extended to an invertible linear transformation from
$\mathbb{F}^{(X)}$ to itself by linear extension of the action, namely:

$g\cdot\left(\sum_{x\in X}a_{x}x\right)=\sum_{x\in X}a_{x}(g\cdot x).$

In turn, if $V$ is a vector space over the field $\mathbb{F}$, then every
group representation $\rho:G\to GL(V)$ turns the vector space $V$ into ab
$\mathbb{F}[G]$ module with elements of $\mathbb{F}\left[G\right]$ acting on
an element of $V$ by

$\left(\sum_{g\in G}a_{g}g\right)v=\sum_{g\in G}a_{g}\rho(g)v.$

On the other hand, every module $V$ over $\mathbb{F}[G]$ is a vector space,
and the action of $\mathbb{F}[G]$ is a linear transformation. Hence, when a
module over $\mathbb{F}[G]$ is a finite-dimensional vector space over
$\mathbb{F}$, it defines a matrix representation of $G$.

###  2.3 Shapes and Standard Young Tableaux

Standard Young tableaux are a classical object widely studied in many branches
of mathematics. Often, they are used to describe the irreducible
representations of $\mathfrak{S}_{n}$. This section provides the basic
definitions that will be used later. Our exposition is mainly based on [38]
and [44], which one can refer to for a more detailed treatment of the subject.

######  Definition 2.3.1.

Let $\lambda\vdash n$. The Ferrer’s diagram or shape of $\lambda$ is an array
$n$ of cells, having $l(\lambda)$ left justified rows, such that row $i$
contains $\lambda_{i}$ cells for $1\leq i\leq l(\lambda)$.

######  Remark 2.3.2.

In this text, we use the English notation, where row $i$ appears above the row
$i+1$. Sometimes Ferrer’s diagrams are called Young diagrams.

The cell in row $i$ and column $j$ has coordinates $(i,j)$.

If $m\leq n$ and $\mu\vdash m$ and $\lambda\vdash n$, we denote
$\mu\subseteq\lambda$ if $l(\mu)\leq l(\lambda)$ and $\mu_{i}\leq\lambda_{i}$
for every $1\leq i\leq l(\mu)$.

######  Definition 2.3.3.

Let $m\leq n$, $\mu\vdash m$, $\lambda\vdash n$. The skew shape of
$\lambda/\mu$ is an array of $n-m$ cells obtained by removing the first
$\mu_{i}$ cells from row $i$ in the shape of $\lambda$. If $m=0$, the skew
shape $\lambda/\mu$ is called normal or just a shape, and we write $\lambda$
instead of $\lambda/\mu$.

######  Definition 2.3.4.

A Young tableau of shape $\lambda$ is an array $T$ obtained by filling the
cells of the Young diagram of $\lambda$ by the numbers $1,\dots,n$
bijectively. A young tableau T of shape $\lambda$ is also called a
$\lambda$-tableau and is denoted $T^{\lambda}$. We also write
$\mathbf{sh}\,T=\lambda$.

######  Definition 2.3.5.

The tableau $T$ is a standard Young tableau if it is a Young tableau and every
row read left to right and column read from top to bottom of $T$ is an
increasing sequence. The set of all standard Young tableaux of shape $\lambda$
will be denoted ${\rm SYT}(\lambda)$. The size of ${\rm SYT}(\lambda)$ will be
denoted $f^{\lambda}$.

######  Definition 2.3.6.

A semistandard Young tableau of shape $\lambda$ is an array $T$ obtained by
replacing the cells of shape $\lambda$ with positive integers, such that the
rows of $T$ are non-decreasing sequences and the columns of $T$ are increasing
sequences. The set of all semistandard Young tableaux of shape $\lambda$ will
be denoted ${\rm SSYT}(\lambda)$.

######  Definition 2.3.7.

For a standard or semistandard Young tableaux $T$, the content or type of $T$
is the sequence $\mathbf{type}\,T=\mu=(\mu_{1},\dots,)$ where $\mu_{i}$ is
equal to the number of times that $i$ appears in $T$. The set of semistandard
Young tableaux of shape $\lambda$ and content $\mu$ is denoted with
$\mathcal{T}_{\lambda\mu}^{0}$. The size of $\mathcal{T}_{\lambda\mu}^{0}$ is
called the Kostka number $K_{\lambda\mu}$.

######  Remark 2.3.8.

All the definitions involving shapes can be generalized to skew shapes by
replacing $\lambda$ with $\lambda/\mu$ in the definition to obtain skew Young
tableaux, standard skew Young tableaux and semistandard skew Young tableaux,
$f^{\lambda/\mu}$, etc.

###  2.4 Statistics on permutations and Young tableaux

######  Definition 2.4.1.

Let $X$ be a set. A statistic on $X$ is a function $f:X\to A$ where
$A\subseteq{\mathbb{N}}\cup\left\\{0\right\\}$ or $A\subseteq
2^{{\mathbb{N}}\cup\left\\{0\right\\}}$.

The study of statistics on finite objects has a crucial role in combinatorics.
The notion of equidistribution is crucial as it often allows us to unify
questions that deal with seemingly different statistics.

######  Definition 2.4.2.

Let $f:X\to A$ be a statistic on the set $X$ and $g:Y\to A$ a statistic on the
set $Y$. We say that $f$ and $g$ are equidistributed if for every $a\in A$ we
have

$\left|\\{x\in X:f(x)=a\\}\right|=\left|\\{y\in Y:g(x)=a\\}\right|.$

######  Remark 2.4.3.

The notions of a statistic and a distribution of a statistic are naturally
extended to multisets.

In the rest of this section, we describe some of the classical statistics on
$\mathfrak{S}_{n}$ and their generalizations on ${\rm SYT}(n)$ that will be
needed later.

######  Definition 2.4.4.

Let $\pi\in\mathfrak{S}_{n}$. We say that $i$ is a descent of $\pi$ if
$\pi_{i}>\pi_{i+1}$. We denote the descent set of $\pi$ by

$\operatorname{Des}(\pi)\coloneqq\left\\{i:\pi_{i}>\pi_{i+1}\right\\}.$

The notion of descent can be extended to other objects. For example, it is
easily extended to finite sequences of integers. In Chapter 3 of this work, we
study descents defined on non-crossing partitions of $[n]$.

Extension of descents on the standard Young tableaux plays a significant role
in algebraic combinatorics and is defined as follows.

######  Definition 2.4.5.

The descent set of a standard (skew) Young tableau $T$ is

$\operatorname{Des}(T)\coloneqq\left\\{i:\text{$i+1$ appears in a lower row of
$T$ than $i$}\right\\}.$

The Robinson-Schensted-Knuth correspondence, or RSK in short, is a bijection
between permutations on $n$ and ordered pairs of standard Young tableaux of
the same shape. It also connects the descents of permutations and standard
Young tableaux.

######  Theorem 2.4.6.

[38, Chapter 3] There exists a bijection

$RSK:\mathfrak{S}_{n}\to\biguplus_{\lambda\vdash n}{\rm SYT}(n)\times{\rm
SYT}(n)$

such that if $\pi\xrightarrow{RSK}\left({P_{\pi}},{Q_{\pi}}\right)$ then:

  1. 1.

$\mathbf{sh}\,P_{\pi}=\mathbf{sh}\,Q_{\pi}.$

  2. 2.

$\pi^{-1}\xrightarrow{RSK}\left({Q_{\pi}},{P_{\pi}}\right).$

  3. 3.

$\operatorname{Des}(\pi)=\operatorname{Des}(Q_{\pi})$ and
$\operatorname{Des}(\pi^{-1})=\operatorname{Des}(P_{\pi})$.

######  Definition 2.4.7.

Let $X$ be a set with descent statistic $Des:X\to\left[n\right]$. For $x\in X$
the descent number of $x$ is the size of its descent set:

$\operatorname{des}(x)\coloneqq|Des(x)|.$

Inversions are similar to descents and can be seen as their generalization.

######  Definition 2.4.8.

Let $\pi\in\mathfrak{S}_{n}$. We say that $(i,j)$ is an inversion of $\pi$ if
$i<j$ and $\pi_{i}>\pi_{j}$. We denote the inversion set of $\pi$ with

$\operatorname{\mathrm{Inv}}(\pi)\coloneqq\left\\{(i,j):\text{$i<j$ and
$\pi_{i}>\pi_{j}$}\right\\}.$

The number of inversions of $\pi$ is called the inversion number of $\pi$ and
is denoted with $\operatorname{\mathrm{inv}}(\pi)$.

A statistic closely related to descents and inversions is the major index.

######  Definition 2.4.9.

Let $\pi\in\mathfrak{S}_{n}$. The major index of $\pi$ is defined as the sum
of its descents:

$\operatorname{\mathrm{maj}}(\pi)\coloneqq\sum_{i\in\operatorname{Des}{\pi}}i.$

The inverse major index of $\pi$ is defined as the major index of its inverse.

$\operatorname{\mathrm{imaj}}(\pi)=\operatorname{\mathrm{maj}}(\pi^{-1}).$

######  Definition 2.4.10.

The standard Coxeter generators of $\mathfrak{S}_{n}$ are the transpositions
$s_{i}=(i\ i+1)$ for $1\leq i\leq n-1$. The minimal number of Coxeter
generators required to express the permutation $\pi\in\mathfrak{S}_{n}$ as a
product of Coxeter generators is called the Coxeter length of $\pi$.

The connection between the length of a permutation and its inversion number is
stated below.

######  Theorem 2.4.11.

[13, Chapter 1] For every $\pi\in\mathfrak{S}_{n}$,
$\operatorname{\mathrm{inv}}(\pi)$ is equal to its Coxeter length.

###  2.5 Symmetric and quasi-symmetric functions

####  2.5.1 Symmetric functions

Let ${\mathbf{x}}=\left\\{x_{n}\right\\}_{n\in\mathbb{N}}$ be a set of
commuting indeterminates.

Symmetric and quasi-symmetric functions in ${\bf x}$ can be defined over
various (commutative) rings of coefficients, including the ring of integers
$\mathbb{Z}$; for simplicity we define it over the field $\mathbb{Q}$ of
rational numbers. For a sequence
$\mu=\left\\{\mu_{n}\right\\}_{n\in\mathbb{N}}$, let

${\mathbf{x}}^{\mu}=\prod_{n\in\mathbb{N}}x_{n}^{\mu_{n}}.$

For formal power series
$f({\mathbf{x}})=\sum\limits_{a\in\mathcal{A}}c_{a}x^{a}$, $[x^{a}]f$ will
denote $c_{a}$, the coefficient of $x^{\alpha}$ in $f$.

######  Definition 2.5.1.

A symmetric function in the variables $x_{1},x_{2},\ldots$ is a formal power
series $f({\bf x})\in\mathbb{Q}[[{\bf x}]]$, of bounded degree, such that for
any three sequences (of the same length $k$) of positive integers,
$(a_{1},\ldots,a_{k})$, $(i_{1},\dots,i_{k})$ and $(j_{1},\dots,j_{k})$, the
coefficients of $x_{i_{1}}^{a_{1}}\cdots x_{i_{k}}^{a_{k}}$ and of
$x_{j_{1}}^{a_{1}}\cdots x_{j_{k}}^{a_{k}}$ in $f$ are the same:

$[x_{i_{1}}^{a_{1}}\cdots x_{i_{k}}^{a_{k}}]f=[x_{j_{1}}^{a_{1}}\cdots
x_{j_{k}}^{a_{k}}]f.$

A symmetric function $f$ is called homogeneous of degree $n$ if every for
every $\alpha$ such that $\left[x^{\alpha}\right]\neq 0$, we have
$\sum\limits_{i=1}^{\infty}\alpha_{i}=n$. The vector space of homogeneous
functions of degree $n$ is denoted $\Lambda_{n}$.

It is easy to see, that if $f\in\Lambda_{n}$ and
$\left[{\mathbf{x}}^{\mu}\right]f\neq 0$, then by definition of symmetric
function, $[{\mathbf{x}}^{\lambda}]f=[{\mathbf{x}}^{\mu}]f$ where $\lambda$ is
the partition obtained by writing the parts of $\mu$ in non-increasing order.
Hence, every $f\in\Lambda_{n}$ can be written as a linear combination of

$m_{\lambda}=\sum_{\begin{subarray}{c}\left(x_{i_{1}},\dots,x_{l}\right)\\\
\text{$i_{j}\neq i_{k}$ for $j\neq
k$}\end{subarray}}x_{i_{1}}^{\lambda_{1}}\dots x_{i_{l}}^{\lambda_{l}}$

where $\lambda=\left(\lambda_{1},\dots,\lambda_{l}\right)$ ranges over all
partitions of $n$. It is also clear that $m_{\lambda}$ are independent,
therefore

${m_{\lambda}:\lambda\vdash n}$

is a basis o $\Lambda_{n}$. The function $m_{\lambda}$ is called monomial
symmetric function corresponding to $\lambda$. We will work with another basis
for $\Lambda_{n}$.

######  Definition 2.5.2.

For a semistandard Young tableau $T$, define $x^{T}$ to be $x^{\mu}$ where
$\mu=\mathbf{type}\,T$ as in Definition 2.3.7.

######  Definition 2.5.3.

Schur functions, indexed by partitions, are defined as follows:

$s_{\lambda}=\sum_{T\in{\rm SSYT}(\lambda)}x^{T},$

where ${\rm SSYT}(\lambda)$ is the set of semistandard Young tableaux of shape
$\lambda$, defined in Section 2.3.

######  Remark 2.5.4.

Skew Schur functions are defined analogously by replacing partitions with skew
shapes in the definition.

There is a dictionary relating symmetric functions to characters of the
symmetric group $\mathfrak{S}_{n}$. The irreducible characters of
$\mathfrak{S}_{n}$ are indexed by partitions $\lambda\vdash n$ and denoted
$\chi^{\lambda}$. The Frobenius characteristic map ${\operatorname{ch}}$ from
class functions on $\mathfrak{S}_{n}$ to symmetric functions is defined by
${\operatorname{ch}}(\chi^{\lambda})=s_{\lambda}$, and extended by linearity.
The Frobenius characteristic map has two properties that allow reducing the
study of characters to the study of symmetric function. First, it is an
isometry between the space of class functions on $\mathfrak{S}_{n}$ and
$\Lambda_{n}$, where the inner product on characters is defined by
$\left<\chi^{\mu},\chi^{\nu}\right>=\delta_{\mu\nu}$ and the inner product on
$\Lambda_{n}$ is defined by $\left<s_{\mu},s_{\nu}\right>=\delta_{\mu\nu}.$
The other property is that if $\chi$ and $\mu$ are irreducible characters for
$\mathfrak{S}_{n}$ and $\mathfrak{S}_{m}$ respectively, then
${\operatorname{ch}}(\chi\cdot\mu)=s_{\mu}s_{\nu}$ where $\chi\cdot\mu$
denotes the induced character $(\chi\otimes\mu)\uparrow^{\mathfrak{S}_{n+m}}$.
A symmetric function $f$ is Schur-positive if in the expansion of $f$ in the
basis of symmetric functions

$f=\sum_{\lambda\vdash n}a_{\lambda}s_{\lambda}$

we have $a_{\lambda}\geq 0$ and $a_{\lambda}$ is an integer for every
$\lambda\vdash n$.

####  2.5.2 Quasisymmetric functions

Quasisymmetric functions allow us to reduce questions about representations
and symmetric functions to the study of descents. The following definition of
a quasi-symmetric function can be found in [44, 7.19].

######  Definition 2.5.5.

A quasi-symmetric function in the variables $x_{1},x_{2},\ldots$ is a formal
power series $f({\bf x})\in\mathbb{Q}[[{\bf x}]]$, of bounded degree, such
that for any three sequences (of the same length $k$) of positive integers,
$(a_{1},\ldots,a_{k})$, $(i_{1},\dots,i_{k})$ and $(j_{1},\dots,j_{k})$, where
the last two are increasing, the coefficients of $x_{i_{1}}^{a_{1}}\cdots
x_{i_{k}}^{a_{k}}$ and of $x_{j_{1}}^{a_{1}}\cdots x_{j_{k}}^{a_{k}}$ in $f$
are the same:

$[x_{i_{1}}^{a_{1}}\cdots x_{i_{k}}^{a_{k}}]f=[x_{j_{1}}^{a_{1}}\cdots
x_{j_{k}}^{a_{k}}]f$

whenever $i_{1}<\ldots<i_{k}$ and $j_{1}<\ldots<j_{k}$. The space of
quasisymmetric functions is denoted $\mathcal{Q}$. A quasisymmetric function
$f$ is homogeneous of degree $n$ if $[x^{\alpha}]f$ implies that
$\sum\limits_{i=1}^{\infty}\alpha_{i}=n$. The space of homogeneous
quasisymmetric functions of degree $n$ is denoted $\mathcal{Q}_{n}$.

Every symmetric function is quasi-symmetric but not conversely. For example,
the function $\sum_{i<j}{x_{i}^{2}x_{j}}$ is quasi-symmetric but not
symmetric.

The monomial quasisymmetric functions $M_{\alpha}$ are defined by

$M_{\alpha}=\sum_{i_{1}<\dots<i_{k}}x_{i_{1}}^{\alpha_{1}}\dots
x_{i_{k}}^{\alpha_{k}}$

where $\alpha$ runs over compositions of $n$ that do not have zero parts,
viewed as finite sequences.

It is easy to see that $M_{\alpha}$ is a basis of $\mathcal{Q}_{n}$. However,
we will use another basis that provides a connection from descents to
characters and symmetric functions.

######  Definition 2.5.6.

For each subset $D\subseteq[n-1]$ define the fundamental quasi-symmetric
function

$\mathcal{F}_{n,D}(x):=\sum_{\begin{subarray}{c}i_{1}\leq i_{2}\leq\ldots\leq
i_{n}\\\ {i_{j}<i_{j+1}\text{ if }j\in
D}\end{subarray}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}.$

######  Definition 2.5.7.

Let ${\mathcal{B}}$ be a set of combinatorial objects, equipped with a descent
map $\operatorname{Des}:{\mathcal{B}}\to 2^{[n-1]}$ which associates to each
element $b\in{\mathcal{B}}$ a subset $\operatorname{Des}(b)\subseteq[n-1]$.
Define the quasi-symmetric function associated with ${\mathcal{B}}$ by

$\mathcal{Q}({\mathcal{B}}):=\sum\limits_{b\in{\mathcal{B}}}\mathcal{F}_{n,\operatorname{Des}(b)}.$

######  Definition 2.5.8.

We say that ${\mathcal{B}}$ is a fine set or Schur-positive  if
$\mathcal{Q}({\mathcal{B}})$ is symmetric and the coefficients $a_{\lambda}$
are non-negative integers in the expansion

$\mathcal{Q}({\mathcal{B}})=\sum\limits_{\lambda\vdash
n}a_{\lambda}s_{\lambda}.$

where $s_{\lambda}$ are Schur functions.

The following fundamental theorem is due to Gessel.

######  Theorem 2.5.9.

[44, Theorem 7.19.7] For every shape $\lambda\vdash n$,

$\mathcal{Q}({{\rm SYT}(\lambda)})=s_{\lambda}.$

######  Remark 2.5.10.

Skew Schur functions are defined similarly to Schur functions by replacing
shape with skew shape. The result of Theorem 2.5.9 also holds for skew shapes.
Namely, we have:

$\mathcal{Q}({\rm SYT}(\lambda/\mu))=s_{\lambda/\mu}.$

Every subset of $J={\mathbb{N}}$ can be associated with the sequence
$\left\\{j_{n}\right\\}_{n\in{\mathbb{N}}}$ where

$j_{n}=\begin{cases}1&n\in J\\\ 0&n\notin J\end{cases}.$

######  Definition 2.5.11.

For a subset $J\subseteq{\mathbb{N}}$, define
$X^{J}=x^{\\{j_{n}\\}_{n\in{\mathbb{N}}}}$ where
$\\{j_{n}\\}_{n\in{\mathbb{N}}}$ is the sequence associated with $J$.

######  Theorem 2.5.12.

[3] For every set $\mathcal{A}$, equipped with a descent map
$\operatorname{Des}:\mathcal{A}\to 2^{[n-1]}$, the following statements are
equivalent:

$\mathcal{Q}(\mathcal{A})=\sum_{\lambda\vdash n}c_{\lambda}s_{\lambda}$

and

$\sum_{a\in\mathcal{A}}x^{\operatorname{Des}(a)}=\sum_{\lambda\vdash
n}c_{\lambda}\sum_{T\in SYT(\lambda)}x^{\operatorname{Des}(T)}.$

In particular, if $\mathcal{A}$ is Schur-positive, then $c_{\lambda}\geq 0$.

######  Remark 2.5.13.

The theorem in the paper is stated for subsets of $\mathfrak{S}_{n}$. However,
the proof remains correct if we replace $\mathcal{A}\subseteq\mathfrak{S}_{n}$
with “$\mathcal{A}$ equipped with a descent map”.

The Frobenius characteristic map can be redefined in terms of quasisymmetric
functions as follows:

${\operatorname{ch}}(\chi^{\lambda})=\sum_{T\in
SYT(\lambda)}\mathcal{F}_{n,\operatorname{Des}(T)}.$

We often rely on the following observation. Hence, even though it is evident,
we state it explicitly.

######  Lemma 2.5.14.

Let $A$ and $B$ disjoint sets equipped with a descent map

$\operatorname{Des}:A\uplus B\to 2^{n-1}$

for some $n\in{\mathbb{N}}$. Then

$\mathcal{Q}(A\uplus B)=\mathcal{Q}(A)+\mathcal{Q}(B).$

####  2.5.3 Examples of Schur-positive sets

Recall from the Subsection 2.5.1 that a symmetric function is Schur-positive
if all the coefficients in its expansion in the basis of Schur functions are
non-negative. Determining whether a given symmetric function is Schur-positive
is a significant problem in contemporary algebraic combinatorics [45].

The following problem is also long-standing; see, for example, [22].

######  Problem 2.5.15.

Given a set $A$, equipped with a descent map, is $\mathcal{Q}(A)$ symmetric?
In case of an affirmative answer, is it Schur-positive?

In the remainder of the section, we describe a few classic examples of Schur-
positive sets in $\mathfrak{S}_{n}$. These sets and their generalizations are
studied in more depth in Chapters 4 and 5 in perspective of cyclic descent
extensions, which are defined in Section 4.1.

Before proceeding to the mentioned above examples, we note that Schur-
positivity questions are also crucial for sets that are not subsets of
$\mathfrak{S}_{n}$, as it implies the existence of a representation of
$\mathfrak{S}_{n}$. We have already seen an example in the previous
subsection, the set of (skew) Young tableaux. Another set - of maximal chains
in the non-crossing partition lattice and its subset of convex caterpillars
will be studied in Chapter 3.

######  Definition 2.5.16.

The permutations $\pi,\sigma\in\mathfrak{S}_{n}$ are said to be Knuth
equivalent if $P_{\sigma}=P_{\sigma}$ where $P_{\sigma}$ is the first SYT in
the RSK bijection. A Knuth class of $T$ is the set

$K_{T}=\left\\{\pi\in\mathfrak{S}_{n}:P_{\pi}=T\right\\}.$

Schur-positivity of a Knuth class is an immediate result of theorems 2.5.9 and
2.4.6. To see that, observe that if
$\pi\xrightarrow{RSK}\left({P_{\pi}},{Q_{\pi}}\right)$ then
$\operatorname{Des}(\pi)=\operatorname{Des}(Q_{\pi})$ and that by theorem
2.4.6 we have bijection from $K_{T}$ to $SYT_{\lambda}$ where
$\lambda=\mathbf{sh}\,T$ and therefore the descents of $K_{T}$ and
$SYT(\lambda)$ are equally distributed. Combining with theorem 2.5.9 we obtain

$\mathcal{Q}(K_{T})=\mathcal{Q}(SYT(\lambda)=s_{\lambda}.$

Inverse descent classes defined below are another classic example.

######  Definition 2.5.17.

Let $J\subseteq[n-1]$. The inverse descent class of $\mathfrak{S}_{n}$
corresponding to $J$ is defined by

$D_{J,n}^{-1}=\left\\{\pi\in\mathfrak{S}_{n}:\operatorname{Des}(\pi^{-1})=J\right\\}.$

Schur-positivity of inverse descent classes follows from theorem 2.4.6 and the
following equality:

$\displaystyle D_{J,n}^{-1}$
$\displaystyle=\left\\{\pi\in\mathfrak{S}_{n}:\operatorname{Des}(\pi^{-1})=J\right\\}$
$\displaystyle=\biguplus_{\operatorname{Des}{T}=J}\left\\{\pi:\pi\xrightarrow{RSK}\left({P_{\pi}},{T}\right)\right\\}$
$\displaystyle=\biguplus_{\operatorname{Des}{T}=J}K_{T}.$

Combining with lemma 2.5.14 we obtain

$\mathcal{Q}(D_{J,n}^{-1})=\mathcal{Q}(\biguplus_{\operatorname{Des}{T}=J}K_{T})=\sum_{\operatorname{Des}{T}=J}s_{\mathbf{sh}\,T}.$

A classic result by Foata and Schützenberger proved in [19] (also see Section
1.4 in [43] for more accessible proof) states that there exists a bijection
$\phi:\mathfrak{S}_{n}\to\mathfrak{S}_{n}$ such that

  1. 1.

$\operatorname{\mathrm{maj}}(\pi)=\operatorname{\mathrm{inv}}(\phi(\pi))$.

  2. 2.

$\operatorname{Des}(\pi^{-1})=\operatorname{Des}(\phi(\pi)^{-1})$.

It immediately followsfrom Defiition 2.4.10 that Coxeter length of $\pi$ and
$\pi^{-1}$ are equal. In addition, by Theorem 2.4.11, the Coxeter length of a
permutation $\pi$ in $\mathfrak{S}_{n}$ is equal to
$\operatorname{\mathrm{inv}}(\pi)$. Therefore, we
$\operatorname{\mathrm{inv}}(\pi)=\operatorname{\mathrm{inv}}(\pi^{-1})$.
Hence, the mapping $\phi$ satisfies the following equations:

  1. 1.

$\operatorname{\mathrm{imaj}}(\pi)=\operatorname{\mathrm{maj}}(\pi^{-1})=\operatorname{\mathrm{inv}}(\phi(\pi^{-1}))=\operatorname{\mathrm{inv}}(\phi(\pi^{-1})^{-1})$.

  2. 2.

$\operatorname{Des}(\pi)=\operatorname{Des}(\phi(\pi^{-1})^{-1})$

If we denote $\psi(\pi)=(\phi^{-1}(\pi^{-1}))^{-1}$ we obtain a bijective
function from $\mathfrak{S}_{n}$ to $\mathfrak{S}_{n}$ such that

  1. 1.

$\operatorname{\mathrm{inv}}(\pi)=\operatorname{\mathrm{imaj}}(\psi(\pi))$.

  2. 2.

$\operatorname{Des}(\pi)=\operatorname{Des}(\psi(\pi))$.

Hence the distributions of $\operatorname{Des}$ on the sets

$A=\left\\{\pi\in\mathfrak{S}_{n}:\operatorname{\mathrm{inv}}(\pi)=m\right\\}$

and

$B=\left\\{\pi\in\mathfrak{S}_{n}:\operatorname{\mathrm{imaj}}(\pi)=m\right\\}$

are equal. By Theorem 2.5.12, the Schur-positivity of a set $X$ depends only
on the distribution of $\operatorname{Des}$ on $X$. Therefore, $A$ is Schur-
positive only and only if $B$ is. It is obvious that $B$, the set of
permutations $\pi$ in $\mathfrak{S}_{n}$ with $\\\ imaj(\pi)=m$, can be
expressed as a disjoint union of inverse descent classes and is Schur-
positive. Therefore, the set of permutations with fixed length $m$ is also
Schur-positive.

The Schur-positive sets mentioned above will be explored in more depth in
Chapter 4.

Another important class is the set of permutations with a fixed cycle type. In
[22], it was shown that they are Schur-positive. Their generalization - the
roots of unity are studied in Chapter 5.

##  Chapter 3 Schur-positivity of convex caterpillars

###  3.1 Introduction

A symmetric function is called Schur-positive if all the coefficients in its
expansion in terms of Schur functions are non-negative.

With a set $A$ of combinatorial objects, equipped with a descent map
$\operatorname{Des}:A\to 2^{[n-1]}$, one associates the quasi-symmetric
function

$\mathcal{Q}(A):=\sum\limits_{\pi\in
A}\mathcal{F}_{n,\operatorname{Des}(\pi)}$

where $\mathcal{F}_{n,D}$ (for $D\subseteq[n-1]$) are Gessel’s fundamental
quasi-symmetric functions; see Subsection 2.5 for more details.

This chapter focuses on Schur-positive sets of maximal chains in partially
ordered sets. Maximal chains in a labeled poset $P$ are equipped with a
natural descent map. A well-known conjecture of Stanley [40, III, Ch. 21]
implies that all examples of Schur-positive labeled posets, in this sense,
correspond to intervals in the Young lattice.

Another way to equip the set of maximal chains with a descent map is by the
edges in the Hasse diagram. A classic example of a Schur-positive set of this
type, the set of all maximal chains in the non-crossing partition lattice of
type $A$, was given by Stanley [41]. An $EL$ edge-labeling of this poset was
presented in an earlier work of Björner [12]; see also [14, 31, 9].

The goal of this chapter is to present an interesting set of maximal chains in
the non-crossing partition lattice $NC_{n}$ (equivalently: a set of edge-
labeled trees) which is Schur-positive. We will use a variant of Björner’s
$EL$-labeling, presented in [9].

It is well known that maximal chains in the non-crossing partition lattice may
be interpreted as factorizations of the $n$-cycle $(1,2,\dots,n)$ into a
product of $n-1$ transpositions.

######  Definition 3.1.1.

A factorization $t_{1}\cdots t_{n-1}$ of the $n$-cycle $(1,2,\dots,n)$ as a
product of transpositions is called linearly ordered if, for every $1\leq
i\leq n-2$, $t_{i}$ and $t_{i+1}$ have a common letter.

######  Example 3.1.2.

The factorization $(1\ 4)(1\ 3)(1\ 2)$ of $(1\ 2\ 3\ 4)$ is linear, while $(1\
3)(3\ 4)(1\ 2)$ is not.

This definition is motivated by Theorem 3.3.1 below. Denote the set of
linearly ordered factorizations of $(1,2,\dots,n)$ by $\mathcal{L}_{n}$.

######  Proposition 3.1.3.

For every $n\geq 1$, the number of linearly ordered factorizations of the
$n$-cycle $(1,2,\dots,n)$ is

$|\mathcal{L}_{n}|=n2^{n-3}.$

Our main result is

######  Theorem 3.1.4.

The set of linearly ordered factorizations of the $n$-cycle $(1,2,\dots,n)$

satisfies

$\mathcal{Q}(\mathcal{L}_{n})=\sum_{k=0}^{n-1}(k+1)s_{(n-k,1^{k})},$

where the descent set of any $u\in\mathcal{L}_{n}$ is defined by the edge
labeling of [9]. In particular, $\mathcal{L}_{n}$ is Schur-positive.

It should be noted that Theorem 3.1.4 does not follow from Stanley’s proof of
the Schur-positivity of the set of all maximal chains in $NC_{n}$; Stanley’s
action on maximal chains does not preserve linearly ordered chains.

We prove Theorem 3.1.4 by translating it into the language of geometric trees
called convex caterpillars.

######  Definition 3.1.5.

A tree is called a caterpillar if the subgraph obtained by removing all its
leaves is a path. This path is called the _spine_ of the caterpillar.

######  Definition 3.1.6.

A convex caterpillar of order $n$ is a caterpillar drawn in the plane such
that

  1. (a)

the vertices are in convex position (say, the vertices of a regular polygon)
and are labeled ${1,\ldots,n}$ clockwise;

  2. (b)

the edges are drawn as non-crossing straight line segments; and

  3. (c)

the spine forms a cyclic interval $(a,a+1),(a+1,a+2),\ldots,(b-1,b)$ in $[n]$.

Denote by ${Ct}_{n}$ the set of convex caterpillars of order $n$.

######  Example 3.1.7.

Figure 3.1 shows a convex caterpillar $c\in{Ct}_{8}$, with spine consisting of
the edges $(8,1)$ and $(1,2)$, forming a cyclic interval.

12345678 Figure 3.1: A convex caterpillar and its spine

Goulden and Yong [23] introduced a mapping from factorizations of
$(1,2,\ldots,n)$ to non-crossing geometric trees. This mapping is not
injective: to recover the factorization from the tree, one has to choose a
linear extension of a specific partial order on the edges, which we call the
Goulden-Yong partial order; see Definition 3.2.2 below.

In a previous work [27], we proved that the Goulden-Yong order is linear if
and only if the geometric tree is a convex caterpillar; see Theorem 3.3.1
below. It follows that the Goulden-Yong map, restricted to the set
$\mathcal{L}_{n}$ of linearly ordered factorizations, is a bijection between
$\mathcal{L}_{n}$ and the set ${Ct}_{n}$ of convex caterpillars of order $n$.

######  Definition 3.1.8.

The descent set of a linearly ordered factorization
$u=(t_{1},\ldots,t_{n-1})\in\mathcal{L}_{n}$ is

$\operatorname{Des}(u):=\\{i\in[n-2]\,:\,t_{i}=(b,c)\text{ and
}t_{i+1}=(b,a)\text{ with }\ c>a\\}.$

######  Example 3.1.9.

The convex caterpillar $c\in{Ct}_{8}$, drawn in Figure 3.1, corresponds to the
linearly ordered word

$u=\left((7,8),(6,8),(5,8),(1,8),(1,2),(2,4),(2,3)\right)\in U_{8},$

for which $\operatorname{Des}(u)=\\{1,2,3,4,6\\}$.

######  Remark 3.1.10.

In [9], the authors define a map $\phi$ from the set denoted here
$\mathcal{L}_{n}$ to the symmetric group $\mathfrak{S}_{n-1}$; for a detailed
description see Subsection 3.3.2 below. The map $\phi$ is an $EL$-labeling of
the non-crossing partition lattice. This property, relations to Björner’s
$EL$-labeling and other positivity phenomena will be discussed in another
paper.

It turns out that our Definition 3.1.8 above fits nicely with this map.

######  Lemma 3.1.11.

For any $u\in\mathcal{L}_{n}$,

$\operatorname{Des}(\phi(u))=\operatorname{Des}(u).$

See Proposition 3.3.15 below. We further show that the number of caterpillars
with a given descent set depends only on the cardinality of the descent set.

######  Lemma 3.1.12.

For every subset $J\subseteq[n-2]$,

$|\\{c\in{Ct}_{n}:\ \operatorname{Des}(c)=J\\}|=|J|+1.$

These two key lemmas are used to prove Theorem 3.1.4.

###  3.2 Background

This section provides the necessary definitions and historical background to
explain the main results. More information can be found in the references.

####  3.2.1 Maximal chains in the non-crossing partition lattice

The systematic study of non-crossing partitions began with Kreweras [29] and
Poupard [34]. Surveys of results and connections with various areas of
mathematics can be found in [39] and [10].

A non-crossing partition of the set $[n]$ is a partition $\pi$ of $[n]$ into
nonempty blocks with the following property: for every $a<b<c<d$ in $[n]$, if
some block $B$ of $\pi$ contains $a$ and $c$ and some block $B^{\prime}$ of
$\pi$ contains $b$ and $d$, then $B=B^{\prime}$. Let $NC_{n}$ be the set of
all non-crossing partitions of $[n]$. Define a partial order on $NC_{n}$, by
refinement: $\pi\leq\sigma$ if every block of $\pi$ is contained in a block of
$\sigma$. This partial order turns $NC_{n}$ into a graded lattice.

An _edge labeling_ of a poset $P$ is a function from the set of edges of the
Hasse diagram of $P$ to the set of integers. Several different edge labelings
of $NC_{n}$ were defined and studied by Björner [12], Stanley [41], and Adin
and Roichman [9]. Let $\Lambda$ be an edge labeling of $NC_{n+1}$, and let
$F_{n+1}$ be the set of maximal chains in $NC_{n+1}$. For each maximal chain
$\mathfrak{m}:\pi_{0}<\pi_{1}<\dots<\pi_{n}$ define

$\Lambda^{*}(\mathfrak{m}):=\left(\Lambda(\pi_{0},\pi_{1}),\ldots,\Lambda(\pi_{n-1},\pi_{n})\right)\in{\mathbb{N}}^{n},$

with a corresponding descent set

$\operatorname{Des}(\mathfrak{m}):=\left\\{i\in[n-1]\,:\,\Lambda(\pi_{i-1},\pi_{i})>\Lambda(\pi_{i},\pi_{i+1})\right\\}.$

The non-crossing partition lattice is intimately related to cycle
factorizations. The $n$-cycle $(1,2,\ldots,n)$ can be written as a product of
$n-1$ transpositions. There is a well-known bijection between such
factorizations and the maximal chains in $NC_{n+1}$; see, for example, [30,
Lemma 4.3]. A classical result of Hurwitz states that the number of such
factorizations is $n^{n-2}$ [26, 46], thus equal to the number of labeled
trees of order $n$. In the next section, we will describe a connection between
maximal chains and geometric trees.

####  3.2.2 The Goulden-Yong partial order

With each sequence of $n-1$ different transpositions
$w=(t_{1},\dots,t_{n-1})$, associate a geometric graph $G(w)$ as follows. The
vertex set is the set of vertices of a regular $n$-gon, labeled clockwise
$1,2,\dots,n$. The edges correspond to the given transpositions
$t_{1},\dots,t_{n-1}$, where the edge corresponding to a transposition
$t_{k}=(i,j)$ is the line segment connecting vertices $i$ and $j$. See Figure
3.2 for the geometric graph $G(w)$ corresponding to
$w=((1,4),(4,6),(4,5),(1,2),(2,3))$.

123456 Figure 3.2: $G(w)$ for $w=((1,4),(4,6),(4,5),(1,2),(2,3))$

Let $F_{n}$ be the set of all factorizations of the $n$-cycle $(1,2,\ldots,n)$
into a product of $n-1$ transpositions. Write each element of $F_{n}$ as a
sequence $(t_{1},\ldots,t_{n-1})$, where $t_{1}\cdots t_{n-1}=(1,2,\ldots,n)$.
The following theorem of Goulden and Yong gives the necessary and sufficient
conditions for a sequence of $n-1$ transpositions to belong to $F_{n}$.

######  Theorem 3.2.1.

[23, Theorem 2.2] A sequence of transpositions $w=(t_{1},\ldots,t_{n-1})$
belongs to $F_{n}$ if and only if the following three conditions hold:

  1. 1.

$G(w)$ is a tree.

  2. 2.

$G(w)$ is non-crossing; namely: two edges may intersect only in a common
vertex.

  3. 3.

Cyclically decreasing neighbors: For every $1\leq i<j\leq n-1$, if
$t_{i}=(a,c)$ and $t_{j}=(a,b)$, then $c>_{a}b$. Here, $<_{a}$ is the linear
order $a<_{a}a+1<_{a}\dots<_{a}a-1$.

For example, the graph in Figure 3.2 corresponds to a sequence $w\in F_{6}$
and therefore satisfies the conditions of Theorem 3.2.1.

Note that a sequence $w=(t_{1},\ldots,t_{n-1})\in F_{n}$ carries more
information than its Goulden-Yong tree $G(w)$: It defines a linear order on
the edges, with the edge corresponding to $t_{i}$ preceding the edge
corresponding to $t_{j}$ whenever $i<j$. How much of this information can be
recovered from the tree?

######  Definition 3.2.2.

Let $T$ be a non-crossing geometric tree (namely, satisfying conditions 1 and
2 of Theorem 3.2.1) on the set of vertices of a regular $n$-gon, labeled
clockwise $1,2,\dots,n$. Define relations $\prec_{T}$ and $\leq_{T}$ on the
set of edges of $T$ as follows:

  1. 1.

For edges $s$ and $t$ of $T$, we have $s\prec_{T}t$, if $s=(x,z)$ and
$t=(x,y)$ have a common vertex $x$ and $z>_{x}y$ as in condition 3 of Theorem
3.2.1.

  2. 2.

We have $(a,b)\leq_{T}(c,d)$ if there exists a sequence of edges
$(a,b)=t_{0},\ldots,t_{k}=(c,d)$ $(k\geq 0)$ such that for every $0\leq i\leq
k-1$, the edges $t_{i}$ and $t_{i+1}$ satisfy $t_{i}\prec_{T}t_{i+1}$.

######  Lemma 3.2.3.

Let $T$ be a non-crossing geometric tree. Then $\leq_{T}$ is a partial order
on the set of edges of $T$.

###### Proof.

One needs to show that $\leq_{T}$ is reflexive, transitive and antisymmetric
relation on the edges of $T$. Observe that $\leq_{T}$ is reflexive, since for
every edge $t$ of $T$, the sequence $)$ trivially satisfies the conditions of
$\leq_{T}$ as in Definition 3.2.2, hence $t\leq_{T}t$ holds. Next, observe
that if $s\leq_{T}t$ and $t\leq_{T}u$, then by definition of $\leq_{T}$ there
exist sequences $t=t_{0},t_{1},\dots,t_{k}=s$, $s=s_{0}<\dots s_{l}=u$ such
that $t_{i}\prec_{T}t_{i+1}$ for every $0\leq i\leq k-1$ and
$s_{j}\prec_{T}s_{j+1}$ for every $0\leq j\leq l-1$. Then the sequence
$t=t_{0},\dots,t_{k}=s=s_{0},s_{1},\dots,s_{l}=u$ is the sequence that
satisfies the definition of $\leq_{T}$ for $t$ and $u$.

Before showing that $\leq_{T}$ is antisymmetric, note that $\prec_{T}$ is a
strict order on any subset of edges of $T$ that share a common vertex. In
addition, $\prec_{T}$ is an amtisymmetric relation as well. Let $e$ and $f$
edges in $T$ such that $e\leq_{T}f$. By definition of $\leq_{T}$ there exists
a sequence $e=t_{0},\dots,t_{k}=f$ such that $t_{i}\prec_{T}t_{i+1}$ for every
$0\leq i\leq k-1$ such that $t_{i}\prec_{T}t_{i+1}$. Therefore, if we replace
every subsequence $t_{1},\dots,t_{k}$ of form $(v,u_{m}),\dots,(v,u_{m+l})$
with $(v,u_{m}),(v,u_{m+l})$, we obtain a subsequence
$s_{1},\dots,s_{k^{\prime}}$ of $t_{0},\dots,t_{k}$ with the same property
$s_{i}\prec_{T}s_{i+1}$ for every $0\leq i\leq k^{\prime}-1$, every two
consecutive edges share a common vertex, and for every vertex there are at
most two edges in the sequence $s_{0},\dots,s_{k^{\prime}}$ that have it as an
endpoint. If we denote $e=(a,u_{1})$, $s_{i}=(u_{i},u_{i+1})$ for $1\leq i\leq
k^{\prime}-1$, $f=(u_{k^{\prime}-1},b)$ the sequence of vertices
$a,u_{0},\dots,u_{k^{\prime}-1},b$ is a path from $a$ to $b$ in the tree $T$.
One the other hand, if $f\leq_{T}e$, by the same reasoning, one shows an
existence of a sequence $f=s^{\prime}_{1},\dots,s^{\prime}_{k^{\prime\prime}}$
with the same properties as $s_{0},\dots,s_{k^{\prime}}$. Since there is
exactly one path between two vertices in a tree, we have
$k^{\prime}=k^{\prime\prime}$ and that
$(s_{0},\dots,s_{k^{\prime}})=(s^{\prime}_{k^{\prime}\prime},\dots,s^{\prime}_{9}).$
Hence, we have both $s_{i}\prec_{T}s_{i+1}$ and $s_{i+1}\prec_{T}s_{i}$ for
every $0\leq i\leq k^{\prime}-1$, which is a contradiction, unless
$k^{\prime}=0$. Therefore $\leq_{T}$ prime is antisymmetric. We have shown
that $\leq_{T}$ is reflexive, transitive and antisymmetric. Therefore, we are
done. ∎

We call $\leq_{T}$ the Goulden-Yong partial order corresponding to $T$.

######  Observation 3.2.4.

For every factorization $w=(t_{1},\ldots,t_{n})\in F_{n}$, the order

$t_{1}<t_{2}<\ldots<t_{n}$ is a linear extension of the Goulden-Yong order
$<_{G(w)}$.

######  Example 3.2.5.

In Figure 3.2, the tree $T=G(w)$ gives the partial order satisfying
$(1,4)<_{T}(4,6)<_{T}(4,5)$ and $(1,4)<_{T}(1,2)<_{T}(2,3)$. It is not a
linear order. The order $(1,4)<(4,6)<(4,5)<(1,2),(2,3)$ is a linear extension
of it.

###  3.3 Convex caterpillars

In this section, we prove Theorem 3.1.4 using the properties of convex
caterpillars.

####  3.3.1 Basic properties of convex caterpillars

Let us use the following conventions. All arithmetical operations on the
elements of $[n]$ will be performed modulo $n$. We write $[a,b]$ to denote the
cyclic interval $\\{a,a+1,\dots,b\\}$. Using this notation, for the edges $(a\
b),(a\ c)$ of a geometric non-crossing tree $T$, we have $(a\ c)<_{T}(a\ b)$
if and only if $b\in[a,c]$.

The following result was proved in [27]. Later in this section, we provide a
somewhat different proof, details of which will be used later.

######  Theorem 3.3.1.

[27, Theorem 3.2] The Goulden-Yong order on the edge set of a non-crossing
geometric tree $T$ is linear (total) if and only if $T$ is a convex
caterpillar.

The following observation follows from the fact that a linear extension of a
Goulden-Yong order $<_{T}$ on the edges of the geometric non-crossing tree $T$
corresponds to a factorization of the cycle $(1\dots n)$ into $n-1$
transpositions.

######  Observation 3.3.2.

If $T$ is a geometric non-crossing tree and $<_{T}$ is linear, then any two
consecutive edges in $<_{T}$, viewed as transpositions in $\mathfrak{S}_{n}$,
do not commute and therefore have a common vertex.

The following lemma gives sufficient conditions for $<_{T}$ to be non-linear.

######  Lemma 3.3.3.

Let $T$ be a non-crossing geometric tree. The order $<_{T}$ is not linear in
the following cases.

  1. 1.

There are edges $(a\ b),(c\ d),(e\ f)$ of $T$ such that $(a\ b)<_{T}(c\ d),(e\
f)$ and $c,d\in[a,b-1]$ and $e,f\in[b,a-1]$.

  2. 2.

$T$ has edges $(a\ b),(c\ d),(e\ f)$ such that $(c\ d),(e\ f)<(a\ b)$ and
$c,d\in[b+1,a]$ and $e,f\in[a+1,b]$.

###### Proof.

We prove the first case, the second one being similar by reversing directions.
Assume that $<_{T}$ is linear and that the first case holds. For every
$v\in[a+1,b-1]$, the edge $(v\ b)$ is smaller than $(a\ b)$ in $<_{T}$. The
same is true for any edge $(a\ v)$ with $v\in[b+1,a-1]$. Combining this fact
with the non-crossing property of $T$, we deduce that the endpoints of any
edge that is larger than $(a\ b)$ in $<_{T}$ are either both in $[a,b-1]$ or
both in $[b,a-1]$. On the other hand, by Observation 3.3.2, every pair of
consecutive edges shares a common vertex. Therefore, the endpoints of any two
consecutive edges greater than $(a\ b)$ in $<_{T}$ must all be in either
$[a,b-1]$ or $[b,a-1]$. Using induction, we conclude that the endpoints of the
edges greater than $(a\ b)$ in $<_{T}$ are all in $[a,b-1]$ or all in
$[b,a-1]$, contradicting the assumption. ∎

We are ready to prove Theorem 3.3.1.

###### Proof of Theorem 3.3.1.

Assume that $T$ is a convex caterpillar. If the spine of $T$ does not contain
any edges, then $T$ is a star; hence, every pair of edges is comparable
because they have a common vertex, and the Goulden-Yong order is linear.

Otherwise, let $(a\ a+1),(a+1\ a+2)\dots,(b-2\ b-1),(b-1\ b)$ be the spine of
$T$. For every pair of edges $(k\ l)$ and $(k\ m)$ that share a common vertex
$k$, $(k\ l)<_{T}(k\ m)$ holds if and only if $m\in[k+1,l-1]$ where
$[k+1,l-1]$ denotes the cyclic interval $\\{k+1,\dots,l-1\\}$. Note that it is
simply a restatement of the fact that the neighbors of $k$ are ordered
counterclockwise. Therefore, all the edges of the spine are comparable and
$(a\ a+1)<_{T}(a+1\ a+2)\dots<_{T}(b-1\ b)$. It also implies that if $(k\
k+1)$ is an edge in the spine, then for every edge $(k\ l)$ that has $k$ as an
endpoint, $(k\ l)\leq_{T}(k\ k+1)$ and for every edge $(k+1\ m)$ that has
$k+1$ as an endpoint, we have $(k\ k+1)\leq_{T}(k+1\ m)$. It follows that if
the edges $(k\ k+1),(k+1\ k+2)\dots,(m-1\ m)$ are in the spine of $T$, then
for every edge $(k\ j)$ connected to $k$ and every edge $(m\ l)$ connected to
$m$ we have $(k\ j)\leq_{T}(k\ k+1)<_{T}\dots<_{T}(m-1\ m)\dots\leq_{T}(m\
l)$. Any edge in the caterpillar is either in the spine or has a common vertex
with an edge in the spine. Therefore, any two edges are comparable.

To prove the converse statement, assume that $<_{T}$ is linear. Enumerate the
edges such that $(a_{1}\ b_{1})<_{T}\dots<_{T}(a_{n-1}\ b_{n-1})$. Let $t_{l}$
denote the $l$-th edge in $<_{T}$, namely $(a_{l}\ b_{l})$.

By Observation 3.3.2, since $<_{T}$ is linear, every pair of adjacent edges
shares a common vertex. Now we claim that the first edge must be of the form
$(i\ i+1)$ for some $i$. To see that, denote $t_{1}=(i\ j)$. By the proof of
Lemma 3.3.3 the endpoints of every other edge of $T$, which is necessarily
larger that $t_{1}$ in the linear order, must be either both in $[i,j-1]$ or
both in $[j,i-1]$. By Lemma 3.3.3, either there are no edges with endpoints in
$[i,j-1]$ or no edges with endpoints in $[j,i-1]$, which implies that either
$[i,j]$ or $[j,i]$ consists of precisely two points, which means that either
$i=j+1$ or $j=i+1$ holds.

Next, observe that $i$ must be a leaf since the existence of an edge $(i\
j)<_{T}(i\ i+1)$, contradicts the fact that $(i\ i+1)$ is the first edge in
$<_{T}$. Next, we use induction to show that for every $1\leq m\leq n-1$, the
following statements hold:

  1. 1.

The endpoints of the first $m$ edges in $<_{T}$ form a cyclic interval $[j,k]$
in $[n]$.

  2. 2.

Vertices $j,j+1,\dots,i-1,i$ are leaves in $T$.

  3. 3.

Edges $(i\ i+1),(i+1\ i+2),\dots(k-1\ k)$ are edges in $T$ and occur among the
first $m$ edges.

  4. 4.

Every edge that has at least one of $j,j+1\dots,k-1$ as an endpoint occurs
among the first $m$ edges.

  5. 5.

Either $t_{m}$ = $(k-1\ k)$ or $t_{m}=(k\ j)$ is true.

As we have shown, $t_{1}=(i\ i+1)$ for some $1\leq i\leq n$ and $i$ is a leaf.
Therefore, the statements hold for $m=1$. Assume that the statement holds for
$m$. According to the induction hypothesis, we have either $t_{m}=(k\ j)$ or
$t_{m}=(k-1\ k)$. From the linearity of $<_{T}$, $t_{m+1}$ and $t_{m}$ have a
common vertex. Again, by the induction hypothesis $j$ and $k-1$ cannot be
endpoints of $t_{m+1}$, therefore, $t_{m+1}$ must have $k$ as an endpoint.
Next, we show that $t_{m+1}$ is either $(k\ k+1)$ or $(k\ j-1)$. Assume
$t_{m+1}=(k\ l)$ for $l\neq j-1,k+1$. There must be an edge (necessarily not
among the first $m$ edges) with endpoint $j-1$, and similarly an edge with
endpoint $k+1$. Therefore we must have edges $(k\ l)<_{T}(s\ t),(u\ v)$ with
$u,v\in[k\ l-1]$ and $s,t\in[l,k-1]$ contradicting Lemma 3.3.3. Now if
$t_{m+1}=(k\ k+1)$, we are done, since statements $1$ and $2$ hold by the
induction hypothesis for $m$, $3$ and $5$ hold for $m+1$, and $4$ holds
because $(k\ k+1)$ must be the greatest edge in $<_{T}$ that has $k$ as an
endpoint according to Part 3 of Theorem 3.2.1.

If $t_{m+1}=(k\ j-1)$, then for every $v\in[k+1,j-2]$ we have $(j-1\
v)<_{T}(j-1\ k)$, which implies that if $(j-1\ v)=t_{l}$ then $l\leq m$, which
is impossible since $v\notin[j,k]$ according to the induction assumption. On
the other hand, for every $v\in[j,k-1]$, $(j-1\ v)$ cannot be an edge since,
by assumption, every edge with endpoints $j,\dots k-1$ occurs among the first
$m$ edges. Therefore, $j-1$ must be a leaf. Again, it is easy to check that
assumptions $1,2,3,4,5$ still hold for $m+1$. Now, for $m=n-1$, we see that
$T$ must be a geometric caterpillar because, by construction, the vertices
that are not leaves are $i+1,i+2,\dots,k$ for some $k$, with edges $(i+1\
i+2),\dots,(k-1,k)$ connecting them. ∎

For example, the tree in Figure 3.2 is a caterpillar but not a convex one. The
corresponding Goulden-Yong order is not linear.

######  Corollary 3.3.4.

A non-crossing geometric tree $T$ on $n$ vertices is a convex caterpillar if,
and only if, there is a unique $w\in F_{n}$ such that $G(w)=T$.

We can view each edge of $T$ as a transposition. Therefore, in the rest of the
paper, we shall identify a convex caterpillar $c\in{Ct}_{n}$ with the
corresponding sequence of transpositions $(t_{1},\ldots,t_{n-1})\in F_{n}$.

######  Proposition 3.3.5.

In a convex caterpillar $c=(t_{1},\dots,t_{n-1})$:

  1. 1.

Any two consecutive edges $t_{i}$ and $t_{i+1}$ share a common vertex.

  2. 2.

The first edge $t_{1}$ is of the form $(a,a+1)$ for some $a$. The same holds
for the last edge $t_{n-1}$.

###### Proof.

The first part is simply a restatement of Observation 3.3.2. The second part
follows from the proof of Theorem 3.3.1. ∎

######  Definition 3.3.6.

Let $e$ be an edge of a caterpillar $c$.

  1. 1.

We say that $e$ is a _branch_ if (at least) one of its endpoints is a leaf.

  2. 2.

We say that $e$ is a _link_ if its endpoints have cyclically consecutive
labels.

We get the following observation by carefully reading the proof of Theorem
3.3.1.

######  Observation 3.3.7.

An edge of a convex caterpillar $c$ is both a link and a branch if and only if
it is either the first or the last edge of $c$.

######  Lemma 3.3.8.

Let $c=(t_{1},\dots,t_{n-1})\in{Ct}_{n}$. The following statements hold.

  1. 1.

The endpoints of the first $k$ edges form a cyclic interval in $[n],$ for
every $1\leq k\leq n-1$.

  2. 2.

If the first edge is $(i,i+1)$, then the endpoints of the first $k$ branches
which are leaves are $i,i-1,\dots,i-k+1$, in that order.

  3. 3.

If the first edge is $(i,i+1)$ then the first $k$ links are
$(i,i+1),(i+1,i+2),\ \dots,\ (i+k-1,i+k)$.

  4. 4.

For $1\leq k<n-1$, the product of the first $k$ edges, viewed as
transpositions, is equal to the cycle $(l\ l+1\ \dots\ m)$ where $l$ is the
leaf endpoint of the last branch among the first $k$ edges and $(m-1,m)$ is
the last link among the first $k$ edges.

###### Proof.

Parts $1$, $2$ and $3$ follow from the proof of Theorem 3.3.1. Part $4$
follows by induction and using the fact that if the product of the first $k$
edges (viewed as transpositions) is the cycle $(l\ l+1\dots\ l+k)$, where the
cyclic interval $[l,l+k]$ is formed by the endpoints of the first $k$ edges,
then $t_{k+1}$, viewed as transposition, is either $(l+k\ l+k+1)$ or $(l+k\
l-1)$. Multiplying the cycle $(l\ l+1\dots\ l+k)$ by $t_{k+1}$, it is easily
verified that the statement is true for $k+1$. ∎

######  Corollary 3.3.9.

Every $c=(t_{1},\dots,t_{n-1})\in{Ct}_{n}$ is completely determined by its
first edge $t_{1}$ and the set of indices $i$ for which $t_{i}$ is a branch, ,
which can be any subset of [n-1] containing $1$ and $n-1$.

This proves, in particular, Proposition 3.1.3.

####  3.3.2 A labeling of maximal chains

The following labeling of maximal chains in the non-crossing partition lattice
was introduced by Adin and Roichman in [9] and is closely related to the
$EL$-labeling introduced by Björner in [12]. This subsection describes this
labeling, denoted by $\phi$.

Recall, from Definition 3.1.8, the notion of a descent set of a convex
caterpillar.

Next, we show the connection to the descents defined by the map $\phi$ in [9].
First, let us describe $\phi$. For $w=(t_{1},\dots,t_{n-1})\in F_{n}$ define
the partial products $\sigma_{j}=t_{j}\dots t_{n-1}$ with $\sigma_{n}=id$. By
definition, $\sigma_{j}=t_{j}\sigma_{j+1}$. For $1\leq j\leq n-1$ define

$A_{j}=\left\\{1\leq i\ n-1:\sigma_{j}(i)>\sigma_{j+1}(i)\right\\}.$

We get the following statement from the discussion preceding Definition 3.2 in
[9].

######  Proposition 3.3.10.

The following statements hold.

  1. 1.

For each $1\leq j\leq n-1$, $|A_{j}|=1$.

  2. 2.

The map $\pi_{w}$ defined by

$\pi_{w}(j)=i\ if\ A_{j}=\left\\{i\right\\}$

is a permutation in $\mathfrak{S}_{n-1}$.

######  Definition 3.3.11.

[9, Definition 3.2] Define $\phi:F_{n}\to\mathfrak{S}_{n-1}$ by

$\phi(w)=\pi_{w}.$

Define for each $w\in F_{n}:$

$\operatorname{Des}(w)=\operatorname{Des}(\phi(w)).$

####  3.3.3 Descents of convex caterpillars

We now calculate the restriction of $\phi$ to $Ct_{n}$. Before we proceed,
note that the arguments used to prove Theorem 3.3.1 hold for the last edges.
Therefore, we can formulate statements analogous to the ones used in the proof
for the first edges of $c$ for the last edges of $c$ instead. We sum them up
in the following lemma.

######  Lemma 3.3.12.

Let $c=(t_{1},\dots,t_{n-1})\in{Ct}_{n}$. The following statements hold for
every $1\leq m\leq n-1$:

  1. 1.

The last edge of $c$, $t_{n-1}$ is of the form $(i-1\ i)$ for some $i$ and $i$
is a leaf of $c$.

  2. 2.

The endpoints of the last $m$ edges in $T$ for a cyclic interval in $[j,k]$ in
$[n]$.

  3. 3.

Vertices $k,k-1,\dots,i$ are leaves in $T$ and are endpoints of the last $m$
edges.

  4. 4.

Edges $(j,j+1),\dots,(i-1,i)$ are edges in $T$ and occur among the last $m$
edges.

  5. 5.

Every edge that has $j+1,\dots,k$ as an endpoint occurs among the last $m$
edges.

  6. 6.

Either $t_{n-m}=(k,k+1)$ or $t_{n-m}=(k,j)$ is true.

Note that the product of the last $m$ edges in a caterpillar is just
$\sigma_{n-m}$. Parts 5 and 6 of the preceding lemma can be reformulated in
terms of $\sigma_{j}$ and $t_{j}$, as follows.

######  Corollary 3.3.13.

Let $c=(t_{1},\dots,t_{n})\in{Ct}_{n}$. Then, for every $1\leq j\leq n-1$,
$\sigma_{j}$ is equal to the cycle $(l\ l+1\ \dots\ m)$ for some $l\in[n]$ and
$t_{j}=(l,l+1)$ or $t_{j}=(l,m)$.

The following proposition gives us a simple method to calculate the values of
$\phi$ restricted to ${Ct}_{n}$.

######  Proposition 3.3.14.

Let $c\in Ct_{n}$, $1\leq j\leq n-1$ and $\sigma_{j+1}=(l\ l+1\ \dots m)$.
Then

$\phi(c)(j)=\begin{cases*}l&if $\sigma_{j+1}(l)\neq l$ and $l\neq n$\\\ m&if
$\sigma_{j+1}(l)=l$ and $l>m$ or $l=n$\\\ m-1&if $\sigma_{j+1}(l)=l$ and
$l<m$\end{cases*}$

###### Proof.

By Corollary 3.3.13, we have $\sigma_{j}=(l\ l+1\ \dots m)$, and either
$t_{j}=(l,l+1)$ and $\sigma_{j+1}=(l+1\ \dots\ m)$ hold, or $t_{j}=(l,m)$ and
$\sigma_{j+1}=(l\ l+1\ \dots\ m-1)$. By Proposition 3.3.10 there is exactly
one $1\leq i\leq n-1$ such that $\sigma_{j}(i)>\sigma_{j+1}(i)$, which is
equal to $\phi(c)(j)$ by Definition 3.3.11. We calculate it for each case.
Before proceeding, note that if $t_{j}=(l,l+1)$, then $\sigma_{j+1}(m)=l+1$
and if $t_{j}=(l,m)$ then $\sigma_{j+1}(m)=m$. In both cases, we have
$\sigma_{j+1}(m)\neq l=\sigma_{j+1}(m)$.

First, observe that if $l=n$, then whether $t_{j}=(l,m)$ or $t_{j}=(l-1\ l)$
we have

$\sigma_{j}(m)=n>\sigma_{j+1}(n),$

which implies $\phi(c)(j)=m$.

If $l\neq n$ and $t_{j}=(l,l+1)$ then

$\sigma_{j+1}(l)=l<l+1=\sigma_{j}(l),$

hence $\phi(c)(j)=l$.

If $l\neq n$ and $t_{j}=(m,l)$ and $l>m$, then

$\sigma_{j}(m)=l>m=\sigma_{j+1}(m),$

and $\\\ phi(c)(j)=m$. Otherwise,

$\sigma_{j+1}(m-1)=l<m=\sigma_{j}(m),$

hence, $\phi(c)(j)=m-1$. ∎

######  Proposition 3.3.15.

The descent set of a convex caterpillar, defined in Definition 3.1.8,
coincides with the descent set defined using the map $\phi$.

###### Proof.

Let $c=(t_{1},\dots,t_{n-1})\in{Ct}_{n}$. We show that for every $1\leq i\leq
n-2$, $j$ is a descent of $\phi(c)$ if and only $j$ is a descent of $c$ as in
Definition 3.1.8, namely $t_{j}=(k,l)$, $t_{j+1}=(l,m)$ for $1\leq k,l,m\leq
n$, such that $k>m$. We do this by verifying the statement by calculating the
$\phi(c)(j),\phi(c)(j+1)$ using Proposition 3.3.14 for every $1\leq j\leq n-2$
and every possible configuration of $t_{j},t_{j-1}$.

First, we check that the statement is true in the special case $j=n-2$. If
$j=n-2$, then by Lemma 3.3.12, $\sigma_{n-1}=(i,i+1)$ for some $1\leq i\leq n$
and two possibilities for $t_{n-2}$.

  1. 1.

$t_{n-2}=(i-1,i)$. If $i-1,i\neq n$, then $t_{n-2}=(i-1,i),t_{n-1}=(i,i+1)$
and $i-1<i<i+1$, thus $n-2$ is not a decent of $c$ and is not a descent of
$\phi(c)$, since $\phi(c)(n-2)=i-1<i=\phi(c)(n-1)$.

If we have $i=n$, then $t_{n-2}=(n-1,n),t_{n-1}=(n,1)$, which means that $n-2$
is a descent of $c$. But we also have $\phi(c)(n-1)=1$ and $\phi(c)(n-2)=n-1$,
which means that $n-1$ is also a descent of $\phi(c)$.

On the other hand, if $i-1=n$, we have $t_{n-2}=(n,1)$ and $t_{n-1}=(1,2)$,
which means that $n-2$ is a descent of $c$ and is a descent of $\phi(c)$,
since $\phi(c)(n-2)=2>1=\phi(c)(n-1)$.

  2. 2.

$t_{n-2}=(i,i+2)$. If none of $i,i+1$ equals $n$, then
$t_{n-2}=(i,i+2),t_{n-1}=(i,i+1)$, where $i+2>i+1$, which implies that $n-2$
is a descent of $c$ and also a descent of $\phi(c)$ since
$\phi(n-2)=i+1>i=\phi(n-1)$.

If $i+1=n$, then $t_{n-2}=(n-1,1),t_{n-1}=(n-1,n)$, which implies that $n-2$
is not a descent of $c$ and also not a descent of $\phi(c)$, since
$\phi(c)(n-2)=1<n-1=\phi(c)(n-1)$.

If $i=n$, then $t_{n-2}=(n,2),t_{n-1}=(n,1)$, which implies that $n-2$ is a
descent of $c$ and also a descent of $\phi(c)$, as we have
$\phi(c)(n-2)=2>1=\phi(c)(n-1)$.

We show that the statement is true for $1\leq j<n-2$. By Lemma 3.3.12, we have
$\sigma_{j+2}=(l,l+1\ \dots\ m)$ for some $1\leq l\leq n$ and four
possibilities $t_{j},t_{j+1}$.

  1. 1.

We have $t_{j}=(l-2,l-1)$ and $t_{j+1}=(l-1,l)$. Then $j$ is not a descent of
$c$, if $l-2<l$, which implies $l-2<l-1<l$. Applying Proposition 3.3.14, we
get $\phi(j)(l-2)$ and $\phi(j)(j+1)=l-1$, which means $j$ is also not descent
of $\phi(c)$.

If $j$ is a descent of $c$, then either $l-1=n$ or $l-2=n$. If we have$l-2=n$,
then $t_{j}=(n,1),t_{j+1}=(1,2)$ and $\sigma_{j+2}=(2\ \dots\ m)$. From
Proposition 3.3.14, it follows that $\phi(c)(j)=m$ and $\phi(c)(j+1)=1$, which
means that $j$ is also a descent of $\phi(c)$. In case $l-1=n$, we have
$t_{j}=(n-1,n),t_{j}=(n,1)$ and $\sigma_{j+2}=(1,\dots,m)$. Applying
Proposition 3.3.14, we get $\phi(c)(j)=n-1$, $\phi(c)(j+1)=m$, which implies
that $j$ is also a descent of $\phi(c)$.

  2. 2.

We have $t_{j}=(l-1,l)$ and $t_{j+1}=(l,m+1)$. In this case, $j$ is not a
descent of $c$ if $l-1<m+1$ holds, which implies that $l-1<l<m<m+1$. Then we
have $\phi(c)(j)=l-1$ and $\phi(c)(j+1)=m$, again indicating that $j$ is not a
descent of $\phi(c)$.

If $j$ is a descent of $c$, we have $l-1>m+1$, together with the following
possibilities:

    1. (a)

We have $l-1=n$, $t_{j}=(n,1)$, $t_{j+1}=(1,m+1)$ and $\sigma_{j+1}(c)=(1\
\dots\ m)$. Then $\phi(c)(j)=m+1$ and $\phi(c)(j+1)=m$ and $j$ is a descent of
$\phi(c)$.

    2. (b)

We have $m=n$, $t_{j}=(l-1,l)$, $t_{j+1}=(l,1)$ and $\sigma_{j+2}(l\dots n)$.
In this case

$\phi(c)(j)=l-1>1=\phi(c)(j+1)$

and $j$ is a descent of $\phi(c)$.

    3. (c)

We have $m<m+1<l-1<l$ and $\sigma_{j+2}=(l\dots m)$. Then
$\phi(c)(j)=l-1>m=\phi(c)(j+1)$ and $j$ is a descent of $\phi(c)$.

In each case, $j$ is a descent of $c$ if and only if $j$ is a descent of
$\phi(c)$.

  3. 3.

We have $t_{j}=(l-1,m+1)$ and $t_{j+1}=(l-1,l)$. The condition for $j$ to not
be a descent of $c$ is that $m+1<l$, which implies $m+1<l-1<l$. Then
$\phi(c)(j)=m+1$ and $\phi(c)(j+1)=l-1$ and $j$ is also not a descent of
$\phi(c)$. If $j$ is a descent of $c$, then $m+1>l-1$, which implies
$m+1>m>l>l-1$. In this case, we have $\phi(c)(j)=m$ and $\phi(c)(j+1)=l-1$,
which implies that $j$ is also a descent of $\phi(c)$.

  4. 4.

We have $t_{j}=(l,m+2)$ and $t_{j+1}=(l,m+1)$. Then $j$ is not a descent of
$c$ if $m+2<m+1$, which holds only if $m+1=n$. Then $t_{j}=(l,1)$ and
$t_{j+1}=(l,n)$ with $\sigma_{j+2}=(l\ \dots\ m)$. Then $\phi(c)(j)=1$ and
$\phi(c)(j+1)=n-1$ and $j$ is also not a descent of $\phi(c)$.

When $j$ is a descent of $c$, then $m+2>m+1$. In this case, we have $l>m+1$ if
and only if $l>m+2$. If $l>m+1,m+2$, then we have

$\phi(c)(j)=m+2>\phi(c)(j+1)=m+1$

and if $l<m+1$ we have

$\phi(c)(j)=m+1>\phi(c)(j+1)=m.$

In both cases, $j$ is a descent of $\phi(c)$.

We have exhausted all possible configurations for $j$, and $t_{j},t_{j+1}$,
and our proof is complete.

∎

####  3.3.4 Schur-positivity of convex caterpillars

######  Definition 3.3.16.

Let $c=(t_{1},\dots,t_{n-1})$ be a convex caterpillar, and let $i$ be the
index of the first edge with $1$ as its endpoint. The edge $t_{i}$ is called
_main edge_ of $c$ and the index $i$ is called _main index_ of $c$, denoted
$\mathtt{I}(c)$.

For example, for $c=\left((4,5),(5,6),(3,6),(1,6),(1,2)\right)$ we have
$\mathtt{I}(c)=4$.

Using Lemma 3.3.8, we prove the following explicit description of the descents
of a convex caterpillar $c$, based on $\mathtt{I}(c)$ and on the geometry of
$c$.

######  Lemma 3.3.17.

Let $c\in{Ct}_{n}$ and $i\in[n-2]$. Then:

  1. 1.

For $1\leq i<\mathtt{I}(c)-1$, $i$ is a descent of $c$ if and only if
$t_{i+1}$ is a branch of $c$.

  2. 2.

For $i=\mathtt{I}(c)-1$, $i$ is always a descent of $c$.

  3. 3.

For $i=\mathtt{I}(c)$, $i$ is a descent of $c$ if and only if $1$ is not a
leaf of $c$.

  4. 4.

For $\mathtt{I}(c)<i\leq n-2$, $i$ is a descent of $c$ if and only if $t_{i}$
is a branch of $c$.

###### Proof.

We prove each case separately

  1. 1.

First, suppose that $i=\mathtt{I}(c)$. Then $t_{i}=(a\ b)$ and $t_{i+1}=(b\
1)$ for some $2\leq a,b\leq n$. Obviously, $a>1$, therefore, $t_{i}$ is a
descent.

  2. 2.

If $t_{i+1}$ is a branch, then $t_{i}=(a\ b),\ t_{i+1}=(a\ c)$ for some
$a,b,c>1$. If $(a\ b)$. By Lemma 3.3.8 $b=a-1$ if $(a\ b)$ is a link or
$b=c+1$ if $(a\ b)$ is a branch, the endpoints of the first $i+1$ edges form
the cyclic interval $[c,a]$. Since $i<i(c)$ we $1<c<b<a$, so $i$ is a descent.
On the other hand, if $t_{i+1}$ is a link, then $t_{i}=(a,b)$, $t_{i+1}=(b\
b+1)$, and also $a$ is between $b+1$ and $b$ in $<_{b}$. Since $1<a$, we have
$a<b$, so $i$ is not a descent.

  3. 3.

Now, if $i=\mathtt{I}(c)$ and $1$ is a leaf. Then we have $t_{i}=(a\ 1),\
t_{i+1}=(a\ b).$ Since $1<b$, $t_{i}$ is not a descent. In contrast, if
$t_{i}$ is a link, then $t_{i}=(1\ a),\ t_{i+1}=(1\ b)$ and since both $a$ and
$b$ are sorted counterclockwise and are greater than $1$ in cyclic order
$<_{1}$, we have $b<a$, so $i$ is a descent.

  4. 4.

Now suppose that $i>\mathtt{I}(c)$. Then if $t_{i}$ is a branch, we have
$t_{i}=(a\ b)\ t_{i+1}=(a\ c)$ where $b$ and $c$ are ordered counterclockwise
and $a<b,c<n$, which implies that $c<b$ and that $t_{i}$ is a descent. On the
other hand, if $t_{i}$ is a link, we have $t_{i}=(a\ a+1),\ t_{i+1}=(a+1\ k)$
where $k>a$, and $i$ is not a descent.

∎

Combining Lemmas 3.3.8 and 3.3.17 with Corollary 3.3.9, we deduce the
following key proposition.

######  Proposition 3.3.18.

A convex caterpillar $c$ is uniquely determined by $\mathtt{I}(c)$ and
$\operatorname{Des}(c)$.

###### Proof.

By Lemma 3.3.9, it suffices to show that the pair
$(\mathtt{I}(c),\operatorname{Des}(c))$ determines the first edge and
branches. Note that by Observation 3.3.7, the first and last edges are always
branches.

Denote $k:=\mathtt{I}(c)$. When $i<k$, combining Lemma 3.3.17 and Lemma 3.3.8
allows us to determine whether the $i$-th edge is a branch or a link. By Part
2 of Lemma 3.3.17, we know whether $1$ is a leaf and whether $e_{k}$ is a
branch. The first edge is determined in both cases by applying parts $2$ and
$3$ of Lemma 3.3.8. Branches with indices greater than $k$ are determined by
Part $3$ of Lemma 3.3.17. Therefore, the first edge and the branches are
entirely determined by the descent set and $k=\mathtt{I}(c)$ as desired. ∎

The following lemma describes the possible values of $\mathtt{I}(c)$, given
the descent set of $c$.

######  Lemma 3.3.19.

Let $c\in{Ct}_{n}$. Then $\mathtt{I}(c)=1$ or
$\mathtt{I}(c)-1\in\operatorname{Des}(c)$.

###### Proof.

Let $X\subseteq\left[n-2\right]$ and suppose that $\operatorname{Des}(c)=X$.
We show that $\mathtt{I}(c)=1$ or $\mathtt{I}(c)\in X+1$. It is clear that if
$\mathtt{I}(c)\neq 1$ then there exists a $i\in\mathtt{des}_{C}(1)+1$ such
that $\mathtt{I}(c)=i$ according to part $1$ of the lemma 3.3.17. ∎

######  Lemma 3.3.20.

For every subset $J\subseteq\left[n-2\right]$ and every
$i\in\left(1+J\right)\cup\left\\{1\right\\}$, there exists a unique
$c\in{Ct}_{n}$ such that $\operatorname{Des}(c)=J$ and $\mathtt{I}(c)=i$.

###### Proof.

Recall that every caterpillar is determined by its first edge and true
branches, where every $J\subseteq\left\\{2,\dots,n-2\right\\}$ can appear as
the set of true branches of a caterpillar. Placing $\mathtt{I}(c)$ after $x\in
J$ results in a proper set of true branches, which defines a caterpillar. Now,
suppose that $i\notin J$. Then $(1,2)$ can be the first edge of the leaf since
$1$ is a leaf; hence $1$ is not a descent, and the branches correspond to the
members of $X$. If $1\in X$, then $(n\ 1)$ can be the first edge, with the
rest of the branches defined by the descents. ∎

######  Corollary 3.3.21.

For every subset $J\subseteq\left[n-2\right]$, the number of convex
caterpillars with a descent set $J$ equals $\left|J\right|+1$.

The following observation is well known.

######  Observation 3.3.22.

For every $0\leq k\leq n-1$ we have

$\\{\operatorname{Des}(T)\,:\,T\in{\rm
SYT}(n-k,1^{k})\\}=\\{J\subseteq[n-1]\,:\,|J|=k\\},$

each set being obtained exactly once.

###### Proof of Theorem 3.1.4.

Combine Corollary 3.3.21 with Observation 3.3.22 and Theorem 2.5.9 to deduce

$\mathcal{Q}(Ct_{n})=\sum_{k=0}^{n+1}(k+1)\sum\limits_{\begin{subarray}{c}J\subseteq[n-1]\\\
|J|=k\end{subarray}}\mathcal{F}_{n,J}=\sum_{k=0}^{n+1}(k+1)s_{n-k,1^{k}}.$

∎

##  Chapter 4 Cyclic descent extensions

###  4.1 Introduction

This chapter and the next study cyclic descent extensions. We will build upon
recent work by Adin, Hegedüs and Roichman [3].

Recall that the descent set of a permutation
$\pi=\left[\pi_{1},\dots,\pi_{n}\right]\in\mathfrak{S}_{n}$ is

$\operatorname{Des}(\pi)\coloneqq\left\\{1\leq i\leq
n-1:\pi_{i}>\pi_{i+1}\right\\}\subseteq\left[n-1\right].$

Its cyclic descent set was defined by Cellini in [15] as

$\operatorname{\mathrm{CDES}}(\pi)\coloneqq\left\\{1\leq i\leq
n:\pi_{i}>\pi_{i+1}\right\\}\subseteq\left[n\right],$

with the convention that $\pi_{n+1}\coloneqq\pi_{1}$.

######  Definition 4.1.1.

The cyclic shift of a set is the bijection ${\rm sh}:2^{[n]}\longrightarrow
2^{[n]}$ defined by

$\mathrm{sh}(P)\coloneqq\left\\{i+1\pmod{n}:i\in P\right\\}.$

Define also the cyclic shift of a permutation $\pi\in\mathfrak{S}_{n}$ by

$\rho(\pi)=\left[\pi_{n},\pi_{1},\dots,\pi_{n-1}\right].$

######  Observation 4.1.2.

$\operatorname{\mathrm{CDES}}$ together with $\rho$ satisfy the following 3
conditions.

  1. 1.

$\operatorname{\mathrm{CDES}}(\pi)\cap\left[n\right]=\operatorname{Des}(\pi$).

  2. 2.

$\operatorname{\mathrm{CDES}}\left(\rho\left(\pi\right)\right)=\rm{sh}\left(\operatorname{\mathrm{CDES}}\left(\pi\right)\right)$.

  3. 3.

For all $\pi\in\mathfrak{S}_{n}$,
$\emptyset\subsetneq\operatorname{\mathrm{CDES}}(\pi)\subsetneq\left[n\right]$.

We are interested in generalizing this situation as follows.

######  Definition 4.1.3.

[6] Let $\mathcal{T}$ be a finite set, equipped with a descent map
$\operatorname{Des}:\mathcal{T}\longrightarrow 2^{[n-1]}$. A cyclic extension
of $\operatorname{Des}$ is a pair $(\operatorname{\mathrm{cDes}},p)$, where
$\operatorname{\mathrm{cDes}}:\mathcal{T}\longrightarrow 2^{[n]}$ is a map and
$p:\mathcal{T}\longrightarrow\mathcal{T}$ is a bijection, satisfying the
following axioms: for all $T$ in $\mathcal{T}$,

$\begin{array}[]{rl}\text{(extension)}&\operatorname{\mathrm{cDes}}(T)\cap[n-1]=\operatorname{Des}(T),\\\
\text{(equivariance)}&\operatorname{\mathrm{cDes}}(p(T))={\rm
sh}(\operatorname{\mathrm{cDes}}(T)),\\\ \text{(non-
Escher)}&\varnothing\subsetneq\operatorname{\mathrm{cDes}}(T)\subsetneq[n].\end{array}$

The term non-Escher refers to M. C. Escher’s drawing “Ascending and
Descending” [48], which illustrates the impossibility of the cases
$\operatorname{\mathrm{cDes}}(\cdot)=\varnothing$ and
$\operatorname{\mathrm{cDes}}(\cdot)=[n]$ for permutations in
$\mathfrak{S}_{n}$.

As stated earlier, Cellini’s $\operatorname{\mathrm{CDES}}$(with $p=\rho$) is
a cyclic extension of $\operatorname{Des}$ on $\mathcal{T}=\mathfrak{S}_{n}$.

Before we proceed, let us stress several properties of cyclic descent
extensions.

######  Example 4.1.4.

Consider the following subset of $\mathfrak{S}_{4}$.

$T=\left\\{\left[1,2,3,4\right],\left[2,1,3,4\right],\left[2,3,1,4\right],\left[2,3,4,1\right],\left[3,4,1,2\right],[3,1,4,2]\right\\}$

Define $p$ by

$p:\left[\begin{array}[]{cc}[1,2,3,4]&\mapsto[2,1,3,4]\mapsto[2,3,1,4]\mapsto[2,3,4,1]\mapsto\left[1,2,3,4\right]\\\
&[3,4,1,2]\mapsto[3,1,4,2]\mapsto\left[3,4,1,2\right]\end{array}\right]$

with $cDes$ defined by

$\begin{split}\operatorname{\mathrm{cDes}}\left[1,2,3,4\right]&=\left\\{4\right\\}\\\
\operatorname{\mathrm{cDes}}\left[2,1,3,4\right]&=\left\\{1\right\\}\\\
\operatorname{\mathrm{cDes}}\left[2,3,1,4\right]&=\left\\{2\right\\}\\\
\operatorname{\mathrm{cDes}}\left[2,3,4,1\right]&=\left\\{3\right\\}\\\
\operatorname{\mathrm{cDes}}\left[3,4,1,2\right]&=\left\\{2,4\right\\}\\\
\operatorname{\mathrm{cDes}}\left[3,1,4,2\right]&=\left\\{1,3\right\\}.\end{split}$

We see that $(cDes,p)$ is a cyclic descent extension. We can also define

$\overline{p}:\left[\begin{array}[]{cc}[1,2,3,4]&\mapsto[2,1,3,4]\mapsto[3,4,1,2]\mapsto[2,3,4,1]\mapsto\left[1,2,3,4\right]\\\
&[2,3,1,4]\mapsto[3,1,4,2]\mapsto\left[3,4,1,2\right]\end{array}\right]$

with $\overline{\operatorname{\mathrm{cDes}}}$ defined by

$\begin{split}\overline{\operatorname{\mathrm{cDes}}}\left[1,2,3,4\right]&=\left\\{4\right\\}\\\
\overline{\operatorname{\mathrm{cDes}}}\left[2,1,3,4\right]&=\left\\{1\right\\}\\\
\overline{\operatorname{\mathrm{cDes}}}\left[3,4,1,2\right]&=\left\\{2\right\\}\\\
\overline{\operatorname{\mathrm{cDes}}}\left[2,3,4,1\right]&=\left\\{3\right\\}\\\
\overline{\operatorname{\mathrm{cDes}}}\left[2,3,1,4\right]&=\left\\{2,4\right\\}\\\
\overline{\operatorname{\mathrm{cDes}}}\left[3,1,4,2\right]&=\left\\{1,3\right\\}.\end{split}$

Then $(\overline{cDes},\overline{p})$ is also a cyclic descent extension.

However, while cyclic descent extension is not unique, the following holds.

######  Theorem 4.1.5.

[6] For a finite set $\mathcal{T}$ equipped with descent map
$\operatorname{Des}:\mathcal{T}\longrightarrow 2^{[}n-1]$, If
$(\operatorname{\mathrm{cDes}},p)$ and
$(\overline{\operatorname{\mathrm{cDes}}},\overline{p})$ are two cyclic
descent extensions of $\operatorname{Des}$ then $\operatorname{\mathrm{cDes}}$
and $\overline{\operatorname{\mathrm{cDes}}}$ are equidistributed.

We restrict our attention to cyclic descent extensions on Schur-positive sets.
Recall that a set is Schur-positive if, and only if, it can be represented as
a disjoint union of sets, such $\operatorname{Des}$ on every set in the
disjoint union is equidistributed with $\operatorname{Des}$ on $SYT(\lambda)$
for some shape $\lambda$. Therefore, the study of cyclic descent extensions on
Schur-positive sets reduces to the study of cyclic descent extensions on
Standard Young Tableaux, which can be reduced to the study of the
corresponding quasi-symmetric function $\mathcal{Q}(A)$.

A necessary and sufficient criterion for a skew shape $\lambda/\mu$ that
determines whether ${\rm SYT}(\lambda/\mu)$ has a cyclic descent extension was
found in [6].

Recall that a ribbon is a skew shape that doesn’t contain a $2\times 2$
square.

######  Example 4.1.6.

$\young(::\hfil\hfil,::\hfil,\hfil\hfil\hfil,\hfil).$

######  Theorem 4.1.7 ([6, Theorem 1.1]).

Let $\lambda/\mu$ be a skew shape with $n$ cells. The descent map
$\operatorname{Des}$ on ${\rm SYT}(\lambda/\mu)$ has a cyclic extension
$(\operatorname{\mathrm{cDes}},p)$ if and only if $\lambda/\mu$ is not a
connected ribbon.

The proof was not constructive. A constructive proof was later given by Huang
[25].

While this solves the problem of the existence of a cyclic descent extension
for sets that have descents equidistributed with the $SYT$ of some shape, it
does not solve the problem in general. The disjoint union $C=A\uplus B$ of
Schur-positive sets $A$ and $B$ can have a cyclic descent extension, while
neither $A$ nor $B$ have it.

######  Example 4.1.8.

Let $\lambda=(n-k,1^{k})$ and $\mu=(n-k-1,1^{k+1})$. Then
$\operatorname{Des}({\rm SYT}(\lambda))$ is just the set of all subsets of
$[n-1]$ of size $k$ and $\operatorname{Des}({\rm SYT}(\mu))$ is the set of all
subsets of $[n-1]$ of size $k+1$. It is clear that both ${\rm SYT}(\lambda)$
and ${\rm SYT}(\mu)$ do not have cyclic descent extension since all their
descents have the same size, and shift and restriction to $[n-1]$ must change
the size. However their disjoint union ${\rm SYT}(\lambda)\uplus{\rm
SYT}(\mu)$ has a cyclic descent extension, since one can define
$cDes(T):=Des(T)\cup\\{n\\}$ for $T\in SYT(\lambda)$ and $cDes(T):=Des(T)$ for
$T\in SYT(\mu)$, with a properly defined bijection $p$.

On the other hand, the following holds.

######  Lemma 4.1.9.

The class of sets with a cyclic descent extension is closed under disjoint
union.

###### Proof.

if $A$ and $B$ are disjoint sets with $\operatorname{Des}_{A}:A\to 2^{[n-1]}$
and $\operatorname{Des}_{B}:B\to 2^{[n-1]}$ such that both $A$ and $B$ have a
cyclic descent extension $(\operatorname{\mathrm{cDes}}_{A},p_{A})$ and
$(\operatorname{\mathrm{cDes}}_{B},p_{B})$ then $A\uplus B$ has a cyclic
descent extension $(\operatorname{\mathrm{cDes}},p)$ defined by

$(\operatorname{\mathrm{cDes}}(T),p(T))=\begin{cases}\left(cDes_{A}\left(T\right),p_{A}(T)\right)&T\in
A\\\ \left(cDes_{B}\left(T\right),p_{B}(T)\right)&T\in B\end{cases}.$

∎

By Example 4.1.8, if we have
$\mathcal{Q}(A)=s_{(n-k,1^{k})}+s_{(n-k-1,1^{k+1})}$, or equivalently, the
descents of A and ${{\rm SYT}(n-k,1^{k})\uplus{\rm SYT}(n-k-1,1^{k+1})}$ are
equidistributed, then $A$ has a cyclic descent extension.

A necessary and sufficient condition on $Q(A)$, under which the Schur-positive
set $A$ has a cyclic descent extension and was proved in [3]. We proceed to
describe this condition.

######  Definition 4.1.10.

The shape $(n-k,1\dots,1)$ is called a hook. The numbers $k$ and $n-k-1$ are
leg length and arm length of the hook, respectively.

######  Example 4.1.11.

The hook $h=(5,1,1,1)$

$\young(\hfill\hfill\hfill\hfill\hfill,\hfill,\hfill,\hfill)$

has leg length $3$ and arm length $4$.

We rely on the following lemma from [3].

######  Lemma 4.1.12.

Let $A$ be a Schur-positive set with
$\mathcal{Q}(A)={\operatorname{ch}}(\phi)$. Denote

$m_{\lambda}\coloneqq\left\langle\phi,\chi^{\lambda}\right\rangle=\left\langle\mathcal{Q}\left(A\right),s_{\lambda}\right\rangle.$

Let $h_{k}$ = $m_{\left(n-k,1^{k}\right)}$. Then

$h_{k}=\left|\left\\{a\in
A:\operatorname{Des}\left(a\right)=\left[k\right]\right\\}\right|$

######  Definition 4.1.13.

Let $A$ be a Schur-positive set. Define

$h_{k}(A)=\left<\mathcal{Q}(A),s_{(n-k,1^{k})}\right>$

and the hook polynomial of $A$ by

$H_{A}(x)=\sum\limits_{k=0}^{n-1}h_{k}(A)x^{k}.$

The following sufficient and necessary condition for cyclic descent extension
on a Schur-positive set to exist was proved in [3].

######  Lemma 4.1.14.

Let $A$ be a Schur-positive set. Then a cyclic descent extension of $Des$ on
$A$ exists if and only if $1+x$ divides the hook polynomial $H_{A}(x)$ and the
coefficients of $\frac{H_{A}(X)}{1+x}$ are non-negative.

Before we move on, we state a simple property of hook polynomials that follows
from a similar property of quasi-symmetric functions.

######  Lemma 4.1.15.

Let $A$ and $B$ be disjoint Schur-positive sets. Then

$H_{A\uplus B}(x)=H_{A}(X)+H_{B}(X).$

The rest of this work deals with proof of the existence of cyclic descent
extension for particular Schur-positive sets in $\mathfrak{S}_{n}$.

Adin, Hegedüs and Roichman in [3] solved the problem for permutations with a
given cycle type. This chapter considers permutations with a given inversion
number and permutations with a given inverse descent set. The next chapter
deals with proof of the existence of cyclic descent extensions for roots of
unity in $\mathfrak{S}_{n}$.

###  4.2 Inverse descent classes and their cyclic descent extensions

We restate Definition 2.5.17

######  Definition 4.2.1.

Let $J\subseteq[n-1]$. Define the inverse descent class of $J$ in
$\mathfrak{S}_{n}$ by

$D_{J,n}^{-1}=\left\\{\pi\in\mathfrak{S}_{n}|Des(\pi^{-1})=J\right\\}.$

We are also interested in a generalization of inverse descent classes.

######  Definition 4.2.2.

Let $\mathcal{J}\subseteq 2^{[n]}$. Define generalized inverse descent class

$D_{\mathcal{J},n}^{-1}=\left\\{\pi\in\mathfrak{S}_{n}|\operatorname{Des}(\pi^{-1})\in\mathcal{J}\right\\}.$

or equivalently

$D_{\mathcal{J},n}^{-1}=\biguplus_{J\in\mathcal{J}}D_{J,n}^{-1}.$

It is easy to see that generalized inverse decent classes are Schur-positive
since they are disjoint unions of Schur-positive sets. We are interested in
determining the conditions for generalized inverse descent classes to have
cyclic descent extensions.

To answer this question, we first calculate $H_{D^{-1}_{J,n}}(x)$ for
$J\subseteq[n]$. By discussion after Definition 2.5.17, the inverse descent
class $D_{J,n}^{-1}$ is the disjoint union of the Knuth classes for standard
Young tableaux $T$ that have $\operatorname{Des}{T}=J$. Namely, we have

$D_{J,n}^{-1}=\biguplus_{\operatorname{Des}{T}=J}K_{T}.$

Now, observe that $Des$ is a bijection between the hooks with leg length $k$
and the subsets of $[n-1]$ of size $k$. Hence, there is exactly one hook $T$
with $\operatorname{Des}(T)=J$, and it has of shape $(n-|J|,1^{|J|})$.
Therefore we have $h_{|J|}=1$ and $h_{k}=0$ for $k\neq|J|$. This result is
summarized in the following lemma.

######  Lemma 4.2.3.

Let $J\subseteq[n]$.

$h_{k}(D^{-1}_{J,n})=\delta_{k,|J|}.$

where $\delta$ is the Kronecker delta. Equivalently,
$H_{D_{J,n}^{-1}}(x)=x^{|J|}$.

Since $1+x$ does not divide $x^{k}$, we immediately obtain the following
result by lemma 4.1.14.

######  Theorem 4.2.4.

For every $J\subseteq[n-1]$, no cyclic descent extension exists for
$D_{J,n}^{-1}$.

For the generalized inverse descent class, we obtain the following result:

######  Lemma 4.2.5.

Let $\mathcal{J}\in 2^{n-1}$. Let
$j_{k}=\big{|}\left\\{J\in\mathcal{J}\mid|J|=k\right\\}\big{|}$. Then a cyclic
descent extension for $D^{-1}_{\mathcal{J},n}$ exists if and only if

$\frac{\sum\limits_{k=0}^{n-1}j_{k}x^{k}}{1+x}$

is a polynomial with non-negative integer coefficients.

###### Proof.

Recall that $D_{\mathcal{J},n}^{-1}=\biguplus_{J\in\mathcal{J}}D_{J,n}^{-1}$.
By lemma 4.1.15 we have

$\begin{split}H_{D_{\mathcal{J},n}^{-1}}(x)=H_{\bigcup\limits_{J\in\mathcal{J}}D_{J,n}^{-1}}(x)=\sum\limits_{J\in\mathcal{J}}H_{J}(x)=\sum\limits_{J\in\mathcal{J}}x^{|J|}\\\
=\sum_{k=0}^{n-1}\sum\limits_{\begin{subarray}{c}J\in\mathcal{J}\\\
|J|=k\end{subarray}}x^{k}=\sum\limits_{k=0}^{n-1}j_{k}x^{k}\end{split}.$

and by lemma 4.1.14 has a cyclic descent extension only if
$\sum_{k=0}^{n-1}j_{k}x^{k}$ is divisible by $1+x$ and the quotient polynomial
has non-negative integer coefficients, as desired. ∎

Applying the theorem, we obtain the following result.

######  Theorem 4.2.6.

The following sets in $\mathfrak{S}_{n}$ have a cyclic descent extension under
the following conditions

  1. 1.

$D_{2^{J},n}^{-1}$ if and only if $J\neq\emptyset$.

  2. 2.

$D_{[I,J],n}^{-1}$ for an interval

$[I,J]=\left\\{K:I\subseteq K\ and\ K\subseteq J\right\\}$

(in the poset $2^{[n-1]}$ ordered by inclusion), if and only if $I\subsetneq
J$.

  3. 3.

For a maximal chain $C$ in the poset $[I,J]$, $D_{C,n}^{-1}$ has a cyclic
descent extension if and only $2\not|(|J|-|I|)$. In particular, $D_{C,n}^{-1}$
for a maximal chain $C$ in $2^{[n-1]}$ has a cyclic descent extension if and
only if $n-1$ is odd, or equivalently $n$ is even.

###### Proof.

  1. 1.

The number of subsets of $J$ of size $k$ is $j_{k}=\binom{|J|}{k}$. Hence, we
have

$\sum_{k=0}^{|J|}j_{k}x^{k}=\sum_{k=0}^{|J|}\binom{|J|}{k}x^{k}=(1+x)^{|J|}$

which is divisible by $1+x$ unless $|J|=0$. The quotient

$\frac{(1+x)^{|J|}}{1+x}=(1+x)^{|J-1|}$

is clearly a polynomial with non-negative integer coefficients. Hence
$D_{2^{J},n}^{-1}$ has a cyclic descent extension unless $J=\emptyset$, as
desired.

  2. 2.

The number of subsets $D^{-1}_{[I,J],n}$ of size $k$ is
$\binom{|J|-|I|}{k-|I|}.$ Thus

$\sum_{k}j_{k}x^{k}=x^{|I|}(1+x)^{|J|-|I|}$

.

  3. 3.

For a maximal chain $C$ in $[I,J]$, we have

$\sum_{k}j_{k}x^{k}=\sum_{k=|I|}^{k=|J|}x^{k}$

which is divisible by $1+x$ with quotient having non-negative integer
coefficients when $|J|-|I|$ is odd, and is not divisible by $1+x$ otherwise.

∎

###  4.3 Permutations with given inversion number

It is known that the set of permutations in $\mathfrak{S}_{n}$ with a given
inversion number is Schur-positive. See for example [8], Section 9.5. Hence,
it is natural to ask the following question.

######  Question 4.3.1.

Is there a cyclic descent extension for the set of permutations in
$\mathfrak{S}_{n}$ with a given inversion number $k$?

In this section, we give an answer to this question for case $k<n$, proving
the following theorem.

######  Theorem (4.3.11).

For $k<n$, the set of permutations in $\mathfrak{S}_{n}$ with $k$ inversions
has a cyclic descent extension if and only if $k$ is not a generalized
pentagonal number.

Recall the definition of generalized pentagonal numbers.

######  Definition 4.3.2.

A number $n\in{\mathbb{N}}$ is a _generalized pentagonal numbers_ if there is
$m\in{\mathbb{N}}$ such that $n=\frac{(3m\pm 1)m}{2}$.

The rest of this section is devoted to proving this theorem. First, we
introduce some notation and definitions. Let
$\operatorname{\mathrm{inv}}(\pi)$ denote the number of inversions
$\pi\in\mathfrak{S}_{n}$.Recall that by Definition 2.4.9 the major index of a
permutation $\pi$ denoted $\operatorname{\mathrm{maj}}(\pi)$ is the sum of
descents, namely ${\operatorname{\mathrm{maj}}(\pi)=\sum\limits_{i\in
Des(\pi)}i}$ and the inverse major index of $\pi$, denoted
$\operatorname{\mathrm{imaj}}(\pi)$ is the major index of $\pi^{-1}$,
specifically, ${\operatorname{\mathrm{imaj}}(\pi)=\sum\limits_{i\in
Des(\pi^{-1})}i}$. We define the following sets.

######  Definition 4.3.3.

Let $k\in{\mathbb{N}}\cup\\{0\\}.$ Denote $\operatorname{\mathrm{inv}}_{k}$
the set of permutations in $\mathfrak{S}_{n}$ with inversion number $k$, that
is

$\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})=\\{\pi\in\mathfrak{S}_{n}:inv(\pi)-k\\}.$

The set of permutations in $\mathfrak{S}_{n}$ with inverse major index $k$ is
denoted $\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})$, namely

$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})=\\{\pi\in\mathfrak{S}_{n}:\operatorname{\mathrm{imaj}}(\pi)=k\\}.$

Before going into detail, let us describe the structure of the proof. First,
using a classical result by Foata and Schützenberger from [19], we show that
the descents of $\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})$ and
$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})$ are equidistributed,
which implies that that $\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})$
admits a cyclic descent extension if and only if
$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})$ does.

However, $\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})$ can be expressed
as a disjoint union of inverse descent classes, which allows us easily to
calculate $H_{\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n}}(x)$, the hook
polynomial of $\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})$.

Then we check when the conditions of Lemma 4.1.14 hold for
$H_{\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})}(x)$. We show then,
that divisibility by $(1+x)$ for $n>k$, is equivalent to coefficients of
$x^{k}$ being $0$ in the expansion

$\prod_{0<n}(1-x^{n})=\sum_{0\leq k}a_{k}x^{k},$

which, by the famous Euler’s pentagonal number theorem, implies that $k$ is
not a generalized pentagonal number.

Using the same tools used in the proof of Euler’s pentagonal number theorem,
we show the second condition of Lemma 4.1.14 for
$H_{inv_{k}(\mathfrak{S}_{n})}$ $(1+x)$ divides
$H_{\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})}$ still holds. That is,
the coefficients
$\frac{H_{\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})(x)}}{1+x}$ non-
negative which finishes our proof of Theorem 4.3.11.

We proceed to carry out the details of the proof.

We begin citing the classical result of Foata and Schützenberger from [19].

######  Theorem 4.3.4 ([19], Theorem 1).

There exists a bijection $\phi:\mathfrak{S}_{n}\to\mathfrak{S}_{n}$ such that

$\operatorname{Des}(\phi(\pi)^{-1})=\operatorname{Des}(\pi^{-1})$

and

$\operatorname{\mathrm{inv}}(\phi(\pi))=\operatorname{\mathrm{maj}}(\pi).$

Recall that by Theorem 2.4.11, the inversion number of
$\pi\in\mathfrak{S}_{n}$ is equal to its length in Coxeter generators
$s_{1},\dots,s_{n-1}$ and therefore
$\operatorname{\mathrm{inv}}(\pi)=\operatorname{\mathrm{inv}}(\pi^{-1})$.
Using this fact, we show that a bijection exists with similar relations for
$\operatorname{\mathrm{imaj}}$ and $\operatorname{\mathrm{inv}}$.

######  Corollary 4.3.5.

There exists a bijection $\psi:\mathfrak{S}_{n}\to\mathfrak{S}_{n}$ such that

$\operatorname{Des}(\psi(\tau))=\operatorname{Des}(\tau)$

and

$\operatorname{\mathrm{inv}}(\psi(\tau))=\operatorname{\mathrm{imaj}}(\tau).$

###### Proof.

Let us define $\psi:\mathfrak{S}_{n}\to\mathfrak{S}_{n}$ by

$\psi(\tau)=\phi(\tau^{-1})^{-1}.$

By the preceding theorem, we have

$\operatorname{Des}\left(\psi(\tau)\right)=\operatorname{Des}\left(\phi(\tau^{-1})^{-1}\right)=\operatorname{Des}(\left(\tau^{-1}\right)^{-1})=\operatorname{Des}(\tau)$

and

$\operatorname{\mathrm{inv}}(\psi(\tau))=\operatorname{\mathrm{inv}}\left(\phi(\tau^{-1})^{-1}\right)=\operatorname{\mathrm{inv}}\left(\phi(\tau^{-1})\right)=\operatorname{\mathrm{maj}}\left(\tau^{-1}\right)=\operatorname{\mathrm{imaj}}(\tau),$

which proves our claim. ∎

For our purposes, it is more useful to restate it in the following form.

######  Corollary 4.3.6.

The sets $\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})$ and
$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})$ have equidistributed
descents.

From the preceding corollary, by Definition 2.5.7,
$\mathcal{Q}\left(\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})\right)=\mathcal{Q}\left(\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})\right)$.
Therefore, the existence of cyclic descent extension for
$\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})$ is equivalent to the
existence of cyclic descent extension for
$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})$.

It is easy to see that

$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})=\left\\{\pi\in\mathfrak{S}_{n}\big{|}\operatorname{\mathrm{maj}}(\pi^{-1})=k\right\\}$

is a disjoint union of inverse descent classes, namely

$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})=\left\\{\pi\in\mathfrak{S}_{n}\big{|}\operatorname{\mathrm{maj}}(\pi^{-1})=k\right\\}=\biguplus_{\begin{subarray}{c}J\subseteq[n-1]\\\
\sum_{j\in J}j=k\end{subarray}}D_{J,n}^{-1},$

which allows us to apply Lemmas 4.1.15 and 4.2.3 to obtain

$\begin{split}H_{\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})}(x)=H_{\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})}(x)=\sum\limits_{\begin{subarray}{c}J\subseteq[n-1]\\\
\sum_{j\in
J}j=k\end{subarray}}H_{D_{J,n}^{-1}}(x)=\sum\limits_{\begin{subarray}{c}J\subseteq[n-1]\\\
\sum_{j\in J}j=k\end{subarray}}x^{|J|}.\end{split}$

Note that the sets satisfying $J\subseteq[n-1]$ and $\sum\limits_{j\in J}=k$
are the partitions of $k$ into $|J|$ distinct parts of size equal or smaller
than $n-1$.

Denote the number of partitions of $k$ into $m$ distinct parts $pd(k,m)$. Let
$Pd_{k}(x)$ be the generating function for the number of partitions of $k$
into distinct parts, namely, the polynomial

$Pd_{k}(x)=\sum pd(k,m)x^{m}.$

It is easy to see the following.

######  Observation 4.3.7.

For $n>k$,
$h_{m}\bigl{(}\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})\bigr{)}=pd(k,m)$
and

$H_{\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})}(x)=\sum\limits_{{\begin{subarray}{c}J\subseteq[n-1]\\\
\sum_{j\in J}j=k\end{subarray}}}x^{|J|}=\sum pd(k,m)x^{m}=Pd_{k}(x).$

Using the preceding observation, we obtain a necessary condition for the
existence of a cyclic descent extension on
$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})$ and
$\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})$ when $k<n$.

######  Lemma 4.3.8.

Let $k,n\in{\mathbb{N}}$ such that $k<n$. If a cyclic descent extension on
$\operatorname{\mathrm{inv}}_{k}(\mathfrak{S}_{n})$ exists, then $a_{k}=0$ in
the expansion

$\prod_{1\leq n}(1-x^{n})=\sum_{0\leq k}a_{k}x^{k}.$

###### Proof.

Let us examine the series $\sum\limits_{k}Pd_{k}(t)x^{k}$. We have

$\begin{split}\sum_{0\leq k}Pd_{k}(t)x^{k}&=\sum_{0\leq
k}x^{k}\sum_{m=0}^{k}pd(k,m)t^{m}=\sum_{0\leq m}\sum_{m\leq
k}pd(k,m)t^{m}x^{k}\\\ &=\sum_{m\leq 0}t^{m}\sum_{m\leq
k}\left(\sum\limits_{\begin{subarray}{c}1\leq i_{1}<\dots<i_{m}\\\
i_{1}+\dots+i_{m}=k\end{subarray}}\prod_{j=1}^{m}x^{i_{j}}\right)\\\
&=\sum_{0\leq m}\left(\sum_{1\leq
i_{1}<\dots<i_{m}}\prod_{j=1}^{m}tx^{i_{j}}\right)=\prod_{1\leq
n}(1+tx^{n}).\end{split}$

Substituting $t=-1$ in $\prod\limits_{1\leq n}(1+tx^{n})$, we obtain the
equality

$\prod_{1\leq n}(1-x^{n})=\sum_{0\leq k}Pd_{k}(-1)x^{k}=\sum_{0\leq
k}a_{k}x^{k}.$

Since $k<n$, by Observation 4.3.7, we have
$H\bigl{(}\operatorname{\mathrm{imaj}}_{k}\mathfrak{S}_{n}\bigr{)}(x)=Pd_{k}(x)$.
By Lemma 4.1.14, if a cyclic descent extension for
$\operatorname{\mathrm{imaj}}_{k}(\mathfrak{S}_{n})$ then $(1+x)|Pd_{k}(x)$.
But $Pd_{k}(t)$ if is divisible by $(1+t)$, then $a_{k}=Pd_{k}(-1)=0$ proving
our claim. ∎

The following result, known as the pentagonal number theorem, is due to Euler.

######  Theorem 4.3.9 (Pentagonal number theorem).

We have

$\prod\limits_{1\leq n}(1-x^{n})=1+\sum\limits_{1\leq
m}(-1)^{m}\left(x^{\frac{(3m-1)m}{2}}+x^{\frac{(3m+1)m}{2}}\right)$

Some notation and arguments from the proof of this theorem, as in [43,
Proposition 1.8.7], are used later. Therefore, we provide a slightly modified
version here to ease comprehension.

###### Proof.

Let $Q(k)$ be the set of partitions of $k$ into distinct parts. Let $q_{e}(k)$
be the number of partitions of $k$ into an even number of distinct parts, and
let $q_{o}(k)$ be the number of partitions of $k$ into an odd number of
distinct parts. From the proof of Lemma 4.3.8, we have $a_{k}=Pd_{k}(-1)$ in
the expansion

$\prod_{1\leq n}(1-x^{n})=\sum_{0\leq k}a_{k}x^{k}.$

On the other hand,

$Pd_{k}(-1)=\sum_{m=1}^{k}pd(k,m)(-1)^{m}==q_{e}(k)-q_{o}(k)=\sum_{\lambda\in
Q(k)}(-1)^{l(\lambda)}.$

Thus, to prove the theorem, it is enough to show that

$a_{k}=q_{e}(k)-q_{o}(k)=\left\\{\begin{array}[]{rl}(-1)^{m}&\text{if}\
k=\frac{(3m\pm 1)m}{2}\text{\ }{forsome}\ m\in{\mathbb{N}}\\\
0&\text{otherwise}.\end{array}\right.$

It is easy to see that $a_{0}=1$. Therefore the following arguments assume
that $k>1$. To prove the statement $k\neq\frac{(3m\pm 1)m}{2}$, we show that
$a_{k}=0$ by defining an involution $\phi:Q(k)\to Q(k)$ such that
$l(\lambda)\not\equiv l(\phi(\lambda))(\bmod 2)$ for all $\lambda\in Q(k)$.
When $k=\frac{(3m\pm 1)m}{2}$, we will define a partition $\mu\in Q(k)$ with
$l(\mu)=m$ and an involution $\phi:Q(k)\setminus\\{\mu\\}\to
Q(k)\setminus\\{\mu\\}$ such that $l(\lambda)\not\equiv l(\phi(\lambda))(\bmod
2)$ for all $\lambda\in Q(k)\setminus\\{\mu\\}$.

For a partition $\lambda\in Q(k)$, let $L_{\lambda}$ denote the length of the
last row of the Ferrers diagram of $\lambda$ and let $D_{\lambda}$ the number
of rows $i$ in $\lambda$ for which $\lambda_{i}=\lambda_{1}-i+1$ and
$\lambda_{i}>0$. For example for $\lambda=(7,6,5,3,2)$ we have $D_{\lambda}=3$
and $L_{\lambda}=2$. We define $\phi$ on $Q(k)$ as follows.

If $D_{\lambda}<L_{\lambda}$ define
$\phi(\lambda)=(\phi(\lambda)_{1},\dots,\phi(\lambda)_{l(\lambda)+1})$ by

$\phi(\lambda)_{i}=\left\\{\begin{array}[]{rl}\lambda_{i}-1&\text{if}\ 1\leq
i\leq D_{\lambda}\\\ \lambda_{i}&\text{if}\ D_{\lambda}+1\leq i\leq
l(\lambda)\\\ D_{\lambda}&\text{if}\ i=l(\lambda)+1.\end{array}\right.$

If $D_{\lambda}\geq L_{\lambda}$. Define
$\phi(\lambda)=(\phi(\lambda)_{1},\dots,\phi(\lambda)_{l(\lambda)-1})$ by

$\phi(\lambda)_{i}=\left\\{\begin{array}[]{rl}\lambda_{i}+1&\text{if}\ 1\leq
i\leq L_{\lambda}\\\ \lambda_{i}&\text{if}\ L_{\lambda}+1\leq i\leq
l(\lambda)-1.\end{array}\right.$

When $D_{\lambda}<L_{\lambda}$ then $\phi(\lambda)\in Q(k)$ unless
$l(\lambda)=D_{\lambda}=L_{\lambda}-1$. In this case, we have
$\lambda=(\lambda_{1},\lambda_{1}-1,\dots,\lambda_{1}-l(\lambda)+1=l(\lambda)+1)$
and $\phi(\lambda)=(\lambda_{1}-1,\dots,l(\lambda),l(\lambda))$, and since two
smallest parts of $\phi(\lambda)$ are equal, $\phi(\lambda)\notin Q(k)$. Then
$k=\frac{(3m+1)m}{2}$ for $m=D_{\lambda}$.

When $D_{\lambda}\geq L_{\lambda}$ then $\phi(\lambda)\in Q(k)$, unless
${L_{\lambda}=D_{\lambda}=l_{\lambda}}$. In this case, we have
${\lambda=(\lambda_{1},\lambda_{1}-1,\dots,\lambda_{1}-l(\lambda)+1=l(\lambda))}$
and
$\phi(\lambda)=(\lambda_{1}+1,\lambda_{1},\dots,\lambda_{1}-l(\lambda)+2)$.
But then $\phi(\lambda)\notin Q(k)$, since the sum of the parts of
$\phi(\lambda)$ is equal to $k-1$. In this case $k=\frac{(3m-1)m}{2}$ for
$m=l(\lambda)$.

By the definition of $\phi$, we have ${l(\phi(\lambda))=l(\lambda)\pm 1}$. In
addition, when both ${\lambda\in Q(k)}$ and ${\phi(\lambda)\in Q(k)}$, then
$\phi(\phi(\lambda))=\lambda$. To see that, consider the following geometric
interpretation. First, identify $\lambda$ with its Ferrers diagram. Then, if
$D_{\lambda}<L_{\lambda}$, remove the rightmost cell in each of the first
$D_{\lambda}$ rows of $\lambda$ and add a new row of length $D_{\lambda}$
below to obtain $\phi(\lambda)$. Otherwise, if $L_{\lambda}\leq D_{\lambda}$,
remove the last row of $\lambda$, and add a new cell to the right in each one
of the first $L_{\lambda}$ rows of $\lambda$. It is easy to see that when both
$\lambda$ and $\phi(lambda)$ are both in $Q(k)$, applying $\phi$ twice puts
the moved cells of the shape $\lambda$ back in their original position without
moving other cells and therefore $\phi(\phi(\lambda))=\lambda$. As we have
shown, $\lambda\in Q(k)$ such that $\phi(\lambda)\notin Q(k)$ exists if and
only if $k=\frac{(3m\pm 1)m}{2}$ some $m\in{\mathbb{N}}$, therefore if
$k\neq\frac{(3m\pm 1)m}{2}$ for every $m\in{\mathbb{N}}$, $\phi$ is an
involution on $Q(k)$ with the property $l(\phi(\lambda))=l(\lambda)\pm 1$.

There is no $k\in{\mathbb{N}}$ such that
$k=\frac{(3m_{1}+1)m_{1}}{2}=\frac{(3m_{2}-1)m_{2}}{2}$ such that $m_{1}\neq
m_{2}$ and $m_{1},m_{2}in{\mathbb{N}}$. Therefore, there is at most one
$\mu\in Q(k)$ for which one $\phi(\mu)\notin Q(k)$. Therefore, $\phi$ is an
involution on $Q(k)$ when $k\neq\frac{(3m\pm 1)m}{2}$ and is an involution on
$Q(k)\setminus\\{\mu\\}$ where ${\mu=(2m,\dots,m+1)}$ if
$k=\frac{(3m+1)m}{2}$, and ${\mu=(2m-1,\dots,m)}$ if $k=\frac{(3m-1)m}{2}$. It
follows that $\phi$ is an involution on $Q(k)\setminus{\mu}$ with the property
the property $l(\phi(\lambda))=l(\lambda)\pm 1$ for $k=\frac{(3m\pm 1)m}{2}$.
Observe that $l(\mu)=m$.

Therefore, for $k\in{\mathbb{N}}$ we have

$a_{k}=q_{e}(k)-q_{o}(k)=\sum_{\lambda\in
Q(k)}(-1)^{l(\lambda)}=\left\\{\begin{array}[]{rl}(-1)^{m}&\text{if}\
k=\frac{(3m\pm 1)m}{2}\ \text{for some}\ m\in{\mathbb{N}}\\\
0&\text{otherwise}\end{array}\right.$

and the proof is finished. ∎

Now we proceed to show that if $Pd_{k}(-1)=0$, then the coefficients of
$\frac{Pd_{k}(t)}{(1+x)}$ are nonnegative integers. We make the following
observation by closely examining the proof of the pentagonal number theorem.

######  Observation 4.3.10.

For $k\neq\frac{(3m\pm 1)m}{2}$, there exists an involution

$\phi:Q(k)\to Q(k)$

such that $l(\phi(\lambda))=l(\lambda)\pm 1$.

Using the involution $\phi$, we finish the proof of Theorem 4.3.11.

######  Theorem 4.3.11.

For $k<n$, the set of permutations in $\mathfrak{S}_{n}$ with $k$ inversions
has a cyclic descent extension if and only if $k$ is not a generalized
pentagonal number.

###### Proof.

First, observe that if $k$ is a generalized pentagonal number, then
$Pd_{k}(-1)\neq 0$ by Euler’s Pentagonal Number Theorem, which implies that
$(1+t)$ does not divide $Pd_{k}(t)$.

For the opposite direction, we show that if $k$ is not a generalized
pentagonal number, then $\frac{Pd_{k}(t)}{1+t}$ is a polynomial with integer
non-negative coefficients. Let $d$ be the degree of $Pd_{k}(t)$, which is
equal to $\max\\{l(\lambda)|\lambda\in Q(k)\\}$. Denote $pd(k,m)=a_{m}$ and

$b_{m}=\big{|}\\{\lambda\in Q(k)|l(\phi(\lambda))=l(\lambda)+1\\}\big{|}.$

Observe that $a_{1}=b_{1}$, as there is exactly one partition $\lambda=(k)$ of
$k$ with $1$ distinct part and we obviously have $l(\phi((k)))=l(k-1,1)=2$.

Also, we must have $b_{d}=0$ as $l(\phi(\lambda))=l(\lambda)+1=d+1$
contradicts the fact that $d$ is the maximal possible length of an element
$\lambda$ of $Q(k)$.

Since we have $l(\phi(\lambda))=l(\lambda)\pm 1$, and
$\phi(\phi(\lambda))=\lambda$, the number of elements $\lambda$ of $Q(k)$ with
$l(\lambda)=i$ for which $l(\phi(\lambda))=l(\lambda)-1=i-1$ is equal to the
number of elements of $Q(k)$ with length $i-1$ for which
$l(\phi(\lambda))=l(\lambda)=(i-1)+1$ which is exactly $b_{i-1}$. Similarily,
the number of elements of $Q(\lambda)$ with length $i$ for which
$l(\phi(\lambda))=l(\lambda)+1=i+1$ is $b_{i}$ by definition. Hence,
$a_{i}=b_{i-1}+b_{i}$.

Combining everything we have $a_{1}=b_{1}=1$, $b_{d}=0$,
$a_{i}=b_{i-1}+b_{i}$. Multiplying $1+t$ and $b_{1}t+\dots b_{d-1}t^{d-1}$ we
have

$\begin{split}(1+t)\sum_{i=1}^{d-1}b_{i}t^{i}&=b_{1}t+\sum_{i=2}^{d-1}(b_{i-1}+b_{i})t^{i}+b_{d-1}t^{d}\\\
&=a_{1}t+\sum_{i=2}^{d-1}a_{i}t^{i}+a_{d}t^{d}=\sum_{i=1}^{d}a_{i}t^{i}=Pd_{k}(t).\end{split}$

It is easy to see that the coefficients $b_{i}$ are not negative. By Corollary
4.3.6 and Observation 4.3.7 we have
$H_{\operatorname{\mathrm{inv}}_{k}}(t)=H_{\operatorname{\mathrm{imaj}}_{k}}(t)=Pd_{k}(t)$.
The result follows. ∎

##  Chapter 5 On cyclic descents of roots of unity

###  5.1 Background and main results

Adin, Hegedüs and Roichman characterized the conjugacy classes in the
symmetric group, which carry a cyclic descent extension [3].

######  Theorem 5.1.1.

[3, Theorem 1.4] Let $\lambda$ be a partition of $n$, and let
$C_{\lambda}\subseteq\mathfrak{S}_{n}$ be the corresponding conjugacy class.
The descent map $\operatorname{Des}$ on $C_{\lambda}$ has a cyclic extension
$(\operatorname{\mathrm{cDes}},p)$ if and only if $\lambda$ is not of the form
$(r^{s})$ for some square-free $r$.

Motivated by this result, we explore the existence of a cyclic descent
extension for roots of unity of order $d$ in $\mathfrak{S}_{n}$.

######  Definition 5.1.2.

A permutation $\pi\in\mathfrak{S}_{n}$ is a root of unity of order $d$, or
$d$-root of unity, if $\pi^{d}=e$ where $e$ is the identity permutation in
$\mathfrak{S}_{n}$. The set of roots of unity order $d$ in $\mathfrak{S}_{n}$
will be denoted by $\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}$.

The following observation describes the roots of unity of order $d$ in
$\mathfrak{S}_{n}$.

######  Observation 5.1.3.

Let $\pi$ be a permutation with cycle decomposition
$\pi=\sigma_{1}\dots\sigma_{k}$ with corresponding cycle lengths
$c_{1},\dots,c_{k}$. Then the order of $\pi$ in $\mathfrak{S}_{n}$ is

$ord(\pi)=lcm(c_{1},\dots,c_{k}).$

Hence, a permutation $\pi$ is a root of unity of order $d$ if and only if
$\pi$ is a product of disjoint cycles with lengths that divide $d$.

Therefore, the set of roots of unity of order $d$ in $\mathfrak{S}_{n}$ is a
disjoint union of conjugacy classes.

######  Remark 5.1.4.

For convenience, for partition $\lambda=(\lambda_{1},\dots,\lambda_{k})$, we
write $lcm(\lambda)=\lambda(\lambda_{1},\dots,\lambda_{k}$). Using this
notation, we have

$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}=\biguplus_{lcm(\lambda)|d}C_{\lambda}.$

Calculations suggest the following conjecture.

######  Conjecture 5.1.5.

A cyclic descent extension for the set of roots of unity of order $d$ in
$\mathfrak{S}_{n}$ exists if, and only if, $(d,n)\neq 1$.

In this chapter, we show that the $(d,n)=1$ condition is necessary and prove
the conjecture for the case when $d=p^{k}$ for some prime number
$p\in{\mathbb{N}}$ and $k\in{\mathbb{N}}$. In particular, we prove the
following:

######  Theorem 5.1.6.

The set of roots of unity of order $d$ in $\mathfrak{S}_{n}$:

  1. 1.

Does not have a cyclic descent extension if $n$ and $d$ are coprime.

  2. 2.

Has a cyclic descent extension when $d$ is a prime power and $d$ and $n$ are
not co-prime.

This chapter is structured as follows. In Section 5.2, we show that the
condition $(d,n)\neq 1$ is necessary and show that the set of cyclic roots of
unity of order $p^{k}$ for a prime number $p$ and $k\in{\mathbb{N}}$ in
$\mathfrak{S}_{n}$ admits a cyclic descent extension if and only if the set of
roots of order $p$ does. In addition, prove the theorem for the case when $d$
is a power of $2$.

In Section 5.3, we show that for a Schur-positive subset $A$ of
$\mathfrak{S}_{n}$, the existence of cyclic descent extension can be
reformulated in terms of multiplicities unimodal permutations in $A$ instead
of hook-lengths in $\mathcal{Q}(A)$. In particular, we introduce the _unimodal
maxima polynomial_ $U_{A}(x)$, which counts the unimodal permutations in $A$
by their maxima. We show that $A$ has a cyclic descent extension if and only
if $U_{A}(x)$ satisfies the same conditions of Lemma 4.1.14 that $H_{A}(x)$
does. This equivalence allows us to attack the problem of the existence of
cyclic descent extension for $\mathfrak{S}_{n}$ using the existing tools and
results for unimodal permutations in $\mathfrak{S}_{n}$.

The last sections are devoted to proving the Conjecture 5.1.5 for the case
when $d$ is a power of a prime number $p$, which has three stages. First, in
Section 5.4, we prove the conjecture for the case when $d=n$ for a prime
number $d$. After that, in Section 5.5, we explore the structure of unimodal
permutations and their cycle structure. In Section 5.6, we explore the
implications of the cycle structure on the distribution of the maxima. Then we
derive the divisibility conditions of Lemma 4.1.14 for
$U_{\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}}(x)$, finishing the proof
of Theorem 5.1.6.

###  5.2 Basic propositions

In this section, we show the necessity of $d$ and $p$ being coprime for the
existence of a cyclic descent extension for
$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}$. We also show that the
existence of a cyclic descent extension for
$\mathcal{R}_{p}{\left(\mathfrak{S}_{n}\right)}$ for a prime $p$ implies the
existence of a cyclic descent extension for
$\mathcal{R}_{p^{k}}{\left(\mathfrak{S}_{n}\right)}$ for every $k\geq 1$. We
conclude this section with proof of the Theorem 5.1.6 for the case of
$d=2^{k}$, which doesn’t require the machinery developed in the later sections
of this chapter.

First, we prove that the condition that $d$ and $n$ are not coprime is
necessary.

######  Lemma 5.2.1.

If $d$ and $n$ are coprime, then
$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}$ has no cyclic descent
extensions.

###### Proof.

By remark 5.1.4 we have

$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}=\biguplus_{lcm(\lambda)|d}C_{\lambda}.$

But $lcm(\lambda)|d$ for $\lambda=(r^{s})$ for square-free $r$ means that
$r|d$, and since necessarily $r|n$ and $(n,d)=1$ we must have $r=1$ and
$\lambda=(1^{n})$, which means $C_{\lambda}=C_{(1^{n})}=\\{e\\}$. Otherwise,
$\lambda\neq(r^{s})$ for every square-free $r$ and $s\in{\mathbb{N}}$.
Therefore, by Theorem 5.1.1, for every $\lambda$, when $lcm(\lambda)|d$,
$C_{\lambda}$ has a cyclic descent extension, unless $C_{\lambda}=\\{e\\}$.
Denote $\biguplus_{lcm(\lambda)|d,C_{\lambda}\neq\\{e\\}}C_{\lambda}=C.$ By
Lemmas 4.1.9 and 4.1.15 $C$ has a cyclic descent extension and
$(1+x)|H_{C}(x)$. On the other hand $H_{\\{e\\}}(x)=1$. Obviously
$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}=C\uplus\\{e\\}$, and

$H_{\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}}(x)=H_{C}(x)+H_{\\{e\\}}(x)=H_{C}(x)+1.$

Since $(1+x)|H_{C}(x)$, $(1+x)\not|(H_{C}(x)+1$, which implies that
$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}$ has no cyclic descent
extension. ∎

Now we show that when $d=p^{k}$ for some prime number $p$, to prove the cyclic
descent extensibility of $\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}$, it
is enough to prove the cyclic descent extensibility of
$\mathcal{R}_{p}{\left(\mathfrak{S}_{n}\right)}$.

######  Lemma 5.2.2.

Assume that $p|n$, $p$ is prime and a cyclic descent extension exists for
$\mathcal{R}_{p}{\left(\mathfrak{S}_{n}\right)}$. Then for every $d=p^{k}$
with $k>1$, $\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}$ has a cyclic
descent extension.

###### Proof.

Let $C$ denote
$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}\setminus\mathcal{R}_{p}{\left(\mathfrak{S}_{n}\right)}$.
If $C=\emptyset$ then we are done, since
$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}=\mathcal{R}_{p}{\left(\mathfrak{S}_{n}\right)}$
in this case. Otherwise, we have

$C=\biguplus_{\begin{subarray}{c}lcm(\lambda)|p^{k}\\\
lcm(\lambda)>p\end{subarray}}C_{\lambda}.$

But every conjugacy class $C_{\lambda}$ in the union has a cycle of length
$p^{t}$ for $t>1$, which is not square-free, namely $\lambda$ is not of the
form $(r^{s})$ with square-free $r$. It follows that $C_{\lambda}$ has a
cyclic descent extension, which implies the same for $C$ by Lemma 4.1.9. By
assumption, $\mathcal{R}_{p}{\left(\mathfrak{S}_{n}\right)}$ has a cyclic
descent extension, and so does
$\mathcal{R}_{d}{\left(\mathfrak{S}_{n}\right)}$, as a disjoint union of $C$
and $\mathcal{R}_{p}{\left(\mathfrak{S}_{n}\right)}$. ∎

We proceed to prove Theorem 5.1.6 when $d=2$. We do it now, as the proof does
not need the tools we develop in later sections. In addition, we can later
assume that $d\neq 2^{k}$ when proving the general case, thus significantly