%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{106}
%% 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}

 \def\KK{\mathbb{K}}
 \def\oG{\mathsf{O}\cG}
 \def\ozeta{\zeta_{\oG}}

\usepackage{lipsum}

%% define your title in the usual way
\title[Kromatic quasisymmetric functions]{Kromatic quasisymmetric functions}

\author{Eric Marberg\thanks{\href{mailto:emarberg@ust.hk}{emarberg@ust.hk}. This work was supported by Hong Kong RGC grants 16306120 and 16304122.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Hong Kong University of Science and Technology}

%% 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{We provide a construction for the kromatic symmetric function $\bX_G$ of a graph introduced by Crew, Pechenik, and Spirkl using combinatorial (linearly compact) Hopf algebras. As an application, we show that $\bX_G$ has a positive expansion into multifundamental quasisymmetric functions. We also study two related quasisymmetric $q$-analogues of $\bX_G$, which are $K$-theoretic generalizations of the quasisymmetric chromatic function of Shareshian and Wachs. We classify exactly when one of these analogues is symmetric. For the other, we derive a positive expansion into symmetric Grothendieck functions for graphs $G$ that are natural unit interval orders.}

%% 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 symmetric functions, combinatorial Hopf algebras, linearly compact modules, multifundamental quasisymmetric functions}

%% 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{kromatic.bib}
\input{preamble.tex}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

\section{Introduction}

 

 

The purpose of this note is to re-examine the algebraic
origins of the \defn{kromatic symmetric function} of a graph that was
recently introduced by Crew, Pechenik, and Spirkl \cite{CPS}, and to study two
quasisymmetric analogues of this power series. 

Let $\NN = \{0,1,2,\dots\}$,
$\PP = \{1,2,3,\dots\}$,
and $[n] = \{1,2,\dots,n\}$ for $n \in \NN$.
All graphs are undirected by default, and
are assumed to be simple with a finite set of vertices.
We do not distinguish between isomorphic graphs. 

If $G$ is any graph then 
we write $V(G)$ for its set of vertices and $E(G)$ its set of edges.
A \defn{proper coloring} of $G$ is a map $\kappa :  V(G) \to \PP$ with $\kappa(u) \neq \kappa(v)$ for all   $\{u,v\} \in E(G)$.
For maps $\kappa : V \to \PP$ let $x^\kappa = \prod_{i \in V } x_{\kappa(i)}$ where $x_1,x_2,\dots$ are commuting variables.

\begin{definition}[Stanley \cite{Stanley95}]
The \defn{chromatic symmetric function} of $G$ is 
the symmetric power series $ X_G := \sum_\kappa x^\kappa $
where the sum is over all proper colorings $\kappa$ of $G$.
\end{definition}
 


\begin{example} If $G=K_n$ is the \defn{complete graph} with $V(G)=[n]$ then $X_G=n!   e_n$
for the \defn{elementary symmetric function} $e_n := \sum_{1 \leq i_1 <i_2< \dots <i_n} x_{i_1} x_{i_2}\cdots x_{i_n}$.
\end{example}


A poset is \defn{$(3+1)$-free} if it does not contain a 3-element chain $a<b<c$ whose elements are all 
incomparable to some fourth element $d$.
The \defn{Stanley--Stembridge conjecture} \cite{stanley.stembridge}
proposes that if $G$ is the incomparability graph of a $(3+1)$-free poset then $X_G$ has a positive expansion into elementary symmetric functions.
This conjecture has several refinements and generalizations,
and has been resolved in a number of interesting special cases, but remains open in general.



Let $G$ be an \defn{ordered graph}, that is, a graph with a total order $<$ on its vertex set $V(G)$.
An \defn{ascent} (resp., \defn{descent}) of a map $\kappa : V(G) \to \PP$ is an edge $\{u,v\} \in E(G)$ with $u<v$ 
and  $\kappa(u) <\kappa(v)$
(resp., $\kappa(u)>\kappa(v)$). Let $\asc_{G}(\kappa)$
and
$\des_{G}(\kappa)$ be the number of ascents and descents.
Shareshian and Wachs \cite{SW2016} introduced the following $q$-analogue of $X_G$:

\begin{definition}[\cite{SW2016}]
The \defn{chromatic quasisymmetric function} of an ordered graph
 $G$ is   $X_G(q) = \sum_\kappa q^{\asc_G(\kappa)} x^\kappa 
 \in  \NN[q]\llbracket x_1,x_2,\dots\rrbracket $ where the sum is
 over all proper colorings.
 \end{definition}

 \begin{example} If $G=K_n$   then $X_G(q)= [n]_q!   e_n$
 where $[i]_q = \tfrac{1-q^i}{1-q}$ and $[n]_q! = \prod_{i=1}^n [i]_q$.
 \end{example}
 
 
  Let $\Set(\PP)$ be the set of finite nonempty subsets of $\PP$.
For a map
 $\kappa : V \to \Set(\PP)$
define $x^\kappa = \prod_{i \in V}  \prod_{j \in \kappa(i)} x_j$.
A \defn{proper set-valued coloring} is a map $\kappa : V(G) \to \Set(\PP)$
with $\kappa(u) \cap \kappa(v) = \varnothing$ for all $\{u,v\} \in E(G)$.
There is also a ``$K$-theoretic'' analogue of $X_G$:
\begin{definition}[Crew, Pechenik, and Spirkl \cite{CPS}]
The \defn{kromatic symmetric function} of a graph
 $G$ is the sum $\bX_G = \sum_\kappa x^\kappa \in \ZZ\llbracket x_1,x_2,\dots\rrbracket $
 over all proper set-valued colorings of $G$.
\end{definition}

 
\begin{example} $ \bX_{K_n}= n!\sum_{r= n}^\infty {r \brace n} e_r $
where ${r \brace n}$ is the Stirling number of the second kind.  
\end{example}

\begin{remark}\label{clan-rmk}
Given $\alpha : V \to \NN$, let $ \cCl_\alpha(V)$ be the set of pairs $(v,i)$ with $v \in V$ and $i \in [\alpha(v)]$. 
If $G$ is a graph and  $\alpha : V(G) \to \NN$ is any map, then
the \defn{$\alpha$-clan graph}  $\Cl_\alpha(G)$ has vertex set $\cCl_\alpha(V(G))$
and edges
 $\{ (v,i),(w,j)\}$  whenever $\{v,w\} \in E(G)$ or 
 both $v=w$ and $i\neq j$. 
As observed in \cite{CPS}, one has 
$
\bX_G = \sum_{\alpha : V(G) \to \PP} \tfrac{1}{\alpha!} X_{\Cl_\alpha(G)}
$
where $\alpha! := \prod_v \alpha(v)!$.
Many   properties of $X_G$ extend to $\bX_G$
via this identity, but some interesting features of $\bX_G$ cannot be explained by this formula alone.
 \end{remark}
 
