=Paper=
{{Paper
|id=Vol-2113/paper2
|storemode=property
|title=Cyclic descent extensions and distributions
|pdfUrl=https://ceur-ws.org/Vol-2113/paper2.pdf
|volume=Vol-2113
|authors=Ron M. Adin,Sergi Elizalde,Victor Reiner,Yuval Roichman
|dblpUrl=https://dblp.org/rec/conf/gascom/AdinERR18
}}
==Cyclic descent extensions and distributions==
https://ceur-ws.org/Vol-2113/paper2.pdf
Cyclic descent extensions and distributions
Ron M. Adin Sergi Elizalde
Department of Mathematics Department of Mathematics
Bar-Ilan University Dartmouth College
Ramat-Gan 52900, Israel Hanover, NH 03755, USA
radin@math.biu.ac.il sergi.elizalde@dartmouth.edu
Victor Reiner Yuval Roichman
School of Mathematics Department of Mathematics
University of Minnesota Bar-Ilan University
Minneapolis, MN 55455, USA Ramat-Gan 52900, Israel
reiner@math.umn.edu yuvalr@math.biu.ac.il
Abstract
The notion of descent set is classical both for permutations and for
standard Young tableaux (SYT). Cellini introduced a natural notion of
cyclic descent set for permutations, and Rhoades introduced such a no-
tion for SYT, but only of rectangular shapes. In this paper, we describe
cyclic descents for SYT of various other shapes. Motivated by these
findings, we define cyclic extensions of descent sets in a general con-
text, and we show that they exist for SYT of almost all shapes. Finally,
we introduce the ring of cyclic quasisymmetric functions and apply it
to analyze the distributions of cyclic descents over permutations and
SYT.
1 Introduction
The notion of descent set, for permutations as well as for standard Young tableaux (SYT), is classical. Cellini
introduced a natural notion of cyclic descent set for permutations, and Rhoades introduced such a notion for
SYT — but only for rectangular shapes.
In [ER17a] and [AER18] we defined cyclic descent set maps for SYT of various shapes; see Theorem 3.2 below
and the remark following it. Motivated by these results, cyclic extensions of descent sets have been defined in
a general context and shown to exist for SYT of almost all shapes [ARR17]; see Theorem 4.1 below. The proof
applies nonnegativity properties of Postnikov’s toric Schur polynomials, providing a new interpretation of certain
Gromov-Witten invariants. Finally, the ring of cyclic quasisymmetric functions has been introduced and studied
in [AGRR+18], and further applied to analyze the resulting cyclic Eulerian distributions.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org
32
2 Background
The descent set of a permutation π = [π1 , . . . , πn ] in the symmetric group Sn on n letters is defined as
Des(π) := {1 ≤ i ≤ n − 1 : πi > πi+1 } ⊆ [n − 1],
where [m] := {1, 2, . . . , m}. For example, Des([2, 1, 4, 5, 3]) = {1, 4}. Its cyclic descent set was defined by
Cellini [Cel98] as
cDes(π) := {1 ≤ i ≤ n : πi > πi+1 } ⊆ [n], (1)
with the convention πn+1 := π1 . For example, cDes([2, 1, 4, 5, 3]) = {1, 4, 5}. This cyclic descent set was further
studied by Dilks, Petersen, Stembridge [DPS09] and others. It has the following important properties. Consider
the two actions of the cyclic group Z, on Sn and on the power set of [n], in which the generator p of Z acts by
p
[π1 , π2 , . . . , πn−1 , πn ] − 7 → [πn , π1 , π2 , . . . , πn−1 ],
p
{i1 , . . . , ik } 7−→ {i1 + 1, . . . , ik + 1} mod n.
Then for every permutation π, one has the following three properties:
cDes(π) ∩ [n − 1] = Des(π) (extension) (2)
cDes(p(π)) = p(cDes(π)) (equivariance) (3)
∅ ( cDes(π) ( [n] (non-Escher) (4)
The term non-Escher refers to M. C. Escher’s drawing “Ascending and Descending”, which paradoxically depicts
the impossible cases cDes(π) = ∅ and cDes(π) = [n].
There is also an established notion of descent set for a standard (Young) tableau (SYT) T of a skew shape
λ/µ:
Des(T ) := {1 ≤ i ≤ n − 1 : i + 1 appears in a lower row of T than i} ⊆ [n − 1].
For example, the following SYT T of shape λ/µ = (4, 3, 2)/(1, 1) has Des(T ) = {2, 3, 5}:
1 2 7
3 5
4 6
For the special case of an SYT T of rectangular shape, Rhoades [Rho10, Lemma 3.3] introduced a notion of
cyclic descent set cDes(T ), possessing the above properties (2), (3) and (4) with respect to the Z-action in which
the generator p acts on tableaux via Schützenberger’s jeu-de-taquin promotion operator. A similar concept of
cDes(T ) and accompanying action p was introduced for two-row shapes and certain other skew shapes (see
Subsection 3.2 for the list) in [AER18, ER17a], and used there to answer Schur positivity questions.
3 Cyclic descents: definition and examples
3.1 Definition
Let us begin by formalizing the concept of a cyclic extension. Recall the bijection p : 2[n] −→ 2[n] induced by
the cyclic shift i 7→ i + 1 (mod n), for all i ∈ [n].
Definition 3.1. Let T be a finite set. A descent map is any map Des : T −→ 2[n−1] . A cyclic extension of
Des is a pair (cDes, p), where cDes : T −→ 2[n] is a map and p : T −→ T is a bijection, satisfying the following
axioms: for all T in T ,
(extension) cDes(T ) ∩ [n − 1] = Des(T ),
(equivariance) cDes(p(T )) = p(cDes(T )),
(non-Escher) ∅ ( cDes(T ) ( [n].
The non-Escher axiom is used to prove the (essential) uniqueness of the cyclic extension.
33
3.2 Examples
Cyclic extensions of descent maps have been given previously in several cases:
• For T = Sn , the descent set Des(π) of a permutation π was described in Section 2, as was Cellini’s original
cyclic extension (cDes, p). Note that n ≥ 2 is required for the non-Escher property.
• Let T = SYT(λ) where λ = (ab ) has rectangular shape, e.g.
λ = (53 ) =
Consider the usual notion of descent set Des(T ) on standard tableaux, as in Section 2. As mentioned earlier,
Rhoades [Rho10, Lemma 3.3] showed that Schützenberger’s jeu-de-taquin promotion operation p provides a
cyclic extension (cDes, p). Again, we require a, b ≥ 2 for the non-Escher property.
New examples are given in [AER18].
Theorem 3.2.
1. Let T = SYT(λ) where λ is a hook plus internal corner, namely λ = (n − 2 − k, 2, 1k ) for 0 ≤ k ≤ n − 4;
e.g.,
λ = (8, 2, 1, 1, 1) =
There is a unique cyclic descent map cDes on T , defined as follows: by the extension property, it suffices
to specify when n ∈ cDes(T ), and one decrees this to hold if and only if the entry T2,2 − 1 lies strictly west
of T2,2 (namely, in the first column of T ); see [AER18] for more details. Note that for most shapes in this
family there are several possible shifting bijections p, so that the cyclic extension (cDes, p) is not unique.
2. Let T = SYT(λ) with λ of two-row shape, namely λ = (n − k, k) for 2 ≤ k ≤ n/2; e.g.,
λ = (8, 3) =
There exists a cyclic extension of Des defined as follows; see [AER18]. Decree that n ∈ cDes(T ) if and only
if both
− the last two entries in the second row of T are consecutive, and
− for every 1 < i < k, T2,i−1 > T1,i .
Other examples involve direct sums of shapes. Given t (skew) shapes ν 1 , . . . , ν t , the direct sum ν 1 ⊕ν 2 ⊕· · ·⊕ν t
is the skew shape consisting of t diagrams of shapes ν 1 , . . . , ν t , for each i the diagram of ν i+1 is strictly northeast
of the diagram of ν i , with no rows or columns in common.
• Given
P any (strict) composition α of n, that is, an ordered sequence of positive integers α = (α1 , . . . , αt ) with
α
i i = n, consider the associated horizontal strip skew shape
α⊕ := (α1 ) ⊕ (α2 ) ⊕ · · · ⊕ (αt )
whose rows, from southwest to northeast, have sizes α1 , . . . , αt . For T in T = SYT(α⊕ ), we define
cDes(T ) := {1 ≤ i ≤ n : i + 1 is in a lower row than i},
where n + 1 is interpreted as 1, as well as a bijection p : SYT(α⊕ ) → SYT(α⊕ ) which first replaces each
entry j of T by j + 1 (mod n) and then re-orders each row to make it left-to-right increasing. One can
34
check that this (cDes, p) is a cyclic extension of Des, with t ≥ 2 required for the non-Escher property. For
example, when α = (3, 4, 2) (and n = 9), one has the following standard tableaux T of shape α⊕ :
3 9 1 4
p
T = 1 5 7 8 7−→ p(T ) = 2 6 8 9
2 4 6 3 5 7
p
cDes(T ) = {1, 3, 5, 9} 7−→ cDes(p(T )) = {1, 2, 4, 6}
This generalizes the case of (cDes, p) on Sn , since for α = (1n ) = (1, 1, . . . , 1) one has a bijection Sn →
SYT(α⊕ ) which sends a permutation w to the tableau whose entries are w−1 (1), . . . , w−1 (n) read from
southwest to northeast; e.g., for n = 5,
1
4
w = [5, 3, 1, 4, 2] 7−→ 2
5
3
This bijection maps Cellini’s cyclic extension (cDes, p) on Sn to the one on SYT(α⊕ ) for α = (1, 1, . . . , 1)
defined above1 .
• Furthermore, for any nonempty partition λ ` n − 1, the partition λ ⊕ (1), e.g.
λ = (4, 3, 1) ⊕ (1) =
has an explicit cyclic extension of Des described in [ER17a]. This case was, in fact, our original motivation,
and the question of existence of a cyclic extension of Des on SYT(λ/µ) appears there as [ER17a, Problem
5.5].
4 Cyclic descents for standard Young tableaux
Our first main result is a necessary and sufficient condition for the existence of a cyclic extension cDes of the
descent map Des on the set SYT(λ/µ) of standard Young tableaux of shape λ/µ, with an accompanying Z-action
on SYT(λ/µ) via an operator p, satisfying properties (2), (3) and (4). In this story, a special role is played by
the skew shapes known as ribbons (connected skew shapes containing no 2 × 2 rectangle), and in particular hooks
(straight ribbon shapes, namely λ = (n − k, 1k ) for k = 0, 1, . . . , n − 1). Early versions of [AER18] and [ER17a]
conjectured the following result.
Theorem 4.1. [ARR17, Theorem 1.1] Let λ/µ be a skew shape. The descent map Des on SYT(λ/µ) has a
cyclic extension (cDes, p) if and only if λ/µ is not a connected ribbon. Furthermore, for all J ⊆ [n], all such
cyclic extensions share the same cardinalities #cDes−1 (J).
Our strategy for proving Theorem 4.1 is inspired by a result of Gessel [Ges84, Theorem 7] that we recall here.
For a subset J = {j1 < . . . < jt } ⊆ [n − 1], the composition (of n)
α(J, n) := (j1 , j2 − j1 , j3 − j2 , . . . , jt − jt−1 , n − jt ) (5)
defines a connected ribbon having the entries of α(J, n) as row lengths, and thus an associated (skew) ribbon
Schur function X
sα(J,n) := (−1)#(J\I) hα(I,n) (6)
∅⊆I⊆J
1 This cyclic descent map can be further generalized to strips, which are the disconnected shapes each of whose connected
components consists of either one row or one column; see [AER18].
35
with the following property: for any skew shape λ/µ, the descent map Des : SYT(λ/µ) −→ 2[n−1] has fiber sizes
given by
#Des−1 (J) = hsλ/µ , sα(J,n) i (∀J ⊆ [n − 1]), (7)
where h−, −i is the usual inner product on symmetric functions.
By analogy, for a subset ∅ 6= J = {j1 < j2 < . . . < jt } ⊆ [n] we define the corresponding cyclic composition
of n as
αcyc (J, n) := (j2 − j1 , . . . , jt − jt−1 , j1 + n − jt ), (8)
with αcyc (J, n) := (n) when J = {j1 }; note that αcyc (∅, n) is not defined. The corresponding affine (or cyclic)
ribbon Schur function is then defined as
X
s̃αcyc (J,n) := (−1)#(J\I) hαcyc (I,n) . (9)
∅6=I⊆J
We then collect enough properties of this function to show that there must exist a map cDes : SYT(λ/µ) → 2[n]
and a Z-action p on SYT(λ/µ), as in Theorem 4.1, such that fiber sizes are given by
#cDes−1 (J) = hsλ/µ , s̃αcyc (J,n) i (∀ ∅ ( J ( [n]). (10)
The nonnegativity of this inner product when λ/µ is not a connected ribbon ultimately relies on relating s̃αcyc (J,n)
to a special case of Postnikov’s toric Schur polynomials, with their interpretation in terms of Gromov-Witten
invariants for Grassmannians [Pos05].
5 Cyclic quasisymmetric functions
5.1 The ring of cyclic quasisymmetric functions
Recall from [Ges84] the following basic definitions: A quasi-symmetric function is a formal power series f ∈
Z[[x1 , x2 , . . .]] of bounded degree such that, for any t ≥ 1, any two increasing sequences i1 < · · · < it and
i01 < · · · < i0t of positive integers, and any sequence (m1 , . . . , mt ) of positive integers, the coefficients of xm mt
i1 · · · x it
1
m1 mt
and xi0 · · · xi0 in f are equal. Denote by QSym the set of all quasi-symmetric functions, and by QSymn the
1 t
set of all quasi-symmetric functions which are homogeneous of degree n.
The fundamental quasi-symmetric function corresponding to a subset J ⊆ [n − 1] is defined by
X
Fn,J := xi1 · · · xin ,
where the sum extends over all sequences (i1 , . . . , in ) of positive integers such that j ∈ J ⇒ ij < ij+1 and
j 6∈ J ⇒ ij ≤ ij+1 . The set {Fn,J : J ⊆ [n − 1]} forms a basis for the additive abelian group QSymn .
The cyclic analogues of these concepts are introduced in [AGRR+18].
Definition 5.1. A cyclic quasi-symmetric function is a formal power series f ∈ Z[[x1 , x2 , . . .]] of bounded degree
such that, for any t ≥ 1, any two increasing sequences i1 < · · · < it and i01 < · · · < i0t of positive integers, any
sequence m = (m1 , . . . , mt ) of positive integers, and any cyclic shift m0 = (m01 , . . . , m0t ) of m, the coefficients of
m01 m0t
xm mt
i1 · · · xit and xi0 · · · xi0 in f are equal.
1
1 t
Denote by cQSym the set of all cyclic quasi-symmetric functions, and by cQSymn the set of all cyclic quasi-
symmetric functions which are homogeneous of degree n.
Observation 5.2. QSym, cQSym and the set Sym of symmetric functions (sometimes denoted Λ) are graded
abelian groups satisfying
Sym ( cQSym ( QSym (11)
It is not too difficult to check that they are also rings, that is, closed under the multiplication operation on power
series. For Sym, QSym this is well-known; the proof for cQSym is given in [AGRR+18].
36
5.2 Fundamental cyclic quasisymmetric functions
cyc
Definition 5.3. For each subset J ⊆ [n] denote by Pn,J the set of all pairs (w, k) consisting of a word w =
(w1 , . . . , wn ) ∈ Nn and an index k ∈ [n] which satisfy
(i) The word w is “cyclically weakly increasing” from index k, namely wk ≤ wk+1 ≤ . . . ≤ wn ≤ w1 ≤ . . . ≤
wk−1 .
(ii) If j ∈ J then wj 6= wj+1 , where indices are computed modulo n. (This condition is vacuous for J = ∅.)
Remark 5.4. The index k is uniquely determined by the word w, unless all the letters of w are equal; in which
case, any index k ∈ [n] will do. These “constant words” are relevant only for J = ∅, and the definition implies
cyc
that each of them is counted n times (and not just once) in Pn,∅ .
cyc
Example 5.5. Let n = 5 and J = {1, 3}. The pairs (12345, 1), (23312, 4) and (23122, 3) are in P5,{1,3} (see
Figure 1), but the pairs (12354, 1), (22312, 4) and (23112, 3) are not.
1 2 2
5 2 2
∧ 2 ∧ 3 ∧ 3
4 1 2
3 3 1
cyc
Figure 1: The pairs (12345, 1), (23312, 4) and (23122, 3) in P5,{1,3} .
Let Dn,J := {i ∈ Z/nZ : J + i ≡ J (mod n)} be the stabilizer of J under the action of Z/nZ by cyclic shifts,
and let dn,J := #Dn,J .
Definition 5.6. The fundamental cyclic quasisymmetric function corresponding to a subset J ⊆ [n] is defined
by
cyc
X
Fn,J := d−1
n,J xw1 xw2 · · · xwn .
cyc
(w,k)∈Pn,J
[n] [n] [n]
Let 20 be the set of all nonempty subsets of [n], and let c20 be the set of orbits of elements of 20 under
cyc cyc
cyclic shifts. If J and J 0 are in the same orbit then Fn,J = Fn,J 0.
cyc [n]
Theorem 5.7. The set {Fn,J : J ∈ c20 } is a Z-basis for cQSymn .
Furthermore, letting sλ/µ be the skew Schur function indexed by a non-ribbon shape λ/µ, we have
X cyc
Fn,cDes(T ) = sλ/µ . (12)
T ∈SYT(λ/µ)
6 Cyclic Eulerian distributions
The distribution of descents on sets of permutations and other combinatorial objects, known as the Eulerian
distribution, has been studied extensively; see, e.g., [BBS09], [Pet15, p. 91] and references therein. In this section
we study the distribution of cyclic descents over SYT and compare it to its distribution over permutations.
37
6.1 Univariate generating functions
The descent number is the size of the descent set. For any skew shape λ/µ of size n there is a known expression
[Sta99, equation (7.96)] for the generating function of the descent number, des, on standard Young tableaux of
shape λ/µ: X X
tdes(T ) = (1 − t)n+1 sλ/µ (1m+1 )tm . (13)
T ∈SYT(λ/µ) m≥0
m
Here sλ/µ (1 ) is the specialization of the skew Schur function sλ/µ (x1 , x2 , . . .) given by x1 = . . . = xm = 1
and xm+1 = . . . = 0. Note that when µ = ∅ this becomes even more explicit, through the hook-content
formula [Sta99, Cor. 7.21.4] for the specialization sλ (1m ). In particular, for the skew shape (1)⊕n this gives the
well-known Carlitz formula for the Eulerian distribution on Sn :
X X
Sdes
n (t) := tdes(w) = (1 − t)n+1 (m + 1)n tm (14)
w∈Sn m≥0
An analogous expression for the cyclic descent number cdes is proved in [ARR17].
Corollary 6.1. For any skew shape λ/µ of size n which is not a connected ribbon,
X X tm
tcdes(T ) = n(1 − t)n sλ/µ (1m ) . (15)
m
T ∈SYT(λ/µ) m≥1
In particular, for the skew shape (1)⊕n this gives
X X
Scdes
n (t) := tcdes(w) = n(1 − t)n mn−1 tm = nt Sdes
n−1 (t) (n ≥ 2). (16)
w∈Sn m≥1
For two-row shapes, [ARR17, Lemma 2.4] is applied in [AER18] to deduce the following.
Theorem 6.2. For any 2 ≤ k ≤ n/2,
k
X X n k−1 n−k−1 k−2 n−k
tcdes(T ) = − td .
d d−1 d−1 d−1 d−1
T ∈SYT((n−k,k)) d=1
6.2 Multivariate generating functions
Next we compare the distribution of cDes on SYT(λ) to the distribution of cDes on Sn . Recall [Sag01, Theorem
3.1.1 and §5.6 Ex. 22(a)] that the Robinson-Schensted correspondence is a bijection between Sn and the set of
pairs of standard Young tableaux of the same shape λ (and size n), having the property that if w 7→ (P, Q) then
Des(w) = Des(Q). Consequently
X X X
tDes(w) = fλ tDes(T ) .
w∈Sn λ`n T ∈SYT(λ)
Here tS := λ
Q
i∈S ti for S ⊆ {1, 2, . . .}, while λ ` n means λ is a partition of n, and f := #SYT(λ).
Note P
that Theorem 4.1 implies that any non-hook shape λ, as well as any disconnected skew shape λ/µ, will
have T ∈SYT(λ/µ) tcDes(T ) well-defined and independent of the choice of cyclic extension (cDes, p) for Des on
SYT(λ/µ). Recall from Section 3 the notation ⊕ for direct sum of shapes.
By Equation (12), or alternatively by Equation (10), we deduce the following second main result.
Theorem 6.3. For any n ≥ 2
n−1
X
X
cDes(w)
X
λ
X
cDes(T ) n−2 X
t = f t + tcDes(T ) ,
k−1
w∈Sn non-hook T ∈SYT(λ) k=1 T ∈SYT((1k )⊕(n−k))
λ`n
where cDes is defined on Sn by Cellini’s formula (1) and on standard Young tableaux (of the relevant shapes)
as in Theorem 4.1.
38
The explicit description of the unique cyclic descent map on near-hook SYT given in [AER18], is applied there
to deduce the following.
Proposition 6.4. 1. For any n ≥ 2
n−1
X X n
Y
tcDes(T ) = (1 + ti ) − 1 − t1 · · · tn .
k=1 T ∈SYT((1k )⊕(n−k)) i=1
2. For any n ≥ 4
n−2 n n
X X Y X t j
tcDes(T ) = 1 + t1 · · · tn + (1 + ti ) · −1 + .
i=1 j=1
(1 + t j−1 )(1 + t j )
k=2 T ∈SYT((n−k,2,1k−2 ))
6.3 Cyclic Eulerian distribution on Sn
We now focus on λ/µ = (1)⊕n , where we can take T = Sn and use the extra symmetry to get more refined
results. Consider the multivariate generating functions
X
SDes Des
n (t) = Sn (t1 , . . . , tn−1 ) := tDes(w)
w∈Sn
and X
ScDes
n (t) = ScDes
n (t1 , . . . , tn−1 , tn ) := tcDes(w) .
w∈Sn
Note that SDes cDes
n (t) and Sn (t) are, respectively, the flag h-polynomials for the type An−1 Coxeter complex and
for the reduced Steinberg torus considered by Dilks, Petersen, and Stembridge [DPS09]. The two are related by
an obvious specialization cDes
Sn (t) t =1 = SDes n (t). (17)
n
On the other hand, ScDesn (t) and SDes
n−1 (t) are also related in a slightly less obvious way. Define an action
of the cyclic group Z/nZ = hci = {e, c, c2 , · · · , cn−1 } on Z[t1 , . . . , tn ] by shifting subscripts modulo n, i.e.
c(ti ) = ti+1 (mod n) .
Proposition 6.5. For n ≥ 2, one has
n
X
ScDes ci tn SDes
n (t) = n−1 (t) (18)
i=1
and also
ScDes
n (t) = g(t) + t[n] g(t−1 ), (19)
where
n−1
X
g(t) = g(t1 , . . . , tn−1 ) := ScDes ti · ci SDes
n (t) t =0
= n−1 (t) t =0 . (20)
n n
i=1
Remark 6.6. Formulas (17) and (18) imply the following interesting (and seemingly new) recurrence for the
ordinary multivariate Eulerian distribution SDes
n (t):
" n #
X
Des i Des
Sn (t) = ti · c Sn−1 (t) .
i=1 tn =1
One can specialize ScDes
n (t) to a bivariate generating function
X
Scdes
n (t, u) := tdes(w) ucdes(w)−des(w)
w∈Sn
by setting t1 = t2 = · · · = tn−1 := t and tn := u. The following result generalizes an observation of Fulman [Ful00]
and Petersen [Pet05].
39
Proposition 6.7. For n ≥ 2 one has
d
Scdes
n (t, u) = nt + (u − t) t Sdes
n−1 (t). (21)
dt
d
Remark 6.8. The coefficients of f (t) = dt tSdes
n−1 (t) appear as OEIS entry A065826.
The preceding calculations lead to an exponential generating function for Scdes
n (u, t), generalizing work of
Petersen [Pet15, Proposition 14.4]. For more details see [ARR17, §6].
7 Final remarks and open problems
Detailed proofs of Theorems 4.1 and 6.3 may be found in the full version paper [ARR17]. Our proof of the
existence of (cDes, p) in Theorem 4.1, whose strategy was sketched above, is indirect and involves arbitrary
choices.
Problem 7.1. Find a natural, explicit map cDes and cyclic action p on SYT(λ/µ) as in Theorem 4.1.
Problem 7.2. Find a Robinson-Schensted-style bijective proof of Theorem 6.3.
For J = {j1 , · · · , jt } ⊆ [n] let −J := {−j1 , . . . , −jt } (interpreted modulo n).
Corollary 7.3. Let λ/µ be a skew shape of size n which is not a connected ribbon. For any J ⊆ [n] and any
cyclic extension cDes of the usual descent map on SYT(λ/µ), the fiber size
#cDes−1 (J) = #cDes−1 (−J).
Problem 7.4. For a solution of Problem 7.1, find an involution on SYT(λ/µ) which sends the cyclic descent
set to its negative.
Problem 7.5. For non-ribbon shapes λ/µ, can one choose the operator p in Theorem 4.1 and a polynomial X(q)
to obtain a cyclic sieving phenomenon (CSP) ?
This problem was solved by Rhoades [Rho10] for rectangular shapes and by Pechenik [Pec14] for shapes
(k, k, 1n−2k ). Recalling from [ER17a] the cyclic descent extension for SYT(λ ⊕ (1)), Equation (10) in the current
paper has been applied in [ARS+18] to obtain a refined CSP on SYT of these skew shapes.
Acknowledgements
Thanks to the anonymous referees for their useful comments, which led to an improved presentation.
References
[AER18] R. M. Adin, S. Elizalde and Y. Roichman. Cyclic descents for near-hook and two-row shapes. At
https://arxiv.org/abs/1801.00044, 2018.
[AGRR+18] R. M. Adin, I. Gessel, V. Reiner and Y. Roichman. Cyclic quasisymmetric functions. In preparation.
[ARR17] R. M. Adin, V. Reiner and Y. Roichman. On cyclic descents for tableuax. At
https://arxiv.org/abs/1710.06664, 2017.
[ARS+18] C. Ahlbach, B. Rhoades and J. P. Swanson. Euler-Mahonian refined cyclic sieving. In preparation.
[BBS09] M. Barnabei, F. Bonetti and M. Silimbani. The Eulerian distribution on centrosymmetric involutions.
Discrete Mathematics and Theoretical Computer Science, 11:95-115, 2009.
[Bjo84] A. Björner. Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings.
Advances in Mathematics, 52:173–212, 1984.
[Bon12] M. Bóna. Combinatorics of Permutations, 2nd edition. Discrete Mathematics and its Applications,
CRC Press, Boca Raton, 2012.
40
[BKPT16] A. S. Buch, A. Kresch, K. Purbhoo and H. Tamvakis. The puzzle conjecture for the cohomology of
two-step flag manifolds. Journal of Algebraic Combinatorics, 44:973-1007, 2016.
[Cel98] P. Cellini. Cyclic Eulerian elements. European Journal of Combinatorics, 19:545–552, 1998.
[CPY15] M. Chmutov, P. Pylyavskyy and E. Yudovina. Matrix-Ball Construction of affine Robinson-Schensted
correspondence. At https://arxiv.org/abs/1511.05861, 2015.
[DPS17] K. Dilks, O. Pechenik and J. Striker. Resonance in orbits of plane partitions and increasing tableaux.
Journal of Combinatorial Theory Series A, 148:244–274, 2017.
[DPS09] K. Dilks, K. Petersen and J. Stembridge. Affine descents and the Steinberg torus. Advances in Applied
Mathematics, 42:423–444, 2009.
[ER17a] S. Elizalde and Y. Roichman. Schur-positive sets of permutations via products of grid classes. Journal
of Algebraic Combinatorics, 45:363-405, 2017.
[ER17a] S. Elizalde and Y. Roichman. On rotated Schur-positive sets. Journal of Combinatorial Theory Series
A, 152:121-137, 2017.
[Ful00] J. Fulman. Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting. Journal of
Algebra, 231:614–639, 2000.
[Ges84] I. M. Gessel. Multipartite P-partitions and inner products of skew Schur functions. in: Combinatorics
and algebra (Boulder, Colo., 1983), pp. 289–317, Contemp. Math. 34, Amer. Math. Soc., Providence, RI,
1984.
[GR97] I. M. Gessel and C. Krattenthaler. Cylindric partitions. Transactions of the American Mathematical
Society, 349:429–479, 1997.
[Ira16] A. Iraci. Cyclic sieving phenomenon in noncrossing partitions. M.Sc. Thesis, Univ. di Pisa, 2016.
[Kan01] R. Kane. Reflection groups and invariant theory. CMS Books in Mathematics 5, Springer-Verlag, New
York, 2001.
[Mac15] I. G. Macdonald. Symmetric functions and Hall polynomials. 2nd edition. Oxford Classic Texts in the
Physical Sciences, The Clarendon Press, Oxford University Press, New York, 2015.
[McN06] P. McNamara. Cylindric skew Schur functions. Advances in Mathematics, 205:275–312 (2006).
[MS16] J. Morse and A. Schilling. Crystal approach to affine Schubert calculus. International Mathematics
Research Notices, 2016(8):2239–2294, 2016.
[Paw16] B. Pawlowski. A representation-theoretic interpretation of positroid classes. At
https://arxiv.org/abs/1612.00097.
[Pec14] O. Pechenik. Cyclic sieving of increasing tableaux and small Schrder paths. Journal of Combinatorial
Theory Series A, 125:357-378, 2014.
[Pet05] T. K. Petersen. Cyclic descents and P -partitions. Journal of Algebraic Combinatorics, 22:343-375, 2005.
[Pet15] T. K. Petersen. Eulerian numbers. Birkhäuser Advanced Texts, Birkhäuser/Springer, New York, 2015.
[Pos05] A. Postnikov. Affine approach to quantum Schubert calculus. Duke Mathematical Journal, 128:473–509,
2005.
[Rho10] B. Rhoades. Cyclic sieving, promotion, and representation theory. Journal of Combinatorial Theory
Series A, 117:38–76, 2010.
[Sag01] B. E. Sagan. The symmetric group: Representations, combinatorial algorithms, and symmetric functions,
2nd edition. Graduate Texts in Mathematics 203. Springer-Verlag, New York, 2001.
41
[Sol68] L. Solomon. A decomposition of the group algebra of a finite Coxeter group. Journal of Algebra, 9:220–
239, 1968.
[Sta82] R. P. Stanley. Some aspects of groups acting on finite posets. Journal of Combinatorial Theory Series
A, 32:132–161, 1982.
[Sta12] R. P. Stanley. Enumerative combinatorics, Vol. 1, Second edition. Cambridge Studies in Advanced
Mathematics 49, Cambridge Univ. Press, Cambridge, 2012.
[Sta99] R. P. Stanley. Enumerative combinatorics, Vol. 2. Cambridge Studies in Advanced Mathematics 62,
Cambridge Univ. Press, Cambridge, 1999.
42