\documentclass[ALCO,Unicode,published]{cedram}
\usepackage{color,hyperref,tikz}
\usepackage[edges]{forest}
\usepackage{shuffle}
\providecommand{\noopsort}[1]{}
\usetikzlibrary{matrix,arrows,shapes}
\usetikzlibrary{decorations.markings} \usetikzlibrary{arrows.meta}
\title{Quasisymmetric functions distinguishing trees}
\author{\firstname{Jean-Christophe} \lastname{Aval}}
\address{LaBRI, CNRS, Universit\'e de Bordeaux\\
351 cours de la Lib\'eration\\ 33405 Talence\\ France}
\email{aval@labri.fr}
\thanks{The first author was supported by the French ANR grant COMBIN\'E (19-CE48-0011).}
\author{\firstname{Karimatou} \lastname{Djenabou}}
\address{African Institute for Mathematical Sciences\\ 6 Melrose Road\\ Muizenberg 7945\\ South Africa}
\email{karimatou@aims.ac.za}
\author{\firstname{Peter} \middlename{R. W.} \lastname{McNamara}}
\address{Department of Mathematics, Bucknell University\\ Lewisburg, PA 17837\\ USA}
\email{peter.mcnamara@bucknell.edu}
%\date{\today}
\renewcommand{\labelitemi}{$\circ$}
\renewcommand{\theenumi}{\alph{enumi}}
\newcommand{\diG}{\overrightarrow{G}}
\newcommand{\diH}{\overrightarrow{H}}
\newcommand{\asc}{\mathrm{asc}}
\newcommand{\qsym}{{\it{QSym}}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\om}{\omega}
\newcommand{\anti}{\mathrm{anti}}
\newcommand{\wt}{\mathrm{wt}}
\newcommand{\KK}[1]{\overline{K}_{#1}}
\newcommand{\kpw}{K_{(P,\om)}}
\newcommand{\des}{\mathrm{des}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\co}{\mathrm{co}}
\newcommand{\inv}[1]{\overline{#1}}
\newcommand{\F}{{\mathcal F}}
\newcommand{\Cb}{\mathcal{C}}
\newcommand{\Pat}{{\mathcal P}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\wP}{\uparrow}
\newcommand{\sP}{\Uparrow}
\newcommand{\pa}
{\begin{tikzpicture}[scale=0.25]
\tikzstyle{every node}=[draw, shape=circle, inner sep=1pt];
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw (a1) -- (a3) -- (a2) -- (a4) ;
\end{tikzpicture}}
\newcommand{\pc}
{\begin{tikzpicture}[scale=0.25]
\tikzstyle{every node}=[draw, shape=circle, inner sep=1pt];
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw (a1) -- (a3) -- (a2) -- (a4) -- (a1) ;
\end{tikzpicture}}
\newcommand{\pf}
{\begin{tikzpicture}[scale=0.25]
\tikzstyle{every node}=[draw, shape=circle, inner sep=1pt];
\draw (0,1) node (a1) {};
\draw (-0.5,0) node (a2) {};
\draw (0.5,0) node (a3) {};
\draw (a2) -- (a1) ;
\draw [double distance = 1pt] (a3) -- (a1) ;
\end{tikzpicture}}
\newcommand{\pe}
{\begin{tikzpicture}[scale=0.25]
\tikzstyle{every node}=[draw, shape=circle, inner sep=1pt];
\draw (0,0) node (a1) {};
\draw (-0.5,1) node (a2) {};
\draw (0.5,1) node (a3) {};
\draw (a2) -- (a1) ;
\draw [double distance = 1pt] (a3) -- (a1) ;
\end{tikzpicture}}
\newcommand{\shiftpics}[1]{\raisebox{-0.6ex}{#1}}
\newcommand{\pac}{(\shiftpics{\pa}\,,\shiftpics{\pc})}
\newcommand{\pef}{[\shiftpics{\pe},\shiftpics{\pf}]}
\keywords{chromatic, quasisymmetric function, digraph, poset, P-partition, rooted tree}
\subjclass{05E05, 06A07, 06A11, 05C05, 05C20}
\datepublished{2023-06-19}
\begin{document}
\equalenv{proposition}{prop}
\equalenv{corollary}{coro}
\equalenv{definition}{defi}
\equalenv{remark}{rema}
\equalenv{example}{exam}
\begin{abstract}
A famous conjecture of Stanley states that his chromatic symmetric function distinguishes trees. As a quasisymmetric analogue, we conjecture that the chromatic quasisymmetric function of Shareshian and Wachs and of Ellzey distinguishes directed trees. This latter conjecture would be implied by an affirmative answer to a question of Hasebe and Tsujie about the $P$-partition enumerator distinguishing posets whose Hasse diagrams are trees. They proved the case of rooted trees and our results include a generalization of their result.
\end{abstract}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
As an extension of the chromatic polynomial $\chi_G(k)$ of a graph $G = (V,E)$, Stanley \cite{Sta95} introduced the chromatic symmetric function $X_G(\x)$ defined by
\begin{equation}\label{equ:stanley}
X_G(\x) = \sum_\kappa x_1^{\# \kappa^{-1}(1)} x_2^{\# \kappa^{-1}(2)} \cdots
\end{equation}
where the sum is over all proper colorings $\kappa : V \to \{1,2,\ldots\}$. Observe that setting $x_i=1$ for $1\leq i \leq k$ and $x_i=0$ otherwise yields $\chi_G(k)$. Two famous and unsolved conjectures appear in \cite{Sta95}. One of these, known as the Stanley--Stembridge conjecture \cite[Conj.~5.5]{StSt93}\cite[Conj.~5.1]{Sta95} is about the $e$-positivity of $X_G(\x)$ for incomparability graphs of $(\mathbf{3}+\mathbf{1})$-free posets and does not concern us here. Of more interest to us is that Stanley gave a pair of non-isomorphic graphs on five vertices (see Figure~\ref{fig:equalxg}(c) with the arrows removed) that have the same $X_G(\x)$. As a result, we say that $X_G(\x)$ does not \emph{distinguish} graphs. Stanley stated ``We do not know whether $X_G$ distinguishes trees.'' Subsequent papers, such as \cite{AMZ17,AMZ21,AlZa14,Fou03,HeJi19,HuCh20,LoSe19,MMW08,OrSc14,SST15}, have established that $X_G(\x)$ distinguishing trees is certainly worthy of being called a conjecture; for example, \cite{HeJi19} shows that $X_G(\x)$ distinguishes trees with up to 29 vertices.
We focus on a generalization of $X_G(\x)$ to labeled graphs introduced by Shareshian and Wachs \cite{ShWa16}, denoted $X_G(\x, t)$, which has an extra parameter $t$ and is now just a quasisymmetric function in general. In fact, we will use a further generalization of $X_G(\x)$ to directed graphs (digraphs) $\diG$ due to Ellzey \cite{Ell17,Ell17+,EllThesis} and denoted $X_{\diG}(\x,t)$.
Our original goal in this project was to study equality among $X_{\diG}(\x, t)$. It is not obvious if $X_{\diG}(\x, t)$ will be more or less successful at distinguishing digraphs compared to $X_G(\x)$ distinguishing graphs: there are far more digraphs than graphs for a given number of vertices, but $X_{\diG}(\x, t)$ contains more information than $X_G(\x)$. It is not hard to find digraphs with the same $X_{\diG}(\x, t)$; three such equalities are given in Figure~\ref{fig:equalxg}.
\tikzset{->-/.style={decoration={
markings,
mark=at position #1 with {\arrow[scale=1.5]{Straight Barb}}},postaction={decorate}}}
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1.5]
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\begin{scope}
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw[->-=0.55] (a1) -- (a3);
\draw[->-=0.55] (a3) -- (a2);
\draw[->-=0.55] (a3) -- (a4);
\draw[->-=0.55] (a4) -- (a2);
\end{scope}
\begin{scope}[yshift=10ex] \draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw[->-=0.55] (a3) -- (a1);
\draw[->-=0.55] (a2) -- (a3);
\draw[->-=0.55] (a4) -- (a3);
\draw[->-=0.55] (a2) -- (a4);
\end{scope}
\end{scope}
\begin{scope}
\draw (0.5,-0.75) node {(a)};
\end{scope}
\begin{scope}[xshift=15ex]
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\begin{scope}
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw[->-=0.55] (a1) -- (a3);
\draw[->-=0.55] (a3) -- (a4);
\draw[->-=0.55] (a2) -- (a1);
\draw[->-=0.75] (a4) -- (a1);
\draw[->-=0.35] (a3) -- (a2);
\draw[->-=0.55] (a4) to [bend left=20] (a2);
\draw[->-=0.55] (a2) to [bend left=20] (a4);
\end{scope}
\begin{scope}[yshift=10ex]
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw[->-=0.55] (a1) -- (a3);
\draw[->-=0.55] (a3) -- (a4);
\draw[->-=0.55] (a1) -- (a2);
\draw[->-=0.75] (a4) -- (a1);
\draw[->-=0.75] (a2) -- (a3);
\draw[->-=0.55] (a4) to [bend left=20] (a2);
\draw[->-=0.55] (a2) to [bend left=20] (a4);
\end{scope}
\end{scope}
\begin{scope}
\draw (0.5,-0.75) node {(b)};
\end{scope}
\end{scope}
\begin{scope}[xshift=30ex]
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\begin{scope}
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw (2,0) node (a5) {};
\draw[->-=0.55] (a1) -- (a3);
\draw[->-=0.55] (a1) -- (a2);
\draw[->-=0.55] (a2) -- (a3);
\draw[->-=0.55] (a2) -- (a4);
\draw[->-=0.55] (a3) -- (a4);
\draw[->-=0.55] (a4) -- (a5);
\end{scope}
\begin{scope}[yshift=10ex]
\draw (0,0) node (a1) {};
\draw (0,1) node (a2) {};
\draw (1,0.5) node (a3) {};
\draw (2,0) node (a4) {};
\draw (2,1) node (a5) {};
\draw[->-=0.55] (a1) -- (a2);
\draw[->-=0.55] (a1) -- (a3);
\draw[->-=0.55] (a2) -- (a3);
\draw[->-=0.55] (a3) -- (a4);
\draw[->-=0.55] (a3) -- (a5);
\draw[->-=0.55] (a4) -- (a5);
\end{scope}
\end{scope}
\begin{scope}
\draw (1,-0.75) node {(c)};
\end{scope}
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Pairs of digraphs with equal chromatic quasisymmetric functions}
\label{fig:equalxg}
\end{figure}
One way to bring Stanley's conjecture into the quasisymmetric setting would be by stating that $X_{\diG}(\x, t)$ distinguishes directed acyclic graphs, but (a) and (c) of Figure~\ref{fig:equalxg} show that such a statement is false. Instead, we offer the following conjecture, which is a natural extension of Stanley's conjecture to the quasisymmetric setting; it is stated as a question in \cite{AlSu21}.
\begin{conjecture}\label{con:chromatic_trees}
$X_{\diG}(\x, t)$ distinguishes directed trees.
\end{conjecture}
In other words, the conjecture states that if directed trees
$\diG$ and $\diH$ are not isomorphic then $X_{\diG}(\x, t) \neq X_{\diH}(\x, t)$. Our approach to tackling Conjecture~\ref{con:chromatic_trees} will be to translate it into a question about posets. When $\diG$ is a directed acyclic graph, we can represent $\diG$ as a poset by saying $v_i \leq v_j$ if there is a directed path from $v_i$ to $v_j$. In other words, draw $\diG$ so that all the edges point upwards on the page; removing the arrows results in a Hasse diagram of a poset, possibly with some redundant edges; see Figure~\ref{fig:dg2poset}. Let $P$ denote the resulting poset. As we will see, the coefficient of the highest power of $t$ that appears in $X_{\diG}(\x, t)$ will be the well-known strict $P$-partition enumerator $\KK{P}(\x)$, a fact previously mentioned in \cite[Theorem~7.4]{AlSu21} and \cite[p.~11]{Ell17+}. Obviously two chromatic quasisymmetric functions are different if their coefficients on the highest power of $t$ are different. So to prove Conjecture~\ref{con:chromatic_trees} it suffices to prove the following conjecture. A poset being a tree simply means its Hasse diagram is a~tree.
\begin{conjecture}\label{con:poset_trees}
$\KK{P}(\x)$ distinguishes posets that are trees.
\end{conjecture}
We have verified this conjecture for all such posets with at most 11 elements. A main advantage of the poset setting is that Conjecture~\ref{con:poset_trees}, and equality among $\KK{P}$ in general, has already been studied in the literature as we detail in Section~\ref{sec:poset_results}. In fact, Conjecture~\ref{con:poset_trees} appears as a question in \cite[Problem~6.1]{HaTs17}. Section~\ref{sec:prelims} will give the necessary background, including definitions of the quasisymmetric functions mentioned above. While we only needed the \emph{strict} $P$-partition enumerator above, in Section~\ref{sec:strict_weak_edges}, we consider the original $(P,\om)$-partition enumerator $\kpw(\x)$ which allows for a mixture of strict and weak relations. Such $(P,\om)$ are called $\emph{labeled posets}$. Interestingly, $\kpw$ does \emph{not} distinguish labeled posets that are trees, but we offer the following conjecture. A poset that is a tree is said to be a \emph{rooted tree} if it has a unique minimal~element.
\begin{conjecture}\label{con:labeled_rooted_trees}
$\kpw(\x)$ distinguishes labeled posets that are rooted trees.
\end{conjecture}
Hasebe and Tsujie \cite{HaTs17} have shown the case when all the relations are weak (or all strict), and we generalize their result by establishing Conjecture~\ref{con:labeled_rooted_trees} for a class of labeled rooted trees that we call \emph{fair trees}. The class of fair trees interpolates between rooted trees with all weak edges and those with all strict edges. We believe our result on fair trees (Theorem~\ref{thm:fair-trees}) is the first non-trivial result stating that $\kpw(\x)$ distinguishes a class of posets with a mixture of strict and weak edges. We conclude in Section~\ref{sec:conclusion} with several directions for further study.
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}\label{sec:prelims}
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The chromatic symmetric function for directed graphs}
%%%%%%%%%%%%%%%%%%%%%%%%%
Let $\mathbb{P}$ denote the set of positive integers. For a positive integer $n$, we write $[n]$ to denote the set $\{1,\ldots,n\}$.
\begin{definition}[\cite{Ell17+}]\label{def:xg}
Let $\diG = (V,E)$ be a directed graph. Given a proper coloring $\kappa: V \to \mathbb{P}$ of $\diG$, we define an \emph{ascent} of $\kappa$ to be a directed edge $(v_i, v_j) \in E$ with $\kappa(v_i) < \kappa(v_j)$, and we let $\asc(\kappa)$ denote the number of ascents of $\kappa$. The chromatic quasisymmetric function of $\diG$ is
\begin{equation}\label{equ:xgt}
X_{\diG}(\x, t) = \sum_{\kappa} t^{\asc(\kappa)} x_1^{\# \kappa^{-1}(1)} x_2^{\# \kappa^{-1}(2)} \cdots
\end{equation}
where the sum is over all proper colorings of $\diG$.
\end{definition}
Setting $t=1$ yields Stanley's chromatic symmetric function $X_G(\x)$ of~\eqref{equ:stanley}, where $G$ denotes the undirected version of $\diG$. When $\diG$ is a directed acyclic graph, which is the case of most interest to us, $X_{\diG}(\x, t)$ coincides with the chromatic quasisymmetric function of Shareshian and Wachs. We use the digraph setting because in the labeled graph setting of Shareshian--Wachs, there are lots of trivial equalities among $X_G(\x, t)$ that result just from relabeling.
\begin{example}
Let $\diG$ be the 3-element path with the directions as shown below. With colors $a**-=0.6] (v1) -- (v2);
\draw[->-=0.6] (v3) -- (v2);
\end{tikzpicture}
\ \ \ \ \ \ \ \ \ \ \
\]
\smallskip
\[
\begin{array}{ccc|c}
\kappa(v_1) & \kappa(v_2) & \kappa(v_3) & \asc(\kappa) \\ \hline
a & b & c & 1\\
a & c & b & 2\\
b & a & c & 0\\
b & c & a & 2\\
c & a & b & 0\\
c & b & a & 1\\
a & b & a & 2\\
b & a & b & 0
\end{array}
\]
Thus
\[
X_{\diG}(\x,t) = (2 + 2t + 2t^2)M_{111} + t^2 M_{21} + M_{12}\,,
\]
where $M$ denotes the basis of monomial quasisymmetric functions (see Subsection~\ref{sub:qsym} for the necessary background on quasisymmetric functions).
Setting $t=1$ gives $X_G(\x) = 6m_{111} + m_{21}$ from which we get $\chi_G(k) = 6 \binom{k}{3} +k(k-1) = k(k-1)^2$, as expected.
\end{example}
Let us make a couple of observations about types of $X_{\diG}(\x,t)$-equality that arise. By setting $t=1$, we know equal $X_{\diG}(\x,t)$ means the underlying undirected graphs must have equal $X_G(\x)$ and the examples in Figure~\ref{fig:equalxg} show two scenarios: either the underlying undirected graphs are isomorphic, or they are not isomorphic but have equal $X_G(\x)$. The $X_G(\x)$-equality implied by Figure~\ref{fig:equalxg}(c) is the one given by Stanley in \cite{Sta95}.
Figure~\ref{fig:equalxg}(a) shows an example of $X_{\diG}(\x, t)$ being invariant under reversal of all the edge directions. Letting $\alpha^{\mathrm{rev}}$ denote the reversal of the composition $\alpha$, this invariance will hold whenever the coefficients of $M_\alpha$ and $M_{\alpha ^{\mathrm{rev}}}$ in $X_{\diG}(\x, t)$ are equal for all $\alpha$, so in particular when $X_{\diG}(\x, t)$ is symmetric \cite[Cor.~2.7]{ShWa16} \cite[Prop.~2.6]{Ell17+}. But not all equalities among $X_{\diG}(\x, t)$ with isomorphic underlying graphs arise from reversal of all edges, as shown by Figure~\ref{fig:equalxg}(b).
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The poset perspective}
%%%%%%%%%%%%%%%%%%%%%%%%%
As mentioned in the Introduction, when $\diG$ is a directed acyclic graph we can view it as a poset; see Figure~\ref{fig:dg2poset} for an example, with a coloring given by numbers next to each vertex.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1.0]
\begin{scope}
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\draw (0,0) node (e) {$v_4$};
\draw (-1,1) node (b) {$v_1$};
\draw (1,1) node (d) {$v_5$};
\draw (0,2) node (c) {$v_2$};
\draw (-2.4,1) node (a) {$v_3$};
\draw[->-=0.55] (a) -- (b);
\draw[->-=0.55] (c) -- (b);
\draw[->-=0.55] (e) -- (b);
\draw[->-=0.55] (d) -- (e);
\draw[->-=0.55] (d) -- (c);
\draw[->-=0.55] (d) -- (b);
\end{scope}
\draw (0.45, 0) node {\textcolor{blue}{\textbf{2}}};
\draw (-2.4, 1.5) node {\textcolor{blue}{\textbf{1}}};
\draw (-1, 1.5) node {\textcolor{blue}{\textbf{5}}};
\draw (0.45, 2) node {\textcolor{blue}{\textbf{3}}};
\draw (1, 1.5) node {\textcolor{blue}{\textbf{1}}};
\draw (0,-1) node {(a)};
\end{scope}
\begin{scope}[xshift=10em]
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\draw (0,0) node (d) {$v_5$};
\draw (-1,1) node (e) {$v_4$};
\draw (1,1) node (c) {$v_2$};
\draw (0,2) node (b) {$v_1$};
\draw (2,1) node (a) {$v_3$};
\draw (d) -- (e) -- (b) -- (a);
\draw (d) -- (c) -- (b);
\end{scope}
\draw (0.45, 0) node {\textcolor{blue}{\textbf{1}}};
\draw (2, 1.5) node {\textcolor{blue}{\textbf{1}}};
\draw (-1, 1.5) node {\textcolor{blue}{\textbf{2}}};
\draw (-0.45, 2) node {\textcolor{blue}{\textbf{5}}};
\draw (1, 0.52) node {\textcolor{blue}{\textbf{3}}};
\draw (0,-1) node {(b)};
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Converting from a proper coloring of a digraph to a strict $P$-partition. The numbers next to each node correspond to a coloring in the digraph on the left and the corresponding $(P,\om)$-partition of the labeled poset on the right.}
\label{fig:dg2poset}
\end{figure}
Now consider the coefficient of the highest power of $t$ that appears in $X_{\diG}(\x, t)$. This coefficient enumerates colorings that strictly increase along every directed edge, as in Figure~\ref{fig:dg2poset}(a). We now compare this to the definition of Stanley's $(P,\om)$-partitions.
Let $P$ be a poset with $n$ elements; we write $|P|=n$. Denote the order relation on $P$ by $\leq_P$, while $\leq$ denotes the usual order on the positive integers. A \emph{labeling} of $P$ is a bijection $\om : P \to [n]$. A \emph{labeled poset} $(P,\om)$ is then a poset $P$ with an associated labeling $\om$.
\begin{definition}\label{def:popartition}
For a labeled poset $(P,\om)$, a \emph{$(P,\om)$-partition} is a map $f$ from $P$ to the positive integers satisfying the following two conditions:
\begin{itemize}
\item if $a <_P b$, then $f(a) \leq f(b)$, \ie $f$ is order-preserving;
\item if $a <_P b$ and $\om(a) > \om(b)$, then $f(a) < f(b)$.
\end{itemize}
\end{definition}
In other words, a $(P,\om)$-partition is an order-preserving map from $P$ to the positive integers with certain strictness conditions determined by $\om$. Examples of $(P,\om)$-partitions $f$ are given in Figure~\ref{fig:popartitions}, where the images under $f$ are written in bold and blue next to the nodes.
The meaning of the double edges in the figure follows from the following observation about Definition~\ref{def:popartition}. For $a, b \in P$, we say that $a$ is \emph{covered} by $b$ in $P$, denoted $a \prec_P b$, if $a <_P b$ and there does not exist $c$ in $P$ such that $a <_P c <_P b$. Note that a definition equivalent to Definition~\ref{def:popartition} is obtained by replacing both appearances of the relation $a <_P b$ with the relation $a \prec_P b$. In other words, we require that $f$ be order-preserving along the edges of the Hasse diagram of $P$, with $f(a) < f(b)$ when the edge $a \prec_P b$ satisfies $\om(a) > \om(b)$. With this in mind, we will consider those edges $a \prec_P b$ with $\om(a) > \om(b)$ as \emph{strict edges} and we will represent them in Hasse diagrams by double lines. Similarly, edges $a \prec_P b$ with $\om(a) < \om(b)$ will be called \emph{weak edges} and will be represented by single lines.
From the point-of-view of $(P,\om)$-partitions, the labeling $\om$ only determines which edges are strict and which are weak. Therefore, we say that two labeled posets $(P,\om)$ and $(Q,\om')$ are \emph{isomorphic} if $P$ and $Q$ are isomorphic as posets and they have equivalent sets of strict and weak edges according to a poset isomorphism. Thus many of our figures from this point on will not show the labeling $\om$, but instead show some collection of strict and weak edges determined by an underlying $\om$.
\begin{center}
\begin{figure}[htbp]
\begin{tikzpicture}[scale=0.7]
\begin{scope}
\begin{scope}
\tikzstyle{every node}=[shape=circle, inner sep=2pt];
\draw (0,0) node[draw] (a1) {1} +(0.6,-0.3) node {\textcolor{blue}{\textbf{4}}};
\draw (0,1.5) node[draw] (a4) {4} +(0.0,0.65) node {\textcolor{blue}{\textbf{3}}};
\draw (-1.5,2.5) node[draw] (a2) {2} +(-0.6,-0.3) node {\textcolor{blue}{\textbf{4}}};
\draw (1.5,2.5) node[draw] (a3) {3} +(0.6,-0.3) node {\textcolor{blue}{\textbf{7}}};
\draw (a2) -- (a1) -- (a3);
\draw[double distance=2pt] (a3) --(a4) -- (a2);
\end{scope}
\draw (0,-1.3) node {(a)};
\end{scope}
\begin{scope}[xshift=15em]
\begin{scope}
\tikzstyle{every node}=[shape=circle, inner sep=2pt];
\draw (0,0) node[draw] (a1) {1} +(0.6,-0.3) node {\textcolor{blue}{\textbf{4}}};
\draw (0,1.5) node[draw] (a4) {2} +(0.0,0.65) node {\textcolor{blue}{\textbf{3}}};
\draw (-1.5,2.5) node[draw] (a2) {3} +(-0.6,-0.3) node {\textcolor{blue}{\textbf{4}}};
\draw (1.5,2.5) node[draw] (a3) {4} +(0.6,-0.3) node {\textcolor{blue}{\textbf{4}}};
\draw (a2) -- (a1) -- (a3);
\draw(a3) --(a4) -- (a2);
\end{scope}
\draw (0,-1.3) node {(b)};
\end{scope}
\begin{scope}[xshift=30em]
\begin{scope}
\tikzstyle{every node}=[shape=circle, inner sep=2pt];
\draw (0,0) node[draw] (a1) {4} +(0.6,-0.3) node {\textcolor{blue}{\textbf{1}}};
\draw (0,1.5) node[draw] (a4) {3} +(0.0,0.65) node {\textcolor{blue}{\textbf{3}}};
\draw (-1.5,2.5) node[draw] (a2) {1} +(-0.6,-0.3) node {\textcolor{blue}{\textbf{4}}};
\draw (1.5,2.5) node[draw] (a3) {2} +(0.6,-0.3) node {\textcolor{blue}{\textbf{7}}};
\draw[double distance=2pt] (a2) -- (a1) -- (a3);
\draw[double distance=2pt] (a3) --(a4) -- (a2);
\end{scope}
\draw (0,-1.3) node {(c)};
\end{scope}
\end{tikzpicture}
\caption{Examples of $(P,\om)$-partitions}
\label{fig:popartitions}
\end{figure}
\end{center}
If $\om$ is order-preserving, as in Figure~\ref{fig:popartitions}(b), then $P$ is said to be \emph{naturally labeled} and all the edges are weak. In this case, we typically omit reference to the labeling and so a $(P,\om)$-partition is then traditionally called a $P$-partition. At the other extreme, when $\om$ is order-reversing, as in Figure~\ref{fig:popartitions}(c), $f$ must strictly increase along each edge. Such $(P,\om)$-partitions that are required to strictly increase along each edge will be called \emph{strict $P$-partitions}.
Returning to Figure~\ref{fig:dg2poset}, the key observation is now clear: the proper colorings of a directed acyclic graph $\diG$ that contribute to the coefficient of the highest power of $t$ in $X_{\diG}(\x,t)$ are in bijection with strict $P$-partitions of the corresponding poset $P$.
To make the algebraic connection, the well-known $(P,\om)$-partition enumerator is defined by
\begin{equation}\label{equ:kp}
\kpw(\x) = \sum_{f} x_1^{\#f^{-1}(1)} x_2^{\# f^{-1}(2)} \cdots
\end{equation}
where the sum is over all $(P,\om)$-partitions $f:P \to \mathbb{P}$. When all the edges of $(P,\om)$ are weak, so the sum is over $P$-partitions, we will denote the $P$-partition enumerator $\kpw(\x)$ simply by $K_P(\x)$ or just $K_P$. Similarly, we will use $\KK{P}$ to denote $\kpw(\x)$ when all the edges are strict, thus enumerating strict $P$-partitions. Comparing~\eqref{equ:xgt} and~\eqref{equ:kp} when $P$ is the poset corresponding to a directed acyclic graph $\diG$, we see that $\KK{P}(\x)$ is exactly the coefficient of the highest power of $t$ in $X_{\diG}(\x,t)$. This connection between $\KK{P}$ and $X_{\diG}(\x, t)$ has previously been mentioned in \cite[Theorem~7.4]{AlSu21} \cite[p.~11]{Ell17+}. As a corollary, if Conjecture~\ref{con:poset_trees} is true, then so is Conjecture~\ref{con:chromatic_trees}.
With this implication now established, we will work almost entirely in the poset setting. Although the direct connection between $X_{\diG}(\x, t)$ and $\kpw$ uses the setting of strict $P$-partitions and $\KK{P}$, most of the results in the literature work with $P$-partitions and $K_P$. However, for equality questions, the two settings are equivalent since $\KK{P}$ can be obtained from $K_P$ and vice-versa; see \cite[\S 3]{McWa14} for the full details of this equivalence and involutions on $(P,\om)$-partition enumerators. In particular, Conjecture~\ref{con:poset_trees} can be restated as the assertion that $K_P(\x)$ distinguishes posets that are trees.
\begin{remark}
In addition to its simple statement, Conjecture~\ref{con:poset_trees} has the virtue that some natural more general statements are false. The first example of non-isomorphic posets with the same $K_P$ was given in \cite{McWa14} and appears in Figure~\ref{fig:equal_kp}(a). A $\emph{bowtie}$ is the poset consisting of elements $a_1,a_2,b_1,b_2$ with cover relations $a_i < b_j$ for all $i,j$. Notice that each poset in Figure~\ref{fig:equal_kp}(a) has a bowtie as an induced subposet. Otherwise, we say the poset is \emph{bowtie-free}. Weakening the tree hypothesis of Conjecture~\ref{con:poset_trees} to bowtie-free results in a false statement, with Figure~\ref{fig:equal_kp}(b) being the smallest counterexample.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1.0]
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\begin{scope}
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw (-1,1) node (a5) {};
\draw (0,2) node (a6) {};
\draw (1,2) node (a7) {};
\draw (a1) -- (a5) -- (a7) -- (a4) -- (a2) -- (a6) -- (a3) -- (a1);
\end{scope}
\begin{scope}[yshift=18ex]
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw (-1,1) node (a5) {};
\draw (0,2) node (a6) {};
\draw (1,2) node (a7) {};
\draw (a1) -- (a5) -- (a6) -- (a3) -- (a1) -- (a7) -- (a4) -- (a2) -- (a6);
\end{scope}
\end{scope}
\begin{scope}
\draw (0.5,-0.75) node {(a)};
\end{scope}
\begin{scope}[xshift=25ex]
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\begin{scope}
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (1,1) node (a4) {};
\draw (-1,1) node (a5) {};
\draw (0,2) node (a6) {};
\draw (1,2) node (a7) {};
\draw (2,0) node (a8) {};
\draw (2,1) node (a9) {};
\draw (2,2) node (a10) {};
\draw (a1) -- (a5) -- (a10) -- (a9) -- (a8) -- (a7) -- (a4) -- (a2) -- (a6) -- (a3) -- (a1);
\end{scope}
\begin{scope}[yshift=18ex]
\draw (0,0) node (a1) {};
\draw (1,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (-1,1) node (a5) {};
\draw (0,2) node (a6) {};
\draw (1,2) node (a7) {};
\draw (2,0.6) node (a8) {};
\draw (2,1.4) node (a9) {};
\draw (3,0) node (a10) {};
\draw (3,2) node (a11) {};
\draw (a1) -- (a5) -- (a6) -- (a2) -- (a9) -- (a11) -- (a10) -- (a8) -- (a7) -- (a1);
\draw (a1) -- (a3) -- (a6);
\end{scope}
\end{scope}
\begin{scope}
\draw (1,-0.75) node {(b)};
\end{scope}
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Pairs of posets with equal $P$-partition enumerators}
\label{fig:equal_kp}
\end{figure}
Conjecture~\ref{con:poset_trees} equivalently states that for posets $P$ and $Q$ that are trees, if $\KK{P} = \KK{Q}$ then $P$ and $Q$ are isomorphic. We can consider weakenings of the equality hypothesis in this statement. The \emph{$F$-support} of a quasisymmetric function $f$ is the set of compositions $\alpha$ for which the coefficient of $F_\alpha$ is non-zero when $f$ is expanded in the $F$-basis. But the $F$-support of $\KK{P}$ and $\KK{Q}$ being equal does not imply that $P$ and $Q$ are isomorphic, with a counterexample given by the posets in Figure~\ref{fig:f_support}, which both have $F$-support $\{221, 212, 122, 2111, 1211, 1121, 1112, 11111\}$.
In contrast, see Subsection~\ref{sub:ps} for versions of Conjecture~\ref{con:poset_trees} that use much less information than in $\KK{P}(\x)$ to distinguish posets that are trees.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1.0]
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\begin{scope}
\draw (1,0) node (a1) {};
\draw (0,0) node (a2) {};
\draw (1,1) node (a3) {};
\draw (0,1) node (a4) {};
\draw (1,2) node (a5) {};
\draw[double distance=2pt] (a2) -- (a4) -- (a1) -- (a3) -- (a5);
\end{scope}
\begin{scope}[xshift=10em]
\draw (0,0) node (a1) {};
\draw (0,1) node (a2) {};
\draw (1,1) node (a3) {};
\draw (0,2) node (a4) {};
\draw (1,2) node (a5) {};
\draw[double distance=2pt] (a1) -- (a2) -- (a4) -- (a3) -- (a5);
\end{scope}
\end{tikzpicture}
\end{center}
\caption[caption]{The strict $P$-partition enumerators of these two posets have the same $F$-support}
\label{fig:f_support}
\end{figure}
\end{remark}
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Quasisymmetric functions}\label{sub:qsym}
%%%%%%%%%%%%%%%%%%%%%%%%%
It follows directly from its definition that $\kpw$ is a quasisymmetric function. In fact, $\kpw$ served as a motivating example for Gessel's original definition \cite{Ges84} of quasisymmetric functions.
For our purposes, quasisymmetric functions are elements of $\mathbb{Z}[[x_1, x_2, \ldots]]$ and we denote the ring of quasisymmetric functions by \qsym. We will make use of both of the classical bases for \qsym. If $\alpha = (\alpha_1, \alpha_2, \ldots, \alpha_k)$ is a composition of $n$, then we define the \emph{monomial quasisymmetric function} $M_\alpha$ by
\[
M_\alpha = \sum_{i_1 < i_2 < \ldots < i_k} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2} \cdots x_{i_k}^{\alpha_k}.
\]
As we know, compositions $\alpha = (\alpha_1, \alpha_2, \ldots, \alpha_k)$ of $n$ are in bijection with subsets of $[n-1]$, and let $S(\alpha)$ denote the set
$\{\alpha_1, \alpha_1+\alpha_2, \ldots, \alpha_1+\alpha_2 + \cdots+ \alpha_{k-1}\}$. Thus we also denote $M_\alpha$ by $M_{S(\alpha), n}$. Notice that these two notations are distinguished by the latter one including the subscript $n$; this subscript is helpful since $S(\alpha)$ does not uniquely determine $n$.
The second classical basis is composed of the \emph{fundamental quasisymmetric functions} $F_\alpha$ defined by
\begin{equation}\label{equ:F2M}
F_\alpha = F_{S(\alpha), n} = \sum_{S(\alpha) \subseteq T \subseteq [n-1]} M_{T,n}\,.
\end{equation}
The relevance of this latter basis to $\kpw$ is due to Theorem~\ref{theo:KinF} below, which first appeared in \cite{StaThesis71,StaThesis} and, in the language of quasisymmetric functions, in \cite{Ges84}.
Every permutation $\pi \in S_n$ has a descent set $\des(\pi)$ given by $\{i \in [n-1] : \pi(i) > \pi(i+1)\}$, and we will call the corresponding composition of $n$ the \emph{descent composition} of $\pi$, denoted $\co(\pi)$. For example, if $\pi = 243561$, then $\des(\pi) = \{2,5\}$ and $\co(\pi) = 231$. Let $\L(P,\om)$ denote the set of all linear extensions of $P$, regarded as permutations of the $\om$-labels of $P$. For example, for the labeled poset in Figure~\ref{fig:popartitions}(a), $\L(P,\om) = \{1423, 1432, 4123, 4132\}$.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\tikzstyle{every node}=[shape=circle, inner sep=2pt];
\draw (0,0) node[draw] (a1) {1};
\draw (0,1.5) node[draw] (a3) {3};
\draw (-1.5,2.5) node[draw] (a2) {2};
\draw (1.5,2.5) node[draw] (a4) {4};
\draw (a1) -- (a3) -- (a4);
\draw[double distance=2pt] (a3) -- (a2);
\end{tikzpicture}
\caption{The labeled poset of Example~\ref{exa:kexpansion}}
\label{fig:labeled_poset}
\end{center}
\end{figure}
\begin{theorem}[\cite{Ges84,StaThesis71,StaThesis}]\label{theo:KinF}
Let $(P,\om)$ be a labeled poset with $|P|=n$. Then
\[
\kpw = \sum_{\pi \in \L(P,\om)} F_{\des(\pi), n} = \sum_{\pi \in \L(P,\om)} F_{\co(\pi)}\,.
\]
\end{theorem}
\begin{example}\label{exa:kexpansion}
The labeled poset $(P,\om)$ of Figure~\ref{fig:labeled_poset} has $\L(P,\om) = \{1324, 1342\}$ and hence
\begin{align*}
\kpw ={}& F_{\{2\},4} + F_{\{3\},4} \\
={}& F_{22} + F_{31} \\
= \begin{split} {}&(M_{\{2\},4} + M_{\{1,2\},4} + M_{\{2,3\},4} + M_{\{1,2,3\},4}) \\{}& + (M_{\{3\},4} + M_{\{1,3\},4} + M_{\{2,3\},4} + M_{\{1,2,3\},4}) \end{split} \\
={}& M_{22} + M_{31} + M_{112} + 2M_{211} + M_{121} + 2M_{1111}.
\end{align*}
\end{example}
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Consequences of the poset viewpoint}\label{sec:poset_results}
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
As mentioned in the Introduction, an advantage of the poset viewpoint is that equality among $K_P$ has already been studied in the literature. In this largely expository section, we gather together these results, especially those relevant to Conjecture~\ref{con:poset_trees}. As the $K_P$ notation indicates, these results are confined to posets with all weak edges.
Results from the literature mostly fall into three classes: irreducibility, classes of posets within which we know that the $P$-partition enumerator distinguishes the posets, and necessary conditions on $P$ and $Q$ for $K_P = K_Q$.
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Irreducibility}
%%%%%%%%%%%%%%%%%%%%%%%%%
If $P$ disconnects into two posets $P_1$ and $P_2$, then it follows from the definition of $K_P$ that $K_P = K_{P_1}K_{P_2}$. On the other hand, a key result from \cite{LiWe21} is that if $P$ is connected, then $K_P$ is irreducible in \qsym. Moreover, \qsym\ is known to be a unique factorization domain \cite{Haz01,LaPy08,MaRe95}. As a consequence, Liu and Weselcouch deduce the following result.
\begin{corollary}[{\cite[Corollary~4.20]{LiWe21}}]\label{cor:factors}
For a poset $P$, the irreducible factorization of $K_P$ is given by $K_P = \prod_i K_{P_i}$, where the $P_i$ are the connected components of $P$.
\end{corollary}
Therefore, when studying $K_P = K_Q$, it suffices to consider the case when both $P$ and $Q$ are connected (see \cite[Corollary~4.21]{LiWe21}). Additionally, a proof of Conjecture~\ref{con:poset_trees} would also mean that $K_P$ distinguishes forests.
Returning briefly to the setting of the chromatic quasisymmetric function $X_{\diG}$ we get the following consequence.
\begin{proposition}
For directed acyclic graphs $\diG$ and $\diH$ with $X_{\diG}(\x,t) = X_{\diH}(\x,t)$, if $\diG$ is connected then so is $\diH$.
\end{proposition}
\begin{proof}
If $\diH$ has connected components $\diH_1, \ldots, \diH_r$ with $r\geq 2$, then it follows from Definition~\ref{def:xg} that $X_{\diH}(\x,t)$ factors as
\[
X_{\diH}(\x,t) = X_{\diH_1}(\x,t) \cdots X_{\diH_r}(\x,t).
\]
Thus
\begin{equation}\label{equ:connected_digraph}
X_{\diG}(\x,t) = X_{\diH_1}(\x,t) \cdots X_{\diH_r}(\x,t).
\end{equation}
Now consider the irreducibility of the coefficient of the highest power of $t$ on both sides of~\eqref{equ:connected_digraph}. On the left-hand side, this is $K_P$ for the poset $P$ corresponding to $\diG$, and $K_P$ is irreducible since $\diG$ and hence $P$ is connected. On the right-hand side, this coefficient is the product of the coefficients of the highest powers of $t$ in each $X_{\diH_i}(\x,t)$, which is a contradiction since we know these coefficients are not constants.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Distinguishing within classes of posets}\label{sub:classes}
%%%%%%%%%%%%%%%%%%%%%%%%%
The $P$-partition enumerator $K_P$ is known to distinguish posets within each of the following classes.
\begin{itemize}
\item Rooted trees \cite{HaTs17,Zho20+}, i.e. posets that are trees with a single minimal element.
\item More generally, posets that are both bowtie-free and \textsf{N}-free \cite{HaTs17}. As one would expect, \textsf{N} is the poset consisting of elements $a_1,a_2,b_1,b_2$ whose cover relations are $a_1 < b_1 > a_2 < b_2$, and a poset is \textsf{N}-free if it does not contain \textsf{N} as an induced subposet.
\item Series-parallel posets \cite[Theorem~5.2]{LiWe21}. These can be defined in two ways. They are the posets that can be formed by repeated operations of disjoint union and ordinal sum. Equivalently, they are the \textsf{N}-free posets.
\item Posets of width two \cite{LiWe20}.
\item Posets whose Greene shape is a hook \cite{LiWe20}. The \emph{Greene shape} of a poset $P$ is the partition $(c_1-c_0, c_2-c_1, \ldots)$ where $c_i$ is the maximum cardinality of a union of $k$ chains of $P$. So a poset whose Greene shape is the hook $(j, 1^i)$ has a maximal chain with $j$ elements and $i$ additional elements which form an ~antichain.
\item Posets with Greene shape $(k, 2, 1, 1, \ldots, 1)$ for some $k\geq2$ \cite{LiWe20}.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Necessary conditions for equality}
%%%%%%%%%%%%%%%%%%%%%%%%%
If $K_P = K_Q$, then all the statements in the next list hold. In the same way that knowledge of $K_P$ is equivalent to knowledge of $\KK{P}$, both are equivalent to knowledge of $K_{P^*}$ where $P^*$ is the dual of $P$ (see, for example, \cite[\S 3]{McWa14}). Thus all the statements below have dual versions.
\begin{itemize}
\item $P$ and $Q$ obviously have the same number of vertices; if they are not trees, they need not have the same number of edges, as shown by Figure~\ref{fig:equal_kp}(a).
\item By Theorem~\ref{theo:KinF}, $P$ and $Q$ have the same number of linear extensions.
\item The \emph{jump} of an element $p$ of $P$ is defined to be the length (number of edges) of the longest chain from $p$ down to a minimal element of $P$. Then $P$ and $Q$ have the same number of elements of jump $i$ for all $i$ \cite{McWa14}. This can sometimes be a quick way to show that $K_P \neq K_Q$\,.
\item $K_{P_i} = K_{Q_i}$, where $P_i$ denotes the induced subposet of $P$ consisting of elements of jump at least $i$ \cite{McWa14}. For example, with $i=1$, we get that $K_{P^-} = K_{Q^-}$, where $P^-$ denotes the result of deleting all the minimal elements from $P$.
\item The \emph{up-jump} of $p$ denotes the length of the longest chain from $p$ to a maximal element, and define the \emph{jump-pair} of $P$ to be (jump of $p$, up-jump of $p$). Then for all $i$ and $j$, the number of elements with jump pair $(i,j)$ is the same for $P$ as for $Q$ \cite{LiWe20}.
\item Let $\anti_{k,i,j}(P)$ denote the number of $k$-element order ideals $I$ of $P$ such that $I$ has $i$ maximal elements and $P\setminus I$ has $j$ minimal elements. Then $\anti_{k,i,j}(P) = \anti_{k,i,j}(Q)$ for all $i,j,k$ \cite{LiWe20}.
\item Summing over $j$ and $k$ in the previous item, we get that $P$ and $Q$ have the same number of antichains of each size, as conjectured in \cite{McWa14} and shown in \cite{LiWe20}.
\item Suppose that for some $k$ and $i$, $P$ has a unique order ideal $I_P$ of size $k$ with $i$ maximal elements, and similarly for an order ideal $I_Q$ of $Q$. Then $K_{P\setminus I_P}$ can be determined from $K_P$ \cite[Corollary 3.6]{LiWe20} and hence $K_{P\setminus I_P} = K_{Q \setminus I_Q}$.
\item Summing over $j$ in $\anti_{k,i,j}(P)$ shows that the number of order ideals of size $k$ with $i$ maximal elements has to be the same for $P$ as for $Q$. Then there are various ways we can combine the results above. For example, the number of elements with principal order ideal of size $k$ and up-jump $j$ is the same for $P$ as for $Q$ \cite{LiWe20}.
\item The Greene shape of $P$ equals that of $Q$ \cite{LiWe20}.
\item A $P$-partition $f$ is \emph{pointed} if $f$ is surjective onto $[k]$ for some $k$ and $f^{-1}(i)$ has a unique minimal element for all $i$ with $1 \leq i \leq k$. The weight of $f$ is the composition $\wt(f) = (\#f^{-1}(1), \#f^{-1}(2), \ldots)$. The number of pointed $P$-partitions of any given weight is the same for $P$ and $Q$. This follows immediately from the result of \cite{AlSu21} that if we expand $K_P$ in the (unnormalized) power sum basis $\psi_\alpha$ of type I, then the coefficient of $\psi_\alpha$ equals the number of pointed $P$-partitions of weight $\alpha$ .
\item \cite[Lemma~4.10]{LiWe20} shows that any finite poset $P$ has a unique antichain $A$ of maximum size such that any other antichain of maximum size is contained in the order ideal $I(A)$ generated by $A$. Let $P^-$ be the subposet consisting of elements less than $A$ in $P$. Then since $K_{P^-}$ is determined by $K_P$ (also shown in \cite{LiWe20}), we must have $K_{P^-} = K_{Q^-}$. Similarly for the subposet $P^+$ above $A$.
\end{itemize}
If one is given non-isomorphic trees $T_1$ and $T_2$, it is typically straightforward to find a result on the list above that will show that they have unequal $P$-partition enumerators. However, the problem is that the result used will depend on $T_1$ and $T_2$, \ie we don't have a systematic way.
Trees of rank one are difficult enough that they are a good test case for techniques; see Figure~\ref{fig:rank_one} for a non-isomorphic pair. We can use $\anti_{k,1,j}(P)$ and $ \anti_{k,1,j}(P^*)$ to determine the degree sequences for the maximal and minimal elements, respectively; these match up in the figure. To distinguish the pair in the figure, we can use pointed $P$-partitions: the tree on the right has a pointed $P$-partition of weight $(4,1,4,2)$ but the tree on the left does not.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\begin{scope}
\draw (-2,0) node (a1) {};
\draw (-0.67,0) node (a2) {};
\draw (0.67,0) node (a3) {};
\draw (2,0) node (a4) {};
\draw (-3,2) node (b1) {};
\draw (-2,2) node (b2) {};
\draw (-1,2) node (b3) {};
\draw (0,2) node (b4) {};
\draw (1,2) node (b5) {};
\draw (2,2) node (b6) {};
\draw (3,2) node (b7) {};
\draw (a1) -- (b1);
\draw (a1) -- (b2);
\draw (a1) -- (b3) -- (a2);
\draw (b3) -- (a3) -- (b4);
\draw (a4) -- (b4);
\draw (a4) -- (b5);
\draw (a4) -- (b6);
\draw (a4) -- (b7);
\end{scope}
\begin{scope}[xshift=22em]
\draw (-2,0) node (a1) {};
\draw (-0.67,0) node (a2) {};
\draw (0.67,0) node (a3) {};
\draw (2,0) node (a4) {};
\draw (-3,2) node (b1) {};
\draw (-2,2) node (b2) {};
\draw (-1,2) node (b3) {};
\draw (0,2) node (b4) {};
\draw (1,2) node (b5) {};
\draw (2,2) node (b6) {};
\draw (3,2) node (b7) {};
\draw (a1) -- (b1);
\draw (a1) -- (b2);
\draw (a1) -- (b3) -- (a2);
\draw (a2) -- (b4) -- (a3);
\draw (a4) -- (b4);
\draw (a4) -- (b5);
\draw (a4) -- (b6);
\draw (a4) -- (b7);
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Two trees of rank one with the same degree sequences but different $K_P$}
\label{fig:rank_one}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Adding strict edges}\label{sec:strict_weak_edges}
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
This section considers extending Conjecture~\ref{con:poset_trees} in the following way, as inspired by \cite[Problem~6.2]{HaTs17}: does $\kpw$ distinguish labeled trees when we allow any mixture of strict and weak edges? The answer is ``no'' in general as shown, for example, by the labeled trees in Figure~\ref{fig:trees_equal_kpw}.
In fact, this question connects to a studied one in the realm of symmetric functions. Semistandard Young tableaux of a skew shape $\lambda/\mu$ can be considered as $(P,\om)$-partitions of a particular labeled poset; see \cite[\S7.19]{Sta99}, for example. In this case, $\kpw$ equals the skew Schur function $s_{\lambda/\mu}$\,. When $\lambda/\mu$ is a \emph{ribbon}, meaning it is connected and has no 2-by-2 block of cells, the corresponding $(P,\om)$ will be a tree. It is well known that $s_{\lambda/\mu}$ is invariant under rotation of $\lambda/\mu$ by 180$^\circ$ thus yielding an infinite class of pairs of trees with the same $\kpw$; the simplest example is in Figure~\ref{fig:trees_equal_kpw}(b). It is natural to ask if they are other pairs of ribbons, unequal under 180$^\circ$ rotation, that give rise to the same skew Schur function. The answer is ``yes'' and the full classification of such pairs is given in \cite{BTvW06}.
On the other hand, Hasebe and Tsujie \cite{HaTs17} have shown that $\kpw$ distinguishes \emph{rooted} trees with all strict (equivalently all weak) edges. In Conjecture~\ref{con:labeled_rooted_trees}, we propose that their result also holds for arbitrary labeled posets that are rooted trees. In other words, if we want $\kpw$ to distinguish trees with a mixture of strict and weak edges, restricting to rooted trees works. We have verified Conjecture~\ref{con:labeled_rooted_trees} for $n\leq 10$.
Although we have not succeeded in resolving Conjecture~\ref{con:labeled_rooted_trees}, the rest of this section focuses on results that still significantly generalize those in \cite{HaTs17}, as we next explain.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\begin{scope}
\draw (1,0) node (a1) {};
\draw (3,0) node (a2) {};
\draw (0,1) node (a3) {};
\draw (2,1) node (a4) {};
\draw (4,1) node (a5) {};
\draw (2,2.4) node (a6) {};
\draw (a5) -- (a2) -- (a4) -- (a6);
\draw (a1) -- (a3);
\draw[double distance=2pt] (a1) -- (a4);
\end{scope}
\begin{scope}[yshift=-10em]
\draw (2,0) node (a1) {};
\draw (0.4,1) node (a2) {};
\draw (2,1.4) node (a3) {};
\draw (3.6,1) node (a4) {};
\draw (0.4,2.4) node (a5) {};
\draw (3.6,2.4) node (a6) {};
\draw (a1) -- (a3);
\draw (a1) -- (a2) -- (a5);
\draw (a4) -- (a6);
\draw[double distance=2pt] (a1) -- (a4);
\end{scope}
\end{scope}
\begin{scope}[yshift=-13em]
\draw (2,0) node {(a)};
\end{scope}
\begin{scope}[xshift=20em,yshift=-4em]
\begin{scope}
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\draw (1,0) node (a1) {};
\draw (0,1) node (a2) {};
\draw (2,1) node (a3) {};
\draw (a1) -- (a3);
\draw[double distance=2pt] (a1) -- (a2);
\begin{scope}[yshift=-6em]
\draw (0,0) node (a1) {};
\draw (2,0) node (a2) {};
\draw (1,1) node (a3) {};
\draw (a1) -- (a3);
\draw[double distance=2pt] (a2) -- (a3);
\end{scope}
\end{scope}
\begin{scope}[yshift=-9em]
\draw (1,0) node {(b)};
\end{scope}
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Pairs of labeled trees with the same $\kpw$}
\label{fig:trees_equal_kpw}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Fair trees}
%%%%%%%%%%%%%%%%%%%%%%%%%
We consider rooted trees as being rooted at the bottom, and thus a child is above its parent.
\begin{definition}
A {\em fair tree} is a labeled poset $(P,\om)$ such that:
\begin{itemize}
\item the underlying poset $P$ is a rooted tree,
\item for each vertex $v$ in $(P,\om)$, its outgoing edges (to its children) are either all strict or all weak.
\end{itemize}
\end{definition}
Figure \ref{fig:fair-tree-ex} shows an example of a fair tree. The ``fair'' terminology comes from the idea that each parent is equally strict with all its children.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\draw (0,0) node (a1) {};
\draw (-2.5,1) node (a2) {};
\draw (0,1) node (a3) {};
\draw (2.5,1) node (a4) {};
\draw (-3,2) node (a5) {};
\draw (-2,2) node (a6) {};
\draw (-1,2) node (a7) {};
\draw (0,2) node (a8) {};
\draw (1,2) node (a9) {};
\draw (2.5,2) node (a10) {};
\draw (-2,3) node (a11) {};
\draw (2,3) node (a12) {};
\draw (3,3) node (a13) {};
\draw (a1) -- (a2);
\draw (a1) -- (a3);
\draw (a1) -- (a4);
\draw (a2) -- (a5);
\draw (a2) -- (a6);
\draw (a10) -- (a12);
\draw (a10) -- (a13);
\draw[double distance=2pt] (a6) --(a11);
\draw[double distance=2pt] (a3) --(a7);
\draw[double distance=2pt] (a3) --(a8);
\draw[double distance=2pt] (a3) --(a9);
\draw[double distance=2pt] (a4) --(a10);
\end{tikzpicture}
\end{center}
\caption{Example of a fair tree of size $13$}
\label{fig:fair-tree-ex}
\end{figure}
We will prove that the fair trees are distinguished by the $(P,\om)$-partition enumerator $\kpw$. In fact, we shall consider a wider class $\Cb$ which we introduce next.
Let us define the following (noncommutative) operations on labeled posets.
For $(P,\om)$ and $(Q,\om')$ two labeled posets (considered as posets with assignments of strict and weak edges),
the \emph{weak (\resp strict) ordinal sum} $(P,\om)\wP (Q,\om')$ (\resp $(P,\om)\sP (Q,\om')$) is the labeled poset obtained
by placing $(P,\om)$ below $(Q,\om')$
and adding a weak (\resp strict) edge from each maximal element of $P$ to each minimal element of $Q$.
It will be helpful in what follows to pick an explicit labeling of the elements of these ordinal sums that is consistent with the strictness of the edges. We will label $(P,\om)\wP (Q,\om')$ by copying over the labels from $(P,\om)$ and $(Q,\om')$ but increasing each of the $\om'$-labels by $|P|$ so that the labeling is a bijection to $[|P|+|Q|]$. We can label the disjoint union $(P,\om)\sqcup (Q,\om')$ in the same way. Similarly, $(P,\om)\sP (Q,\om')$ will be labeled by instead increasing each of the $\om$-labels by $|Q|$.
\begin{definition}\label{def:C}
We define the set $\Cb$ of labeled posets recursively by:
\begin{enumerate}[label=(\alph*)]
\item\label{it42a} the one-element labeled poset $[1]$ is in $\Cb$;
\item \label{it42b} for any $(P,\om)$ and $(Q,\om')$ in $\Cb$, their disjoint union $(P,\om)\sqcup (Q,\om')$ is in $\Cb$;
\item \label{it42c} for any $(P,\om)$ in $\Cb$, the ordinal sums
$[1]\wP (P,\om)$ and $[1]\sP (P,\om)$
are in $\Cb$;
\item \label{it42d} for any $(P,\om)$ in $\Cb$, the ordinal sums
$(P,\om)\wP [1]$ and $(P,\om)\sP [1]$
are in $\Cb$.
\end{enumerate}
\end{definition}
Figure \ref{fig:Cb-ex} shows an example. See Subsection~\ref{sub:Cv2} for a characterization of $\Cb$ in terms of forbidden subposets.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\draw (0,-1) node (a1) {};
\draw (-5,-2) node (a2) {};
\draw (-1.5,-2) node (a3) {};
\draw (-6,-3) node (a4) {};
\draw (-5,-3) node (a5) {};
\draw (-4,-3) node (a6) {};
\draw (-2,-3) node (a7) {};
\draw (-1,-3) node (a8) {};
\draw (1,-3) node (a9) {};
\draw (3,-3) node (a10) {};
\draw (4,-3) node (a11) {};
\draw (-5.5,-4) node (a12) {};
\draw (3.5,-4) node (a13) {};
\draw (-3,-5) node (a14) {};
\draw (5.5, -3.5) node (a15) {};
\draw (5.5, -2.5) node (a16) {};
\draw (a1) -- (a2);
\draw (a1) -- (a3);
\draw (a1) -- (a9);
\draw (a1) -- (a10);
\draw (a1) -- (a11);
\draw (a3) -- (a7);
\draw (a3) -- (a8);
\draw (a4) -- (a12);
\draw (a5) -- (a12);
\draw[double distance=2pt] (a2) --(a4);
\draw[double distance=2pt] (a2) --(a5);
\draw[double distance=2pt] (a2) --(a6);
\draw[double distance=2pt] (a10) --(a13);
\draw[double distance=2pt] (a11) --(a13);
\draw[double distance=2pt] (a12) --(a14);
\draw[double distance=2pt] (a6) --(a14);
\draw[double distance=2pt] (a7) --(a14);
\draw[double distance=2pt] (a8) --(a14);
\draw[double distance=2pt] (a15) --(a16);
\end{tikzpicture}
\end{center}
\caption{Example of an element of $\Cb$ of size $16$.}
\label{fig:Cb-ex}
\end{figure}
\begin{remark}
We can use Definition~\ref{def:C} to give an alternative and recursive definition of fair trees.
Define {\em fair forests} as the class defined recursively by \ref{it42a}--\ref{it42c} in Definition~\ref{def:C}. Fair trees are nothing but connected fair forests, thus are elements of ~$\Cb$.
\end{remark}
The main result in this section is the following.
It is a generalization of Theorems~1.3 and~5.1 in \cite{HaTs17}; see Proposition~\ref{prop:Cb-pat} below for the analogue of Hasebe and Tsujie's bowtie- and \textsf{N}-free characterization.
\begin{theorem}\label{thm:fair-trees}
The $(P,\om)$-partition enumerator $\kpw$ distinguishes elements in $\Cb$,
thus in particular fair trees. More formally, for labeled posets $(P,\om)$ and $(Q,\om')$ in $\Cb$,
the following assertions are equivalent:
\begin{enumerate}
\item $(P,\om)$ and $(Q,\om')$ are isomorphic;
\item $\kpw=K_{(Q,\om')}$.
\end{enumerate}
\end{theorem}
The crux of the proof is the irreducibility result Proposition~\ref{prop:irred-C}, in the same way that irreducibility played a key role in \cite{HaTs17,LiWe21}. We first need more background on \qsym.
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Products of quasisymmetric functions}\label{sub:prods_qsym}
%%%%%%%%%%%%%%%%%%%%%%%%%
It will help our intuition to recall how to interpret $F_\alpha$ as a $(P,\om)$-partition enumerator. If $\alpha$ is a composition of $n$, we let $P$ be the chain with $n$ elements, labeled from top to bottom by any permutation $\pi$ of $[n]$ such that $\co(\pi) = \alpha$. That the resulting $\kpw = F_\alpha$ follows directly from Theorem~\ref{theo:KinF}; see Figure~\ref{fig:f_poset} for an example. Thinking just in terms of strict and weak edges, for a general $\alpha$, simply insert the strict edges so that the numbers of elements in the chains of contiguous weak edges, from bottom to top, match the parts of $\alpha$.
\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\tikzstyle{every node}=[draw, shape=circle, inner sep=2pt];
\draw (0,0) node (a1) {\small 1};
\draw (0,1) node (a2) {\small 2};
\draw (0,2) node (a3) {\small 6};
\draw (0,3) node (a4) {\small 5};
\draw (0,4) node (a5) {\small 3};
\draw (0,5) node (a6) {\small 4};
\draw (a1) -- (a2) -- (a3);
\draw (a5) -- (a6);
\draw[double distance=2pt] (a3) --(a4) -- (a5);
\end{tikzpicture}
\end{center}
\caption{This labeled poset has $(P,\om)$-partition enumerator $F_{312}$.}
\label{fig:f_poset}
\end{figure}
From~\eqref{equ:kp}, we know that labeled posets $(P,\om)$ and $(Q,\om')$ satisfy
\[
\kpw K_{(Q,\om')} = K_{(P,\om) \sqcup (Q,\om')}.
\]
Thus we can interpret the product $F_\alpha F_\beta$ as a $(P,\om)$-partition enumerator for a disjoint union of two appropriately labeled chains. One fact that we need later from this interpretation is summarized in the following lemma.
\begin{lemma}\label{lem:deg2}
Let $f_1$ and $f_2$ be two non-constant elements of \qsym.
Then the $F$-support of $f_1 f_2$ contains at least one composition $\gamma$ whose first part $\gamma_1$ is at least $2$.
The same is true when focusing on the last part of the compositions appearing in the $F$-support of $f_1 f_2$.
\end{lemma}
\begin{proof}
First consider two non-empty compositions $\alpha$ and $\beta$. Construct two labeled chains $(P,\om)$ and $(Q,\om')$ such that $F_\alpha=K_{(P,\om)}$ and $F_\beta=K_{(Q,\om')}$. Thus $F_\alpha F_\beta = K_{(P,\om) \sqcup (Q,\om')}$. It is obvious that there is at least one element $\pi$ in the set $\L((P,\om) \sqcup (Q,\om'))$ with $\pi_1<\pi_2$. By Theorem~\ref{theo:KinF}, this gives rise to an element $F_\gamma$ in the $F$-support of $F_\alpha F_\beta$ with $\gamma_1\ge2$.
Now, let us consider two non-constant elements $f_1$ and $f_2$ of \qsym.
Let us denote by $\alpha$ (\resp $\beta$) the lexicographically maximal composition in the $F$-support of $f_1$ (\resp $f_2$).
It is clear that the lexicographically maximal element in the product $f_1 f_2$ comes from the product $F_\alpha F_\beta$,
thus the case above applies.
The case of the last part is similar, requiring just two tweaks. First, if $\ell$ denotes the number of elements in $(P,\om) \sqcup (Q,\om')$, it is obvious that there is at least one element $\pi$ in the set $\L((P,\om) \sqcup (Q,\om'))$ with $\pi_{\ell-1}<\pi_\ell$. This yields an element $F_\gamma$ in the $F$-support of $F_\alpha F_\beta$ such that the last part of $\gamma$ is at least 2. Secondly, instead of considering the lexicographically maximal composition, we use the composition whose reversal is lexicographically maximal.
\end{proof}
Let us introduce two operations on compositions
(which are already known but we shall use notation relevant to our context):
\begin{equation}\label{equ:uparrow}
(\alpha_1,\alpha_2,\dots,\alpha_k) \wP (\beta_1,\beta_2,\dots,\beta_\ell)
=
(\alpha_1,\alpha_2,\dots,\alpha_k+\beta_1,\beta_2,\dots,\beta_\ell),
\end{equation}
and
\begin{equation}\label{equ:upuparrow}
(\alpha_1,\alpha_2,\dots,\alpha_k) \sP (\beta_1,\beta_2,\dots,\beta_\ell)
=
(\alpha_1,\alpha_2,\dots,\alpha_k,\beta_1,\beta_2,\dots,\beta_\ell),
\end{equation}
which give rise to two (noncommutative) products in \qsym, defined on the $F$-basis:
\begin{equation}\label{equ:f_uparrow}
F_{\alpha} \wP F_{\beta}
=
F_{\alpha \wP \beta},
\end{equation}
and
\begin{equation}\label{equ:f_upuparrow}
F_{\alpha} \sP F_{\beta}
=
F_{\alpha \sP \beta}.
\end{equation}
The use of the same notation as for labeled posets is justified by the following statement.
\begin{proposition}\label{prop:k_products}
For any two labeled posets $(P,\om)$ and $(Q,\om')$,
$$K_{(P,\om)\wP(Q,\om')}=\kpw \wP K_{(Q,\om')}$$
and
$$K_{(P,\om)\sP(Q,\om')}=\kpw \sP K_{(Q,\om')}.$$
\end{proposition}
\begin{proof}
Let us prove the first assertion.
By Theorem~\ref{theo:KinF},
\[
K_{(P,\om) \wP (Q,\om')} = \sum_{\pi\in\L((P,\om)\wP (Q,\om'))} F_{\co(\pi)}.
\]
By definition of $\wP$ for labeled posets, those $\pi\in\L((P,\om)\wP (Q,\om'))$ are concatenations of $\sigma\in\L(P,\om)$ and $\tau\in\L(Q,\om')$ but where each entry of $\tau$ is increased by $|P|$. Consequently, $\co(\pi) = \co(\sigma)\wP \co(\tau)$. Thus, using \eqref{equ:f_uparrow}, we have
\begin{align*}
K_{(P,\om) \wP (Q,\om')}
&= \sum_{\sigma\in\L(P,\om),\:\tau\in\L(Q,\om')} F_{\co(\sigma)\wP \co(\tau)}\\
&= \sum_{\sigma\in\L(P,\om),\:\tau\in\L(Q,\om')} F_{\co(\sigma)}\wP F_{\co(\tau)}\\
&= \kpw \wP K_{(Q,\om')}\ .
\end{align*}
The second assertion is proved similarly.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{An involution on labeled posets}
%%%%%%%%%%%%%%%%%%%%%%%%%
Given a labeled poset $(P,\om)$, we can switch the strictness of the edges to obtain a new labeled poset $\inv{(P,\om)}$.
We will follow \cite{McWa14} by referring to this operation on labeled posets as the \emph{bar operation}. In the setting of quasisymmetric functions, we may define
\[
\inv{F_\alpha} = \inv{F_{S(\alpha),n}} = F_{\inv{S(\alpha)},n}
\]
where for any subset $S$ of $[n-1]$ we let $\inv{S}=[n-1]\backslash S$, and we extend it to \qsym\ by linearity. In the example of Figure~\ref{fig:f_poset}, we get $\inv{F_{312}} = \inv{F_{\{3,4\},6}} = F_{\{1,2,5\},6}= F_{1131}$.
The following lemma states that these two bar operations are compatible, and that the latter operation commutes with the product in \qsym.
\begin{lemma}\label{lem:bar}
We have:
\begin{enumerate}[label=(\alph*)]
\item \label{it47a} $\inv{\kpw} = K_{\inv{(P,\om)}}$ for any labeled poset $(P,\om)$;
\item \label{it47b} $\inv{fg}=\inv{f}\inv{g}$ for any $f$ and $g$ in \qsym.
\end{enumerate}
\end{lemma}
\begin{proof}
For the first assertion, observe that the bar operation that sends $(P,\om)$ to $\inv{(P,\om)}$ on general labeled posets can be done at the level of the labeling $\om$ by simply replacing each label $\omega(i)$ by $|P|+1-\om(i)$. Then in the notation of the $F$-expansion of $\kpw$ in Theorem~\ref{theo:KinF}, each $\des(\pi)$ is sent to its complement $[n-1]\backslash\des(\pi)$, resulting in $\inv{\kpw}$, as required.
For the second assertion, recall the interpretation of $F_\alpha$ as $\kpw$ for a labeled chain $(P,\omega)$ from the start of Subsection~\ref{sub:prods_qsym}, along with the interpretation there of $F_\alpha F_\beta$.
Thus~\ref{it47a} implies that $\inv{F_\alpha F_\beta} = \inv{F_\alpha} \; \inv{F_\beta}$, from which~\ref{it47b} follows by linearity.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Irreducibility}
%%%%%%%%%%%%%%%%%%%%%%%%%
A crucial fact towards proving Theorem \ref{thm:fair-trees} is the irreducibility
of $\kpw$ for elements of $\Cb$.
\begin{proposition}\label{prop:irred-C}
If $(P,\om)$ is a connected element of $\Cb$ then $\kpw$ is irreducible in \qsym.
\end{proposition}
To prove this, we first recall the following general property. A polynomial with integer coefficients is said to be \emph{primitive} if
whenever an integer $k$ divides all its coefficients we have $k=\pm1$.
In the same vein, since we consider $\qsym \subseteq \mathbb{Z}[[x_1, x_2, \ldots]]$, we say $f \in \qsym$ is \emph{primitive} if whenever an integer $k$ divides $f$ in \qsym\ we have $k = \pm1$.
We are interested in whether $\kpw$ is primitive.
To answer this question, let us define the \emph{leading term} of a formal power series $f$ expanded in terms of monomials as the term $c_\alpha x^\alpha = c_\alpha x_1^{\alpha_1} x_2^{\alpha_2} \cdots$ with lexicographically largest $\alpha$ such that $c_\alpha \neq 0$; naturally, we call this $c_\alpha$ the \emph{leading coefficient}. For a labeled poset $(P,\om)$, we define $x^{\mathrm{jump}(P,\om)} = x_1^{j_1} x_2^{j_2} \cdots$ where $j_i$ is the number of elements of $(P,\om)$ of jump $i-1$.
\begin{proposition}[{\cite[proof of Proposition 4.2]{McWa14}}]\label{prop:prim}
For any labeled poset $(P,\om)$, the leading term of $\kpw$ is $x^{\mathrm{jump}(P,\om)}$. In particular, the leading coefficient of $K_{(P, \om)}$ is $1$ and $K_{(P, \om)}$ is primitive.
\end{proposition}
The next lemma is relevant to the recursive construction of $\Cb$.
\begin{lemma}\label{lem:irred}
If $f$ is a primitive element of \qsym\ then the polynomials
$F_1\wP f$,\ $F_1\sP f$,\ $f\wP F_1$, and $f\sP F_1$
are irreducible in \qsym.
\end{lemma}
\begin{proof}
Let us first deal with $F_1\sP f$.
Assume that $F_1\sP f$ is reducible.
Note that if $f$ expands as $\sum c_\alpha F_\alpha$ then $F_1\sP f = \sum c_\alpha F_{\alpha^+}$, where $\alpha^+$ is obtained from $\alpha$ by appending an entry of 1 at the start. Thus since $f$ is primitive, $F_1\sP f$ is also primitive, so there exist non-constants $g,g'\in \qsym$, such that
\begin{equation}\label{eq:lem-irred1}
F_1\sP f = g g'.
\end{equation}
All $\alpha$ in the $F$-support of $F_1\sP f$ satisfy $\alpha_1=1$ but by Lemma~\ref{lem:deg2}, the $F$-support of the right-hand side of~\eqref{eq:lem-irred1} contains at least one $\alpha$ with $\alpha_1 \geq 2$, a contradiction. The case of $f\sP F_1$ is treated similarly, using the last part of $\alpha$ instead of the first part.
Let us now consider $F_1\wP f$.
We again assume $F_1\wP f$ is reducible and now $\alpha^+$ is obtained from $\alpha$ by increasing the first part by 1. The primitivity
implies the existence of two non-constants $g,g'\in \qsym$,
such that $F_1\wP f = g g'$. We apply the bar operator to this equality
and get
\[
\inv{F_1\wP f} = \inv{g g'} = \inv{g} \inv{g'}.
\]
by Lemma~\ref{lem:bar}\ref{it47b}. Since the elements $\alpha$ of the $F$-support of $F_1\wP f$ all satisfy $\alpha_1\ge 2$, we know all $\alpha'$ in the $F$-support of
$\inv{F_1\wP f}$ satsify $\alpha'_1 = 1$.
We are thus led to the same contradiction as in the first case.
The case of $f\wP F_1$ is treated similarly.
\end{proof}
Since we will only be considering labeled posets in $\Cb$ for the remainder of this section, we will abbreviate $(P,\om)$ as $P$ for easier reading.
\begin{proof}[Proof of Proposition \ref{prop:irred-C}]
If $P$ has just a single element, then $K_P = F_1$, which is irreducible. Otherwise, since $P$ is connected and constructed recursively, it must be of one of the forms $[1]\wP P'$,\ $[1]\sP P'$,\
$P'\wP [1]$, or $P'\sP [1]$, where $P' \in \Cb$. The result now follows from Propositions~\ref{prop:k_products} and~\ref{prop:prim}, and Lemma~\ref{lem:irred}.
\end{proof}
\begin{remark}
A special case of Proposition~\ref{prop:irred-C}, or even just Lemma~\ref{lem:irred}, is that $F_\alpha$ is irreducible in \qsym, as previously shown in~\cite{LaPy08}.
\end{remark}
We are now in a position to prove the main result of this section.
\begin{proof}[Proof of Theorem \ref{thm:fair-trees}]
It is obvious that when $P$ and $Q$ are isomorphic, then $K_P=K_Q$.
Let us prove the converse.
We shall use induction on the size of $P$, with the case of size 1 being trivial.
Assuming now that the size of $P$ is at least $2$,
we may decompose $P$ and $Q$ uniquely into non-empty
connected components:
$P=\sqcup_{i=1}^r P_i$
and
$Q=\sqcup_{i=1}^s Q_i$.
We have
\[
\prod_{i=1}^r K_{P_i}
=
\prod_{i=1}^s K_{Q_i}.
\]
Since \qsym\ is a unique factorization domain \cite{Haz01,LaPy08,MaRe95},
the irreducibility of $K_{P_i}$ and $K_{Q_i}$ from Proposition~\ref{prop:irred-C}
implies that $r=s$ and that for every $i$, we have $K_{P_i} = K_{Q_i}$ (up to a suitable renumbering).
When $r \ge 2$, the size of each $P_i$ and $Q_i$ is smaller than the size of $P$
and thus $P_i$ and $Q_i$ are isomorphic for every $i$ by the induction hypothesis.
Thus $P$ and $Q$ are also isomorphic.
Suppose now that $r = 1$, i.e. $P$ and $Q$ are connected. Thus,
since their size is greater than $1$, they may be written as
$P=[1]\wP P'$ or $P=[1]\sP P'$
or
$P=P'\wP [1]$ or $P=P' \sP [1]$,
and similarly for $Q$.
By Theorem~\ref{theo:KinF}, we can distinguish among these four possibilities by observing whether the first part of the compositions $\alpha$ in the $F$-support of $K_P$ (equivalently $K_Q$) are all equal to $1$ or all greater than $1$, and similarly for the last part of all such $\alpha$. Specifically, $P=[1]\wP P'$ if and only if $\alpha_1 > 1$ for all $\alpha$, implying $Q=[1]\wP Q'$. Similarly, $P=[1]\sP P'$ if and only if $\alpha_1=1$ for all $\alpha$, implying $Q=[1]\sP Q'$. And $P=P'\wP [1]$ (\resp $P=P' \sP [1]$) if and only if the last part of $\alpha$ is greater than 1 (\resp equals 1) for all $\alpha$, implying $Q=Q'\wP [1]$ (\resp $Q=Q' \sP [1]$).
So for a given $P$ and $Q$ with $K_P = K_Q$\,, at least one of the following four properties holds:
\begin{itemize}
\item $P=[1]\wP P'$ and $Q=[1]\wP Q'$, or
\item $P=[1]\sP P'$ and $Q=[1]\sP Q'$, or
\item $P=P'\wP [1]$ and $Q=Q'\wP [1]$, or
\item $P=P'\sP [1]$ and $Q=Q'\sP [1]$.
\end{itemize}
In the first case, applying Proposition~\ref{prop:k_products} gives $F_1\wP K_{P'} = F_1\wP K_{Q'}$. Let us expand this in the $F$-basis as $\sum c_\alpha F_\alpha$. From~\eqref{equ:f_uparrow} and~\eqref{equ:uparrow}, we see that by just subtracting $1$ from the first part $\alpha_1$ in each term $F_\alpha$, we get $K_{P'} = K_{Q'}$, with $P'$ of size smaller than $P$.
By induction, $P'$ and $Q'$ are isomorphic, and hence so are $P$ and $Q$.
In the second case, we have $F_1\sP K_{P'} = F_1\sP K_{Q'}$.
Let us expand this in the $F$-basis as $\sum c_\alpha F_\alpha$.
From~\eqref{equ:f_upuparrow} and~\eqref{equ:upuparrow}, we see that by just removing the first part $\alpha_1=1$
in each term $F_\alpha$, we get $K_{P'} = K_{Q'}$, with $P'$ of size smaller than $P$, giving the same conclusion.
The last two cases are resolved similarly by focusing on the last entry of $\alpha$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A different characterization of $\Cb$}\label{sub:Cv2}
%%%%%%%%%%%%%%%%%%%%%%%%%
To end this section, we shall give a characterization of the class $\Cb$
in terms of forbidden subposets.
We need to distinguish two notions of subposets of labeled posets.
For the first, we ignore the labeling and consider the usual notion of induced subposets.
A poset (labeled or not) that avoids a set of unlabeled subposets $S$ in this sense is said to be $(S)$-free.
The second notion is of convex labeled subposets, considered as convex subposets with specific assignments of strict and weak edges.
A labeled poset that avoids a set of labeled convex subposets $S'$ in this sense is said to be $[S']$-free.
Of course these two notions can be used together.
The following result is the analogue in our context of \cite[Theorem 4.3]{HaTs17}.
\begin{proposition}\label{prop:Cb-pat}
Labeled posets in $\Cb$ are exactly $\pac$-$\pef$-free posets.
\end{proposition}
The proof is modeled on the proof of \cite[Theorem 4.3]{HaTs17}. We first recall \cite[Lemma 4.4]{HaTs17}.
\begin{lemma}\label{lem:unique-max-min}
A finite connected $\pac$-free poset has a unique minimal or maximal element.
\end{lemma}
\begin{proof}[Proof of Proposition \ref{prop:Cb-pat}]
Let $P$ be an element of $\Cb$.
We shall prove that it is $\pac$-$\pef$-free by induction on its size.
If $P$ is disconnected then $P=P' \sqcup P''$ with $P'$ and $P''$ in $\Cb$ and non-empty.
By the induction hypothesis, $P'$ and $P''$ are $\pac$-$\pef$-free, and thus so is $P$.
If $P$ is connected, then by definition of $\Cb$, $P$ is of the form
$[1]\wP P'$ or $[1]\sP P'$ or $P'\wP [1]$ or $P' \sP [1]$ for some $P'$ in $\Cb$.
We may assume without loss of generality that $P=[1] \wP P'$.
The induction hypothesis shows that $P'$ is $\pac$-$\pef$-free.
This implies that $P$ is $\pac$-free too; otherwise, we would find three elements $a, b, c$ in $P'$ such that the subposet $(\{1, a, b, c\}, \le_P )$ is isomorphic to $\pa$ or $\pc$,
but this is absurd since $\pa$ and $\pc$ do not have a unique minimal element.
A similar idea implies that $P$ is $\pef$-free too; otherwise, we would find two elements $a, b$ in $P'$ such that the convex labeled subposet $(\{1, a, b\}, \le_P )$ is equal to $\pe$ or $\pf$, but this is impossible by construction.
Let us then prove the converse.
The proof is again based on induction on the size of $P$.
If a finite $\pac$-$\pef$-free poset $P$ is disconnected, then $P = P' \sqcup P''$ for some non-empty $\pac$-$\pef$-free posets $P'$ and $P''$.
The induction hypothesis shows that $P'$ and $P''$ are in $\Cb$, and thus so is $P$.
So let us suppose that $P$ is connected.
Because of Lemma~\ref{lem:unique-max-min}, together with the $\pef$-freeness, we may assume without loss of generality
that $P$ is of the form $[1] \wP P'$ for some poset $P'$. Since $P'$ is a convex subposet of $P$,
it is $\pac$-$\pef$-free, from which the induction hypothesis implies that $P'$ is in $\Cb$, and thus so is $P$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Open problems}\label{sec:conclusion}
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Notes on the main conjectures}
%%%%%%%%%%%%%%%%%%%%%%%%%
Resolving any one of Conjectures~\ref{con:chromatic_trees}, \ref{con:poset_trees} and~\ref{con:labeled_rooted_trees} would represent a significant advance. Taking them in turn, we offer some further observations.
\begin{itemize}
\item Even though our starting point was Conjecture~\ref{con:chromatic_trees}, the only approach taken here is to consider it in terms of Conjecture~\ref{con:poset_trees}. Perhaps there is a more direct way to tackle the former.
\item One difficulty we failed to surmount in tackling Conjecture~\ref{con:poset_trees} was how to use the fact that the posets under consideration are trees; any methods used cannot apply to the posets in~Figure~\ref{fig:equal_kp}.
\item A special case of Conjecture~\ref{con:labeled_rooted_trees} worthy of consideration is that of binary trees, defined here as rooted trees where every element has exactly 0 or 2 children.
Referring to Subsection~\ref{sub:classes}, one could consider series-parallel posets where we allow a mixture of strict and weak edges. In particular, one could define \emph{fair series-parallel posets} by replacing all appearances of ``$[1]$'' in parts \ref{it42c} and \ref{it42d} of Definition~\ref{def:C} with ``$(Q, \om')$.'' Does the analogue of Theorem~\ref{thm:fair-trees} hold?
For any class of posets, labeled or not, we expect the crux of a proof would be the irreducibility, as in Proposition~\ref{prop:irred-C}, \cite[Lemma~3.13]{HaTs17}, and \cite[Theorem~4.19]{LiWe21}. The general question of the irreducibility of $\kpw$ appears as \cite[Questions~7.2 and~7.3]{McWa14}. The irreducibility of $M_\alpha$ and $F_\alpha$ is shown in \cite{LaPy08}.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Quasisymmetric power sum bases}
%%%%%%%%%%%%%%%%%%%%%%%%%
We have given much less consideration to other open problems which we next describe. Liu and Weselcouch's impressive progress in the naturally labeled case \cite{LiWe21} depends on the expansion of $K_P$ in the (unnormalized) power sum basis $\psi_\alpha$ of type I and, in particular, the combinatorial interpretation of this expansion due to Alexandersson and Sulzgruber \cite{AlSu21}. Can other bases of \qsym\ give new insight? Even though the expansion of $K_P$ in other bases might be neither integral nor positive, there could still be interesting combinatorics with appropriate normalization and interpretation of the signs. We did a careful study of the expansion of $K_P$ in the (unnormalized) power sum basis $\phi_\alpha$ of type II. Here, we are following the notation of Ballantine et al.~\cite{BDHMN20}, where extensive information about the bases $\psi_\alpha$ and $\phi_\alpha$ can be found. In particular, they show that the power sum symmetric function $p_\lambda$ expands as
\begin{equation}\label{equ:p_lambda}
p_\lambda = \sum_{\alpha\,:\,\widetilde{\alpha} = \lambda} z_\lambda \psi_\alpha
= \sum_{\alpha\,:\,\widetilde{\alpha} = \lambda} z_\lambda \phi_\alpha
\end{equation}
where both sums are over all compositions $\alpha$ whose weakly decreasing reordering is $\lambda$. As usual, $z_\lambda = 1^{m_1}m_1!\,2^{m_2}m_2! \cdots k^{m_k}m_k!$ where $m_i$ is the multiplicity of $i$ in $\lambda$ and where $\lambda_1 = k$. It follows immediately from~\eqref{equ:p_lambda} that when $f$ is a symmetric function, the coefficient of $\psi_\alpha$ in $f$'s $\psi$-expansion equals the coefficient of $\phi_\alpha$ in $f$'s $\phi$-expansion. We offer the following question: is the converse true? In other words, does the coefficients being equal give a characterization of symmetric functions? We have only anecdotal evidence related to this question and have not given it significant ~thought.
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Principal specialization}\label{sub:ps}
%%%%%%%%%%%%%%%%%%%%%%%%%
Given a quasisymmetric function $f(\x)$ in infinitely many variables $x_1, x_2, \ldots$, we denote by $f(1, q, q^2, \ldots, q^{k-1})$ the element of $\mathbb{Z}[q]$ that results from setting $x_i=q^{i-1}$ for all $i \leq k$ and $x_i=0$ otherwise. This is known as the \emph{principal specialization of order $k$} of $f$ \cite[Sections 7.8, 7.19]{Sta99}. This specialization has a nice interpretation for $\kpw$: if
\[
\kpw(1, q, q^2, \ldots, q^{k-1}) = \sum_{N\geq 0} a(N) q^N,
\]
then we see that $a(N)$ counts the number of $(P,\om)$-partitions $f:P \to \{0,\ldots,k-1\}$ of $N$. Notice that $f$ is now allowed to map to 0 but cannot map to integers larger than $k-1$, and the sum of $f(p)$ as $p$ ranges over $P$ is $N$. Similar interpretations apply to the principal specializations of $X_G$ and $X_{\diG}$\,.
Recall that Stanley's original conjecture states that $X_G(\x)$ distinguishes trees. Clearly $X_G(1,q, q^2, \ldots, q^{k-1})$ contains far less information than $X_G(\x)$, making the following recent conjecture of Loehr and Warrington surprising.
\begin{conjecture}[\cite{LoWa22+}]
$X_G(1,q, q^2, \ldots, q^{n-1})$ distinguishes trees with at most $n$ vertices.
\end{conjecture}
Certainly an affirmative answer to Loehr and Warrington's conjecture would prove Stanley's conjecture.
Inspired by this, we offer the following conjecture which should be compared with Conjecture~\ref{con:poset_trees}.
\begin{conjecture}\label{con:sp_poset_trees}
$\KK{P}(1, q, q^2, \ldots, q^{n-1})$ distinguishes posets with $n$ elements that are trees.
\end{conjecture}
%We have verified this conjecture for $n\leq 10$.
We have verified this conjecture for all such posets with at most $10$ elements.
In fact, it seems that $\KK{P}(1, q, q^2, \ldots, q^{n-2})$ suffices when the posets have $n$ elements.
\begin{conjecture}\label{con:sp_poset_trees_one_fewer}
$\KK{P}(1, q, q^2, \ldots, q^{n-2})$ distinguishes posets with $n$ elements that are trees.
\end{conjecture}
It is not obvious to us whether Conjecture~\ref{con:sp_poset_trees_one_fewer} being true would imply Conjecture~\ref{con:sp_poset_trees}.
\begin{example}
Referring to Figure~\ref{fig:f_support}, the labelel poset $P$ on the left satisfies
\[
\KK{P}(1, q, q^2, q^3) = q^4 + 2q^5 + 4q^6 + 4q^7 + 5q^8 + 4q^9 + 2q^{10} + q^{11}
\]
whereas its dual $P^*$ on the right satisfies
\[
\KK{P^*}(1, q, q^2, q^3) = q^4 + 2q^5 + 4q^6 + 5q^7 + 4q^8 + 4q^9 + 2q^{10} + q^{11}.
\]
So, even though their $F$-supports do not distinguish them, their principal specialization of order 4 does.
This example also exhibits how the principal specialization of $\KK{P}$ of order $k$ compares to that of its dual $P^*$. One can check that for general $P$ with $n$ elements, the coefficient of $q^N$ in $\KK{P}(1, q, q^2, \ldots, q^{k-1})$ equals the coefficient of $q^{n(k-1)-N}$ in $\KK{P^*}(1, q, q^2, \ldots, q^{k-1})$.
\end{example}
However, $\KK{P}(1, q, q^2, \ldots, q^{k-1})$ for $k-1**