Our main results
 provide a natural construction for $\bX_G$  
 using the theory of \defn{combinatorial Hopf algebras}.
 This approach requires some care, as $\bX_G$ is not a symmetric function of bounded degree. We explain things precisely in terms of \defn{linearly compact Hopf algebras} after reviewing a similar, simpler construction of $X_G$ in Section~\ref{back-sect}, following \cite{ABS}.

 
As an application of our approach, we show that $\bX_G$ has a positive expansion into \defn{multifundamental quasisymmetric functions}. We also study two related $q$-analogues of $\bX_G$, which give $K$-theoretic generalizations of $X_G(q)$.
We classify exactly when one of these analogues is symmetric. 
For the other, we extend a theorem of Crew, Pechenik, and Spirkl
(also lifting a theorem of Shareshian and Wachs) to derive a positive expansion into symmetric Grothendieck functions for graphs $G$ 
that are natural unit interval orders.

\section{Background}\label{back-sect}

Let $\KK$ be an integral domain; in practice, one can assume this is $\ZZ$, $\QQ$, $\ZZ[q]$, or $\QQ(q)$.

\subsection{Hopf algebras}

Write $\otimes = \otimes_\KK$ for the tensor product over $\KK$.
A \defn{$\KK$-algebra} is a $\KK$-module $A$ with $\KK$-linear
product $\nabla : A\otimes A \to A$
and unit $\iota : \KK\to A$ 
maps.
Dually, a \defn{$\KK$-coalgebra} is a $\KK$-module $A$ with $\KK$-linear 
coproduct $\Delta : A \to A\otimes A$
and 
counit $\epsilon : A \to \KK$ maps.
 The (co)product and (co)unit maps must satisfy several associativity axioms;
see \cite[\S1]{GrinbergReiner}.

A $\KK$-module $A$ that is both a $\KK$-algebra and a $\KK$-coalgebra is a \defn{$\KK$-bialgebra}
if the coproduct and counit maps are algebra morphisms. 
A bialgebra $A = \bigoplus_{n \in \NN}A_n$ is \defn{graded} if its (co)product and (co)unit are graded maps; in this case $A$ is \defn{connected} if $A_0=\KK$.

 
Let $\End(A)$ denote the set of $\KK$-linear maps $A \to A$. This set is a $\KK$-algebra for the 
product 
$
f \ast g := \nabla \circ (f\otimes g) \circ \Delta
$. 
The unit of this \defn{convolution algebra}
is the composition $ \iota\circ \epsilon$ of the unit and counit of $A$.
A bialgebra $A$ is a \defn{Hopf algebra} if  $\id : A \to A$ has a
two-sided inverse 
$\antipode : A \to A$ in $\End(A)$. When it exists, we call $\antipode$ the \defn{antipode} of $A$.

 
\begin{example}
Let $\cG_n$ for $n \in \NN$ be the free $\KK$-module spanned by all isomorphism classes of undirected graphs with $n$ vertices, and set $\cG = \bigoplus_{n \in \NN} \cG_n$.
One views $\cG$ as 
a connected, graded Hopf algebra 
 with product 
$\nabla(G \otimes H) = G \sqcup H$ and coproduct  
$ \Delta(G) = \sum_{S\sqcup T = V(G)} G|_S \otimes G|_T$
for   graphs $G$ and $H$,
 where $\sqcup$ denotes disjoint union and  $G|_S$ denotes the  subgraph of $G$ induced on $S$.
\end{example}

A \defn{lower set} in a directed acyclic graph $D=(V,E)$ is a set $S\subseteq V$ 
such that if a directed path connects $v \in V$ to $s \in S$ then $v \in S$.
An \defn{upper set}  is the complement of a lower set.


\begin{example}
Let $\cO_n$ for $n \in \NN$ be the free $\KK$-module spanned by all isomorphism classes of directed acyclic graphs with $n$ vertices, and set 
$\cO = \bigoplus_{n \in \NN} \cO_n$. 
One views $\cO$ as a connected, graded Hopf algebra  with product  
$\textstyle \nabla(C \otimes D) = C \sqcup D$ and 
coproduct $ \Delta(D) = \sum D|_S \otimes D|_T$
for directed acyclic graphs  graphs $C$ and $D$,
 where the sum is over all disjoint unions $S\sqcup T = V(D)$ 
 with $S$ a lower set and $T$ an upper set.
\end{example}

A \defn{labeled poset} is a pair $(D,\gamma)$ consisting of a directed acyclic graph $D$ and  an injective map $\gamma : V(D) \to \ZZ$.
We consider $(D,\gamma)=(D',\gamma')$   if 
there is an isomorphism $D \xrightarrow{\sim} D'$, written $v\mapsto v'$, such that
$\gamma(u) - \gamma(v)$ and $\gamma'(u') - \gamma'(v')$ have the same sign for all edges $u\to v\in E(D)$. 
%
If $(D_1,\gamma_1)$ and $(D_2,\gamma_2)$ are labeled posets then let $\gamma_1\sqcup \gamma_2 : V(D_1\sqcup D_2)\to \ZZ$  be
%
any injective map such that $(\gamma_1\sqcup \gamma_2)(u) - (\gamma_1\sqcup \gamma_2)(v)$ has the same sign as $\gamma_i(u) - \gamma_i(v)$ for all $u,v \in V(D_i)$.

\begin{example}
Let $\cP_n$ be the free $\KK$-module spanned by all labeled poset with $n$ vertices, and set $\cP = \bigoplus_{n \in \NN} \cP_n$.
This is a connected, graded Hopf algebra with product 
$ \nabla((D_1,\gamma_1) \otimes (D_2,\gamma_2)) = (D_1\sqcup D_2, \gamma_1\sqcup \gamma_2)$
and coproduct  $
\Delta((D,\gamma)) = \sum  (D|_S,\gamma|_S) \otimes (D|_T,\gamma|_T)
$
where the sum is over all disjoint decompositions $S\sqcup T = V(D)$ 
 with $S$ a lower set and $T$ an upper set.
 \end{example}


A \defn{(strict) composition} $\alpha = (\alpha_1,\alpha_2,\dots,\alpha_l)$ is a finite sequence of positive integers,
called its \defn{parts}.
We say that $\alpha$ is a composition of $|\alpha| := \sum_i \alpha_i\in\NN$.

