%% 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]{FPSAC2021}
\articlenumber{60}
%% 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}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{definition}[thm]{Definition}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{example}[thm]{Example}
\newtheorem{corollary}[thm]{Corollary}
%\newtheorem{def}{Definition}

%\usepackage{lipsum}
\usepackage{mathtools}
\usepackage{amsmath,amssymb,amsthm,amsfonts,mathrsfs}
\usepackage{graphpap,enumitem,color}

%\newtheorem{definition}[theorem]{Definition}


%\renewcommand{\familydefault}{ppl}
%\linespread{1.2}

%\usepackage[margin=1in]{geometry}

\newcommand{\cL}{\mathscr{L}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cZ}{\mathcal{Z}}
\newcommand{\cR}{\mathcal{R}}

\newcommand{\inv}[0]{\text{inv}}
\newcommand{\Des}[0]{\text{Des}}


\newcommand{\co}{\colon}

\DeclareMathOperator{\op}{op}

%% define your title in the usual way
\title[Counting linear extensions]{Counting linear extensions of posets with determinants of hook lengths}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Alexander Garver\thanks{\href{mailto:alexander.garver@gmail.com}{alexander.garver@gmail.com}. Alexander Garver was partially supported by NSERC grant RGPIN/05999-2014 and the Canada Research Chairs program.}\addressmark{1}, Stefan Grosser\thanks{\href{mailto:stefan.grosser@mail.mcgill.ca}{stefan.grosser@mail.mcgill.ca}.}\addressmark{2}, Jacob P. Matherne\thanks{\href{mailto:matherne@uoregon.edu}{matherne@uoregon.edu}. Jacob P. Matherne was partially supported by NSF Grant DMS-1638352, the Association of Members of the Institute for Advanced Study, the Max Planck Institute for Mathematics in Bonn, and the Hausdorff Research Institute for Mathematics in Bonn.}\addressmark{3}, \and Alejandro H. Morales\thanks{\href{mailto:ahmorales@math.umass.edu}{ahmorales@math.umass.edu}. Alejandro Morales was partially supported by NSF Grant DMS-1855536.}\addressmark{4}}

%\author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics, Carleton College, Northfield, MN USA \\ \addressmark{2}Department of Mathematics and Statistics, McGill University, Montr\'eal, QC Canada\\
\addressmark{3}Department of Mathematics, University of Oregon, Eugene, OR USA, and Hausdorff Research Institute for Mathematics, Bonn, Germany\\
\addressmark{4}Department of Mathematics and Statistics, University of Massachusetts, Amherst, MA USA}

%\address{\addressmark{1}Department of This, University of That, There \\ \addressmark{2}School of Something, University of Something Else, Somewhere}

%% put the date of submission here
\received{November 30, 2020}

%% 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{We introduce a class of posets, called mobile posets, which includes both ribbon posets and $d$-complete posets, whose number of linear extensions is given by a determinant of a matrix where entries are products of hook lengths. We also give $q$-analogs of this determinantal formula in terms of the inversion statistic. }

