%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{43}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{mathrsfs}
\usepackage{subcaption}

\theoremstyle{plain}

\newtheorem{innercustomthm}{Theorem}
\newenvironment{repthm}[1]
  {\renewcommand\theinnercustomthm{#1}\innercustomthm}
  {\endinnercustomthm}

\newtheorem{innercustomcor}{Corollary}
\newenvironment{repcor}[1]
  {\renewcommand\theinnercustomcor{#1}\innercustomcor}
  {\endinnercustomthm}

\newtheorem{Thm}{Theorem}
\newtheorem{Lemma}[Thm]{Lemma}
\newtheorem{Cor}[Thm]{Corollary}
\newtheorem*{Prop}{Proposition}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{conjecture}[thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\theoremstyle{remark}
\newtheorem*{case}{Case}
\newtheorem{question}[thm]{Question}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{note}{Note}
\newtheorem{example}[thm]{Example}

\newcommand{\precdot}{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}

\newcommand{\andrew}[1]{{\color{red}{#1}}}
\newcommand{\son}[1]{{\color{blue}{#1}}}


\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\TT}{\mathbb{T}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\BB}{\mathcal{B}}
\newcommand{\BBB}{\mathfrak{B}}
\newcommand{\AAA}{\mathscr{A}}
\newcommand{\DDD}{\mathfrak{D}}
\newcommand{\PPP}{\mathfrak{P}}
\newcommand{\SSS}{\mathfrak{S}}
\newcommand{\CCC}{\mathscr{C}}
\newcommand{\des}{\operatorname{des}}
\newcommand{\Ass}{\textsf{Ass}}
\newcommand{\eps}{\varepsilon}
\def\Tbad{T_{\text{bad}}}
\def\Tgood{T_{\text{good}}}

\def\TU{T_{U}}
\def\TL{T_{L}}
\def\op{\text{op}}
\def\append{\cdot}

\DeclareMathOperator\peak{peak}

\def\flipmap{\Phi_{P,S}}
\def\flipmapinverse{\Phi_{P',S}}

\usepackage{lipsum}

%% define your title in the usual way
\title{On the $f$-vectors of poset associahedra}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Son Nguyen\thanks{\href{mailto:nguy4309@umn.edu}{nguy4309@umn.edu}.}\addressmark{1} 
\and Andrew Sack\thanks{\href{mailto:andrewsack@math.ucla.edu}{andrewsack@math.ucla.edu}. 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.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Mathematics, University of Minnesota, Minneapolis, MN 55455 \\ \addressmark{2}Department of Mathematics, University of California, Los Angeles, CA 90095, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{For any finite connected poset $P$, Galashin introduced a simple convex $(|P|-2)$-dimensional polytope $\mathscr{A}(P)$ called the poset associahedron. First, we show that the $f$-vector of $\mathscr A(P)$ only depends on the comparability graph of $P$.
Additionally, for a family of posets called broom posets, whose poset associahedra interpolate between permutohedra and associahedra, we give a simple combinatorial interpretation of the $h$-vector. The interpretation relates to the theory of stack-sorting and allows us to prove the real-rootedness of some of their $h$-polynomials.


% \andrew{Suggestion for cleaner abstract:
% For any finite connected poset $P$, Galashin introduced a simple convex $(|P|-2)$-dimensional polytope $\mathscr{A}(P)$ called the poset associahedron. First, we show that the $f$-vector of Galashin's poset associahedron $\mathscr A(P)$ only depends on the comparability graph of $P$.  In particular, this allows us to produce a family of polytopes with the same $f$-vectors as permutohedra, but that are not combinatorially equivalent to permutohedra. Additionally, for a family of posets called broom posets, we give a simple combinatorial interpretation of the $h$-vector of their poset associahedra. The interpretation relates to the theory of stack-sorting and allows us to prove the real-rootedness of some of their $h$-polynomials.
% }

}



%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{poset associahedra, stack-sorting, real-rootedness}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}\label{sec:intro}

    For a finite connected poset $P$, Galashin introduced the \emph{poset associahedron} $\AAA(P)$ (see \cite{galashin2021poset}). The faces of $\AAA(P)$ correspond to {\it tubings} of $P$, and the vertices of $\AAA(P)$ correspond to {\it maximal tubings} of $P$;  see Section~\ref{subsec:poset_ass} for the definitions. $\AAA(P)$ can also be described as a compactification of the configuration space of order-preserving maps $P \rightarrow \RR$.
    
    The \emph{comparability graph} of a poset $P$ is a graph $\CCC(P)$ whose vertices are the elements of $P$ and where $i$ and $j$ are connected by an edge if $i$ and $j$ are comparable. A property of $P$ is said to be \emph{comparability invariant} if it only depends on $\CCC(P)$. Properties of finite posets known to be comparability invariant include the order polynomial and number of linear extensions~\cite{stanley1986two}, the fixed point property~\cite{dreesen1985comparability}, and the Dushnik–Miller dimension~\cite{trotter1976dimension}. Our first main result is the following.

    \begin{repthm}{\ref{thm:comparability}}
        The $f$-vector of $\AAA(P)$ is a comparability invariant.
    \end{repthm}

    In our study of the $f$-vectors of poset associahedra, we also consider a rich class of examples whose poset associahedra interpolate between associahedra and permutohedra. A \emph{broom poset} is a poset of the form $A_{n,k} := C_{n+1} \oplus A_k$ where $C_n$ is a chain of $n$ elements, $A_k$ is an antichain of $k$ elements, and $\oplus$ denotes ordinal sum.  In particular, $A_{0,k}$ is a \emph{claw poset} where $\AAA(A_{0,k})$ is a permutohedron, and $A_{n,0}$ is a chain where $\AAA(A_{n,0})$ is an associahedron. Our second main result is to give a combinatorial interpretation of the $h$-vector of $A_{n,k}$, giving a common interpretation for both permutohedra and associahedra. Our interpretation involves the theory of stack-sorting.

    % \andrew{Suggestion for rewriting of this paragraph:

    % Permutohedra and associahedra are both subclasses of poset 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 $\AAA(P)$ is the $(n-1)$-dimensional permutohedron. When $P$ is a chain of $n+1$ elements, i.e. $P = C_{n+1}$, then $\AAA(P)$ is the associahedron $K_{n+1}$.

    % (No need to recall 231-avoiding permutations unless we use this somewhere.)
    % }

    % \andrew{We might want to move some of these paragraphs around.  I think defining broom posets makes more sense here, and stack-sorting later.  Maybe something like:
    
    % We consider a common generalization of these classes of posets.  The \emph{broom} is a poset $A_{n,k} := C_{n+1} \oplus A_k$ where $A_k$ is an antichain of $k$ elements.  In particular, $A_{0,k}$ is a claw poset, and $A_{n,0}$ is the chain $C_{n+1}$. Our second main result is to give a combinatorial interpretation of the $h$-vector of $A_{n,k}$.
    % }

    West's stack-sorting map is a function $s: \SSS_n \rightarrow \SSS_n$ which attempts to sort the permutations $w$ in $\SSS_n$ in linear time, not always sorting them completely (see Definition \ref{def:stack-sorting}).  It is well-known that for the associahedron, $h_i$ counts the number of permutations in $s^{-1}(1\ldots n)$ with exactly $i$ descents. We give a generalization of this result for all broom poset associahedra.
    Define $$\SSS_{n,k} := \{w~|~w\in \SSS_{n+k}, w_i = i~\text{for all}~i>k\}.$$ We prove the following:

    \begin{repthm}{\ref{thm:A_n,k-h-vector}}
        Let $h = (h_0, h_1, \ldots, h_{n+k-1})$ be the $h$-vector of $\AAA(A_{n,k})$. Then $h_i$ counts the number of permutations in $s^{-1}(\SSS_{n,k})$ with exactly $i$ descents.
    \end{repthm}

    An immediate corollary of Theorem \ref{thm:A_n,k-h-vector} is $\gamma$-nonnegativity of $\AAA(A_{n,k})$. In particular, we recall the following result of Br\"anden.

    \begin{repthm}{\ref{thm:ss-preimage-gamma}}[\cite{branden2008actions}]
        For $A \subseteq \SSS_n$, we have
        %
        \[ \sum_{\sigma \in s^{-1}(A)} t^{\des(\sigma)} = \sum_{m = 0}^{\lfloor \frac{n-1}{2}\rfloor} \dfrac{|\{ \sigma \in s^{-1}(A)~:~\peak(\sigma) = m \}|}{2^{n-1-2m}} t^m(1+t)^{n-1-2m}, \]
        %
        where $\peak(\sigma)$ is the number of index $i$ such that $\sigma_{i-1} < \sigma_i > \sigma_{i+1}$.
    \end{repthm}

    Thus, we have the following corollary.

    \begin{repcor}{\ref{cor:A_n,k-gamma-nonnegative}}
        The $\gamma$-vector of $\AAA(A_{n,k})$ is nonnegative.
    \end{repcor}

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

    \begin{repcor}{\ref{cor:ss-size}}
        For all $n,k \geq 0$, we have
        %
        \[ |s^{-1}(\SSS_{n,k})| = k! \cdot C_n^{(k)}. \]
    \end{repcor}

    Finally, in Section \ref{subsec:real-rootedness}, we prove the following strengthening of Corollary \ref{cor:A_n,k-gamma-nonnegative}:

    \begin{repthm}{\ref{thm:A_2-real-rooted}}
        Let $H_n(t)$ be the $h$-polynomial of $\AAA(A_{n,2})$. Then, $H_n(t)$ is real-rooted.
    \end{repthm}

This paper is an extended abstract to~\cite{nguyen2023StackSorting}~and~\cite{nguyen2023Comparability}.

\section{Background}\label{sec:definition}

\subsection{Face numbers}\label{subsec:face_numbers}

    % A \textit{convex polytope} $P$ is the convex hull of a finite collection of points in $\RR^n$. The \textit{dimension} of a polytope is the dimension of its affine span. A face $F$ of a convex polytope $P$ is the set of points in $P$ where some linear functional achieves its maximum on $P$. Faces that consist of a single point are called \textit{vertices} and $1$-dimensional faces are called \textit{edges} of $P$. \andrew{You do not need to define the word polytope.} A $d$-dimensional polytope $P$ is \textit{simple} if any vertex of $P$ is incident to exactly $d$ edges. 

    For a $d$-dimensional polytope $P$, the sequence $(f_{0}(P),\ldots,f_{d}(P))$ is called the \emph{$f$-vector} of $P$, where $f_i(P)$ is the number of $i$-dimensional faces of $P$ and
    %
    \[ f_P(t) = \sum_{i=0}^{d} f_i(P) t^{i} \]
    %
    is called the \emph{$f$-polynomial} of $P$. When $P$ is \emph{simple}, recall that the $h$-polynomial and $\gamma$-polynomial are defined by 
    \[\begin{aligned} f_P(t) & = h_P(t+1),
    \\h_P(t) &= (1+t)^d \gamma\left(\frac {t}{(1+t)^2}\right). & 
    \end{aligned}
    \]


    
\subsection{Poset associahedra}\label{subsec:poset_ass}

    We recall the following definitions.

    \begin{definition}\label{def:poset_def}
        Let $(P,\preceq)$ be a finite poset and let $\sigma,\tau \subseteq P$. 

        \begin{itemize}
            \item $\tau$ is \emph{connected} if it is connected as an induced subgraph of the Hasse diagram of $P$.

            \item $\tau$ is \emph{convex} if whenever $x,z\in \tau$ and $y \in P$ such that $x\preceq y \preceq z$, then $y\in \tau$.

            \item $\tau$ is a \emph{tube} of $P$ if it is connected, convex, and $|\tau| > 1$. We say $\tau$ is a \emph{proper tube} if additionally $|\tau| < |P|$.

            \item $\tau$ and $\sigma$ are \emph{nested} if $\tau \subseteq \sigma$ or $\sigma \subseteq \tau$ and they are \emph{disjoint} if $\tau \cap \sigma = \emptyset$.

            \item We say $\sigma \prec \tau$ if $\sigma \cap \tau = \emptyset$ and there exists $x\in \sigma$ and $y\in \tau$ such that $x\preceq y$.

            \item A \emph{tubing} $T$ of $P$ is a set of proper tubes such that any pair of tubes in $T$ is either nested or disjoint and there is no subset $\{\tau_1,\tau_2,\ldots,\tau_k\}\subseteq T$ such that $\tau_1 \prec \tau_2 \prec \ldots \prec \tau_k \prec \tau_1$. %We will refer to the latter condition as the \textit{acyclic condition}.

            \item A tubing $T$ is \emph{maximal} if it is maximal under inclusion, i.e. $T$ is not a proper subset of any other tubing.
        \end{itemize}
    \end{definition}

    % Figure \ref{fig:tubingEx} shows examples and non-examples of tubings of posets. Note that the right-most example in Figure \ref{subfig:tubingNonEx} is a non-example since it violates the acyclic condition. In particular, if we label the tubes from right to left as $\tau_1,\tau_2,\tau_3$, then we have $\tau_1 \prec \tau_2 \prec \tau_3 \prec \tau_1$.

    % \begin{figure}[h!]
    %  \centering
    %     \begin{subfigure}[b]{0.45\textwidth}
    %         \centering
    %         \includegraphics[scale = 0.55]{tubingEx.pdf}
    %         \caption{Examples}
    %         \label{subfig:tubingEx}
    %     \end{subfigure}
    %  \quad
    %     \begin{subfigure}[b]{0.45\textwidth}
    %         \centering
    %         \includegraphics[scale = 0.55]{tubingNonEx.pdf}
    %         \caption{Non-examples}
    %         \label{subfig:tubingNonEx}
    %     \end{subfigure}

    %     \caption{Examples and non-examples of tubings of posets}
    %     \label{fig:tubingEx}
    % \end{figure}

    % \andrew{These graphics are so tiny you can't read the numbers.  We can either remove them entirely or we need to make them bigger.} \son{How do they look now?}

    \begin{definition}[{\cite[Theorem 1.2]{galashin2021poset}}]
        For a finite, connected poset $P$, there exists a simple, convex polytope $\AAA(P)$ of dimension $|P|-2$ whose face lattice is isomorphic to the set of tubings ordered by reverse inclusion. The faces of $\AAA(P)$ correspond to tubings of $P$, and the vertices of $\AAA(P)$ correspond to maximal tubings of $P$. This polytope is called the \emph{poset associahedron} of $P$.
    \end{definition}

    % \begin{figure}[h!]
    %  \centering
    %     \begin{subfigure}[c]{0.45\textwidth}
    %         \centering
    %         \includegraphics[scale = 0.3]{posetExPerm.pdf}
    %         \caption{Permutohedron}
    %         \label{subfig:posetExPerm}
    %     \end{subfigure}
    %  \quad
    %     \begin{subfigure}[c]{0.45\textwidth}
    %         \centering
    %         \includegraphics[scale = 0.3]{posetExAss.pdf}
    %         \caption{Associahedron}
    %         \label{subfig:posetExAss}
    %     \end{subfigure}

    %     \caption{Permutohedron and associahedron as poset associahedra}
    %     \label{fig:posetAssEx}
    % \end{figure}

    % Examples of poset associahedra can be seen in Figure \ref{fig:posetAssEx}. In particular, if $P$ is a claw, i.e. $P$ consists of a unique minimal element $0$ and $n$ pairwise-incomparable elements as shown in Figure \ref{subfig:posetExPerm}, $\AAA(P)$ is a permutohedron. If $P$ is a chain, $\AAA(P)$ is an associahedron.  \andrew{We can remove some of this background if we need the space.}
\section{Comparability invariance}\label{sec:comparability}

    The \emph{comparability graph} of a poset $P$ is the graph $\CCC(P)$ whose vertices are the elements of $P$ and where $i$ and $j$ are connected by an edge if $i$ and $j$ are comparable. A property of a poset is said to be \emph{comparability invariant} if it only depends on $\CCC(P)$.  In \cite{dreesen1985comparability}, Dreesen, Poguntke, and Winkler give a powerful characterization of comparability invariance which we recall in this section.
    

    \begin{definition}\label{def:substitution}
    Let $P$ and $S$ be posets and let $a \in P$. The \emph{substitution} of $a$ for $S$ is the poset $P(a \to S)$ on the set $(P-\{a\}) \sqcup S$ formed by replacing $a$ with $S$.
    
    More formally, $x \preceq_{P(a \to S)} y$ if and only if one of the following holds:
    \begin{itemize}
        \item $x, y \in P-\{a\}$ and $x \preceq_P y$;
        \item $x, y \in S$ and $x \preceq_S y$;
        \item $x \in S, y \in P-\{a\}$ and $a \preceq_P y$;
        \item $y \in S, x \in P-\{a\}$ and $y \preceq_P a$.
    \end{itemize}
    \end{definition}
    
    \begin{definition}\label{def:auto_subset}
    Let $P$ be a poset and let $S \subseteq P$.  $S$ is called \emph{autonomous} if there exists a poset $Q$ and $a \in Q$ such that $P = Q(a \to S)$.  
    
    Equivalently, $S$ is autonomous if  $\text{for all } x, y \in S$ and $z \in P-S, \text{ we have }$ $$(x \preceq z \Leftrightarrow y \preceq z) \text{ and } (z \preceq x \Leftrightarrow z \preceq y).$$ 
    \end{definition}

    \begin{definition}\label{def:flip}
    For a poset $S$, the \emph{dual poset} $S^{\text{op}}$ is defined on the same ground set where $x \preceq_S y$ if and only if $y \preceq_{S^{\text{op}}} x$. A \emph{flip} of $S$ in $P = Q(a \rightarrow S)$ is the replacement of $P$ by $Q(a \rightarrow S^{\text{op}})$.

    \begin{figure}[h!]
        \centering
        \begin{subfigure}[t]{0.45\textwidth}
        \centering
            \includegraphics[scale = 1]{AutonomousExample.pdf}
        \caption{An autonomous subset $S$ of a poset $P$.}
        \label{fig:AutonomousExample}
            
        \end{subfigure}~
        \begin{subfigure}[t]{0.45\textwidth}
            \centering
            \includegraphics[scale = 1]{ExtendedExampleFlippedPoset.pdf}
            \caption{A flip of $S$.}
            \label{fig:FlipExample}
        \end{subfigure}
        \caption{}
    \end{figure}
    \end{definition}
    
    See Figure \ref{fig:AutonomousExample} for an example of an autonomous subset and Figure \ref{fig:FlipExample} for an example of a flip. 

    \begin{lemma} [{\cite[Theorem 1]{dreesen1985comparability}}] \label{lem:dreesen_comparability}
    
    If $P \text{ and } P'$ are finite posets such that $\CCC(P) = \CCC(P')$ then $P \text{ and } P'$ are connected by a sequence of flips of autonomous subsets. 
        
    \end{lemma}

    Our main technical lemma is the following.

    \begin{lemma}\label{lem:flip_map}
        Let $P$ be a poset and let $S \subseteq P$ be autonomous, and let $P'$ be the poset obtained by flipping $S$ in $P$. Then $\AAA(P)$ and $\AAA(P')$ have the same $f$-vector.
    \end{lemma}

    Lemma \ref{lem:flip_map} immediately gives our first theorem.

    \begin{thm}\label{thm:comparability}
        The $f$-vector of $\AAA(P)$ is a comparability invariant.
    \end{thm}

    Theorem \ref{thm:comparability} may lead one to ask if $C(P) \simeq C(P')$, then are $\AAA(P)$ and $\AAA(P')$ necessarily combinatorially equivalent?  We answer this in the negative with the following example:

    \begin{figure}[h!]
    \centering
    \begin{tabular}{ccc}

        \includegraphics[height = 3cm]{122Poset.pdf} & \qquad\qquad &\includegraphics[height = 3cm]{122.pdf}
         \\

        $P$ & \qquad\qquad & $\AAA(P)$ \\\\


    

        \includegraphics[height = 3cm]{212Poset.pdf} & \qquad\qquad & \includegraphics[height = 3cm]{212.pdf} \\

                 $P'$ & \qquad\qquad & $\AAA(P')$ 
    \end{tabular}
    \caption{$\AAA(P)$ has an octagonal face, but $\AAA(P')$
        does not.}
    \label{fig:counterexample}
\end{figure}

    

    \subsection{Proof sketch of Lemma \ref{lem:flip_map}}\label{subsec:proof_sketch}
    
    Let $P = Q(a \to S)$ and $P' = Q(a \to S^{\op})$. By an abuse of notation, we let $\AAA(P)$ also refer to the set of tubings of $P$. Our goal is to build a bijection $\flipmap: \AAA(P) \to \AAA(P')$ such that for any tubing $T \in \AAA(P)$, we have $|T| = |\flipmap(T)|$. Let $T \in \AAA(P)$.  We will describe how to construct $T' := \flipmap(T)$.

    \begin{definition}
        A tube $\tau \in T$ is \emph{good} if $\tau \subseteq P - S$, $\tau \subseteq S$, or $S \subseteq \tau$ and is \emph{bad} otherwise.  We denote the set of good tubes by $\Tgood$ and the set of bad tubes by $\Tbad$.  
    \end{definition}

    The key idea of defining $\flipmap$ is to decompose $\Tbad$ into a triple $(\mathcal L, \mathcal M, \mathcal U)$ where $\mathcal L$ and $\mathcal U$ are nested sequences of sets, some of which may be marked, contained in $P-S$ and $M$ is an ordered set partition of $S$. We build the decomposition in such a way so that we can uniquely recover $\Tbad$ from $(\mathcal L, \mathcal M, \mathcal U)$. Then, we construct $T'$ by keeping $\Tgood$ and replacing $\Tbad$ by $\Tbad'$, which is obtained from $(\mathcal L, \overline{\mathcal M}, \mathcal U)$ where $\overline{\mathcal M}$ is the reverse of $\mathcal M$. We decompose $\Tbad$ as follows.

    \begin{definition}
        A tube $\tau \in \Tbad$ is called \emph{lower} (resp. \emph{upper}) if there exist $x \in \tau-S$ and $y \in \tau \cap S \text{ such that } x \preceq y$ (resp. $y \preceq x$). We denote the set of lower tubes by $\TL$ and the set of upper tubes by $\TU$.
    \end{definition}

    \begin{lemma}[Structure Lemma]
        $\Tbad$ is the disjoint union of $\TL$ and $\TU$.  
        Furthermore, $\TL \text{ and } \TU$ each form a nested sequence.
    \end{lemma}

    \begin{definition}[Tubing decomposition]  
    \label{def:tubing_decomp}
    
        Let $\TL = \{\tau_1, \tau_2, \ldots \}$ where $\tau_i \subset \tau_{i+1}$ for all $i$.  For convenience, we define $\tau_0 = \emptyset$. We define a nested sequence $\mathcal L = (L_1, L_2, \ldots)$ and a sequence of disjoint sets $\mathcal M_L = (M_{L}^1, M_{L}^2, \ldots)$ as follows. 
        \begin{itemize}
     
    
        \item For each $i \ge 1$, let $L_i = \tau_i - S$, and mark $L_i$ with a star if $(\tau_i - \tau_{i-1}) \cap S \neq \emptyset$.  
    
    \item If $L_{i}$ is the $j$-th starred set, let $M_{L}^j = (\tau_{i}-\tau_{i-1}) \cap S$.
    
    \end{itemize}
    We define the sequences $\mathcal U$ and $\mathcal M_U$ analogously.  
    We make the following definitions.
    \begin{itemize}
        
        \item Let $\hat M := S - \bigcup\limits_{\tau \in \Tbad} \tau.$
    
        \item For sequences $\mathbf{a} \text{ and } \mathbf{b}$, let the sequence $\mathbf{a} \append \mathbf{b}$ be $\mathbf{b}$ appended to $\mathbf{a}$, and let $\overline{\mathbf a}$ be the reverse of $\mathbf{a}$.
    
        \item We define $$\mathcal M :=  \begin{cases}
            \mathcal M_L \append \overline{\mathcal M}_U & \text{if } \hat M = \emptyset\\
    
            \mathcal M_L \append (\hat M) \append \overline{\mathcal M}_U & \text{if } \hat M \neq \emptyset %\text{\son{Are these two cases the same?}\andrew{Technically speaking no, as the sequence containing an empty set is not the same as the empty sequence.}}
            
        \end{cases}$$
        where $(\hat M)$ is the sequence containing $\hat M$.
    
    \item The \emph{decomposition} of $\Tbad$ is the triple $(\mathcal L, \mathcal M, \mathcal U)$.
    \end{itemize}
    
    \end{definition}

    Figure \ref{fig:decomposition} gives an example of a decomposition.

    \begin{figure}[h!]
        \centering
        \begin{subfigure}[t]{0.33\textwidth}
        \centering
        \includegraphics[scale = 1.2]{ExtendedExampleTubingTLandTULabelled.pdf}
        \caption{$T_L$ is blue and $T_U$ is red.    }
        \end{subfigure}~
        \begin{subfigure}[t]{0.66\textwidth}
        \centering
        \includegraphics[scale = 1.2]{Decomposition.pdf}
        \caption{$\mathcal L$ is blue, $\mathcal M$ is purple, and $\mathcal U$ is red.}
        \end{subfigure}
        \caption{The decomposition of $\Tbad$.}
        \label{fig:decomposition}
    \end{figure}

    % Finally, we reconstruct $\Tbad$ from the triple $(\mathcal L, \mathcal M, \mathcal U)$.

    \begin{lemma}[Reconstruction algorithm]\label{lem:reconstruct}
        $\Tbad$ can be reconstructed from its decomposition.
    \end{lemma}
    \begin{proof}
        Let $\mathcal M = (M_1, \dots, M_n)$. To reconstruct $\TL$, we set $\tau_1 = L_1 \cup M_{1}$ and take
        $$\tau_i =\begin{cases} \tau_{i-1} \cup L_i & \text{if $L_i$ is not starred}
        \\ \tau_{i-1} \cup L_i \cup M_{j} & \text{if $L_i$ is marked with the $j$-th star.} \end{cases}$$ 
        
        
        For $\TU$, we set $\tau_1 = U_1 \cup M_{n}$ and
        $$\tau_i =\begin{cases} \tau_{i-1} \cup U_i & \text{if $U_i$ is not starred}
        \\ \tau_{i-1} \cup U_i \cup M_{n-j+1} & \text{if $U_i$ is marked with the $j$-th star.} \end{cases}$$ 
    \end{proof}

    \begin{lemma}
    Applying the reconstruction algorithm to $(\mathcal L, \overline{\mathcal M}, \mathcal U)$  yields a proper tubing $\Tbad'$ of $P'$ with exactly $|\Tbad|$ tubes.
    \end{lemma}

    We define $T' := \Tbad' \sqcup \Tgood$ and take $\flipmap(T) := T'$.
    
    \begin{lemma}
    
    $T'$ is a proper tubing of $P'$. Furthermore, $\flipmapinverse(T') = T$ and $|\flipmap(T)| = |T|$. 
    \end{lemma}



    
\section{Broom posets}\label{sec:broom-posets}

    Recall that the \emph{ordinal sum} of two posets $(P,<_P)$ and $(Q,<_Q)$ is the poset $(R,<_R)$ whose elements are those in $P \cup Q$, and $a\leq_R b$ if and only if
    %
    \begin{itemize}
        \item $a,b\in P$ and $a\leq_P b$ or
        \item $a,b\in Q$ and $a\leq_Q b$ or
        \item $a\in P$ and $b\in Q$.
    \end{itemize}
    %
    We denote the ordinal sum of $P$ and $Q$ as $P~\oplus~Q$. Let $C_n$ be the chain poset of size $n$ and $A_k$ be the antichain of size $k$. In this section, we study the \emph{broom posets} $A_{n,k} = C_{n+1} \oplus A_k$. In particular, $A_{n,0}$ is the chain poset $C_{n+1}$, and $A_{0,k}$ is the claw poset $C_1 \oplus A_k$. Recall that $\AAA(A_{n,0})$ is the associahedron and $\AAA(A_{0,k})$ is the permutohedron. We show that the $h$-vectors of broom posets have a simple combinatorial interpretation in terms of descents of stack-sorting preimages.

    \subsection{Stack-sorting}\label{subsec:stack-sorting}

    In \cite{west1990permutations}, West defined a deterministic version of Knuth's stack-sorting algorithm, which we call the \emph{stack-sorting map} and denote by $s$. The stack-sorting map is defined as follows.

    \begin{definition}[Stack-sorting]\label{def:stack-sorting}
        Given a permutation $\pi \in \SSS_n$, $s(\pi)$ is obtained through the following procedure. Iterate through the entries of $\pi$. In each iteration,
        %
        \begin{itemize}
            \item if the stack is empty or the next entry is smaller than the entry at the top of the stack, push the next entry to the top of the stack;
            \item otherwise, pop the entry at the top of the stack to the end of the output permutation.
        \end{itemize}
        %       
    \end{definition}

    Figure \ref{fig:ss-ex} illustrates the stack-sorting process on $\pi = 3142$.

    \begin{figure}[h!]
        \centering
        \includegraphics[scale=0.5]{ss-ex.pdf}
        \caption{Example of $s(3142)$}
        \label{fig:ss-ex}
    \end{figure}

    \subsection{Catalan convolution}\label{subsec:catalan-convolution}

    Recall that the \emph{Catalan numbers} $C_n = \frac{1}{n+1}\binom{2n}{n}$ have generating function $\mathcal C(t) = \frac{1-\sqrt{1-4t}}{2t}$. The \emph{$k$-th Catalan convolution} is the sequence with generating function $\mathcal C(t)^k$.  For convenience, we denote $[t^n]\mathcal C(t)^k$ by $C_n^{(k)}$.


    % The \textit{Catalan numbers}, $C_n = \frac{1}{n+1}\binom{2n}{n}$, are one of the most well-known sequences in combinatorics. Among hundreds of objects counted by the Catalan numbers, one well-known objects is \textit{Dyck paths}. Recall that a Dyck path of length $2n$ is a path from $(0,0)$ to $(n,n)$ with steps $(1,0)$ (up steps) and $(0,1)$ (right steps) that never goes below the diagonal line. The Catalan convolution is defined as follows.



    The explicit formula for $C_n^{(k)}$ is
    %
    \[ C_n^{(k)} = \dfrac{k+1}{n+k+1}\binom{2n+k}{n}. \]
    %
    % The Catalan convolution has the following combinatorial interpretation: $C_n^{(k)}$ counts the number of Dyck paths of length $2(n+k)$ that start with at least $k$ up steps. For example, $C^{(0)}_n$ is the Catalan number $C_n$. \andrew{Do we ever use this fact again in the extended abstract?} \son{No, except probably why $C^{(0)}_n = C_n$. It's a nice combinatorial interpretation tho}
    
\subsection{$h$-vector}\label{subsec:h-vector}

    Recall that we defined $\SSS_{n,k} = \{w~|~w\in \SSS_{n+k}, w_i = i~\text{for all}~i>k\}$. In this section, our main theorem is:

    \begin{thm}\label{thm:A_n,k-h-vector}
        Let $h = (h_0, h_1, \ldots, h_{n+k-1})$ be the $h$-vector of $\AAA(A_{n,k})$. Then $h_i$ counts the number of permutations in $s^{-1}(\SSS_{n,k})$ with exactly $i$ descents.
    \end{thm}

    As a corollary, we obtain the following result.

    % By the structure of the maximal tubings of $A_{n,k}$, Theorem \ref{thm:A_n,k-h-vector} immediately gives the following result. \andrew{Why is this immediate? } \son{A maximal tubings of $A_{n,k}$ is like a chain, then joined with some maximal element, then another chain and so on, each chain is $C_i$, so with the previous definition it is quite "clear". We can definitely remove the "immediate" part.}

    \begin{cor}\label{cor:ss-size}
        For all $n,k \geq 0$, we have
        %
        \[ |s^{-1}(\SSS_{n,k})| = k! \cdot C_n^{(k)}. \]
    \end{cor}

    % In particular, when $n = 0$, $\AAA(A_{0,k})$ is the permutohedron of $\SSS_k$. Also, $s^{-1}(\SSS_{0,k}) = s^{-1}(\SSS_k) = \SSS_k$. Theorem \ref{thm:A_n,k-h-vector} tells us that the $h$-vector of $\AAA(A_{0,k})$ - the permutohedron of $\SSS_k$ - counts descents in $\SSS_k$, which is a well-known result for permutohedra. Furthermore, Corollary \ref{cor:ss-size} says that $|s^{-1}(\SSS_{0,k})| = |\SSS_k| = k!$.

    % On the other hand, when $k = 0$, $\AAA(A_{n,0})$ is the associahedron $K_{n+1}$. Also, $s^{-1}(\SSS_{n,0}) = s^{-1}(12\ldots n)$, which is the set of stack-sortable permutations in $\SSS_n$. Hence, Theorem \ref{thm:A_n,k-h-vector} yields the well-known result that the $h$-vector of $K_{n+1}$ counts descents of stack-sortable permutations in $\SSS_n$. In addition, Corollary \ref{cor:ss-size} gives $|s^{-1}(12\ldots n)| = C_n$, which is the classical result that Catalan number counts stack-sortable permutations.

    Recall also the following result by Br\"and\'en.

    \begin{thm}[\cite{branden2008actions}]\label{thm:ss-preimage-gamma}
        For $A \subseteq \SSS_n$, we have
        %
        \[ \sum_{\sigma \in s^{-1}(A)} t^{\des(\sigma)} = \sum_{m = 0}^{\lfloor \frac{n-1}{2}\rfloor} \dfrac{|\{ \sigma \in s^{-1}(A)~:~\peak(\sigma) = m \}|}{2^{n-1-2m}} t^m(1+t)^{n-1-2m}, \]
        %
        where $\peak(\sigma)$ is the number of index $i$ such that $\sigma_{i-1} < \sigma_i > \sigma_{i+1}$.
    \end{thm}

    This gives the following corollary.

    \begin{cor}\label{cor:A_n,k-gamma-nonnegative}
        The $\gamma$-vector of $\AAA(A_{n,k})$ is nonnegative.
    \end{cor}

    \begin{remark}
        Corollary \ref{cor:A_n,k-gamma-nonnegative} also follows from the fact that $\AAA(A_{n,k})$ is isomorphic to the graph associahedra of lollipop graphs, which are chordal. It was shown in \cite{postnikov2008faces} that graph associahedra of chordal graphs are $\gamma$-nonnegative.
    \end{remark}

\subsection{Real-rootedness}\label{subsec:real-rootedness}

    In this section, we will sketch the proof of real-rootedness of the $h$-polynomial of $\AAA(A_{n,2})$. We say a polynomial $a_0 + a_1t + \ldots + a_nt^n$ is real-rooted if all of its zeros are real. We say a sequence $(a_0,a_1,\ldots,a_n)$ is real-rooted if the polynomial $a_0 + a_1t + \ldots + a_nt^n$ is real-rooted.

    Let $f$ and $g$ be real-rooted polynomials with positive leading coefficients and real roots $\{f_i\}$ and $\{g_i\}$, respectively. We say that $f$ \emph{interlaces} $g$ if
    %
    \[ g_1 \leq f_1 \leq g_2 \leq f_2 \leq \ldots \leq f_{d-1} \leq g_d \]
    %
    where $d = \deg g = \deg f + 1$. We say that $f$ \emph{alternates left of} $g$ if
    %
    \[ f_1 \leq g_1 \leq f_2 \leq g_2 \leq \ldots \leq f_d \leq g_d \]
    %
    where $d = \deg g = \deg f$. Finally, we say $f$ \emph{interleaves} $g$, denoted $f \ll g$, if $f$ either interlaces or alternates left of $g$.

     Recall that the Narayana polynomial $N_n(t)$ is defined by
    %
    \[ N_n(t) = \sum_{i = 0}^{n-1} a_it^i \]
    %
    where $a_i$ counts the number of permutations in $s^{-1}(1\ldots n)$ with exactly $i$ descents. In other words, $N_n(t)$ is the $h$-polynomial of $\AAA(A_{n,0})$ and $\AAA(A_{n-1,1})$. We have the following result.

    \begin{thm}[\cite{branden2006linear}]\label{thm:N_m-real-rooted}
        For all $n$, $N_n(t)$ is real-rooted. Furthermore, $N_{n-1}(t) \ll N_n(t)$.
    \end{thm}
       
    To prove real-rootedness of the $h$-polynomial of $\AAA(A_{n,2})$, we will need the following ``happy coincidence''.

    \begin{prop}\label{prop:happy-coincidence}
        The number of permutations in $s^{-1}(2134\ldots n)$ with exactly $i$ descents is the same as the number of permutations $w$ in $s^{-1}(1\ldots n)$ with exactly $i$ descents such that $w_1, w_n < n$.
    \end{prop}

    Proposition \ref{prop:happy-coincidence} leads to the following important recurrence.

    \begin{prop}\label{prop:A_2-recurrence}
        Let $H_{n}(t)$ be the $h$-polynomial of $\AAA(A_{n,2})$, and recall that $N_{n+2}(t)$ and $N_{n+1}(t)$ are the $h$-polynomials of $\AAA(A_{n+2,0})$ and $\AAA(A_{n+1,0})$, respectively. We have
        %
        \[ H_{n}(t) = 2N_{n+2}(t) - (1+t)N_{n+1}(t). \]
    \end{prop}

    This recurrence and Theorem~\ref{thm:N_m-real-rooted} allows us to prove the following theorem.

    \begin{thm}\label{thm:A_2-real-rooted}
        Let $H_n(t)$ be the $h$-polynomial of $\AAA(A_{n,2})$. Then, $H_n(t)$ is real-rooted.
    \end{thm}

% \section{An $h$-polynomial recurrence}

\section{Open Questions}

% \begin{question}
%     In \cite{stanley1986two}, Stanley defines the \emph{order polytope} and the \emph{chain polytope}, with the latter defined purely in terms of the comparability graph.  He constructs a piecewise linear volume preserving map between the two polytopes which sends vertices to vertices.

%     In particular, this shows that the number of vertices of the order polytope is a comparability invariant.  Can a similar geometric map be defined on the realization of poset associahedra in \cite{sack2023realization}?

% \end{question}

\begin{question}
    Can we define  $f_{\mathscr A(P)}(z)$ purely in terms of $C(P)$?  It would also be interesting to answer this question even for $f_0$.
\end{question}

\begin{question}
    It remains open to find an interpretation of the $h$-vector of $\AAA(P)$ in terms of the combinatorics of $P$.  Can $h(z)$ be defined purely in terms of $C(P)$?
\end{question}

\begin{question}
    The map $\flipmap$ can be analogously defined for \emph{affine poset cyclohedra}~\cite{galashin2021poset}, where an autonomous subset $S$ has at most one representative from each residue class.  Again, it preserves the $f$-vector of the affine poset cyclohedron.
    Does Lemma \ref{lem:dreesen_comparability} (and hence Theorem~\ref{thm:comparability}) hold for affine posets?
\end{question}

    % It turns out that the recurrence in Proposition \ref{prop:A_2-recurrence} can be generalized to any poset. 
    
    We have the following conjectured generalization of Proposition \ref{prop:A_2-recurrence}.

    \begin{conjecture}\label{conj:recurrence}
        Let $P$ be a poset with an autonomous subposet $S$ that is a chain of size $2$, i.e. $S = C_2$. Let $P_1$ be the poset obtained from $P$ by replacing $S$ by a singleton. Let $P_2$ be the poset obtained from $P$ by replacing $S$ by an antichain of size $2$, i.e. $A_2$. Let $h_{P}(t)$, $h_{P_1}(t)$, $h_{P_2}(t)$ be the $h$-polynomials of $\AAA(P)$, $\AAA(P_1)$, $\AAA(P_2)$, respectively. Then,
        %
        \[ 2h_{P}(t) = h_{P_2}(t) + (1+t)h_{P_1}(t). \]
        %
        As a result, let $\gamma_{P}(t)$, $\gamma_{P_1}(t)$, $\gamma_{P_2}(t)$ be the $\gamma$-polynomials of $\AAA(P)$, $\AAA(P_1)$, $\AAA(P_2)$, respectively. Then,
        %
        \[ 2\gamma_{P}(t) = \gamma_{P_2}(t) + \gamma_{P_1}(t). \]
    \end{conjecture}

    Conjecture \ref{conj:recurrence} is useful in proving real-rootedness of the $h$-polynomials, as shown in Theorem \ref{thm:A_2-real-rooted}. Furthermore, the resulting recurrence of the $\gamma$-polynomial would also be useful in proving $\gamma$-positivity. More generally, we have the following recurrence when $S$ is an antichain of size $n$.

    \begin{conjecture}\label{conj:recurrence3}
        Let $P$ be a poset with an autonomous subposet $S$ that is a chain of size $n$, i.e. $S = C_n$. For $1\leq i \leq n$, let $P_i$ be the poset obtained from $P$ by replacing $S$ by an antichain of size $i$, i.e. $A_i$. Let $h_{P}(t)$, $h_{P_1}(t)$, $\ldots$, $h_{P_n}(t)$ be the $h$-polynomials of $\AAA(P)$, $\AAA(P_1)$, $\ldots$, $\AAA(P_n)$, respectively. Then,
        %
        \begin{equation}\label{eqn:recurrence}
            h_P(t) = \dfrac{1}{n!}\sum_{w\in\SSS_n}B_1(t)^{c_1(w)}\ldots B_n(t)^{c_n(w)}h_{P_{\ell(\lambda(w))}}(t)
        \end{equation}
        %
        where
        %
        \[ B_k(t) = \sum_{i = 0}^{k-1}\binom{k-1}{i}^2t^i \]
        %
        are type B Narayana polynomials, $c_i(w)$ is the number of cycles of size $i$ in $w$, and $\ell(\lambda(w))$ is the length of the cycle type $\lambda(w)$ of $w$.
    \end{conjecture}

    The type B Narayana polynomials above also show up as the rank-generating function of the type B analogue $\text{NC}^B_n$ of the lattice of non-crossing partitions (see \cite{reiner1997non}) and the $h$-polynomials of type B associahedra (see \cite{simion2003type}). 

    % Equation \ref{eqn:recurrence} can also be written as
    % %
    % \[ h_P(t) = \dfrac{1}{n!}\sum_{w\in\SSS_n}B_1(t)^{c_1(w)}\ldots B_n(t)^{c_n(w)}h_{P_{\ell(\lambda(w))}}(t) \]
    % %
    % where $c_i(w)$ is the number of cycles of size $i$ in $w$, and $\ell(\lambda(w))$ is the length of the cycle type $\lambda(w)$ of $w$. 
    
    Equation \ref{eqn:recurrence} bears resemblance to the Frobenius characteristic map. Thus, it is a natural question to ask if there is a representation theory story behind this equation. This is an interesting question for future research.

\acknowledgements{The authors are grateful to Vic Reiner and Pavel Galashin for their guidance. We also thank Colin Defant for helpful discussions about stack-sorting.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
