%% 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]{FPSAC2023}
\articlenumber{25}
%% 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{tikz}
\usepackage{amsfonts}
\usepackage{euscript, mathrsfs,amscd} 
\usepackage{epsfig}
\usepackage{blkarray}
\usepackage{multirow}
\usepackage{mathtools}
\usepackage{bm}
\usepackage{ytableau}
\usepackage{cases}

\usepackage{subfigure}

\usetikzlibrary{decorations.markings}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exam}[thm]{Example}
\newtheorem{rmk}[thm]{Remark}
\theoremstyle{remark}
\newtheorem*{notation}{Notations}

\newcommand\QQ{\mathbb{Q}}
\newcommand\ZZ{\mathbb{Z}}
\newcommand\NN{\mathbb{N}}
\newcommand\PP{\mathbb{P}}

\newcommand\asc{\operatorname{asc}}
\newcommand\des{\operatorname{des}}
\newcommand\inv{\operatorname{inv}}
\newcommand\inc{\operatorname{inc}}
\newcommand\sgn{\operatorname{sgn}}
\newcommand\sh{\operatorname{sh}}
\newcommand\rank{\operatorname{rank}}
\newcommand\lex{\operatorname{lex}}
\newcommand\row{\operatorname{row}}
\newcommand\col{\operatorname{col}}
\newcommand\ch{\operatorname{ch}}
\newcommand\wt{\operatorname{wt}}

\newcommand\WM{\operatorname{WM}}

\newcommand\Des{\operatorname{Des}}
\newcommand\SYT{\operatorname{SYT}}
\newcommand\SSYT{\operatorname{SSYT}}
\newcommand\Par{\operatorname{Par}}
\newcommand\Comp{\operatorname{Comp}}

\newcommand\NSym{\mathsf{NSym}}
\newcommand\Sym{\mathsf{Sym}}
\newcommand\QSym{\mathsf{QSym}}

\newcommand\gge{\succcurlyeq}
\newcommand\lle{\preccurlyeq}
\newcommand\trigeq{\unrhd}
\newcommand\trileq{\unlhd}

\newcommand\TT{\mathcal{T}}
\newcommand\calN{\mathcal{N}}
\newcommand\UU{\mathcal{U}}
\newcommand\EE{\mathcal{E}}
\newcommand\EP{\mathcal{EP}}
\newcommand\SSS{\mathcal{S}}
\newcommand\II{\mathcal{I}}
\newcommand\LL{\mathcal{L}}
\newcommand\HH{\mathcal{H}}

\newcommand\xx{\mathbf{x}}
\newcommand\yy{\mathbf{y}}
\newcommand\uu{\mathbf{u}}
\newcommand\mm{\mathbf{m}}

\newcommand\ee{\mathfrak{e}}
\newcommand\hh{\mathfrak{h}}
\newcommand\sch{\mathfrak{J}}
\newcommand\pp{\mathfrak{p}}
\newcommand\mono{\mathfrak{m}}
\newcommand\ff{\mathfrak{f}}
\newcommand\FF{\mathfrak{F}}
\newcommand\MM{\mathfrak{M}}

\newcommand\ww{\mathsf{w}}
\newcommand\vv{\mathsf{v}}
\newcommand\zz{\mathsf{z}}
\newcommand\pathp{\mathsf{p}}

\newcommand\oo{\mathfrak{o}}

\newcommand\RECTX{2.5}
\newcommand\RECTY{1}