\begin{example}
Fix a composition $\alpha$ and let $x_1,x_2,\dots$ be a countable sequence of commuting variables.
The \defn{monomial quasisymmetric function} of $\alpha$  is the power series 
$M_{\alpha} = \sum_{1\leq i_1<i_2<\dots<i_l} x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2}\cdots  x_{i_l}^{\alpha_l}.$
Let $\QSym =  \KK\spanning\{ M_\alpha : \alpha\text{ any composition}\}$ 
be the ring of quasisymmetric functions of bounded degree.
This ring is a graded connected Hopf algebras 
for the coproduct   
$\Delta(M_\alpha) = \sum_{\alpha=\alpha'\alpha''} M_{\alpha'}\otimes M_{\alpha''}$
where $\alpha'\alpha''$ denotes concatenation of compositions,
and the counit that acts on power series by setting  
$x_1=x_2=\dots=0$.
\end{example}


A \defn{partition} is a composition sorted into decreasing order. 
We write $\lambda = 1^{m_1}2^{m_2}\cdots$ to denote the partition with exactly $m_i$ parts equal to $i$.

\begin{example}
The \defn{elementary symmetric function} of a partition $\lambda$
is the product $e_\lambda := e_{\lambda_1}e_{\lambda_2}\cdots$ where $e_n := M_{1^n}$.
These power series are a basis for the Hopf subalgebra $\Sym \subset \QSym$ of symmetric functions of bounded degree.
\end{example}

\subsection{Combinatorial Hopf algebras}

Following \cite{ABS}, a \defn{combinatorial Hopf algebra} $(H,\zeta)$ is a graded, connected Hopf algebra $H$ of finite graded dimension with an algebra
homomorphism $\zeta : H \to \KK$.

\begin{example}
The pair $(\QSym,\zetaq)$ is an example of a combinatorial Hopf algebra,
where 
 $\zetaq : \QSym\to \KK$ is the map
$\zetaq(f) = f(1,0,0,\dots)$, which sends $M_{(n)} \mapsto 1$ and  $M_\alpha \mapsto 0$ for all $\alpha$ with at least two parts. 
\end{example}

For a graph $G$ define 
 $\zeta_\cG(G) = 0^{|E(G)|}$
 where throughout we interpret $0^0 := 1$.
 For a directed acyclic graph $D$ likewise set 
 %
 $\zeta_\cO(D) = 0^{|E(D)|}$ for each directed acyclic graph $D$.
 These formulas extend to linear maps on $\cG$ and $\cO$.
Finally let  $\zeta_\cP : \cP \to \KK$ be the linear map with $\zeta_\cP((D,\gamma))=1$
if $\gamma(u)<\gamma(v)$ for all edges $u\to v \in E(D) $
with $\zeta_\cP((D,\gamma))=0$ otherwise.
 
\begin{example}
The pairs $(\cG,\zeta_{\cG})$,
$(\cO,\zeta_{\cO})$, and
$(\cP,\zeta_{\cP})$ are all combinatorial Hopf algebras.
\end{example}

A morphism 
 $\Psi :(H,\zeta) \to (H',\zeta')$ is a graded Hopf algebra morphism $\Psi : H \to H'$ with $\zeta = \zeta' \circ \Psi$.
Results in \cite{ABS} show that there exists a unique morphism from any combinatorial Hopf algebra to $(\QSym,\zetaq)$.
Moreover, the image of $\Psi$ is contained in the Hopf subalgebra   $\Sym\subset \QSym$
if $H$ is cocommutative.
There is an explicit formula for this morphism in \cite{ABS}, which 
translates to the following maps for our examples above.




 

 For a graph $G$, let $\AO(G)$ be its set of acyclic orientations.
 For a directed acyclic graph $D$, let $(D,\gamma^\op)$ be the labeled poset with
 $\gamma^\op(u) > \gamma^\op(v)$ for all edges $u\to v \in E(D)$.
Also set $\Gamma(D) =  \sum_{\kappa} x^\kappa \in \NN\llbracket x_1,x_2,\dots\rrbracket 
$
where the sum is over all maps $\kappa : V(D) \to \PP$ with 
$\kappa(u) < \kappa(v)$ whenever $u\to v \in E(D)$.


 More generally, for a labeled poset $(D,\gamma)$ define
$\Gamma(D,\gamma)= \sum_{\kappa} x^\kappa$ 
where the sum is over all maps $\kappa : V(D) \to \PP$ with 
$\kappa(u) \leq \kappa(v)$ whenever $u\to v \in E(D)$ and $\gamma(u) < \gamma(v)$,
and with 
$\kappa(u) < \kappa(v)$ whenever $u\to v \in E(D)$ and $\gamma(u) > \gamma(v)$.
Such maps $\kappa$ are called \defn{$P$-partitions} for $P=(D,\gamma)$ \cite{St1}.
 

\begin{proposition}\label{diagram1-prop}
There is a commutative diagram of combinatorial Hopf algebras
{\footnotesize\[
\begin{tikzcd}
(\cG,\zeta_\cG) \arrow[r,hook] \arrow[dr] & (\cO,\zeta_\cO) \arrow[r,hook] \arrow[d]  & (\cP,\zeta_\cP) \arrow[dl] \\
  & (\QSym,\zetaq)  &  
  \end{tikzcd}
\]}%
in which the horizontal maps send $G\mapsto \sum_{D \in \AO(G)} D$
and $D \mapsto (D,\gamma^\op)$,
and the $\QSym$-valued maps send $G \mapsto X_G$, $D \mapsto \Gamma(D)$,
and $(D,\gamma) \mapsto \Gamma(D,\gamma)$, respectively.
\end{proposition}


\section{$K$-theoretic generalizations}


We now explain how the results in the previous  can be extended ``$K$-theoretically'' to construct interesting quasisymmetric functions of unbounded degree, including $\bX_G$.
 This requires a brief discussion of monoidal structures on \defn{linearly compact modules}.


\subsection{Linearly compact modules}\label{completions-sect}
 
Let $A$ and $B$ be $\KK$-modules
with a $\KK$-bilinear form $\langle\cdot,\cdot\rangle : A \times B \to \KK$.
Assume  $A$ is free and $\langle\cdot,\cdot\rangle$
is \defn{nondegenerate} in the sense that
$b\mapsto \langle \cdot,b\rangle$ is a bijection $B\to \Hom_\KK(A,\KK)$.


Fix a basis $\{a_i\}_{i \in I}$ for $A$.
For each $i \in I$, there exists a unique $b_i \in B$ with
$\langle a_i, b_j \rangle = \delta_{ij}$ for all $i,j \in I$,
and we identify $b \in B$
with the formal linear combination $\sum_{i \in I} \langle a_i ,b\rangle b_i$.
We call $\{b_i\}_{i \in I}$ a \defn{pseudobasis} for $B$.

