centertableaux

# Poset Associahedra and Stack-sorting

Son Nguyen, Andrew Sack This material is based upon work supported by the
National Science Foundation Graduate Research Fellowship Program under Grant
No. DGE-2034835 and National Science Foundation Grants No. DMS-1954121 and
DMS-2046915. Any opinions, findings, and conclusions or recommendations
expressed in this material are those of the author(s) and do not necessarily
reflect the views of the National Science Foundation.

###### Abstract

For any finite connected poset $P$, Galashin introduced a simple convex
$(|P|-2)$-dimensional polytope $\mathscr{A}(P)$ called the poset
associahedron. For a certain family of posets, whose poset associahedra
interpolate between the classical permutohedron and associahedron, we give a
simple combinatorial interpretation of the $h$-vector. Our interpretation
relates to the theory of stack-sorting of permutations. It also allows us to
prove real-rootedness of some of their $h$-polynomials.

###### Contents

  1. 1 Introduction

##  1 Introduction

For a finite connected poset $P$, Galashin introduced the poset associahedron
$\mathscr{A}(P)$ (see [galashin2021poset]). The faces of $\mathscr{A}(P)$
correspond to tubings of $P$, and the vertices of $\mathscr{A}(P)$ correspond
to maximal tubings of $P$; see Section LABEL:sec:poset-ass for the
definitions. $\mathscr{A}(P)$ can also be described as a compactification of
the configuration space of order-preserving maps $P\rightarrow\mathbb{R}$.
Many polytopes can be described as poset associahedra, including permutohedra
and associahedra. In particular, when $P$ is the claw poset, i.e. $P$ consists
of a unique minimal element $0$ and $n$ pairwise-incomparable elements, then
$\mathscr{A}(P)$ is the $n$-permutohedron. On the other hand, when $P$ is a
chain of $n+1$ elements, i.e. $P=C_{n+1}$, then $\mathscr{A}(P)$ is the
associahedron $K_{n+1}$. Among many different combinatorial interpretations
for the $h$-vector $(h_{0},h_{1},\ldots,h_{n-1})$ of $K_{n+1}$, we want to
recall the following interpretation: $h_{i}$ counts the number of 231-avoiding
permutations with exactly $i$ descents.

Stack-sorting is a function $s:\mathfrak{S}_{n}\rightarrow\mathfrak{S}_{n}$
which attempts to sort the permutations $w$ in $\mathfrak{S}_{n}$ in linear
time, not always sorting them completely (see definition in Section
LABEL:subsec:stack-sorting). A permutation $w\in S_{n}$ is stack-sortable if
$s(w)=12\ldots n$. It is well-known that stack-sortable permutations are
exactly 231-avoiding permutations. Thus, we have an alternative interpretation
for the $h$-vector of $\mathscr{A}(C_{n+1})$: $h_{i}$ counts the number of
permutations in $s^{-1}(12\ldots n)$ with exactly $i$ descents.

The focus of our paper is the posets $A_{n,k}=C_{n+1}\oplus A_{k}$ where
$A_{k}$ is the antichain of $k$ elements. In particular, $A_{0,k}$ is a claw
poset, and $A_{n,0}$ is the chain $C_{n+1}$. Surprisingly, the $h$-vector of
$\mathscr{A}(A_{n,k})$ is also counted by descents of stack-sorting preimages.
Let $\mathfrak{S}_{n,k}=\\{w~{}|~{}w\in\mathfrak{S}_{n+k},w_{i}=i~{}\text{for
all}~{}i>k\\}$, we prove the following generalization of the above classic
result.

######  Theorem LABEL:thm:A_n,k-h-vector.

Let $h=(h_{0},h_{1},\ldots,h_{n+k-1})$ be the $h$-vector of
$\mathscr{A}(A_{n,k})$. Then $h_{i}$ counts the number of permutations in
$s^{-1}(\mathfrak{S}_{n,k})$ with exactly $i$ descents.

An immediate corollary of Theorem LABEL:thm:A_n,k-h-vector is
$\gamma$-nonnegativity of $\mathscr{A}(A_{n,k})$. In particular, we have the
following result by Bränden.

######  Theorem LABEL:thm:ss-preimage-gamma ([branden2008actions]).

For $A\subseteq\mathfrak{S}_{n}$, we have

$\sum_{\sigma\in
s^{-1}(A)}x^{\operatorname{des}(\sigma)}=\sum_{m=0}^{\lfloor\frac{n-1}{2}\rfloor}\dfrac{|\\{\sigma\in
s^{-1}(A)~{}:~{}\text{peak}(\sigma)=m\\}|}{2^{n-1-2m}}x^{m}(1+x)^{n-1-2m},$

where $\text{peak}(\sigma)$ is the number of index $i$ such that
$\sigma_{i-1}<\sigma_{i}>\sigma_{i+1}$.

Thus, we have the following corollary.

######  Corollary LABEL:cor:A_n,k-gamma-nonnegative.

The $\gamma$-vector of $\mathscr{A}(A_{n,k})$ is nonnegative.

In addition, in the process of proving Theorem LABEL:thm:A_n,k-h-vector, we
find the size of $s^{-1}(\mathfrak{S}_{n,k})$ in terms of $k!$ and the Catalan
convolution $C_{n}^{(k)}$, which will be introduced in Section
LABEL:subsec:catalan-convolution.