\newcommand\equivclass[1]{#1/{\sim}}
\newcommand\qand{\quad\mbox{and}\quad}
\newcommand\mand{\mbox{ \& }}

\newcommand\CHK[1]{\textcolor{red}{#1}}


%% define your title in the usual way
\title{Chromatic quasisymmetric functions and noncommutative \( P \)-symmetric functions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Byung-Hak Hwang\thanks{\href{mailto:byunghakhwang@gmail.com}{byunghakhwang@gmail.com}.} %\addressmark{1}
}

%% then use \addressmark to match authors to institutions here
% \address{\addressmark{1}Department of This, University of That, There}

%% 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 a natural unit interval order \( P \), we introduce a combinatorial
  operation, called a \emph{local flip}, on proper colorings of \( P \).
  This operation defines an equivalence relation on the proper
  colorings, and the equivalent relation refines the ascent statistic introduced
  by Shareshian and Wachs.
  We also define analogues of noncommutative symmetric functions.
  They reflect properties of \( P \) and local flips,
  and lead us to positive expansions of the
  chromatic quasisymmetric functions into several symmetric function bases.}

%% 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{Chromatic quasisymmetric function, Noncommutative symmetric function, the Stanley--Stembridge conjecture, the \( e \)-positivity conjecture}

%% 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{ncs_fpsac.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}
\subsection{Chromatic quasisymmetric functions}
Chromatic quasisymmetric functions are one of the most notable objects in
algebraic combinatorics, because of their connections with other fields.
In \cite{Sta95,SW16}, Stanley, and then Shareshian--Wachs, introduced the
\emph{chromatic quasisymmetric function} which generalizes the chromatic polynomial. For a graph $G$ on vertex set \( [n] \),
the chromatic quasisymmetric function $X_G(\xx,q)$ of $G$ is defined by
\[
  X_G(\xx,q) = \sum_{\kappa} q^{\asc(\kappa)} x^\kappa,
\]
where $\kappa:[n]\rightarrow \mathbb{P}$ ranges over all proper colorings of $G$,
$\asc(\kappa)$ is the number of edges $\{i,j\}$ such that $i<j$ and
$\kappa(i)<\kappa(j)$, and $x^\kappa=\prod_{v\in V(G)} x_{\kappa(v)}$.

One of the most famous long-standing open problems in algebraic combinatorics
is \emph{the \( e \)-positivity conjecture}, which is about chromatic quasisymmetric functions
(\cref{conj:original_e_positivity_conj})
(the original conjecture was proposed by Stanley--Stembridge, and Shareshian--Wachs gave a refinement of it).

The Shareshian--Wachs quasisymmetric refinement has an advantage for
resolving the $e$-positivity conjecture.
The chromatic quasisymmetric function $X_G(\xx,q)$ has more information about
colorings than $X_G(\xx, 1)$, the chromatic symmetric function, and it is obvious
that the conjecture of
Shareshian--Wachs implies the original $e$-positivity conjecture of
Stanley--Stembridge.
But thanks to the quasisymmetric generalization,
we can cluster colorings of $G$ along the ascent statistic,
and this clustering makes us focus on certain colorings instead of whole ones.
In this sense, the quasisymmetric generalization gives us a hint for the
\( e \)-positivity conjecture.
One can then ask for a natural way which refines the Shareshian--Wachs refinement.

One of the goals of the abstract is to answer this question. We will introduce a
combinatorial operation, called a \emph{local flip}.
This operation defines an equivalence relation on proper colorings,
and this relation refines the refinement of Shareshian and Wachs.
Many results for the Shareshian--Wachs refinement still hold for our refinement.

\subsection{Positivity of symmetric functions}
Whenever a new class of symmetric functions is introduced, a question that naturally
arises is positivity of them with respect to various symmetric function bases.
To show positivity of a given symmetric function,
numerous combinatorial and algebraic tools are developed.
One of such well developed tools is the theory of noncommutative symmetric functions.
Fomin and Greene~\cite{FG98} introduced noncommutative Schur functions to prove
Schur positivity for various symmetric functions.
In \cite{BF17}, Blasiak and Fomin gave a more general algebraic framework of this
approach.

We devote the second half of this abstract to introducing analogues of
noncommutative symmetric functions which reflect properties of a given natural
unit interval order $P$. In the same spirit of \cite{BF17}, these noncommutative
symmetric functions provide expansions of the chromatic quasisymmetric function of
$P$ in terms of several bases.

The full version of this extended abstract is available at \href{https://arxiv.org/abs/2208.09857}{arXiv:2208.09857}.

\section{Background} \label{sec:background}
\subsection{Natural unit interval orders} \label{subsec:NUIO}
Fix a positive integer $n$, and let $\mm=(m_1,\dots,m_n)$ be a weakly
increasing integer sequence satisfying $i\le m_i \le n$ for each $i$.
The \emph{natural unit interval order $P=P(\mm)$} corresponding to $\mm$
is a poset on $[n]=\{1,2,\dots,n\}$ whose ordering $<_P$ is given by $i<_P j$ if $m_i<j$.
The term ``natural unit interval order'' arises from the following unit interval
model: given a natural unit interval order $P$, one can assign a unit interval on
the real line to each $i\in[n]$ such that $i<_P j$ if and only if the unit interval
assigned to $i$ completely lies on the left of the unit interval assigned to $j$.

Let \( P \) be a natural unit interval order on $[n]$.
The \emph{incomparability graph} of $P$ is the graph whose vertex set
is \( [n] \), and for $i<j$, $i$ and $j$ are adjacent if and only if
$j \le m_i$. By abuse of notation, we write the same notation $P$ for
the incomparability graph of $P$.

We also define some notions for words on the alphabet $[n]$ with respect to $P$.
For a word $\ww=\ww_1\ww_2\cdots\ww_d$,
we say that \( \ww \) is of \emph{type \( \mu=(\mu_1,\dots,\mu_n) \)} if the
letter \( \mathsf{i} \) appears \( \mu_i \) times in \( \ww \) for each \( i \).
For $1\le i < d$, $i$ is a \emph{$P$-descent} of $\ww$ if $\ww_i >_P \ww_{i+1}$,
and let
\[
  \Des_P(\ww) = \{ i\in [d-1] \mid \ww_i >_P \ww_{i+1} \}.
\]
For $1\le i < j\le d$, $(i,j)$ is an \emph{\( P \)-inversion pair} of $\ww$
if $\ww_i$ and $\ww_j$ are incomparable in $P$, and $\ww_i>\ww_j$
in the natural order.
Denote by $\inv_P(\ww)$ the number of \( P \)-inversion pairs of $\ww$.

\subsection{Symmetric and quasisymmetric functions}
We assume that the reader is familiar with the basics of the theory of symmetric
and quasisymmetric functions. We follow definitions and notations in
\cite[Chapter~7]{Sta99}.
Here, we only discuss some identities which we will use.

Let \( \xx=(x_1,x_2,\dots) \) be a sequence of commuting indeterminants,
and \( \Sym \subset \QQ[[\xx]] \) be the \( \QQ \)-space of symmetric functions.
The following identities are well known: for \( k\ge 0 \) and a partition \( \lambda \),
\begin{align}
& h_k(\xx) - e_1(\xx) h_{k-1}(\xx) + \cdots + (-1)^k e_k(\xx) = \delta_{k,0}, \qand  \label{eq:relation_eh} \\
& s_\lambda(\xx) = \det (e_{\lambda'_i+j-i}(\xx))_{i,j=1}^{\lambda_1},  \label{eq:dual_jacobi}
\end{align}
where \( h_k(\xx), e_k(\xx) \) and \( s_\lambda(\xx) \) are complete
homogeneous, elementary symmetric function, and Schur functions, respectively,
and \( \lambda' \) is the conjugate of \( \lambda \).

Let $\yy=(y_1,y_2,\dots)$ be another sequence of commuting indeterminants. Define
\begin{equation}
C(\xx,\yy) =  \prod_{j\ge 1} \sum_{\ell\ge 0} x_j^\ell h_\ell(\yy) = \sum_{\lambda} m_\lambda(\xx) h_\lambda(\yy) \in\QQ[[\xx,\yy]]
\label{eq:comm_Cauchy_mh},
\end{equation}
called the \emph{Cauchy product}.

\subsection{Chromatic quasisymmetric functions}
Let $G$ be a simple graph on the vertex set $[n]$.
For a given sequence $\mu=(\mu_1,\mu_2,\dots,\mu_n)\in\NN^n$,
a \emph{proper multi-coloring} $\kappa$ of $G$ of type $\mu$ is a function from $[n]$ to the collection of all finite subsets of $\PP$ such that for each $i\in [n]$, $| \kappa(i) | = \mu_i$ and $\kappa(j)\cap\kappa(k)=\emptyset$ whenever $\{j,k\}\in E(G)$.
The \emph{(multi-)chromatic quasisymmetric function} $X_G(\xx,q;\mu)$ of $G$ is given by
\begin{equation*}
X_G(\xx,q;\mu) = \sum_{\kappa} q^{\asc_G(\kappa)} x^{\kappa},
\end{equation*}
where the sum is over all proper multi-colorings $\kappa$ of type $\mu$, $x^{\kappa} = \prod_{i=1}^n \prod_{k\in\kappa(i)} x_k$ and $\asc_G(\kappa) = | \{ ((i,r),(j,s)) \mid \{i,j\}\in E(G),~ i<j,~ r\in\kappa(i),~ s\in\kappa(j),~ r<s \} |$.
This is a generalization of chromatic quasisymmetric function \( X_G(\xx,q) \)
introduced by Shareshian and Wachs~\cite{SW16}.
By definition, \( X_G(\xx,q;(1^n)) = X_G(\xx,q) \).

In general, $X_G(\xx,q;\mu)$ is a quasisymmetric function, but when $P$ is
a natural unit interval order, $X_P(\xx,q;\mu)$ is a symmetric function
(\cref{thm:X_P=Omega}).
We close this section with an explicit statement of the (refined) $e$-positivity
conjecture.
\begin{conj}[\cite{SS93,Sta95,SW16}] \label{conj:original_e_positivity_conj}
For a natural unit interval order $P$ on $[n]$, let
\[
  X_P(\xx,q;(1^n)) = \sum_{\lambda\vdash n} c_\lambda(q) e_\lambda(\xx).
\]
Then $c_\lambda(q)$ is a polynomial with nonnegative integer coefficients.
\end{conj}

\section{Heaps and local flips} \label{sec:heap_local_flip}
In this section, we review the definition of heaps and define
an operation, called a local flip, on heaps. This operation plays a central role
in this abstract.

Fix a natural unit interval order $P$ on $[n]$, and a nonnegative integer sequence
$\mu=(\mu_1,\dots,\mu_n)\in\NN^n$. Let $P^\mu$ be the graph whose vertex set is
$\{ v_{a,i} \mid a\in [n], 1\le i\le \mu_a\}$, and $v_{a,i}$ and $v_{b,j}$
are adjacent if either $a=b$ or $a$ and $b$ are incomparable in $P$.
A \emph{heap $H$} of $P$ of type $\mu$ is an acyclic orientation of $P^\mu$ satisfying that for each $a\in [n]$ and $1\le i< j\le \mu_a$,
the direction on the edge between $v_{a,i}$ and $v_{a,j}$ is toward $v_{a,i}$.
Clearly a heap of type $(1^n)$ is just an acyclic orientation of the incomparability graph of $P$.
We call a vertex of a heap a \emph{piece}, and denote the set of heaps of $P$ of type $\mu$ by $\HH(P,\mu)$.
The terminology ``heap'' originates from the following diagrammatic realization:
take $n$ unit intervals described in \cref{subsec:NUIO}.
We stack blocks of unit length on top of each interval.
For each $i\in [n]$, the number of blocks stacked on the $i$-th interval equals $\mu_i$. We will often identify heaps with their diagrammatic realizations.

Each proper multi-coloring $\kappa$ of $P$ of type $\mu$ gives us a heap of $P$ of
type $\mu$ as follows: for each vertex $a\in [n]$, list its colors
$\kappa(a)=\{c_{a,1}< \dots < c_{a,\mu_a}\}$, and for each edge
$\{v_{a,i},v_{b,j}\}$ assign the direction $v_{a,i}\leftarrow v_{b,j}$
if $c_{a,i}<c_{b,j}$.
To see this diagrammatically, consider again $n$ unit intervals on the real line.
For each $a\in [n]$ and $c\in\kappa(a)$, place a block at the position of height
$c$ above the $a$-th interval.
After placing all blocks, drop them down as far as gravity takes them,
and then we obtain a heap of type \( \mu \).
For example, let $P=P(2,3,3)$ and $\kappa$ be a proper
multi-coloring of $P$ of type $(3,1,2)$ given by
$\kappa(1) = \{1,3,6\}$, $\kappa(2) = \{4\}$, $\kappa(3) = \{2,6\}$,
shown in \cref{fig:kappa_1},
and its corresponding heap is shown in \cref{fig:kappa_2}.
\begin{figure}
\centering
\subfigure[]{
    \begin{tikzpicture}[scale=.4]
        \draw (0,0) rectangle ++(\RECTX,\RECTY);
        \draw (0,2) rectangle ++(\RECTX,\RECTY);
        \draw (0,5) rectangle ++(\RECTX,\RECTY);
        \draw (1.5,3) rectangle ++(\RECTX,\RECTY);
        \draw (3,1) rectangle ++(\RECTX,\RECTY);
        \draw (3,5) rectangle ++(\RECTX,\RECTY);
        \draw [thick] (-1,0) -- (6.5,0);
    \end{tikzpicture}
\label{fig:kappa_1}
}
\qquad
\subfigure[]{
    \begin{tikzpicture}[scale=.4]
        \draw (0,0) rectangle ++(\RECTX,\RECTY);
        \draw (0,1) rectangle ++(\RECTX,\RECTY);
        \draw (0,3) rectangle ++(\RECTX,\RECTY);
        \draw (1.5,2) rectangle ++(\RECTX,\RECTY);
        \draw (3,0) rectangle ++(\RECTX,\RECTY);
        \draw (3,3) rectangle ++(\RECTX,\RECTY);
        \draw [thick] (-1,0) -- (6.5,0);
    \end{tikzpicture}
\label{fig:kappa_2}
}
\caption{}
\label{fig:kappa}
\end{figure}
For a heap \( H \), let
\(
  K_H(\xx) = \sum_\kappa x^\kappa
\)
where the summation ranges over all proper colorings corresponding to \( H \).
Since heaps are acyclic orientations, we can also regard them as posets.

Let $W(\mu)$ be the set of all words of type $\mu$. For a heap $H$ of $P$ of type $\mu$, let $f:H\rightarrow [d]$ be a linear extension of $H$ where $d=\mu_1+\cdots+\mu_n=|H|$. Then define the word $\ww_f=\ww_{f,1}\cdots\ww_{f,d}$ by $\ww_{f,k} = a$ if $f^{-1}(k) = v_{a,i}\in H$ for some $i$. Then $\ww_f$ is of type $\mu$.
Let
\[
W(H) = \{\ww_f\in W(\mu) \mid \mbox{$f$ is a linear extension of $H$} \}.
\]

For a heap $H$, an edge between $v_{a,i}$ and $v_{b,j}$ is \emph{ascent}
if the edge is toward $v_{a,i}$ and $a>b$ in the natural order.
Let $\asc_P(H)$ denote the number of ascent edges in $H$.

\begin{thm} \label{thm:F_expan}
  We have
  \begin{align*}
    \omega X_P(\xx,q;\mu)
    &= \sum_{H\in \HH(P,\mu)} q^{\asc_P(H)} K_H(\xx) \\
    &= \sum_{\ww\in W(\mu)} q^{\inv_P(\ww)} F_{d,\Des_P(\ww)}(\xx),
  \end{align*}
  where \( F_{d,S}(\xx) \) is a fundamental quasisymmetric function.
\end{thm}

For any distinct pieces $p,q$ and $r$ in $H$, we call $(p,q,r)$ a
\emph{flippable triple} in $H$ if either
\begin{enumerate}[label=(\roman*)]
\item $q$ covers $p$ and $r$, or
\item $q$ is covered by $p$ and $r$.
\end{enumerate}
\begin{defn}
Let $H$ be a heap of $P$ and $(p,q,r)$ a flippable triple in $H$.
A \emph{local flip at $(p,q,r)$} is reversing the directions on the edges
$\{p,q\}$ and $\{q,r\}$.
\end{defn}
\begin{lem}
Let $H$ be a heap and $(p,q,r)$ a flippable triple in $H$.
Then the orientation $H'$ obtained from $H$ by local flipping at $(p,q,r)$ is
acyclic, so $H'$ is also a heap of the same type.
\end{lem}

We can think of a local flip as an operation on diagrammatic realizations of heaps
acting by transposing relative positions of blocks as follows:
\begin{center}
\includegraphics[width=0.35\linewidth]{./figures/flipping_diagram.pdf}
\end{center}

Using local flips, we can define an equivalence relation on the set of heaps of $P$ of type $\mu$: for two heaps $H,H'\in\HH(P,\mu)$, $H\sim H'$ if and only if $H'$ can be obtained from $H$ by applying a finite sequence of local flips. For instance, we illustrate all heaps of $P(2,3,4,5,5)$ of type $(1^5)$ and their equivalence relations in \cref{fig:heap_orbit_2345}.

The following proposition and theorem tell us why local flips are crucial.
\begin{prop} \label{prop:ascent_number}
Local flips preserve the number of ascents.
\end{prop}
\begin{thm} \label{thm:X_P_sym}
  Let $[H]$ be an equivalence class in $\equivclass{\HH(P,\mu)}$. Then
  \[
  K_{[H]}(\xx) := \sum_{H'\in [H]} K_{H'}(\xx) \in \Sym.
  \]
  In particular, $X_G(\xx,q;\mu)$ is a symmetric function.
\end{thm}
\begin{figure}
  \centering
  \includegraphics[width=0.8\linewidth]{./figures/flip_orbits_2345.pdf}
  \caption{All heaps of $P(2,3,4,5,5)$ of type $(1^5)$. A gray line between heaps means that they can be transformed to each other via a local flip. Hence each connected component represents an equivalence class.}
  \label{fig:heap_orbit_2345}
\end{figure}
In addition, \cref{thm:X_P_sym} admits a refinement of
the refined $e$-positivity conjecture.
\begin{conj} \label{conj:refined_e-positivity}
Let $P$ be a natural unit interval order on $[n]$, and $\mu\in\NN^n$.
For any equivalence class $[H]\in\equivclass{\HH(P,\mu)}$, $K_{[H]}(\xx)$ is
$h$-positive.
In particular, $X_P(\xx,q;\mu)$ is $e$-positive.
\end{conj}

We end this section with defining a graph $\Gamma_\mu$ for $\mu\in\NN^n$.
The vertex set of $\Gamma_\mu$ is the set $W(\mu)$ of all words of type $\mu$. Two words $\ww=\ww_1\cdots\ww_d$ and $\vv=\vv_1\dots\vv_d$ are adjacent in $\Gamma_\mu$ if there exists an integer $i$ satisfying the one of the following conditions:
\begin{enumerate}[label=(\roman*),font=\upshape]
\item $\ww_j=\vv_j$ for $j\notin\{i,i+1\}$, and $\{\ww_i\ww_{i+1},\vv_i\vv_{i+1}\}=\{\mathsf{ac, ca}\}$ for some $a<_P c$.
\item $\ww_j=\vv_j$ for $j\notin\{i-1,i,i+1\}$, and  either $\{\ww_{i-1}\ww_i\ww_{i+1},\vv_{i-1}\vv_i\vv_{i+1}\}=\{\mathsf{bac, acb}\}$ or $\{\mathsf{bca, cab}\}$  for some $a<b<c$ satisfying $a\nless_P b$, $b\nless_P c$ and $a<_P c$.
\end{enumerate}
The second condition represents how a local flip operates on words.
\begin{figure}
\centering
\subfigure[]{
\includegraphics[width=0.65\linewidth]{./figures/Gamma_112_heap_w_flip.pdf}
\label{fig:Gamma_112_heap}
}
\subfigure[]{
\includegraphics[width=0.65\linewidth]{./figures/Gamma_112.pdf}
\label{fig:Gamma_112_word}
}
\caption{Let $P=P(2,3,3)$ and $\mu=(1,1,2)$. (a) All heaps of $P$ of type $\mu$ and their equivalence relations. (b) The graph $\Gamma_\mu$.}\label{fig:Gamma_112}
\end{figure}

\section{Noncommutative \texorpdfstring{$P$}--symmetric functions} \label{sec:Noncomm}
In this section, we define noncommutative $P$-symmetric functions associated with
a natural unit interval order $P$, and present their connection
with the chromatic quasisymmetric function of \( P \).
Using these, we provide positivity of $X_P(\xx,q;\mu)$
in several symmetric function bases.

\subsection{An analogue of noncommutative symmetric functions}
Let $P$ be a natural unit interval graph on $[n]$ and $\UU$ the free associative $\ZZ$-algebra generated by $\{u_1,\dots,u_n\}$.
For simplicity we write $u_\ww=u_{\ww_1} u_{\ww_2} \cdots u_{\ww_d}$ for a word $\ww=\ww_1 \ww_2 \cdots \ww_d$ on the alphabet $[n]$.
Let $\II_P$ be the 2-sided ideal of $\UU$ generated by the following elements:
\begin{align}
& u_a u_c - u_c u_a & &\mbox{($a <_P c$),} \label{eq:generator_I1}\\
& u_a u_c u_b - u_b u_a u_c & &\mbox{($a<b<c$, $a\nless_P b$, $b\nless_P c$ and $a<_P c$).} \label{eq:generator_I2}
\end{align}
The ideal is just an algebraic counterpart of the graph $\Gamma_\mu$.

For $k\ge1$, we define the \emph{noncommutative $P$-elementary symmetric function} $\ee_k(\uu)$ by
\begin{equation} \label{eq:def_ee}
\ee_k(\uu) = \sum_{i_1 >_P i_2 >_P \cdots >_P i_k} u_{i_1} u_{i_2} \cdots u_{i_k} \in\UU.
\end{equation}
By convention, let $\ee_0(\uu) = 1$ and $\ee_k(\uu) = 0$ for any $k<0$.
For a partition $\lambda=(\lambda_1,\dots,\lambda_\ell)$, define
$\ee_\lambda(\uu) = \ee_{\lambda_1}(\uu)\cdots\ee_{\lambda_\ell}(\uu)$.

The following property plays a crucial role in the theory of noncommutative symmetric functions.
\begin{thm} \label{thm:e_k_commute}
For any integers $k, \ell\ge 0$, $\ee_k(\uu)$ and $\ee_\ell(\uu)$ commute with
each other modulo $\II_P$, that is,
\[
\ee_k(\uu) \ee_\ell(\uu) \equiv \ee_\ell(\uu) \ee_k(\uu) \mod \II_P.
\]
\end{thm}

Similar to the relation \eqref{eq:relation_eh}, we define the
\emph{noncommutative $P$-complete homogeneous symmetric functions}
$\hh_k(\uu)$ inductively as follows:
\[
\hh_k(\uu) - \ee_1(\uu) \hh_{k-1}(\uu) + \cdots + (-1)^k \ee_k(\uu) = \delta_{k,0},
\]
with $\hh_0(\uu)=1$, and define $\hh_\lambda(\uu) = \hh_{\lambda_1}(\uu)\cdots\hh_{\lambda_\ell}(\uu)$ for a partition $\lambda=(\lambda_1,\dots,\lambda_\ell)$.
Then it is easy to check that
\begin{equation} \label{eq:hh}
\hh_k(\uu) = \sum_{i_1\ngtr_P i_2\ngtr_P \cdots \ngtr_P i_k} u_{i_1} u_{i_2} \cdots u_{i_k}.
\end{equation}
By \cref{thm:e_k_commute}, $\hh_k(\uu)$'s also commute with each other in $\UU/\II_P$.

Define
\[
H(x,\uu) = \sum_{\ell\ge 0} x^\ell \hh_\ell(\uu) \in\UU[[x]]\qand 
\Omega(\xx, \uu) = H(x_1, \uu)H(x_2, \uu)\cdots \in\UU[[\xx]].
\]
Here, $x$ and $\xx$ commute with $\uu$.
We call $\Omega(\xx,\uu)$ the \emph{noncommutative $P$-Cauchy product}.
Since $H(x_i,\uu) H(x_j,\uu) \equiv H(x_j,\uu) H(x_i,\uu)$ modulo $\II_P[[\xx]]$,
we can write $\Omega(\xx,\uu)$ as the usual Cauchy product \eqref{eq:comm_Cauchy_mh}:
\begin{equation} \label{eq:Omega=mh}
\Omega(\xx,\uu) \equiv \sum_{\lambda} m_\lambda(\xx) \hh_\lambda(\uu) \mod \II_P[[\xx]].
\end{equation}
Let $\UU^*$ be the free
$\ZZ$-module generated by words on the alphabet $[n]$, and
$\langle~,~\rangle$ a canonical pairing between $\UU$ and $\UU^*$ such that
$\langle u_\ww , \vv \rangle = \delta_{\ww,\vv}$ for words $\ww$ and $\vv$.
Let \( \II_P^\perp \) be the orthogonal complement of $\II_P$ with respect to
the pair, then we have the naturally induced pairing between $\UU/\II_P$ and $\II_P^\perp$.
Also let $\UU^*_q = \ZZ[q] \otimes_\ZZ \UU^*$ and $\II_{P,q}^\perp = \ZZ[q] \otimes_\ZZ \II_P^\perp$.
Then we extend the pairing to $\UU_q^*$.

Let
\[
\gamma_{H} = \sum_{\ww\in W(H)} \ww \in\UU^* \qand \gamma_{[H]} = \sum_{H'\in [H]} \gamma_{H'} \in\UU^*
\]
for a heap $H$. Then one can show \( \gamma_{[H]}\in\II_P^\perp \). Also let
\[
\gamma_\mu = \sum_{\ww\in W(\mu)} q^{\inv_P(\ww)} \ww = \sum_{[H]\in\equivclass{\HH(P,\mu)}} q^{\asc_P(H)} \gamma_{[H]} \in \II_{P,q}^\perp\subset \UU^*_q.
\]
\begin{thm} \label{thm:X_P=Omega}
For a nonnegative integer sequence $\mu=(\mu_1,\dots,\mu_n)$, we have
\[
K_{[H]}(\xx) = \langle \Omega(\xx,\uu), \gamma_{[H]} \rangle
\qand
\omega X_P(\xx,q;\mu) = \langle \Omega(\xx,\uu), \gamma_\mu \rangle.
\]
In particular, $K_{[H]}(\xx)$ is a symmetric function, and so is $X_P(\xx,q;\mu)$.
\end{thm}
\begin{cor} \label{cor:strategy}
Suppose that we can write
\begin{equation} \label{eq:Omega=gf}
\Omega(\xx,\uu)\equiv \sum_{\lambda} g_\lambda(\xx) \ff_\lambda(\uu) \mod \II_P[[\xx]]
\end{equation}
for some symmetric function basis $g_\lambda(\xx)$ and noncommutative $P$-symmetric functions $\ff_\lambda(\uu)$.
Let $\omega X_P(\xx,q;\mu) = \sum_{\lambda} r_\lambda(q) g_\lambda(\xx)$.
Then for any partition $\lambda$, we have
\[
r_\lambda(q) = \langle \ff_\lambda(\uu), \gamma_\mu \rangle.
\]
\end{cor}
\cref{cor:strategy} offers expansions of $X_P(\xx,q;\mu)$
in terms of various bases.
As an example, let us consider the noncommutative $P$-complete homogeneous
symmetric functions $\hh_\lambda(\uu)$, which we already defined.
They provide the expansion of $X_P(\xx,q;\mu)$
in terms of the forgotten symmetric functions \( f_\lambda(\xx) \).
\begin{thm} \label{thm:f-positive}
Let $X_P(\xx,q;\mu) = \sum_\lambda a_\lambda(q) f_\lambda(\xx)$.
Then we have
\[
  a_\lambda(q) = \sum_{\ww} q^{\inv_P(\ww)},
\]
where $\ww$ ranges over all words of type $\mu$ such that when we split $\ww$
from left to right into consecutive segments of lengths
$\lambda_1,\lambda_2,\dots,\lambda_\ell$, each segment has no $P$-descents.
\end{thm}

\subsection{Noncommutative \texorpdfstring{$P$}--Schur functions} \label{subsec:Noncomm_Schur}
We define noncommutative $P$-Schur functions via the dual
Jacobi--Trudi identity~\eqref{eq:dual_jacobi}.
\begin{defn}
  For a partition $\lambda$, we define the \emph{noncommutative $P$-Schur function} $\sch_\lambda$ by
  \begin{equation} \label{eq:def_ss}
  \sch_\lambda(\uu) = \sum_{\sigma\in\mathfrak{S}_m} \sgn(\sigma) \ee_{\lambda'_1+\sigma(1)-1}(\uu) \ee_{\lambda'_2+\sigma(2)-2}(\uu) \cdots \ee_{\lambda'_m+\sigma(m)-m}(\uu),
  \end{equation}
  where $\lambda'$ is the conjugation of $\lambda$ and $m=\lambda_1$.
\end{defn}
\begin{prop} \label{prop:Omega=ss}
  We have
  \begin{equation} \label{eq:Omega=ss}
    \Omega(\xx,\uu) \equiv \sum_\lambda s_\lambda(\xx) \sch_\lambda(\uu) \mod \II_P[[\xx]].
  \end{equation}
\end{prop}
Similar to ordinary Schur functions, we will provide a combinatorial description of
noncommutative $P$-Schur functions. 
\begin{defn}
For a partition $\lambda$, a \emph{semistandard $P$-tableau of shape $\lambda$} is
a filling of the Young diagram of shape $\lambda$ with $[n]$ satisfying that
\begin{enumerate}
\item[(i)] each row is non-$P$-decreasing from left to right, and
\item[(ii)] each column is $P$-increasing from top to bottom.
\end{enumerate}
A semistandard $P$-tableau $T$ is of \emph{type $\mu=(\mu_1,\dots,\mu_n)$} if each $i\in [n]$ appears $\mu_i$ times in $T$. We denote the set of all semistandard $P$-tableaux of shape $\lambda$ by $\TT_P(\lambda)$. The \emph{reading word} $\ww(T)$ of $T$ is the word obtained by reading $T$ from bottom to top, beginning with the leftmost column of $T$ and working from left to right. 
\end{defn}

\begin{thm} \label{thm:s-positive}
We have
\begin{equation} \label{eq:ss_P-tabluea}
\sch_\lambda(\uu) \equiv \sum_{T\in\TT_P(\lambda)} u_{\ww(T)} \mod \II_P.
\end{equation}
Consequently, $\omega X_P(\xx,q;\mu)$ is $s$-positive and its coefficient of $s_\lambda$ counts semistandard $P$-tableaux of shape $\lambda$ and of type $\mu$. In other words,
\[
\omega X_P(\xx,q;\mu) = \sum_{T} q^{\inv_P(T)} s_{\sh(T)}(\xx),
\]
where $T$ ranges over all semistandard $P$-tableaux of type $\mu$ and $\sh(T)$ denotes the shape of $T$.
\end{thm}
\begin{exam}
  Let \( P=(2,3,3) \) and \( \mu=(1,1,2) \); see \cref{fig:Gamma_112}.
  To obtain the coefficient \( a_{3,1}(q) \)
  of \( s_{3,1}(\xx) \) of \( \omega X_P(\xx,q;\mu) \), it suffices to find
  \framebox{words} \( \ww \) such that \( \ww \) is a reading word
  for some semistandard \( P \)-tableaux of shape \( (3,1) \):
  \begin{center}
      \includegraphics[scale=1]{./figures/s-expansion.pdf}
  \end{center}
  Therefore we have \( a_{3,1}(q) = q^2 + q \).
\end{exam}

\subsection{Noncommutative \texorpdfstring{$P$}--monomial symmetric functions} \label{sec:Noncomm_mono}
Let \( (N_{\lambda,\mu}) \) be the transition matrix between the monomial symmetric functions and the elementary symmetric functions, i.e.,
\( m_\lambda(\xx) = \sum_{\mu} N_{\lambda,\mu} e_\mu(\xx) \).
\begin{defn}
For a partition $\lambda$, the \emph{noncommutative $P$-monomial symmetric function} $\mono_\lambda(\uu)$ is defined by
\begin{equation} \label{eq:def_mono}
\mono_\lambda(\uu) = \sum_{\mu} N_{\lambda,\mu} \ee_\mu(\uu).
\end{equation}
\end{defn}
\begin{prop} \label{prop:Omega=hm}
  We have
  \begin{equation} \label{eq:Omega=hm}
    \Omega(\xx,\uu) \equiv \sum_{\lambda} h_\lambda(\xx) \mono_\lambda(\uu) \mod \II_P[[\xx]].
  \end{equation}
\end{prop}

Stanley and Shareshian--Wachs showed that the sum of certain $e$-coefficients of
chromatic quasisymmetric functions are related to acyclic orientations of the graph.
For $X_P(\xx,q;\mu)$, we have a similar description of $\sum_{\ell(\lambda)=k} c_\lambda(q)$ in terms of certain heaps.
\begin{thm} \label{thm:sum_m=sink_heap}
Let $P$ be a natural unit interval order. Then for \( d, k\ge 1 \), we have
\begin{equation}
\sum_{\substack{\lambda\vdash d \\ \ell(\lambda)=k}} \mono_\lambda(\uu) \equiv \sum_H u_{\ww_H} \mod \II_P \nonumber,
\end{equation}
where $H$ ranges over all heaps of $P$ consisting of $d$ pieces with $k$ sinks.
Consequently, let $X_P(\xx,q;\mu) = \sum_\lambda c_\lambda(q) e_\lambda(\xx)$.
Then we have
\[
  \sum_{\ell(\lambda)=k} c_\lambda(q) = \sum_H q^{\asc_P(H)},
\]
where $H$ ranges over all heaps of type $\mu$ with $k$ sinks.
\end{thm}

We now give a positive monomial expression of \( \mono_\lambda(\uu) \) where
\( \lambda \) is of 2-column shape.
Given a heap $H$, the \emph{rank} of a piece $p$ is the height of $p$ in the diagrammatic realization of $H$, denoted by $\rank(p)$. In particular, $\rank(p)=1$ if and only if $p$ is a sink. In addition, we define the \emph{rank} of $H$ by the maximum rank of pieces.
We say that a connected heap of rank 2 is of \emph{type W} if the number of piece
of rank 1 equals the number of pieces of rank 2 minus 1.

\begin{thm} \label{thm:m_two_column}
For $k\ge \ell\ge0$, we have
\begin{equation} \label{eq:mono_two-column}
\mono_{(2^\ell,1^{k-\ell})}(\uu) \equiv \sum_H u_{\ww_H} \mod \II_P,
\end{equation}
where $H$ ranges over all heaps of $P$ such that $H$ consists of $k$ pieces of rank 1 and $\ell$ pieces of rank 2, and has no connected component of type W. Consequently, let $X_P(\xx,q;\mu) = \sum_\lambda c_\lambda(q) e_\lambda(\xx)$, then
\[
c_{(2^\ell,1^{k-\ell})}(q) = \sum_H q^{\asc_P(H)},
\]
where $H$ ranges over such heaps of type $\mu$.
\end{thm}
\begin{exam}
Let $P=P(2,3,4,5,5)$ and $\mu=(1^5)$ (see \cref{fig:heap_orbit_2345}).
There are two connected heaps of type $\mu$ of rank 2; one is of
type W while the other is not.
Then by \cref{thm:m_two_column}, we have $c_{2,2,1}(q) = q^2$.
\end{exam}
\begin{cor} \label{cor:2_column_unimodal}
  Let \( P \) be a natural unit interval order on \( [n] \),
  and \( X_P(\xx,q) = \sum_\lambda c_\lambda(q) e_\lambda(\xx) \).
  Let \( n_e \) and \( n_o \) be the numbers of connected
  components of \( P \) consisting of even and odd vertices, respectively.
  Then for a partition \( \lambda \) of 2-column shape,
  \[
    c_\lambda(q) = 
    \begin{cases}
      q^{(n-2n_e-n_o)/2} (1+q)^{n_e} & \mbox{if \( P \) is triangle-free and \( \lambda'=((n+n_o)/2, (n-n_o)/2) \),} \\ 
      0 & \mbox{otherwise.}
    \end{cases}
  \]
  In particular, the coefficients \( c_\lambda(q) \) where \( \lambda \) are of
  2-column shape are unimodal.
\end{cor}

We next give a recurrence relation for $\mono_\lambda(\uu)$,
which is equivalent to Harada--Precup's conjecture~\cite[Conjecture~8.1]{HP19}.
For a natural unit interval order $P$, the \emph{height} \( h \) of $P$
the length of longest chains in $P$.
Then, by definition, $\ee_k(\uu) = 0$ for all $k>h$.

\begin{thm}[{\cite[Conjecture~8.1]{HP19}}] \label{thm:m=em}
  Let \( P \) be a natural unit interval order, and $h$ the height of $P$.
  Then, for a partition $\lambda$ of length $\ell\ge h$, we have 
  \[
    \mono_\lambda(\uu) \equiv
    \begin{cases}
      0 & \mbox{if \( \ell > h \),} \\
      \ee_h(\uu)\mono_{\lambda^-}(\uu) & \mbox{if \( \ell = h \),}
    \end{cases}
  \]
  modulo $\II_P$, where $\lambda^- = (\lambda_1-1,\dots,\lambda_\ell-1)$.
\end{thm}
By the same argument as in \cite{HP19}, \cref{thm:m=em} implies $e$-positivity of $X_P(\xx,q;\mu)$ for natural unit interval orders $P$ of height $2$.

\acknowledgements{The author would like to thank Jang Soo Kim for suggestions
to help improve some expositions. The author would also like to thank
Per Alexandersson for useful discussions.}

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

% \bibliographystyle{alpha}
% \bibliography{sample}



\end{document}