We give $\KK$ the discrete topology.
Then the \defn{linearly compact topology} \cite[\S I.2]{Dieudonne} on $B$ is the coarsest topology 
in which the maps $\langle a_i, \cdot \rangle : B \to \KK$ are all continuous.
This topology depends on $\langle\cdot,\cdot\rangle$ but not on the choice of basis for $A$.
For a basis of open sets in the linearly compact topology, see \cite[Eq.\ (3.1)]{Marberg2018}.


\begin{definition}
A \defn{linearly compact} (or \defn{LC} for short) $\KK$-module is a $\KK$-module $B$ with a nondegenerate
bilinear form $A \times B \to \KK$ for some free $\KK$-module $A$, given the linearly compact topology;
in this case we say that $B$ is the \defn{dual} of $A$.
Morphisms between such modules are continuous $\KK$-linear maps.
\end{definition}
 
 




Let $B$ and $B'$ be linearly compact $\KK$-modules dual to free $\KK$-modules $A$ and $A'$.
Let $\langle\cdot,\cdot\rangle$ denote both of the 
associated forms. 
Every linear map $\phi : A' \to A$ has a unique adjoint $\psi : B\to B'$ such that 
$\langle \phi(a), b\rangle = \langle a,\psi(b)\rangle$.  
A linear map $B \to B'$ is continuous when it is the adjoint 
of some linear map $A' \to A$.




\begin{definition}
Define
$B \htimes B' := \Hom_\KK(A\otimes A',\KK)$ and give this the LC-topology from the pairing 
$(A\otimes A') \times \Hom_\KK(A\otimes A',\KK) \to \KK$.
\end{definition}