%% put your French abstract here, or comment this out if you don't have one
\resume{Nous introduisons une classe d'ensembles partiellement ordonn\'es, appel\'es ensembles mobiles partiellement ordonn\'es, qui comprend \`a la fois des ensembles partiellement ordonn\'es en ruban et des ensembles partiellement ordonn\'es complets d, dont le nombre d'extensions lin\'eaires est donn\'e par un d\'eterminant d'une matrice o\`u les entr\'ees sont des produits de longueurs de crochet.   Nous donnons \'egalement des q-analogues de cette formule d\'eterminante en termes de statistique d'inversion.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{{poset, linear extension, $d$-complete poset}}

%% 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, ie. [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{60Garver.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}

Linear extensions of posets are fundamental objects in combinatorics and computer science. The number of linear extensions  of a poset $\cP$, denoted by $e(\cP)$, is a measure of the complexity of the poset. However, computing $e(\cP)$ is a difficult problem---it is $\#P$-complete \cite{bw91}, even for posets with restricted height or dimension \cite{dp18}. Fortunately, for some posets that appear in algebraic and enumerative combinatorics, their number of linear extensions can be efficiently computed through product formulas (posets arising from Young diagrams \cite{frame1954hook}, rooted tree posets \cite{knuth_1998}, $d$-complete posets \cite{ProHLF}),
determinants (posets arising from skew Young diagrams \cite{aitken1943xxvi}), or recursive algorithms (%series parallel posets \cite{mohring1989computationally}, 
tree posets \cite{atk}). 


The main result of this paper is to give a determinantal formula for the number of linear extensions of {\em mobile posets}, a class of posets which includes both ribbons and $d$-complete posets. A mobile poset\footnote{The name ``mobile'' was chosen for the poset's resemblance to mobiles for babies and to the kinetic sculptures of Alexander Calder.} $\cP$ is a poset obtained from a ribbon poset $\cZ$ by allowing every element $z$ in $\cZ$ to cover the maximal element of a nonnegative number of disjoint $d$-complete posets, and by letting at most one element $z'$ of $\cZ$ be covered by a certain element of a $d$-complete poset (see Figure~\ref{fig:mobile tree poset}: Left). If the $d$-complete posets in this description are restricted to rooted tree posets, then the posets in the resulting family are called {\em mobile tree posets} (see Figure~\ref{fig:mobile tree poset}: Right). 

%\textcolor{blue}{Some things to add:  why are linear extensions cool (along with many references), the hook length formula for rooted trees, how counting linear extensions is provably hard even in simple cases, a quick outline of the sections of the paper and short synopsis of how we develop our formula in Theorem 3 via folding.}

In Section~\ref{section:prelim}, we review basic poset definitions including MacMahon's enumeration of the linear extensions of a ribbon poset. Section~\ref{sec_folding} presents the technique of folding posets which allows one to use inclusion-exclusion to enumerate linear extensions. Section~\ref{sec_d_comp_posets} reviews the basics of $d$-complete posets and their hook length formulas. In Section~\ref{sec_component_tree}, we introduce the component tree of a poset, which allows us to state our main theorem for mobile posets (Theorem~\ref{thm:gmobiledetdone}) in Section~\ref{section:mobile}. Lastly, we present a $q$-analog of our main theorem (Theorem~\ref{thm:qmobiledetdone}) for the case of mobile tree posets, using inversions. In the full version of our paper \cite{garver2020counting}, we present an additional $q$-analog, which uses major index.

\begin{figure}
\begin{center}
     \includegraphics[scale=0.8]{mobile_dcomplete2.pdf}
     \qquad
     \includegraphics[scale=0.8]{mobile_precise.pdf}
\end{center}
\caption{Left: schematic of a mobile poset. Right: schematic of a mobile tree poset. The shaded rhombi depict $d$-complete posets, and the shaded triangles depict rooted tree posets.}
\label{fig:mobile tree poset}
\end{figure}

\section{Preliminaries}
\label{section:prelim}

A {\em partially-ordered set} (poset) is a pair $(\cP, \le_\cP)$, with $\cP$ a finite set and $\le_\cP$ a binary relation on $\cP$ that is reflexive, antisymmetric, and transitive. We denote a poset by its underlying set when the order relation is clear from context. Throughout, we view $\le_\cP$ as both a subset of $\cP^2$ and as a way to compare two elements of $\cP$, depending on context.  (Thus, writing $(x,y) \in\ \le_{\cP}$ is equivalent to writing $x \le_{\cP} y$.)  We denote the set of cover relations of $\cP$ by $\lessdot_\cP$. An {\em (induced) subposet} $\cQ$ of $\cP$ is a poset whose underlying set is a subset of the elements of $\cP$, and whose relations are given by $s \leq_{\cQ} t$ if and only if $s \leq_{\cP} t$.  Given two elements $x,y \in \cP$, the {\em interval} $[x,y]$ is the subposet $\{z \in \cP \mid x\leq_{\cP} z \leq_{\cP} y\}$.

If $\cP$ and $\cQ$ are two posets,
we define their {\em disjoint sum} $\cP + \cQ$ as the poset with underlying set the disjoint union $\cP \sqcup \cQ$ and with relations the disjoint union $\le_\cP \sqcup \le_\cQ$.  If $E \subset \cP$, we denote by $\cP \setminus E$ the poset with underlying set $\cP \setminus E$ and with relations $\le_{\cP \setminus E}\ :=\ \le_\cP \setminus\ \{(x,y) \in\ \le_\cP\ \mid x \in E \text{ or } y \in E\}$. %\textcolor{red}{CUT Note that $\cP \setminus E$ is not the subposet of $\cP$ on $\cP \setminus E$. For instance, given the chain $\cP = \{1,2,3\}$ with the natural order and $E = \{2\}$, the poset $\cP \setminus E$ is an antichain whereas the subposet of $\cP$ on $\cP \setminus E$ is a chain with two elements.}
Given a poset $\cP$ with two incomparable elements $x$ and $y$, let $\cP \oplus \{(x,y)\}$ be the poset obtained by adding the cover relation $(x,y)$ and taking the transitive closure. 

\begin{definition}\label{def:slantsum} 
Let $\cP,\cQ_1,\dots,\cQ_m$ be disjoint posets, let $p$ be an element in $\cP$, and let $q_i$ be an element in $\cQ_i$ for $i=1,\dots,m$. The {\em slant sum} of $\cP,\cQ_1,\dots,\cQ_m$ at $p$ and $q_1,\dots,q_m$ is the poset \[\cP \underset{i=1,\ldots,m}{\prescript{p}{}{\big{\backslash}_{q_i}}} \cQ_i := \left(\cP + \cQ_1 +\cdots + \cQ_m\right) \oplus \{(q_1,p),\dots,(q_m,p)\}.\] 
The slant sum operation above is associative with fixed $p$, so this construction does not depend on the order in which we add the posets $\cQ_i$ to $\cP$.
\end{definition}



We now introduce the main object of study in this paper: linear extensions of posets.

\begin{definition}
A {\em linear extension} of an $n$-element poset $\cP$ is a bijection $f\co \cP \to [n]$ that is order-preserving; that is, if $x \le_\cP y$, then $f(x) \le f(y)$.  We denote by $\cL(\cP)$ the set of all linear extensions of $\cP$ and by $e(\cP):=\#\cL(\cP)$ the number of linear extensions of $\cP$.% \textcolor{red}{and by $\overline{e}(\cP):= e(\cP)/n!$ the probability that a permutation of the elements of $\cP$ is a linear extension of $\cP$.}
\end{definition}

An important class of posets to which our theory applies is the class of ribbon posets. Let $S = \{s_1, \ldots, s_k\} \subset [n-1]$ with $s_1 < \cdots < s_k$. A \textit{ribbon} poset $\cZ$ with descent set $S$ is the poset with underlying set $\{z_1,\ldots, z_n\}$ whose cover relations are $z_{i+1} \lessdot z_i$ if $i \in S$ and $z_i \lessdot z_{i+1}$ if $i \not \in S$. The following classical theorem gives a determinant formula for the linear extensions of ribbon posets.

\begin{thm}[{MacMahon \cite[vol. I, p.190]{CA}}]\label{prop:ribbon}
The number of linear extensions of a ribbon poset $\cZ$ with $n$ elements and descent set $S \subset [n-1]$ is given by
\begin{equation}\label{eq:Detribbon}
e(\cZ) = n!\cdot \det\left( \frac{1}{(s_{j+1}-s_i)!} \right)_{0\leq i,j\leq k},
\end{equation}
where $s_0=0$ and $s_{k+1} = n$.
\end{thm}

\section{Folding and an alternating formula for linear extensions}\label{sec_folding}

We begin with a simple inclusion-exclusion formula for $e(\cP)$.

\begin{definition}
Let $\cP$ be a poset, $F \subset \lessdot_\cP$, and $F^{\op} := \{(y,x) \in \cP^2 \mid (x,y) \in F\}$. We write $\cP \ominus F$ for the poset with the same underlying set as $\cP$, but with cover relations $\lessdot_{\cP\setminus F}\ :=\ \lessdot_\cP\!\! \setminus F$.  We call a {\em fold} of $\cP$ at $F$ the poset
\[
\cP_F := (\cP \ominus F) \oplus F^{\op}
\]
obtained by deleting the cover relations in $F$, adding the opposite cover relations, and taking the transitive closure. If $S\subset F$, then we call a {\em partial fold} of $\cP$ at $S$ the poset
\[
\cP_{S,F} := (\cP \ominus F) \oplus S^{\op}.
\]
\end{definition}


\begin{example}\label{ex:poset2folds_new}
Consider the seven element poset $\mathcal{P}$ in the left of Figure~\ref{fig:ex-fold-posets}.
Let $F=\{(c,e),(d,g)\}$, $S_1 = \{(c,e)\}$, and $S_2=\{(d,g)\}$. The posets  $\cP_{\varnothing,F}$, $\cP_{S_1,F}$, $\cP_{S_2,F}$, and $\cP_{F}$ are also depicted in Figure~\ref{fig:ex-fold-posets}.
%\renewcommand{\qedsymbol}{\rule{0.65em}{0.65em}}\hfill\qedsymbol
\end{example}

\begin{figure}
    \centering
    \includegraphics[scale=0.8]{ex_poset_folds.pdf}
    \caption{Examples of a fold of $\cP$ and partial folds where $F=\{(c,e),(d,g)\}$, $S_1= \{(c,e)\}$, and $S_2=\{(d,g)\}$.} 
    \label{fig:ex-fold-posets}
\end{figure}

The next lemma describes how the number of linear extensions of a poset changes when folding at a single cover relation.

\begin{lem}\label{lemma:inclusionexclusion}
Let $\cP$ be a poset and $(x,y)$ be in $\lessdot_{\cP}$. Then
\begin{equation} \label{linext IE decomposition}
\cL(\cP) = \cL(\cP \ominus \{(x,y)\}) \,\setminus\, \cL(\cP_{\{(x,y)\}}).
\end{equation} In particular, we have that
\[
e(\cP) = e(\cP \ominus \{(x,y)\}) - e(\cP_{\{(x,y)\}}).
\]
\end{lem}

\begin{example} \label{ex:poset1fold}
Consider the seven element poset $\mathcal{P}$ in Figure~\ref{fig:ex-ie-posets}: Left.  Choosing either the cover relation $(c,e)$ or $(a,c)$, we obtain
\begin{subequations}
\begin{align}
    77= e(\cP) &=  e(\cP \ominus \{(c,e)\}) - e(\cP_{\{(c,e)\}}) = 105-28, \label{eq:foldbridge}\\
    &= e(\cP \ominus \{(a,c)\}) - e(\cP_{\{(a,c)\}}) = 117-40. \label{eq:foldnonbridge}
\end{align}
\end{subequations}
See the right image in Figure~\ref{fig:ex-ie-posets} for an illustration of these inclusion-exclusion formulas. As a further illustration of~\eqref{eq:foldbridge}, consider the following linear extension $\eta \in \cL(\cP)$: \[a \mapsto 1,\quad b \mapsto 2,\quad c \mapsto 3,\quad d \mapsto 4,\quad e \mapsto 5,\quad f \mapsto 6,\quad g \mapsto 7.\] Notice that $\eta \in \cL(\cP \ominus \{(c,e)\})$ and $\eta \not \in \cL(\cP_ {\{(c,e)\}})$, since $\eta(c) < \eta(e)$. 
%\renewcommand{\qedsymbol}{\rule{0.65em}{0.65em}}\hfill\qedsymbol
\begin{figure}
\begin{center}
    \raisebox{10mm}{\raisebox{3mm}{$\cP =$} \includegraphics[scale=0.8]{ex_poset_originalIE.pdf}} \qquad \qquad 
   \includegraphics[scale=0.8]{IE_poset_ex12.pdf}
\end{center}
\caption{Example of using the inclusion-exclusion formula from Lemma~\ref{lemma:inclusionexclusion} to calculate $e(\cP)$.}
\label{fig:ex-ie-posets}
\end{figure}
\end{example}


The next result follows from repeatedly applying Lemma~\ref{lemma:inclusionexclusion}.

\begin{corollary}\label{corollary:alternating}
Let $\cP$ be a poset, and let $F \subset \lessdot_\cP$.  Then
\begin{equation} \label{equation:alt}
e(\cP) = \sum_{S\subset F}(-1)^{\#S} e(\cP_{S,F}).
\end{equation}
\end{corollary}

\begin{example}\label{ex:poset2folds}
 For the poset $\cP$ from Example~\ref{ex:poset1fold}, Corollary~\ref{corollary:alternating} yields the formula shown in Figure~\ref{fig:example-inclusion-exclusion-2folds}
 %\begin{equation} \label{eq:example-inclusion-exclusion-2folds}
 %     \raisebox{-20pt}{\includegraphics[scale=0.6]{poset_2folds_IE.pdf}}  
%\end{equation}
 when $F=\{(c,e),(d,g)\}$ is the set of cover relations depicted in red on the left-hand side of the above equation.%\renewcommand{\qedsymbol}{\rule{0.65em}{0.65em}}\hfill\qedsymbol
\end{example}

\begin{figure}
    \centering
 \begin{equation*} \label{eq:example-inclusion-exclusion-2folds} 
      \raisebox{-20pt}{\includegraphics[scale=0.8]{poset_2folds_IE.pdf}}  
\end{equation*}
    \caption{{An example of the linear extension formula from~\eqref{equation:alt}.}}
    \label{fig:example-inclusion-exclusion-2folds}
\end{figure}


\section{$d$-complete posets}\label{sec_d_comp_posets}

%\textcolor{red}{NEW SECTION?}

The class of $d$-complete posets is  an important family of posets whose linear extensions we will enumerate. Defined by Proctor in \cite{p99}, $d$-complete posets form a large class of posets containing rooted tree posets and posets arising from Young diagrams,\footnote{See \cite[Table 1]{ProClass} for a complete classification of $d$-complete posets.} while still retaining a hook-length formula for their number of linear extensions.  We recall their definition below (see Definition~\ref{def:dcomp}).




A poset $\cP$ has a {\em diamond} if there are four elements $w,x,y,z$ in $\cP$ such that $z$ covers $x$ and $y$, while $x$ and $y$ cover $w$. For $k \geq 3$, a {\em double-tailed diamond poset} $d_k$ is a poset obtained by adding a $k-3$ chain to the top and bottom of a diamond $(w,x,y,z)$. The {\em neck} elements are the $k-2$ elements above the two incomparable elements $x$ and $y$. A {\em $d_k$-interval} is an interval $[u,v]$ which is isomorphic to $d_k$.  


A subset $S$ of $\cP$ is {\em convex} if for any $x,y \in S$ and any $z \in \cP$ satisfying $x \le z \le y$, one has that $z \in S$. For $k\geq 3$, a {\em $d_k^-$-convex set} is a convex set of $\cP$ that is isomorphic to a $d_k$-interval with the maximal element removed. Note that for $k\geq 4$, a $d_k^-$-convex set is an interval.


\begin{definition}[\cites{p99}]\label{def:dcomp}
A poset $\cP$ is \emph{$d$-complete} if, for any $k\geq 3$, the following properties are satisfied:

\begin{enumerate}
    \item If $I$ is a $d_k^-$-convex set, then there exists an element $p$ in $\cP$ that covers the maximal elements of $I$.
    \item  If $[w, z]$ is a $d_k$-interval, then $z$ does not cover any elements of $\cP$ outside $[w,z]$.
    \item There are no $d_k^-$-convex sets which differ only in their minimal elements.
\end{enumerate}
\end{definition}

A connected $d$-complete poset has a unique maximal element \cite[Section 14]{ProClass}.  Given a connected $d$-complete poset $\cP$, its {\em top tree} $\Gamma$ is the (induced) subgraph of the Hasse diagram of $\cP$ consisting of vertices $x$ in $\cP$ such that $y \geq_{\cP} x$ is covered by at most one other element. (This subgraph is indeed a tree.) An element $y$ of $\cP$ is {\em acyclic} if $y \in \Gamma$ and is not part of the neck of any $d_k$-interval of $\cP$. Note that if $\cP$ is a rooted tree, then $\Gamma = \cP$ and all its elements are acyclic.

Slant sums (see Definition~\ref{def:slantsum}) can be used to combine two $d$-complete posets to obtain a larger $d$-complete poset.

\begin{proposition}[{Proctor \cite[Proposition B]{ProClass}}] \label{prop: slant sum tree d complete}
Let $\cP_1$ be a connected $d$-complete poset with an acyclic element $y$, and  let $\cP_2$ be a connected $d$-complete poset with maximal element $x$. Then the slant sum $\cP:=\cP_1 {}^y\backslash_x \cP_2$ is a $d$-complete poset, and the acyclic elements of $\cP_1$ and $\cP_2$ are acyclic elements of $\cP$.
\end{proposition}

Next, we recall the hook-length formula for the number of linear extensions of a $d$-complete poset. 

\begin{definition}[\cites{p99}]\label{def:dcomphook}
The \emph{hook length} $h_{\cP}(z)$ of an element $z$ in a $d$-complete poset $\cP$ is defined as follows:
\begin{enumerate}

    \item If $z$ is not in the neck of any $d_k$-interval, then $h_{\cP}(z) = \#\{y \mid y \le_{\cP} z\}$.
    \item If $z$ is in the neck of a $d_k$-interval, then we can find some element $w$ such that $[w, z]$ is a $d_{\ell}$-interval for some $\ell$. If $x$ and $y$ are the two incomparable elements in the $d_{\ell}$-interval, then $h_{\cP}(z) = h_{\cP}(x) + h_{\cP}(y) - h_{\cP}(w)$. 
\end{enumerate}
\end{definition}

\begin{thm}[{Peterson--Proctor \cite{ProHLF}}]\label{thm:dhook}
The number of linear extensions of a $d$-complete poset $\cP$ with $n$ elements is
\[
e(\cP) = \frac{n!}{\prod_{x \in \cP} h_\cP(x)},
\]
where $h_{\cP}(x)$ is the hook length of $x$ in $\cP$ from Definition~\ref{def:dcomphook}.
\end{thm}

\section{Component trees and component arrays}\label{sec_component_tree}

%\textcolor{red}{folding stuff; maybe change section title or add new section for folding}

For the rest of the paper, we assume that $\cP$ is connected. However, our results can easily be adapted to the case where $\cP$ is a disconnected poset.

\begin{definition}
We define the \emph{component tree} of $\cP_F$, where $F \subset \lessdot_\cP$, to be the tree $C(\cP_F)$ with vertices $\{\sigma_0, \ldots, \sigma_k\}$ the connected components of the poset $\cP \ominus F$ and edges $\{\sigma_x,\sigma_y\}$ for all $(x,y) \in F$, where $x \in \sigma_x$ and $y \in \sigma_y$. That $C(\cP_F)$ is a tree follows from the fact that none of the cover relations in $F$ lie in an undirected cycle in the Hasse diagram of $\cP$. %\textcolor{red}{We define the {\em component tree} of $\cP_F$ to be the tree $C(\cP_F)$ with vertices the connected components of the poset $\cP \ominus F$, and with edges $(C_x, C_y)$ for each cover relation $(x,y)$ in $F$ where $x \in C_x$ and $y\in C_y$. }
\end{definition}

\begin{definition} \label{def: component array}
Suppose $\#F = k$ and $\sigma = (\sigma_0,\sigma_1,\ldots,\sigma_k)$ is a total order on the vertices of $C(\cP_F)$.  The \emph{component array} $M_\sigma(\cP_F)$ is the triangular array of posets
\[
(M_\sigma(\cP_F))_{i,j} := C(\cP_F)[i,j],
\]
where  $0\leq i\leq j \leq k$ and $C(\cP_F)[i,j]$ is the subposet of $\cP_F$ on the elements in the connected components $\sigma_i,\sigma_{i+1},\ldots, \sigma_j$ of $\cP \ominus F$. We say $\sigma$ is a \emph{path order} if each entry of the component array $M_\sigma(\cP_F)$ is a connected poset.
\end{definition}

%\begin{definition}\label{def:pathorder}
%Let $C(\cP_F)$ be the component tree of a folded poset $\cP_F$ and $\sigma = (\sigma_0,\sigma_1,\ldots,\sigma_k)$ a total order on the vertices of $C(\cP_F)$ is called a \emph{path order} if each entry of the component array $M_\sigma(\cP_F)$ is a connected poset.
%\end{definition}

\begin{example}\label{ex:nonzig3}
For the poset $\cP$ and folds $F$ from Example~\ref{ex:poset2folds}, Figure~\ref{fig: component tree and array} depicts the component tree and component arrays for a path order $\sigma=(\sigma_0,\sigma_1,\sigma_2)$ and an order $\tau=(\sigma_1,\sigma_0,\sigma_2)$ that is not a path order.%\renewcommand{\qedsymbol}{\rule{0.65em}{0.65em}}\hfill\qedsymbol 

\begin{figure}
\begin{center}
\raisebox{22pt}{\includegraphics[scale=0.8]{poset_component_matrix.pdf}} \qquad \,\,  \includegraphics[scale=0.8]{poset_2folds_Matrix} \qquad \,\, 
\includegraphics[scale=0.8]{poset_2folds_Matrix_bad}
\end{center}
\caption{Left: example of component tree $C(\cP_F)$ with a chosen total order $\sigma = (\sigma_0, \sigma_1, \sigma_2)$ on the vertices. Center: example of component array $M_{\sigma}(\cP_F)$. Right: another example of a component array $M_{\tau}(\cP_F)$ with a different order $\tau=(\sigma_1,\sigma_0,\sigma_2)$.}
\label{fig: component tree and array}
\end{figure}
\end{example}

\begin{proposition}\label{prop:goodordering}
There is a path order $\sigma$ on the vertices of $C(\cP_F)$ if and only if $C(\cP_F)$ is a path.
\end{proposition}

%\textcolor{blue}{Mention induced path order, so that we can make sense of the statement of Theorem 3.}



\section{Determinant formulas for linear extensions}
\label{section:mobile}

In this section, we present our main theorem. This theorem gives a determinantal formula for the linear extensions of mobile posets. The definition of the latter appears below.



\begin{definition}\label{def:generalized mobiles}
A {\em (connected) mobile poset} $\cP$ is a poset obtained from a ribbon $\cZ$ by the following two operations:
\begin{enumerate}[label=(\roman*)]
\item For every element $z \in \cZ$, perform a slant sum $\cZ \underset{i=1,\ldots,m_z}{\prescript{z}{}{\big{\backslash}_{r_i}}} \cR_z^{(i)}$ with $m_z \geq 0$ connected $d$-complete posets $\cR_z^{(i)}$ with respective maximal elements $r_i$. Denote the resulting poset by $\cP'$.
\item For at most one element $z' \in \cZ$, perform a slant sum $\cQ_{z'} \,{}^{q}\backslash_{z'}\, \cP'$ where $\cQ_{z'}$ is a connected $d$-complete poset and $q$ is one of its acyclic elements. Such an element $z'$ is called an {\em anchor}.
\end{enumerate}
If no such element $z' \in \cZ$ is used in Operation (ii), we say that the mobile is {\em free-standing with respect to the ribbon $\cZ$}. If each poset attached to $\cZ$ as above is a rooted tree, we say that $\cP$ is a {\em mobile tree poset}. Additionally, we say that a mobile poset $\cP$ is {\em free-standing} if there exists a ribbon $\cZ$ with respect to which $\cP$ is free-standing.
\end{definition}

See the left image in Figure~\ref{fig:mobile tree poset} for a schematic of a mobile poset. 

\begin{example}
Figure~\ref{fig: example and nonexample of mobile} shows four examples: a free-standing mobile, a mobile, and two posets that cannot be expressed as mobiles. %\renewcommand{\qedsymbol}{\rule{0.65em}{0.65em}}\hfill\qedsymbol

\begin{figure}
    \centering
    \includegraphics[scale=.85]{example_mobile_nonmobile.pdf}
    \caption{Examples of (a) a free-standing mobile poset, (b) a mobile poset, and (c) and (d) posets that are not mobile posets.}
    \label{fig: example and nonexample of mobile}
\end{figure}
\end{example}


To state Theorem~\ref{thm:gmobiledetdone}, we identify special types of folds to apply to a mobile poset $\cP$ called path folds.

\begin{definition}
Let $\cP$ be a mobile poset with a ribbon $\mathcal{Z}$ with descents $S$. %\textcolor{red}{Let $\cP$ be a mobile poset and $\cZ := \cZ_S$ be an underlying ribbon poset of $\cP$.}  
The set  of \emph{path folds} for $\cP$ (with respect to $\cZ$) is defined as
\begin{equation}
    \label{eq: folds mobile tree poset}
F = \begin{cases}
\{ (z_{i+1},z_i) \mid i \in S\} &\text{ if } \cP \text{ is free-standing,}\\
\{ (z_{i+1},z_i) \mid i \in S, i<j\} \cup \{ (z_i,z_{i+1}) \mid i \not\in S, i \geq j\} & \text{ otherwise,}  
\end{cases}
\end{equation}
where $j$ is the index of the anchor $z'=z_j$ covered by an acyclic element of a connected $d$-complete poset $\cQ_{z'}$ (see Definition~\ref{def:generalized mobiles} (ii)). 
\end{definition}


\begin{thm} \label{thm:gmobiledetdone}
Let $\cP$ be a mobile poset with $n$ elements, $F$ the set of path folds for $\cP$, and $\sigma$ a path order that is compatible with $F$.  Then 
\begin{equation}\label{eqn:gmobiledet}
e(\cP) \,=\, n!\cdot\det(M_{i,j})_{0 \leq i,j\leq k}, \quad \text{for} \quad 
M_{i,j} := \begin{cases}0 & \text{if } j<i-1,\\
1 & \text{if } j = i-1,\\
1/\prod_{x \in \cP_{i,j}} h_{\cP_{i,j}}(x) & \text{otherwise},
\end{cases}
\end{equation}
where $k$ is the size of $F$ and $\cP_{i,j}$ is the connected $d$-complete poset $(M_\sigma(\cP_F))_{i,j}$. 
\end{thm}

\begin{example} \label{ex:genmobile}
Consider the mobile poset $\cP$ and set $F = \{(e,b), (f,d)\}$ of path folds  pictured in Figure~\ref{fig: component tree and array gen mobile}: Left. The component tree $C(\cP_F)$ and the component array $M_{\sigma}(\cP_F)$ are pictured in Figure~\ref{fig: component tree and array gen mobile}: Center, Right. Applying Theorem~\ref{thm:gmobiledetdone} to $\cP$ gives the determinantal formula
\[e(\cP) = 10!\cdot\det
\begin{pmatrix}
\frac{1}{1} & \frac{1}{9\cdot8\cdot5\cdot3\cdot2\cdot2\cdot2} & \frac{1}{10\cdot9\cdot6\cdot3\cdot2\cdot2\cdot2} \\[6pt]
1 & \frac{1}{8\cdot7\cdot5\cdot3\cdot2\cdot2} & \frac{1}{9\cdot8\cdot6\cdot3\cdot2\cdot2} \\[6pt]
0 & 1 & \frac{1}{1}
\end{pmatrix}
= 240. 
\]

%\renewcommand{\qedsymbol}{\rule{0.65em}{0.65em}}\hfill\qedsymbol

\begin{figure}
    \centering
   \raisebox{30pt}{\includegraphics[scale=0.8]{genmobile_poset_2folds.pdf}} \,\,
    \raisebox{20pt}{\includegraphics[scale=0.8]{genmobile_poset_component_matrix.pdf}} \,\,    \includegraphics[scale=0.8]{genmobile_poset_2folds_Matrix}
    \caption{Left: a mobile poset $\cP$ with folds highlighted. Center: its component tree $C(\cP_F)$, with path order $\sigma = (\sigma_0,\sigma_1,\sigma_2)$. Right: its component array $M_\sigma(\cP_F)$.}
    \label{fig: component tree and array gen mobile}
\end{figure}
\end{example}

\section{Determinant formulas for $q$-analogs of linear extensions}

A \emph{labeled poset} $(\cP, \omega)$ is a poset $\cP$ with $n$ elements, together with a bijection $\omega\co \cP \to [n]$.  
%\textcolor{red}{CUT: We call $\omega$ a \emph{natural labeling} if for any $x,y\in \cP$ with $x <_{\cP} y$, we have $\omega(x) < \omega(y)$}. 
A labeling $\omega$ is \emph{regular} if we have the following: for all $x <_{\cP} z$ and $y\in \cP$, if $\omega(x) < \omega(y) < \omega(z)$ or $\omega(x) > \omega(y) > \omega(z)$ then $x <_{\cP} y$ or $y <_{\cP} z$.  For more on regular labelings, we refer the reader to \cite{q_hook}. Additionally, we define $\inv(\cP,\omega)$ to be the number of \emph{inversions} of $(\cP,\omega)$: pairs $(x,y)$ with $\omega(x) > \omega(y)$ and $x <_{\cP} y$.


\begin{definition}
Let $(\cP,\omega)$ be a labeled poset.  If $f\co \cP \rightarrow [n]$ is a linear extension of $\cP$, then the permutation $\omega \circ f^{-1}\in \mathfrak{S}_n$ is called a \emph{linear extension of the labeled poset} $(\cP,\omega)$.  We write $\cL(\cP,\omega)$ for the set of all linear extensions of $(\cP,\omega)$.
\end{definition}

By restricting to the class of mobile tree posets $\cP$, we identify a distinguished labeling of $\cP$ defined below. With this labeling, we state our final result.

\begin{definition}\label{def:prl}
Let $\cP$ be a mobile tree poset, $F$ the set of path folds for $\cP$ and $\sigma$ a path order compatible with $F$.  Then $\sigma$ gives an order $\cP_{\sigma_0}, \cP_{\sigma_1}, \ldots, \cP_{\sigma_k}$ on the connected components of the poset $\cP \ominus F$.  A labeling $\omega$ on $\cP$ is called a \emph{$\sigma$-partitioned labeling} if whenever $\sigma_i < \sigma_j$, we have
\[
\omega(x) < \omega(y) \qquad \text{for every} \qquad  x \in \cP_{\sigma_i}, \,\,y \in \cP_{\sigma_j}.
\]
Moreover, $\omega$ is called a \emph{$\sigma$-partitioned regular labeling} if it is a $\sigma$-partitioned labeling such that the restriction of $\omega$ to each connected component $\cP_{\sigma_i}$ of $\cP \ominus F$ is a regular labeling of that component.
\end{definition}

%We recall the following definition of inversions for labeled posets.

%\begin{definition} \label{def: major index d-complete}
%Let $(\cP,\omega)$ be a labeled poset. The statistic $\inv(\cP,\omega)$ counts the number of \emph{inversions} of $(\cP,\omega)$: pairs $(x,y)$ with $\omega(x) > \omega(y)$ and $x <_{\cP} y$.
%\textcolor{red}{The \emph{descent set} of $(\cP,\omega)$ is given by $\Des(\cP,\omega) = \{x \in \cP \mid x \lessdot_\cP y \text{ and } \omega(x) > \omega(y)\}$.} %If, in addition, $(\cP,\omega)$ is a labeled $d$-complete poset, then the {\em major index} of $(\cP,\omega)$ is the sum of the hook lengths at the descents of $\omega$:
%\[
%\maj(\cP,\omega) = \sum_{x \in \Des(\cP,\omega)} h_{\cP}(x).
%\]
%\end{definition}

\begin{thm}\label{thm:qmobiledetdone}
Let $(\cP,\omega)$ be a labeled mobile tree poset with $n$ elements, $F$ the set of path folds for $\cP$, $\sigma$ a path order compatible with $F$, and $\omega$ a $\sigma$-partitioned regular labeling of $\cP$. Then
\begin{equation}
e_q^{\inv}(\cP, \omega) \,=\, [n]_q!\cdot\det(M_{i,j})_{0 \leq i,j\leq k}, \quad \text{for} \quad 
M_{i,j} := \begin{cases}0 & \text{if } j<i-1,\\
1 & \text{if } j = i-1,\\
\frac{q^{\inv(\cP_{i,j}, \omega_{i,j})}}{\prod_{x \in \cP_{i,j}} [h_{\cP_{i,j}}(x)]_q} & \text{otherwise},
\end{cases}
\end{equation}
where $k$ is the size of $F$ and $(\cP_{i,j},\omega_{i,j})$ is the labeled rooted tree poset $(M_\sigma(\cP_F,\,\omega))_{i,j}$. 
\end{thm}

\begin{example}\label{ex:qinv}
Let $\cP$ be the mobile tree poset in Figure~\ref{fig: component tree and array2} with  $\sigma$-partitioned regular labeling $\omega$ given by $a\mapsto 1, b \mapsto 3, c \mapsto 6, d\mapsto 4, e \mapsto 2,$ and $f \mapsto 5$. Applying Theorem~\ref{thm:qmobiledetdone} to $(\cP,\omega)$ yields
\[
 e^{\inv}_q(\cP,\omega) = [6]_q! \cdot \det 
    \begin{pmatrix}
        \frac{1}{[1]_q} & \frac{q^3}{[5]_q[4]_q} & \frac{q^5}{[6]_q[5]_q} \\[6pt]
        1 & \frac{q^3}{[4]_q[3]_q} & \frac{q^5}{[5]_q[4]_q} \\[6pt]
        0 & 1 & \frac{1}{[1]_q}
    \end{pmatrix}
     = q^{10} + 3q^9 + 4q^8 + 3q^7 + q^6.
\]
\begin{figure}
    \centering
   \raisebox{35pt}{\includegraphics[scale=0.8]{tree_poset_2folds.pdf}} \quad
    \raisebox{22pt}{\includegraphics[scale=0.8]{tree_poset_component_matrix.pdf}} \,\,\,    \includegraphics[scale=0.8]{tree_poset_2folds_Matrix}
    \caption{Left: a mobile tree poset $\cP$ with folds highlighted. Center: its component tree $C(\cP_F)$, with path order $\sigma = (\sigma_0,\sigma_1,\sigma_2)$. 
    Right: its component array $M_\sigma(\cP_F)$.}
    \label{fig: component tree and array2}
\end{figure}
 \end{example}

%\textcolor{red}{ADD EXAMPLE}

%\textcolor{blue}{One or two sentences that we are able to obtain other q-analogues as well, and cite our paper in SIDMA.}

%\begin{example} \label{ex:mobile}
%Consider the mobile tree poset $\cP$ with Hasse diagram and set of path folds $F=\{(d,a),(d,c)\}$ pictured in Figure~\ref{fig: component tree and array2}: Left. The component tree $C(\cP_F)$ and the component array $M_{\sigma}(\cP_F)$ are illustrated in Figure~\ref{fig: component tree and array2}: Center, Right.

%\end{example}

\acknowledgements{We are grateful to Igor Pak and Bruce Sagan whose comments and questions motivated important applications of our work. We are also thankful to David Barrington, Sergi Elizalde, Jang Soo Kim, Ga Yee Park, Peter Winkler, and Benjamin Young for helpful discussions and suggestions. }

%% 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}