If $\{b_i\}_{i \in I}$ and $\{b'_j \}_{j \in J}$ are pseudobases for $B$ and $B'$,
then we can realize the \defn{completed tensor product} $B\htimes B'$ concretely as the linearly compact $\KK$-module
with the set of tensors $\{ b_i \otimes b_j'\}_{(i,j) \in I \times J}$ as a pseudobasis.



 

 

Suppose $\nabla : B \htimes B \to B$ and $\iota : B \to \KK$ are continuous linear maps
which are the adjoints of linear maps $\epsilon : \KK \to A$ and $\Delta : A \to A \otimes A$.
We say that $(B,\nabla,\iota)$ is an \defn{LC-algebra}
if $(A,\Delta,\epsilon)$ is a $\KK$-coalgebra.
Similarly, we say that 
$\Delta : B \to B\htimes B$ and $\epsilon : B \to \KK$ 
make $B$ into an \defn{LC-coalgebra}
if $\Delta$ and $\epsilon$ are the adjoints of the product and unit 
maps of a $\KK$-algebra on $A$.
%
We define
\defn{LC-bialgebras} and \defn{LC-Hopf algebras} analogously; see \cite{Marberg2018}. 
If $B$ is an LC-Hopf algebra then its \defn{antipode} is the adjoint of the antipode of 
  $A$.



 
 

\subsection{Combinatorial LC-Hopf algebras}

Following \cite{Marberg2018}, we define a \defn{combinatorial LC-Hopf algebra} to be a pair $(H,\zeta)$ consisting of an LC-Hopf algebra $H$ with a continuous linear map $\zeta : H \to \KK\llbracket t\rrbracket$
such that $\zeta(\cdot)|_{t\mapsto 0} $ is the counit of $H$.
A morphism of combinatorial LC-Hopf algebras $\Psi :(H,\zeta) \to (H',\zeta')$ is a LC-Hopf algebra morphism $\Psi : H \to H'$ with $\zeta = \zeta' \circ \Psi$.

 
\begin{example}
Let $\mQSym$ be the set of all quasisymmetric power series in $\KK\llbracket x_1,x_2,\dots,\rrbracket$
of possibly unbounded degree. 
 The (co)product, (co)unit, and antipode  $\QSym$ all extend to continuous $\KK$-linear maps 
that make $\mQSym$
into an LC-Hopf algebra, with $\{M_\alpha\}$ as a pseudobasis.
Then $(\mQSym,\wzetaq)$ is a combinatorial LC-Hopf algebra when $\wzetaq$ is the map $\wzetaq: f \mapsto f(t,0,0,\dots)$.
\end{example}




The preceding example is an instance of a general construction.
 If $A$ is a free $\KK$-module with basis $S$, then its \defn{completion}
$\overline A$ is the 
set of arbitrary $\KK$-linear combinations of $S$.
We view $\overline A$ as a  linearly compact $\KK$-module with $S$ as a pseudobasis,
relative 
to the nondegenerate bilinear form $A \times \overline A \to \KK$
 making $S$ orthonormal.
 
If $(H,\zeta)$ is a combinatorial Hopf algebra then 
then there is a unique way of extending  its (co)unit and (co)product 
to continuous linear maps on
 $\overline H$.  
 As the Hopf algebra $H =\bigoplus_{n \in\NN}$ is graded,
 we can also extend $\zeta : H \to \KK$ to
a continuous linear map $\overline \zeta : \overline H \to \KK\llbracket t\rrbracket$ 
by the formula $\overline \zeta (h) = \zeta(h) t^n$ for $n \in \NN$ and $h \in H_n$.


\begin{proposition}
 If $(H,\zeta)$ is combinatorial Hopf algebra
then the extended structures just given make $(\overline H,\overline \zeta)$ into a combinatorial LC-Hopf algebra,
and the unique morphism  $(H,\zeta)\to (\QSym,\zetaq)$ extends to a morphism 
$(\overline H,\overline\zeta)\to (\mQSym,\wzetaq)$.
\end{proposition}


The pair $(\mQSym,\wzetaq)$ is a final object in the category of combinatorial LC-Hopf algebras,
meaning there is a unique morphism $(H,\zeta) \to(\mQSym,\wzetaq)$ for any combinatorial LC-Hopf algebra.
More specifically,
if $H$ has
 coproduct $\Delta$,
then define $\Delta^{(0)} = \id_H$ and 
$\Delta^{(k)} = (\Delta^{(k-1)}\htimes \id) \circ \Delta 
 : H \to H^{\htimes(k+1)} $
for $k\in \PP$.
For compositions $\alpha = (\alpha_1,\alpha_2,\dots,\alpha_k)$,
let $\zeta_\alpha : H \to \KK$ be the map sending $h \in H$ to the coefficient of $t^{\alpha_1}\otimes t^{\alpha_2}\otimes \cdots \otimes t^{\alpha_k}$
in $\zeta^{\otimes k} \circ \Delta^{(k-1)}(h) \in \KK\llbracket t \rrbracket$.
When $\alpha = \emptyset$ is empty let $\zeta_\emptyset = \zeta(\cdot)|_{t\mapsto 0}$ be the counit of $H$.

\begin{theorem}[{\cite{LM2019}}]
If $(H,\zeta)$ is a combinatorial LC-Hopf algebra then the map 
$\Psi_{H,\zeta} : h \mapsto \sum_\alpha \zeta_\alpha(h) M_\alpha$
is the unique morphism  $(H,\zeta)\to (\mQSym,\wzetaq)$.
\end{theorem}

Let $\mSym$ be the LC-Hopf subalgebra of symmetric functions in $\mQSym$. 
When $H$ cocommutative, the morphism $\Psi_{H,\zeta}$ evidently has its image in $\mSym$.


 
 

 
 
\subsection{Set-valued $P$-partitions}


 For a directed acyclic graph $D$, let
 $\bGamma(D) =  \sum_{\kappa} x^\kappa $
where the sum is over all maps $\kappa : V(D) \to \Set(\PP)$ with 
$\kappa(u) \prec \kappa(v)$ whenever $u\to v \in E(D)$.

\begin{example}
If $D = (1 \to 2 \to 3 \to \dots \to n)$ is an $n$-element chain
then define 
$ \bare_n := \bGamma(D)
  = \sum_{k=0}^\infty \tbinom{n-1+k}{n-1}  e_{n+k}.$
For each partition $\lambda$
let $\bare_\lambda := \bare_{\lambda_1}\bare_{\lambda_2}\cdots.$
These functions are a pseudobasis for $\mSym$.
\end{example}


For a labeled poset $(D,\gamma)$ define
$
\bGamma(D,\gamma)= \sum_{\kappa} x^\kappa$
where the sum is over all maps $\kappa : V(D) \to \Set(\PP)$ with 
$\kappa(u) \preceq \kappa(v)$ whenever $u\to v \in E(D)$ and $\gamma(u) < \gamma(v)$,
and with 
$\kappa(u) \prec \kappa(v)$ whenever $u\to v \in E(D)$ and $\gamma(u) > \gamma(v)$.
Such maps $\kappa$ are called \defn{set-valued $P$-partitions} for $P=(D,\gamma)$ in \cite{LamPylyavskyy,LM2019}.


\begin{example}
If $D = (1 \to 2 \to 3 \to \dots \to n)$ is an $n$-element chain and $S$ is the set of $i \in [n-1] $ with $\gamma(i) > \gamma(i+1)$ then 
the 
we define
$ \bL_{n,S}:=\bGamma(D,\gamma) $.
Following \cite{LamPylyavskyy}, the \defn{multifundamental quasisymmetric function} of a composition $\alpha$ is defined by 
$\bL_{\alpha} :=  \bL_{n,S}$ where $n=|\alpha|$ and $S =I(\alpha):= \{\alpha_1,\alpha_1+\alpha_2,\alpha_1+\alpha_2+\alpha_3,\dots\}\setminus\{n\}$.
These power series form another pseudobasis for $\mQSym$ \cite{LamPylyavskyy}.
An element of $\mQSym$ is \defn{multifundamental positive} if its expansion in this pseudobasis involves only nonnegative coefficients.
\end{example}

A \defn{multilinear extension} of a directed acyclic graph $D$  with $n$ vertices 
is a sequence $w=(w_1,w_2,\dots,w_N)$ with $V(D) = \{w_1,w_2,\dots,w_N\}$
such that $i<j$ whenever $w_i \to w_j \in E(D)$, and $w_i \neq w_{i+1}$ for all $i \in [N-1]$.
If $\mL(D)$ is the set of all multilinear extensions of $D$
and $\gamma : V(D) \to \ZZ$ is injective, then
$\bGamma(D,\gamma) = \sum_{w \in \mL(D)}  \bL_{\ell(w), \Des(w,\gamma)}$
where $\Des(w,\gamma) := \{ i\in [\ell(w)-1] : \gamma(w_i)>\gamma(w_{i+1})\}$ for $w \in \mL(D)$ \cite{LamPylyavskyy}.


 \subsection{Acyclic multi-orientations}
 
 Let $G$ be a graph.  
 An \defn{acyclic multi-orientation} of $G$ 
is an acyclic orientation of the $\alpha$-clan graph $\Cl_\alpha(G)$ from Remark~\ref{clan-rmk}
for some $\alpha : V(G) \to \PP$,
such that for each $v \in V(G)$ both
(a) if $i,j \in [\alpha(v)]$ have $i>j$  then $(v,i)\to (v,j)$ is a directed edge; and
(b) if $i \in [\alpha(v)-1]$ then there exists a directed path 
 involving no edges of the form $(v,j) \to (v,k)$
that connects $(v,i+1)$ to $(v,i)$.
%
Let $\MAO(G)$ be the set of all acyclic multi-orientations of $G$.
 


 
One can relate the $\bare$-expansion of the symmetric function $\bX_G$
to the source counts of its acyclic multi-orientations, generalizing a result of Stanley \cite[Thm.~3.3]{Stanley95}.

 
 

\begin{theorem} Let $G$ be a graph and suppose 
$\bX_G = \sum_{\lambda} c_\lambda \bare_\lambda$ for some coefficients $c_\lambda \in \ZZ$.
Then the number of acyclic multi-orientations of $G$ with exactly $j$ sources and $k$ vertices is $\sum_{{\ell(\lambda)=j, |\lambda| =k}} c_\lambda\in \NN$.
\end{theorem}

 

As noted in \cite{CPS}, in general, the coefficients $c_\lambda$ appearing in $\bX_G = \sum_{\lambda} c_\lambda \bare_\lambda$
can be negative, even when $G = \inc(P)$ is the \defn{incomparability graph} of a $(3+1)$-free poset $P$.


\subsection{Morphisms}

For each graph $G$ let $\bDelta(G) = \sum_{S\cup T = V(G)}   G|_S \otimes G|_T$. This only differs
from our other coproduct in allowing vertex decompositions that are not disjoint.
Likewise, for each directed acyclic graph $D$ and labeled poset $P = (D,\Gamma)$,
 define 
$\textstyle
\bDelta(D) = \sum  D|_S \otimes D|_T
$
and
$
\bDelta(P) = \sum  (D|_S,\gamma|_S) \otimes (D|_T,\gamma|_T),
$
where both sums are over all (not necessarily disjoint) vertex decompositions $S\cup T =  V(D)$ in which $S$ is a lower set, $T$ is an upper set, and $S\cap T$ is an antichain.

Use the continuous linear extensions of these operations
to replace the coproducts in the completions of $\cG$, $\cO$, and $\cP$,
and denote the resulting structures as $\mG$, $\mO$, and $\mP$
to distinguish them from $\wG$, $\wO$, and $\wP$.

\begin{theorem}\label{diagram2-prop}
The pairs $(\mG,\wzeta_\cG)$, $ (\mO,\wzeta_\cO)$, and $(\mP,\wzeta_\cP) $ are all combinatorial LC-Hopf algebras,
and there is a commutative diagram
{\footnotesize\[
\begin{tikzcd}
(\mG,\wzeta_\cG) \arrow[r,hook] \arrow[dr] & (\mO,\wzeta_\cO) \arrow[r,hook] \arrow[d]  & (\mP,\wzeta_\cP) \arrow[dl] \\
  & (\mQSym,\wzetaq)  &  
  \end{tikzcd}
\]}%
in which the horizontal maps send $G\mapsto \sum_{D \in \MAO(G)} D$
and $D \mapsto (D,\gamma^\op)$,
and the $\mQSym$-valued maps send $G \mapsto \bX_G$,
$D \mapsto \bGamma(D)$,
and $(D,\gamma) \mapsto \bGamma(D,\gamma)$.
\end{theorem}

 


 


\begin{corollary}  
The unique morphism  
$(\mG,\wzeta_\cG)  \to (\mQSym,\wzetaq)$
assigns a graph $G$ to its kromatic symmetric function,  which is symmetric as $\mG$ is cocommutative.
One can express $\bX_G= \sum_{D \in \MAO(G)}   \bGamma(D)$ and thus $\bX_G$ is multifundamental positive.
\end{corollary}



Fix a directed acyclic graph $D$. When $\alpha : V(D) \to \NN$ is any map,
define $\oCl_\alpha(D)$ to be the
directed acyclic graph with vertices $\cCl_\alpha(V(D))$ and with edges $ (v,i)\to (w,j)$  whenever $v\to w \in E(D)$ or 
 both $v=w$ and $i< j$.
%
When $\gamma : V(D) \to \ZZ$ is injective, so that
 $(D,\gamma)$ is a labeled poset,
define $\oCl_\alpha(D,\gamma) = (\oCl_\alpha(D), \tilde \gamma)$ to be the
labeled poset where $\tilde \gamma(v, i)  < \tilde \gamma(w, j)$ if and only if $\gamma(v) < \gamma(w)$ or 
both $v=w$ and $i>j$.

\begin{theorem} 
Assume $\QQ\subseteq \KK$. Then there is a commutative diagram 
{\footnotesize\[
\begin{tikzcd}
(\mG,\wzeta_\cG) \arrow[r,hook] \arrow[d,"\cong"] & (\mO,\wzeta_\cO) \arrow[r,hook] \arrow[d,"\cong"]  & (\mP,\wzeta_\cP) \arrow[d,"\cong"] \\
 (\wG,\wzeta_\cG) \arrow[r,hook] & (\wO,\wzeta_\cO)  \arrow[r,hook]&  (\wP,\wzeta_\cP)
  \end{tikzcd}
\]}%
with horizontal maps extending Proposition~\ref{diagram1-prop} and Theorem~\ref{diagram2-prop},
where the vertical isomorphisms are the continuous linear maps
sending $ G \mapsto \sum_{\alpha : V(G) \to \PP} \tfrac{1}{\alpha!} \Cl_\alpha(G)$,
$D \mapsto \sum_{\alpha : V(D) \to \PP}   \oCl_\alpha(D)$,
and
$(D,\gamma) \mapsto \sum_{\alpha : V(D) \to \PP}   \oCl_\alpha(D,\gamma)$, respectively.
\end{theorem}







\subsection{Kromatic quasisymmetric functions}

For the rest of this note we assume $\KK \supseteq \ZZ$ and let $q$ be a formal parameter.
We will consider the polynomial and power series rings $\Sym[q] \subset \mQSym[q]\subset \mQSym\llbracket q\rrbracket$.

Let $G$ be an \defn{ordered graph}, that is, a graph with a total order $<$ on its vertex set $V(G)$.
One can think of the ordering on $V(G)$ as defining an acyclic orientation on the edges of $G$,
and 
we do not distinguish between $G$ and another ordered graph $H$ if the corresponding directed acyclic graphs are isomorphic.
The following power series is a $K$-theoretic generalization of $X_G(q)$ and $q$-analogue of $\bX_G$:

\begin{definition}\label{or-def}
For an ordered graph  $G$ define
$
 \qX_G(q) = \sum_{\kappa}  q^{\asc_{G}(\max\circ \kappa)} x^\kappa  \in \mQSym[q]
 $
where the sum is over all proper set-valued colorings.  
\end{definition}


 


\begin{example} If $G=K_n$ is the complete graph on the vertex set $[n]$ then 
$\textstyle
 \qX_G(q) = [n]_q! \sum_{r= n}^\infty {r \brace n}  e_r =  [n]_q! \sum_{r= n}^\infty {r -1\brace n-1}  \bare_r$
where ${r \brace n}$ is the Stirling number of the second kind. 
\end{example}
 
Let us clarify the apparent asymmetry in Definition~\ref{or-def}.
 Define $\qX^{\des,\min}_G(q)$  by replacing ``$\asc$'' by ``$\des$''
 and ``$\max$'' by ``$\min$'' in Definition~\ref{or-def}.
 Construct $\qX^{\asc,\min}_G(q)$ and $\qX^{\des,\max}_G(q)$ analogously.
 Let $\rho$ be the continuous involution of $\mQSym[q]$ sending $M_{(\alpha_1,\dots,\alpha_k)} \mapsto M_{(\alpha_k,\dots,\alpha_1)}$.
 Let $\tau $ be the involution of $\mQSym[q]$ sending $f \mapsto q^{\deg_q (f)} f(q^{-1})$.
 
\begin{proposition}
We have
 {\small$ \qX_G(q) 
= \rho\(\qX^{\des,\min}_G(q)\)
= \tau\(\qX^{\des,\max}_G(q)\)
= \rho\circ\tau\(\qX^{\asc,\min}_G(q)\)
$}.
\end{proposition}

 
Recall that a \defn{cluster graph} is a disjoint union of complete graphs.

\begin{theorem}  We have
 $\qX_G(q) \in \mSym[q]$ if and only if $G$ is a {cluster graph}.
\end{theorem}

 


Fix $D \in \MAO(G)$.
Each vertex in $D$
has the form $(v,i)$ for some $v \in V(G)$ and $i \in \PP$.
Define 
$ \align(D) :=   |\{  (u,i)\to(v,j) \in E(D) : u<v\text{ and }i=j=1\}|.$

\begin{proposition} 
If $G$ is an ordered graph  then
$\qX_{G}(q) = \sum_{D \in \MAO(G)} q^{\align(D) } \bGamma(D)$.
This power series is multifundamental positive in the sense of being a possibly
infinite $\NN[q]$-linear combination of multifundamental quasisymmetric functions.
\end{proposition}

We can make this more explicit, generalizing a result in \cite{SW2016}.
Following \cite{LamPylyavskyy}, a \defn{multipermutation} of $n \in \NN$
is a word $w=w_1w_2\cdots w_m$ with $\{w_1,w_2,\dots,w_m\} = \{1,2,\dots,n\}$
and $w_i \neq w_{i+1}$ for all $i\in[m-1]$. Let $\bS_n$ be the set of all multipermutations of $n$.

For each $w=w_1w_2\cdots w_m  \in \bS_n$ 
let $\Inv(w)$ be the set of pairs $(w_i,w_j)$ with  $i<j $ and $w_i > w_j$ and 
$\{w_1,w_2,\dots,w_{i-1}\} \cap \{w_i\} = \{w_1,w_2,\dots,w_{j-1}\} \cap \{w_j\} = \varnothing.$
If $P$ is a poset on $[n]$ and $G = \inc(P)$ is its incomparability graph, then we set $\inv_G(w) := |\{ (a,b) \in \Inv(w) : \{a,b\} \in E(G)\}|$ and $S(w,P) :=   \{ m - i : i \in [m - 1] \text{ and }w_i \not >_P w_{i+1}\}$. 

\begin{theorem}
If $G = \inc(P)$ for a poset $P$ on $[n]$ then 
$\displaystyle \qX_{G}(q) = \sum_{w \in \bS_n} q^{\inv_G(w) } \bL_{\ell(w), S(w,P)}.$
\end{theorem}




The homogeneous component of $\qX_G(q)$ of lowest $x$-degree 
recovers $X_G(q)$. The latter power series, like $X_G$, 
naturally arises as the image of 
a morphism of combinatorial Hopf algebras.
In detail, assume $\KK = \ZZ[q]$ and 
let $\oG_n$ be the free $\KK$-module spanned by all isomorphism classes of
ordered graphs with $n$ vertices.
Then the direct sum $\oG := \bigoplus_{n \in \NN} \oG_n$
has a graded connected Hopf algebra structure in
which the product is disjoint union and the coproduct $\Delta_q$ satisfies
\be\label{bDq-eq}
\textstyle\Delta_q(G)= \sum_{S\sqcup T = V(G)}  q^{\asc_{G}(S,T)}G|_S \otimes G|_T
\quad\text{for each ordered graph $G$,}
\ee
where
$
\asc_{G}(S,T):=|\{(s,t) \in S\times T  : \{s<t\} \in E(G)\}|.
$
If  $\ozeta $ is the algebra morphism $\oG \to \KK$ sending $G \mapsto 0^{|E(G)|}$,
%
then $(\oG,\ozeta)$ is a combinatorial Hopf algebra and the 
morphism $(\oG,\ozeta) \to (\QSym,\zetaq)$ sends  $G\mapsto X_G(q)$.



We do not know how to give the completion $\fkm \oG\supset \oG$ a combinatorial LC-Hopf algebra structure that  lets us construct $\qX_G(q)$ in a similar way.
 In particular, we have not been able to find a $K$-theoretic  
 generalization of the coproduct $\Delta_q$.
Unlike the $q=1$ case, simply replacing 
$\sqcup$ in \eqref{bDq-eq} by arbitrary union $\cup$
does not lead to a co-associative map. This problem remains if we change the $q$-power exponent $\asc_G(S,T)$
to other forms like $\asc_G(S- T, T)$, $\asc_G(S, T- S)$, or $\asc_G(S- T, T- S)$.

 
 
\subsection{Another quasisymmetric analogue} %Chromatic quasisymmetric function}

The preceding results indicate that $\qX_G(q)$ is an interesting
quasisymmetric $q$-analogue of $\bX_G$ and $K$-theoretic extension of $X_G(q)$. However, there is another natural candidate for such a generalization.
Continue to let $G$ be an ordered graph.
Following \cite{Hwang}, an \defn{ascent} of a set-valued map $\kappa : V(G) \to \Set(\PP)$ is 
a tuple $(u,v,i,j)$ with  $\{u,v\} \in E(G)$, $i \in \kappa(u)$, $j\in \kappa(v)$, and both $u<v$ and $i<j$.
Let $\asc_{G}(\kappa)$ denote the number of such ascents.

\begin{definition}
For an ordered graph $G$, define
$ \oX_G(q) = \sum_{\kappa} q^{\asc_{G}(\kappa)} x^\kappa  \in \mQSym\llbracket q\rrbracket$
where the sum is over all proper set-valued colorings $\kappa : V(G) \to \Set(\PP)$.
\end{definition}

This definition is closely related to the quasisymmetric functions 
$X_G(\x,q,\mu)$ studied in \cite{Hwang}.
For each map $\mu : V(G) \to \NN$,   Hwang \cite{Hwang} defines
$X_G(\x,q,\mu) := \sum_\kappa q^{\asc_{G}(\kappa)} x^\kappa$ where the sum is over all 
proper set-valued colorings $\kappa$ of $G$ with $|\kappa(v)| = \mu(v)$.
Evidently $\oX_G(q) = \sum_{\mu : V(G) \to \PP} X_G(\x,q,\mu)$, and as noted in \cite[Rem.~2.2]{Hwang}
one has 
$
X_G(\x,q,\mu) = \tfrac{1}{[\mu]_q!} X_{\Cl_\mu(G)}(q)
$
where $[\mu]_q ! := \prod_{v \in V(G)} [\mu(v)]_q!$.
Here,  we view $\Cl_\mu(G)$ as an ordered graph with $(v,i) < (w,j)$ if either $v<w$ or $v=w$ and $i<j$.

Using these observations, various positive or alternating expansions of $X_G(q)$
(e.g., into fundamental quasisymmetric functions \cite[Thm.~3.1]{SW2016}, Schur functions \cite[Thm.~6.3]{SW2016},
power sum symmetric functions \cite[Thm.~3.1]{At2015}, or elementary symmetric functions \cite[Conj.~5.1]{SW2016})
can be extended in a straightforward way to $X_G(\x,q,\mu) $ and $\oX_G(q)$.
See Hwang's results
\cite[Thms.~3.3, 4.10, and 4.19]{Hwang}  and his conjecture \cite[Conj.~3.10]{Hwang}.

Some of these statements require $G$ to be isomorphic to the incomparability graph of a \defn{natural unit interval order}, meaning a poset $P$ on a finite subset of $\PP$ such that if  $x<_P z$
then $x<z$ and every $y$ incomparable in $P$ to both $x$ and $z$ has $x<y<z$ \cite[Prop.~4.1]{SW2016}.\footnote{A finite poset is isomorphic to one with these properties iff it is $(3+1)$- and $(2+2)$-free \cite[\S4]{SW2016}.}
If $G$ has this property, then so do all of its $\alpha$-clans.
Therefore $\oX_G(q)$ is symmetric if $G$ is the incomparability graph of a natural unit order interval  \cite[Thm.~3.8]{Hwang}.




\begin{example} If $K_n$ is the complete graph on  $[n]$ then 
$ \oX_{K_n}(q)= \sum_{r=n}^\infty F_r^{(n)}    e_r
$ for $ F_r^{(n)} :=  \sum_{\substack{k_1,k_2,\dots,k_n \in \PP  \\ k_1+k_2+\dots+k_n = r}} \tbinom{r}{k_1, k_2,\dots,k_n}_q$
where $(q)_n := \prod_{i\in[n]}(1-q^i)$ and $ \tbinom{r}{k_1, k_2,\dots,k_n}_q  = \frac{(q)_r}{(q)_{k_1} (q)_{k_2}\cdots (q)_{k_n}}$. 
\end{example}

When $q$ is a prime power, $F_r^{(n)}$ counts the \defn{strictly increasing flags} of $\FF_q$-subspaces $0=V_0 \subsetneq V_1 \subsetneq \dots \subsetneq V_n = \FF_q^r.$
Vinroot \cite{Vinroot12} derived a recurrence for the
\defn{generalized Galois numbers} $G_r^{(n)}  := \sum_{i=0}^n \binom{n}{i} F_r^{(i)}$.
This can be used to show (setting $F^{(n)}_r = 0$ if $r<0$) that:
\begin{proposition}  
One has
$\textstyle F_{r+1}^{(n)}
=\sum_{i=0}^{n-1} \sum_{j=n-1-i}^n      \tbinom{n}{j}\tbinom{j}{n-1-i}   (-1)^{i} \tfrac{(q)_r}{(q)_{r-i}} F_{r-i}^{(j)}.$

\end{proposition}
 

Like $\qX_G(q)$, the power series $\oX_G(q)$ also does not seem to arise naturally as the image in $\mQSym$ of a  combinatorial LC-Hopf algebra.
Unlike $\qX_G(q)$, however,
 $\oX_G(q)$ is not generally multifundamental-positive (or $\bare$-positive).
However, $\oX_G(q)$ does have a nontrivial positivity property
that is not shared by $X_G(\x,q,\mu)$ or $\qX_G(q)$.


A \defn{set-valued tableau} $T$ of shape $\lambda$ is an assignment of sets $T_{ij} \in \Set(\PP)$
to the cells $(i,j)$ in  
$\D_\lambda = \{ (i,j) \in \PP\times \PP : 1 \leq j \leq \lambda_i\}$
of a partition $\lambda$. We write $(i,j)\in T$ to indicate that $(i,j)$ belongs to the 
shape of $T$.  
A set-valued tableau $T$ is \defn{semistandard} if $T_{ij} \preceq T_{i,j+1}$ 
and $T_{ij} \prec T_{i+1,j}$
for all relevant positions.
Let $x^T: = \prod_{(i,j) \in T} \prod_{k \in T_{ij}} x_k$ and $|T| := \sum_{(i,j) \in T} |T_{ij}|$.

\begin{definition}
The \defn{symmetric Grothendieck function} of a partition $\lambda$ is 
the power series
$ \bars_\lambda := \sum_{ T\in \SetSSYT(\lambda)} (-1)^{|T|-|\lambda|} x^T \in \ZZ\llbracket x_1,x_2,\dots \rrbracket$
where $\SetSSYT(\lambda)$ is the set of all semistandard set-valued tableaux of shape $\lambda$.
\end{definition}



 
Each $\bars_\lambda $ is in $ \mSym$  and the set of all 
symmetric Grothendieck functions is another pseudobasis for $\mSym$.
We write $\mu \subseteq \lambda$ for two partitions with $\D_\mu \subseteq \D_\lambda$ and set $\D_{\lambda/\mu} := \D_\lambda \setminus \D_\mu$.
A \defn{semistandard tableau} of shape $\lambda/\mu$ is a filling of $\D_{\lambda/\mu}$
by positive integers such that each row is weakly increasing
and each column is strict increasing.
 
\begin{definition}[{\cite[Def.~3.8]{CPS}}] Suppose $P$ is a finite poset and $\lambda$ is a partition.
A \defn{Grothendieck $P$-tableau} of shape $\lambda$ is a pair   $T=(U,V)$ 
with these two properties: 
(a) $U$ is a filling of $\D_\mu$ by elements of $P$  for some partition $\mu\subseteq\lambda$,
such that each element of $P$ is in at least one cell,
and  for each $(i,j) \in \D_\mu$ 
one has
$U_{ij} <_P U_{i,j+1}\text{ if }(i,j+1) \in \D_\mu $ and 
$U_{ij} \not>_P U_{i+1,j}\text{ if }(i+1,j) \in \D_\mu$; and
(b) $V$ is a semistandard tableau of shape $\lambda/\mu$, whose entries in each row $i$ are all less than $i$ 
(so $\D_{\lambda/\mu}$ must have no cells in the first row).



\end{definition}

Let $\oT_P$ be the set of Grothendieck $P$-tableaux.
Let $\lambda(T)$ be the shape of $T \in \oT_P$.
One of the main results of \cite{CPS} 
establishes that if $G=\inc(P)$ is the incomparability graph a $(3+1)$-free poset $P$ then 
$\bX_G =\sum_{T \in \oT_P} \bars_{\lambda(T)}.$
This theorem has a $q$-analogue.

 


Suppose $P$ is a finite poset on a subset of $\PP$,
and let $G = \inc(P)$.
Choose some $T = (U,V) \in \oT_P$ and let $\mu$ be the partition shape of the tableau $U$.
Define a \defn{$G$-inversion} of $T$
to be a pair of cells $(i,j),(k,l) \in \D_\mu$ with $i>k$ such that 
$ U_{ij} < U_{kl}$ but $ U_{ij} \not<_P U_{kl}$ and $ U_{ij} \not>_P U_{kl}.$
Finally, let $\inv_G(T)$ be the number of all $G$-inversions of $T$.

\begin{theorem}  If $P$ is a natural unit interval order then 
$\oX_G =\sum_{T \in \oT_P} q^{\inv_G(T)} \bars_{\lambda(T)}.$
\end{theorem}



%\acknowledgements{\lipsum[20]}

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



\end{document}
