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

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage[utf8]{inputenc}
%\usepackage{pst-node}
%\usepackage{auto-pst-pdf}
\usepackage{tikz-cd} 
\usepackage{comment}
\usepackage{stmaryrd}
\usepackage{amsfonts,tikz}
\usepackage{mathtools}
\usepackage{youngtab}
\usepackage{ytableau}
\usetikzlibrary{positioning,automata}
\tikzset{every loop/.style={min distance=10 mm, in=60, out=120, looseness=10}}

\definecolor{darkblue}{rgb}{0.0,0,0.7}
\newcommand{\darkblue}{\color{darkblue}}
\newcommand{\newword}[1]{\textcolor{darkblue}{\textbf{\textit{#1}}}}

% use these commands for typesetting doi and arXiv references in the bibliography
% \newcommand{\doi}[1]{\href{https://doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{https://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newcommand{\bk}{\backslash}
\newcommand{\lm}{\lambda}
\newcommand{\mt}{\widetilde{m}}
\newcommand{\mg}{\mathbb{G}}
\newcommand{\Lm}{\Lambda}
\newcommand{\tm}{\widetilde{m}}
\newcommand{\TM}{\overline{\widetilde{m}}}

\newcommand{\KX}{\overline{X}}
\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\groth}{\overline{s}}
\newcommand{\cc}{\mathsf{c}}
\newcommand{\SSYT}{\mathrm{SSYT}}
\newcommand{\SV}{\mathrm{SV}}
\newcommand{\trans}{\mathsf{T}}
\newcommand{\SSC}{\mathsf{SSC}}
\newcommand{\Gr}{\mathrm{Gr}}

\newcommand{\ebox}{\overline{e}}
\newcommand{\estar}{\overline{e}'}

\newcommand{\Lift}{\textbf{\textsf{Lift}}}

\newtheorem{lemma}{Lemma}[section]
\newtheorem{cor}[lemma]{Corollary}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{conj}[lemma]{Conjecture}
\newtheorem{conjecture}[lemma]{Conjecture}
\newtheorem{problem}[lemma]{Problem}
\newtheorem{proposition}[lemma]{Proposition}

\theoremstyle{remark}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{obs}[lemma]{Observation}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{examplex}[lemma]{Example}
\newenvironment{example}
  {\pushQED{\qed}\renewcommand{\qedsymbol}{$\diamondsuit$}\examplex}
  {\popQED\endexamplex}
  
% \numberwithin{equation}{section}

\usepackage{todonotes}
\newcommand{\Logan}[1]{\todo[size=\tiny,inline,color=red!30]{#1 \\ \hfill --- Logan}}
\newcommand{\Oliver}[1]{\todo[size=\tiny,inline,color=green!30]{#1 \\ \hfill --- Oliver}}
\newcommand{\Sophie}[1]{\todo[size=\tiny,inline,color=orange!30]{#1 \\ \hfill --- Sophie}}

% \newtheorem{thm}{Theorem}
% \newtheorem{lem}{Lemma}

\addbibresource{bib_fpsac}

%% define your title in the usual way
\title{The Kromatic Symmetric Function: A $K$-theoretic analogue of $X_G$}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Logan Crew\addressmark{1}, Oliver Pechenik\addressmark{1}, \and Sophie Spirkl\thanks{{\{lcrew,opecheni,sspirkl\}@uwaterloo.ca}. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding
reference numbers RGPIN-2020-03912, RGPIN-2021-02391, and RGPIN-2022-03093]. \newline Cette recherche a \'et\'e financ\'ee par le Conseil de recherches en sciences naturelles et en g\'enie du Canada (CRSNG),
[num\'eros de r\'ef\'erence RGPIN-2020-03912, RGPIN-2021-02391, et RGPIN-2022-03093]. \newline This project was funded in part by the Government of Ontario.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada}

%% 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{Schur functions are a basis of the symmetric function ring that represent Schubert cohomology classes for Grassmannians. Replacing the cohomology ring with $K$-theory yields a rich combinatorial theory of inhomogeneous deformations, where Schur functions are replaced their $K$-analogues, the basis of \emph{symmetric Grothendieck functions}.
We introduce and initiate a theory of the \emph{Kromatic symmetric function} $\KX_G$, a $K$-theoretic analogue of the chromatic symmetric function $X_G$ of a graph $G$. The Kromatic symmetric function is a generating series for graph colorings in which vertices may receive any nonempty set of distinct colors such that neighboring color sets are disjoint. 

Our main result lifts a theorem of Gasharov (1996) to this setting, showing that when $G$ is a claw-free incomparability graph, $\KX_G$ is a positive sum of symmetric Grothendieck functions. This result suggests a topological interpretation of Gasharov's theorem. We then show that the Kromatic symmetric functions of path graphs are not positive in any of several $K$-analogues of the $e$-basis of symmetric functions, demonstrating that the Stanley--Stembridge conjecture (1993) does not have such a lift to $K$-theory and so is unlikely to be amenable to a topological perspective.
We also define a vertex-weighted extension of $\KX_G$ and show that it admits an edge deletion-contraction relation. Finally, we give a $K$-analogue for $\KX_G$ of the classic monomial-basis expansion of $X_G$.}

%% put your French abstract here, or comment this out if you don't have one

%% put your keywords here, or comment this out if you don't have them yet
\keywords{chromatic symmetric function, $K$-theory, Stanley-Stembridge conjecture, deletion-contraction, symmetric Grothendieck function}

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

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

\begin{document}

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

\section{Introduction}

The \emph{chromatic symmetric function} $X_G$ of a graph $G$ was introduced by R.~Stanley \cite{stanley} as a generalization of G.D.~Birkhoff's \emph{chromatic polynomial} \cite{birkhoff}. While the chromatic polynomial enumerates proper graph colorings by the number of colors used, $X_G$ also records how many times each color is used. A recent boom of research regarding $X_G$ has focused on the \emph{Stanley--Stembridge conjecture} \cite{stanley.stembridge}, which proposes (in a reformulation by M.~Guay-Paquet \cite{guay}) that unit interval graphs have chromatic symmetric functions that expand positively in the $e$-basis of the ring $\Sym$ of symmetric functions. In the last few years, various special cases of this conjecture have been established through direct combinatorial analysis, including the cases of \emph{lollipop graphs} \cite{dahl} and many \emph{claw-free} graphs \cite{hamel2019}.
Another approach has been to consider various generalizations of the chromatic symmetric function and corresponding lifts of the Stanley--Stembridge conjecture. Examples of this latter approach include the \emph{chromatic quasisymmetric function} and \emph{Shareshian--Wachs conjecture} of \cite{wachs} (further studied in, e.g., \cite{abreu, per2022, cho2022, colm}), and D.~Gebhard--B.~Sagan's \cite{noncomm} chromatic symmetric function in noncommuting variables combined with notions of \emph{$(e)$-positivity} and \emph{appendable $(e)$-positivity} (further studied in, e.g., \cite{centered, dahlberg2019, dahl2}). Our work provides a novel generalization of $X_G$ in the same vein.

An important appearance of the ring of symmetric functions $\Sym$ is as the cohomology of complex \emph{Grassmannians} (parameter spaces for linear subspaces of a vector space) or more precisely for the classifying space $BU$. Here, the \emph{Schubert classes} derived from a natural cell decomposition of $BU$ are represented by the \emph{Schur function} basis $s_\lambda$ of $\Sym$. A richer perspective into the topology of $BU$ is obtained by replacing cohomology with a generalized cohomology theory. In particular, there has been much focus on studying the associated combinatorics of the \emph{$K$-theory} ring (see, e.g., \cite{Buch,Monical.Pechenik.Searles,Pechenik.Yong,Thomas.Yong}). In this context, many of the classical objects of symmetric function theory are seen to have interesting $K$-analogues, often resembling ``superpositions'' of classical objects. For example, classical \emph{semistandard Young tableaux} are replaced by \emph{set-valued tableaux} (allowing multiple labels per cell), while Schur functions are replaced by \emph{Grothendieck polynomials} $\groth_\lambda$ (inhomogeneous deformations of $s_\lambda$).

Our work introduces a $K$-analogue of the chromatic symmetric function $X_G$, enumerating colorings of the graph $G$ that assign a nonempty set of distinct colors to each vertex such that adjacent vertices receive disjoint sets. While our \emph{Kromatic symmetric function} $\KX_G$ is new, similar functions have been previously considered. The first such function was originally discussed by Stanley \cite{stanley2} in the context of graph analogues of symmetric functions, with connections to the real-rootedness of polynomials. Recently, as part of his effort to refine Schur-positivity results and the Stanley--Stembridge conjecture, B.-H.~Hwang \cite{hwang} studied a similar quasisymmetric function for graphs endowed with a fixed map $\alpha: V(G) \rightarrow \mathbb{N}$ that dictates the size of the set of colors each vertex receives. To connect chromatic quasisymmetric functions of vertex-weighted graphs to \emph{horizontal-strip LLT polynomials}, F.~Tom \cite{privtom} has considered a variant for fixed $\alpha$ with repeated colors allowed. Our work appears to be the first to connect these ideas to the combinatorics of $K$-theoretic Schubert calculus. (However, \cite{Nenashev.Shapiro} is similar in spirit to our work, developing a $K$-theoretic analogue of the \emph{Postnikov--Shapiro algebra} \cite{Postnikov.Shapiro}, an apparently unrelated invariant of graphs).

In this extended abstract, having introduced the \emph{Kromatic symmetric function}, we begin to develop its combinatorial theory. Further details and proofs are given in the full manuscript \cite{kromatic}. We show that the Kromatic symmetric function $\KX_G$ for any graph $G$ expands positively in a $K$-theoretic analogue (that we also introduce) of the \emph{monomial basis} of $\Sym$. In this expansion, the coefficients enumerate coverings of the graph by (possibly overlapping) \emph{stable sets}. We further extend the definition of $\KX_G$ to a vertex-weighted setting, where we give a deletion-contraction relation analogous to that developed by the first and last authors \cite{delcon} for the vertex-weighted version of $X_G$. 

Our main result is that the Kromatic symmetric function of a \emph{claw-free incomparability graph} expands positively in the symmetric Grothendieck basis $\groth_\lambda$ of $\Sym$, lifting to $K$-theory a celebrated result of V.~Gasharov \cite{gash} that such graphs have Schur-positive chromatic symmetric functions. While all known proofs of Gasharov's theorem are representation-theoretic or purely combinatorial, the existence of our $K$-theoretic analogue suggests that both results likely also have an interpretation in terms of the topology of Grassmannians. Precisely, for each claw-free incomparability graph $G$, there should be a subvariety of the Grassmannian whose cohomology class is represented by $X_G$ and whose $K$-theoretic structure sheaf class is represented by $\KX_G$. It would be very interesting to have an explicit construction of such subvarieties.

On the other hand, we show that the Kromatic symmetric functions $\KX_{P_n}$ of path graphs $P_n$ generally do not expand positively in either of two $K$-theoretic deformations we propose for the $e$-basis of $\Sym$. This fact suggests that the Stanley--Stembridge conjecture, if true, is not naturally interpreted in terms of the cohomology of Grassmannians and is unlikely to be amenable to such topological tools from Schubert calculus. We hope these observations can play a similar role to \cite{Dahlberg.Foley.vanWilligenburg} in limiting the range of potential avenues of attack on the Stanley--Stembridge conjecture.

{\bf This extended abstract is organized as follows.} In \cref{sec:background}, we provide an overview of the background and notation used from symmetric function theory (\cref{sec:sym}), $K$-theoretic Schubert calculus (\cref{sec:K}), and graph theory (\cref{sec:graph}). In \cref{sec:Kromatic}, we formally introduce the Kromatic symmetric function $\KX_G$ and give its basic properties, including a formula for the expansion in a new $K$-analogue of the monomial-basis of $\Sym$ and a deletion-contraction relation for a vertex-weighted generalization. We also give our main theorem that the Kromatic symmetric functions of claw-free incomparability graphs expand positively in symmetric Grothendieck functions, lifting the main result of \cite{gash}. In \cref{sec:StanleyStembridge}, we introduce two different $K$-theoretic analogues of the $e$-basis of $\Sym$ and show that the Kromatic symmetric function $\KX_{P_3}$ of a $3$-vertex path graph $P_3$ is not positive in either analogue, casting doubt on hopes for a Schubert calculus-based approach to the Stanley--Stembridge conjecture.

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

Throughout this work, $\mathbb{N}$ denotes the set of (strictly) positive integers. We write $[n]$ for the set of positive integers $\{1, 2, \dots, n\}$. If $S$ is any set, $2^S$ denotes the power set of all subsets of $S$.

\subsection{Partitions and Symmetric Functions}\label{sec:sym}

In this section, we give a brief overview of necessary background material necessary. Further details can be found, e.g., in the textbooks of Stanley \cite{stanleybook}, Manivel \cite{manivel}, and Macdonald \cite{mac}.

An \newword{integer partition} $\lambda = (\lm_1 \geq \lm_2 \geq  \dots \geq \lm_k)$ is a finite nonincreasing sequence of positive integers. We define $\ell(\lm)$ to be the length of the sequence $\lm$ (so above, $\ell(\lm) = k$). Define $r_i(\lm)$ to be the number of occurrences of $i$ as a part of $\lm$ (so, for example, $r_1(2,1,1) = 2$). If 
\[ 
\sum_{i=1}^{\ell(\lm)} \lm_i = n,
\]
we say that $\lm$ is a partition of $n$, and we write $\lm \vdash n$.
The \newword{Young diagram of shape} $\lm$ is a set of squares called \newword{cells}, left- and top-justified (i.e., in ``English notation''), so that the $i$th row from the top contains $\lm_i$ cells. For example, the Young diagram of shape $(2,2,1)$ is $\ytableausetup{smalltableaux}
\ydiagram{2,2,1}$. Let $C(\lm)$ denote the set of cells of the Young diagram of shape $\lm$. If $\cc \in C(\lm)$ is a cell of the Young diagram of shape $\lambda$, we write $\cc^\uparrow$ for the cell immediately above $\cc$ (assuming it exists), $\cc^\rightarrow$ for the cell immediately right of $\cc$, etc. We write $\lambda^\trans$ for the \newword{transpose} of $\lambda$, the integer partition whose Young diagram is obtained from that of $\lambda$ by exchanging rows and columns.

Let $S_\mathbb{N}$ denote the set of all permutations of the set $\mathbb{N}$ fixing all but finitely-many elements.
A \newword{symmetric function} $f \in \mathbb{C} \llbracket x_1,x_2,\dots, \rrbracket$ is a power series of bounded degree such that for each permutation $\sigma \in S_{\mathbb{N}}$, we have $f(x_1,x_2,\dots) = f(x_{\sigma(1)}, x_{\sigma(2)}, \dots)$. The set $\Sym \subset \mathbb{C}\llbracket x_1,x_2,\dots \rrbracket$ of symmetric functions forms a $\mathbb{C}$-vector space. Furthermore, if $\Lm^d$ denotes the set of symmetric functions that are homogeneous of degree $d$, then each $\Sym^d$ is a vector space, and \[
\Sym = \bigoplus_{d=0}^{\infty} \Sym^d
\]
as graded vector spaces. 

The dimension of $\Sym^d$ as a $\mathbb{C}$-vector space is equal to the number of integer partitions of $d$, and many bases of symmetric functions are conveniently indexed by integer partitions. Below we provide some commonly used bases that will be used in this paper.

\begin{definition}
The following are bases of $\Sym$:
\begin{itemize}
    \item the \newword{monomial symmetric functions} $\{m_{\lm}\}$, defined as
    \[
    m_{\lm} = \sum x_{i_1}^{\lm_1} \dots x_{i_{\ell(\lm)}}^{\lm_{\ell(\lm)}},
    \]
    where the sum ranges over all distinct monomials formed by choosing distinct positive integers $i_1, \dots, i_{\ell(\lm)}$;
    \item the \newword{augmented monomial symmetric functions} $\{ \tm_{\lm} \}$, defined as
    \[
    \tm_{\lm} = \left(\prod_{i=1}^{\infty} r_i(\lm)! \right) m_{\lm};
    \]
    \item the \newword{elementary symmetric functions} $\{e_\lambda \}$, defined by 
    \[
    e_n = \prod_{i_1 < \dots < i_n} x_{i_1} \dots x_{i_n}; \quad e_{\lm} = e_{\lm_1} \dots e_{\lm_{\ell(\lm)}}; 
    \]
    \item and the \newword{complete homogeneous symmetric functions} $\{h_\lambda \}$, defined by
    \[
    h_n = \prod_{i_1 \leq \dots \leq i_n} x_{i_1} \dots x_{i_n}; \quad h_{\lm} = h_{\lm_1} \dots h_{\lm_{\ell(\lm)}}.
    \]
\end{itemize}
\end{definition}

The space of symmetric functions is equipped with a natural inner product $\langle \cdot, \cdot \rangle$; it may be defined by
$
\langle h_{\lm}, m_{\mu} \rangle = \delta_{\lm,\mu},
$
where $\delta_{\bullet, \bullet}$ denotes the \emph{Kronecker delta function}. 

We will also need the basis of Schur functions.  A \newword{Young tableau} of shape $\lm$ is a function $T: C(\lm) \rightarrow \mathbb{N},$
typically visualized by writing the value $T(\cc)$ in the cell $\cc$. A Young tableau $T$ of shape $\lm$ is \newword{semistandard} if for each cell $\cc \in C(\lm)$, we have $T(\cc) \leq T(\cc^\rightarrow)$ and $T(\cc) < T(\cc^\downarrow)$ whenever the cells in question exist. We write $\SSYT(\lambda)$ for the set of all semistandard Young tableaux of shape $\lambda$.
The \newword{Schur function} $s_{\lm}$ is defined by
\[
s_{\lm} = \sum_{T\in \SSYT(\lambda)} x^T, \quad \text{where} \quad
x^T = \prod_{\cc \in C(\lm)} x_{T(\cc)}.\] As $\lambda$ ranges over integer partitions, the Schur functions are another basis of $\Sym$. The  inner product on $\Sym$ also satisfies
$
\langle s_{\lm}, s_{\mu} \rangle = \delta_{\lm,\mu^\trans}.
$

When $f \in \Sym$ is a symmetric function and $\{b_{\lm}\}$ is a basis of symmetric functions indexed by integer partitions $\lm$, the notation $[b_{\mu}]f$ denotes the coefficient of $b_{\mu}$ when $f$ is expanded in the $b$-basis. A symmetric function $f \in \Sym$ is said to be \newword{$b$-positive} if $[b_{\mu}]f$ is nonnegative for every integer partition $\mu$.

\subsection{$K$-theoretic Schubert calculus}\label{sec:K}
The \newword{Grassmannian} $\Gamma_k = \Gr_k(\mathbb{C}^\infty)$ is the parameter space of $k$-dimensional vector subspaces of the space of all eventually-zero sequences of complex numbers. The space $\Gamma_k$ can be given the structure of a projective Ind-variety and has a cell decomposition into cells $\Gamma_\lambda$ indexed by partitions with at most $k$ parts. Each $\Gamma_\lambda$ induces a cohomology class $\sigma_\lambda \in H^\star(\Gamma_k)$ and classically we have $H^\star(\Gamma_k)  \cong \Sym_k = \Sym \cap \mathbb{C}[x_1, \dots, x_k]$ with the isomorphism taking the class of the cell $\sigma_\lambda$ to the Schur polynomial $s_\lambda(x_1, \dots, x_k)$.

Each cell-closure in $\Gamma_k$ also has a structure sheaf, inducing a class in the representable \newword{$K$-theory} ring $K^0(\Gamma_k)$. These $K$-theoretic classes are represented by inhomogeneous symmetric polynomials called \emph{Grothendieck polynomials} $\groth_\lambda(x_1, \dots, x_k)$.

A \newword{set-valued tableau} of shape $\lm$ is a filling $T$ of each cell of $C(\lm)$ with a nonempty \emph{set} of positive integers. The set-valued tableau $T$ is \newword{semistandard} if for each cell $\cc \in C(\lm)$, we have $\max T(\cc) \leq \min T(\cc^\rightarrow)$ and $\max T(\cc) < \min T(\cc^\downarrow)$ whenever the cells in question exist.
In other words, $T$ is semistandard if every Young tableau formed by choosing one number from the set of each cell is semistandard. Let $\SV(\lambda)$ denote the set of all semistandard set-valued tableaux of shape $\lambda$.
The \newword{symmetric Grothendieck function} $\groth_{\lm}$ is
\[
\groth_{\lm} = \sum_{T \in \SV(\lm)} (-1)^{|T|-\ell(\lm)}x^T,
\]
where $|T| = \sum_{\cc \in C(\lm)} |T(\cc)|$ and $x^T = \prod_{\cc \in C(\lm)} \prod_{i \in T(\cc)} x_i$.
Note that $\groth_{\lm}$ contains terms of degree greater than or equal to $|\lm|$, and that the sum of all of its lowest-degree terms is equal to $s_{\lm}$.

\subsection{Graphs and Coloring}\label{sec:graph}

Here, we recall basic notions, terminology, and notations from graph theory. For further details, see, e.g., the textbooks \cite{Diestel,West}.

A \newword{graph} $G$ consists of a set $V$ of \newword{vertices}, and a set $E$ of unordered pairs of distinct vertices called \newword{edges}. All graphs in this paper are \emph{simple}, so there are no loops, and no multi-edges. When $\{v_1,v_2\} \in E(G)$, we will typically denote this edge by $v_1v_2$ and say $v_1$ and $v_2$ are \newword{adjacent}. Two graphs $G,G'$ are \newword{isomorphic} if there is a bijection $\phi : V(G) \to V(G')$ such that $uv \in E(G)$ if and only if $\phi(u) \phi(v) \in E(G')$. In this paper, we consider graphs up to isomorphism.

The \newword{complete graph} $K_d$ with $d$ vertices is the graph such that $V(K_d) = [d]$, and \[E(K_d) = \{vw: v, w \in [d], v \neq w\}.\] The $n$-vertex \newword{path} $P_n$ has vertex set $V(P_n) = [n]$ and edge set $E(P_n) = \{ uv : u,v \in [n], v-u = 1\}$. The \newword{claw} $K_{1,3}$ has vertex set $V(K_{1,3}) = [4]$ and edge set $E(K_{1,3}) = \{12,13,14\}$.

A \newword{stable set} (or \newword{independent set}) of a graph $G$ is a set $S \subseteq V(G)$ of vertices such that for each $v, w \in S$, $vw \notin E(G)$. A \newword{clique} of a graph $G$ is a set $S \subseteq V(G)$ of vertices such that for each $v \neq w \in S$, $vw \in E(G)$. 

For $\alpha : V(G) \to \mathbb{N}$ a vertex weighting of the graph $G$, the \newword{$\alpha$-clan graph of $G$} is the graph $C_\alpha(G)$ obtained by blowing up each vertex $v$ into a clique of $\alpha(v)$ vertices. More formally, $C_\alpha(G)$ has vertex set 
$
V(C_\alpha(G)) = \{(v,i) : v \in V(G), i \in [\alpha(v)] \}.
$
In $C_\alpha(G)$, the vertices $(v,i)$ and $(w,j)$ are adjacent either if $vw \in E(G)$ or if both $v=w$ and $i \neq j$. 

Given a vertex $v \in V(G)$, its \newword{open neighborhood} $N(v)$ is defined by $N(v) = \{w: vw \in E(G)\}$. 
The \newword{contraction} of a graph $G$ by an edge $vw \in E(G)$, notated $G/e$, is the graph with vertex set $V(G/e) = V(G) \bk \{v,w\} \cup \{v^*\}$, and edge set $E(G/e) = E(G) \bk (vN(v) \cup wN(w)) \cup (v^*N(v) \cup v^*N(w))$.

A \newword{coloring} of a graph $G$ is a function $\kappa: V(G) \rightarrow \mathbb{N}$. A coloring $\kappa$ of $G$ is \newword{proper} if $\kappa(a) \neq \kappa(b)$ whenever $ab \in E(G)$. 

The \newword{chromatic symmetric function}\cite{stanley}  of a graph $G$ is the power series
\[
X_{G} = \sum_{\kappa} \prod_{v \in V(G)} x_{\kappa(v)}
\]
where the first sum ranges over all proper colorings $\kappa$ of $G$. Note that, for every graph $G$, $X_G \in \Sym$.




\section{The Kromatic Symmetric Function}\label{sec:Kromatic}

A \newword{vertex-weighted graph} $(G,\alpha)$ consists of a graph $G$ together with a function 
$\alpha \colon V(G) \rightarrow \mathbb{N};
$
we call $\alpha$ the \newword{weight function} on the vertices of $G$.
A \newword{proper $\alpha$-coloring} of $G$ is a function 
$
\kappa : V(G) \to 2^\mathbb{N} \bk \{\emptyset \}
$
assigning to each $v \in V(G)$ a set of $\alpha(v)$ distinct colors in $\mathbb{N}$, subject to the constraint that when $uv \in E(G)$, we have $\kappa(u) \cap \kappa(v) = \emptyset$. Note that these conditions are equivalent to saying that any choice of a single element from each $\kappa(v)$ yields a proper coloring of $G$. A \newword{proper set-coloring} of $G$ is a proper $\alpha$-coloring for some weight function on the vertices of $G$.

The \newword{chromatic symmetric function} of the vertex-weighted graph $(G,\alpha)$ is
\[
X_{G}^\alpha = \sum_{\kappa} \prod_{v \in V(G)} \prod_{i \in \kappa(v)} x_i,
\]
where the first sum runs over all proper $\alpha$-colorings of $G$. Note that up to a scalar factor depending only on $\alpha$, the chromatic symmetric function $X_{G}^\alpha$ equals the chromatic symmetric function $X_{C_\alpha(G)}$ of the $\alpha$-clan graph of $G$. 

\begin{definition}\label{def:Kromatic}
The \newword{Kromatic symmetric function} of a graph $G$ is the symmetric power series
\[
\KX_G = \sum_{\alpha} X_{G}^\alpha,
\]
where $\alpha$ ranges over all weightings of the vertex set $V(G)$.
\end{definition}

In other words, $\KX_G$ enumerates all colorings of $G$ by nonempty sets of colors, such that adjacent vertices receive disjoint sets of colors. Note that $\KX_G$ is not a homogeneous symmetric function, but rather consists of $X_G$ plus terms of degree higher than $|V(G)|$. 

\begin{remark}
Stanley \cite{stanley2} considered a function $Y_G$ related to $\KX_G$, although with two differences. Firstly, $Y_G$ uses the rescaled power series $X_{C_\alpha(G)}$ in place of $X_{G}^\alpha$. Secondly, $Y_G$ allows $\alpha(v) = 0$, whereas the Kromatic symmetric function $\KX_G$ only considers strictly positive vertex weightings. We are unaware of any further study of the functions $Y_G$ since their introduction in \cite{stanley2}.
\end{remark}

Although vertex weightings are used in the definition of $\KX_G$, the function $\KX_G$ is independent of any particular vertex weighting.
We will find it useful to also consider a vertex-weighted analogue of $\KX_G$. Let $\alpha$ and $w$ be independent vertex weightings on $G$. Define
\[
X_{(G,w)}^\alpha = \sum_{\kappa} \prod_{v \in V(G)} \left(\prod_{i \in \kappa(v)} x_i\right)^{w(v)},
\]
where again the first sum runs over all proper $\alpha$-colorings of $G$.
Finally, we define the \newword{vertex-weighted Kromatic symmetric function} of the vertex-weighted graph $(G,w)$ to be
\[
\KX_{(G,w)} = \sum_{\alpha} X_{(G,w)}^\alpha,
\]
where the sum is over all weight functions $\alpha$.


% To study this function, it will be helpful to identify appropriate analogues of the usual symmetric function bases. In the context of multi-valued fillings, the Grothendieck functions $G_{\lm}$ are often the natural analogue of the Schur functions, and the $G$-basis expansion of $KX$ will be discussed more later.

For $\lambda$ an integer partition, let $K_\lambda$ denote the vertex-weighted complete graph \linebreak $(K_{\ell(\lambda)}, w)$, where $w(i) = \lambda_i$ for each $i$.
It is straightforward to see that $X_{K_\lambda} = \tm_{\lm}$, the augmented monomial symmetric function. Thus, by analogy, we define
\[
\TM_{\lm} := \KX_{K_{\lm}} = \sum_{\alpha} \tm_{\lm_1^{\alpha_1}, \dots, \lm_{\ell(\lm)}^{\alpha(\ell(\lm))}},
\]
where the sum is over all vertex weightings $\alpha$ of $K_{\ell(\lambda)}$. We call $\TM_{\lm}$ the \newword{$K$-theoretic augmented monomial symmetric function}. To justify this definition, we show that the Kromatic symmetric function of every graph (even every vertex-weighted graph) is a positive sum of $K$-theoretic augmented monomial symmetric functions. 

First, we need some additional definitions.
We define a \newword{stable set cover} $C$ of  a graph $G$ to be a collection of stable sets of $G$ such that every vertex of $V(G)$ is in at least one element of $C$. In symbols, this means that
\[
\bigcup_{S \in C} S = V(G);
\]
note that this union is not required to be disjoint. We write $\SSC(G)$ for the family of all stable set covers of $G$.
For $C \in \SSC(G)$, if $G$ is endowed with a vertex-weighting $w$, let $\lambda(C)$ be the partition of length $|C|$ whose parts are $\sum_{v \in S} w(v)$ for $S \in C$.
Finally, let the \newword{color class} of the color $i$ in a proper set-coloring $\kappa$ be 
$
\{v \in V(G) : i \in \kappa(v)\},
$
the set of vertices of $G$ that receive color $i$ under $\kappa$.

\begin{proposition}\label{lem:mbasis}
For any vertex-weighted graph $(G,w)$, we have
\[
\KX_{(G,w)} = \sum_{C \in \SSC(G)} \TM_{\lm(C)}.
\]
\end{proposition}
% \begin{proof}
% For each $C\in \SSC(G)$, the monomials of $\TM_{\lm(C)}$ enumerate all proper set-colorings $\kappa$ of $(G,w)$ such that
% \begin{itemize}
%     \item each $S \in C$ is the color class of at least one color $i$ under $\kappa$; and
%     \item for each nonempty $T \subseteq V(G)$ with $T \notin C$, there is no color $j$ such that $T$ is the color class of $j$ under $\kappa$.
% \end{itemize}
% Conversely, every $\kappa$ corresponds to exactly one choice of $C$, so this provides a bijection between the terms of $\KX_{(G,w)}$ and those of $\sum_C \TM_{\lm(C)}$.
% \end{proof}

The Kromatic symmetric function for vertex-weighted graphs also admits a deletion-contraction relation, analogous to that of \cite{delcon} for the chromatic symmetric function. 

Given $S \subseteq V(G)$ and $v \in V(G)$ with $v \notin S$, we let $vS \subseteq E(G)$ denote $\{vs: s \in S\}$.

\begin{proposition}\label{lem:delcon}
Let $(G,w)$ be a vertex-weighed graph, and let $v_1$ and $v_2$ be vertices such that $e = v_1v_2 \notin E(G)$. Then
\begin{align}\label{eq:delcon}
\KX_{(G,w)} = \KX_{(G / e, w / e)}+ \KX_{(G \cup e, w)}+ \KX_{(G \cup e \cup v_1N(v_2), w^1)}+\KX_{(G \cup e \cup v_2N(v_1), w^2)}+\KX_{(G^*, w^*)}
\end{align}
where 
\begin{itemize}
    \item $w^1(v_1) = w(v_1)+w(v_2)$, and for all other $v \in V(G)$, $w^1(v) = w(v)$.
    \item  $w^2(v_2) = w(v_1)+w(v_2)$, and for all other $v \in V(G)$, $w^2(v) = w(v)$.
    \item $G^* = (V(G) \cup v_3, E(G) \cup \{v_1v_2, v_1v_3, v_2v_3\} \cup v_3N(v_1) \cup v_3N(v_2))$.
    \item $w^*(v_3) = w(v_1)+w(v_2)$, and for all other $v \in V(G)$, $w^*(v) = w(v)$.
\end{itemize}
\end{proposition}
% \begin{proof}
% The proof is a direct bijection between the set-colorings contributing to the left and right sides of Equation~\eqref{eq:delcon} as indicated below. In each case it is straightforward to verify the given correspondence is reversible, and that the monomials produced by the corresponding colorings are identical.
% \begin{itemize}
%     \item Set-colorings $\kappa$ of $(G,w)$ such that $\kappa(v_1) = \kappa(v_2)$ correspond to set-colorings $\kappa^*$ of $(G/e,w/e)$ by coloring the contracted vertex $v^*$ as $\kappa^*(v^*) = \kappa(v_1)$, and for all vertices $v$ letting $\kappa^*(v) = \kappa(v)$.
%     \item Set-colorings $\kappa$ of $(G,w)$ such that $\kappa(v_1) \cap \kappa(v_2) = \emptyset$ are also set-colorings of $(G \cup e, w)$.
%     \item Set-colorings $\kappa$ of $(G,w)$ such that $\kappa(v_1) \subsetneq \kappa(v_2)$ correspond to set-colorings $\kappa^*$ of \\ $(G \cup e \cup v_1N(v_2), w^1)$ by letting $\kappa^*(v_1) = \kappa(v_1)$, $\kappa^*(v_2) = \kappa(v_2) \bk \kappa(v_1)$, and for all other $v$ letting $\kappa^*(v) = \kappa(v)$. 
%     \item Set-colorings $\kappa$ of $(G,w)$ such that $\kappa(v_2) \subsetneq \kappa(v_1)$ correspond to set-colorings $\kappa^*$ of \\ $(G \cup e \cup v_2N(v_1), w^2)$ by letting $\kappa^*(v_2) = \kappa(v_2)$, $\kappa^*(v_1) = \kappa(v_1) \bk \kappa(v_2)$, and for all other $v$ letting $\kappa^*(v) = \kappa(v)$. 
%     \item  Set-colorings $\kappa$ of $(G,w)$ that fit into none of the previous categories (those such that each of $\kappa(v_1) \cap \kappa(v_2), \kappa(v_1) \bk \kappa(v_2), \kappa(v_2) \bk \kappa(v_1)$ are nonempty) correspond to set-colorings $\kappa$ of $(G^*,w^*)$ by letting $\kappa^*(v_3) = \kappa(v_1) \cap \kappa(v_2)$, $\kappa^*(v_1) = \kappa(v_1) \bk \kappa(v_2)$, $\kappa^*(v_2) = \kappa(v_2) \bk \kappa(v_1)$, and for all other $v$ letting $\kappa^*(v) = \kappa(v)$.
% \end{itemize}
% \end{proof}

The deletion-contraction relation of \cref{lem:delcon} can be used to yield algorithmically the $\TM_\lambda$-expansion of a Kromatic symmetric function $\KX_{(G,w)}$.

% in an alternative fashion to \cref{lem:mbasis}.

\begin{corollary}\label{lem:recurse}
Arbitrarily applying \cref{lem:delcon} recursively to a graph $(G,w)$ (repeatedly applying it to any nonedge of each graph formed if possible) terminates in a sum of Kromatic symmetric functions of vertex-weighted complete graphs, yielding the $\TM_{\lm}$ expansion of $\KX_{(G,w)}$.
\end{corollary}
% \begin{proof}
% Define the \newword{total stability} of a graph $G$ to be $ss(G)-|V(G)|$, where $ss(G)$ is the number of distinct stable sets of $G$. In other words, since any single vertex of a graph is a stable set, we may view the total stability as the number of non-trivial stable sets. Thus, note that $ss(G)-|V(G)| \geq 0$ and equality holds if and only if $G$ is a complete graph.

% The result then follows immediately from the following claim: after applying \cref{lem:delcon} to $(G,w)$, each of the resulting five graphs has strictly smaller total stability than $G$. We look at each graph separately:
% \begin{itemize}
%     \item $|V(G/e)| = |V(G)|-1$. However
%     \begin{itemize}
%         \item Every stable set of $G/e$ not containing $v^*$ is also a stable set of $G$.
%         \item Every stable set $S$ of $G/e$ containing $v^*$ corresponds to three stable sets of $G$, since we may choose $S \bk \{v^*\} \cup \{v_1\}, S \bk \{v^*\} \cup \{v_2\}, S \bk \{v^*\} \cup \{v_1,v_2\}$
%     \end{itemize}
%     Since in particular at a minimum $S = \{v^*\}$ is a stable set of $G/e$ containing $v^*$, we see that $ss(G) > ss(G/e)+1$, so $ss(G)-|V(G)| > ss(G/e)-|V(G/e)|$
%     \item Each of $G \cup e$, $G \cup e \cup v_1N(v_2)$, $G \cup e \cup v_2N(v_1)$ have the same number of vertices as $G$ but at least one less stable set (namely $\{v_1,v_2\}$).
%     \item $|V(G^*)| = |V(G)|+1$. Enumerating stable sets:
%     \begin{itemize}
%         \item Every stable set of $G^*$ not containing $v_3$ corresponds to a stable set of $G$.
%         \item Any stable set $S$ of $G^*$ containing $v_3$ does not contain $v_1, v_2$, or any vertex in $N(v_1)$ or $N(v_2)$, so corresponds to three stable sets of $G$, namely $S \bk \{v_3\} \cup \{v_1\}, S \bk \{v_3\} \cup \{v_2\}, S \bk \{v_3\} \cup \{v_1,v_2\}$.
%     \end{itemize}
%     Since at a minimum $S = \{v_3\}$ is a stable set of $G^*$ containing $v_3$, we see that $G$ has more stable sets than $G^*$ but one less vertex, so $ss(G)-|V(G)| > ss(G^*)-|V(G^*)|.$
% \end{itemize}

% Therefore the claim holds, and the result follows.
% \end{proof}

Our main result is the following theorem.

\begin{theorem}\label{thm:grot}
If $G$ is a claw-free incomparability graph, then $\KX_G$ is Grothendieck-positive.
\end{theorem}

\begin{proof}
(Sketch.) We use the Jacobi-Trudi formula of Iwao \cite[Proposition 4.4]{iwao} to write a \emph{dual Grothendieck function} as a sum of products of complete homogeneous symmetric functions. Then, for any graph $G$, the inner product of this expression with $\KX_G$ yields a formula for the coefficient of $\groth_\lambda$ in the Grothendieck expansion of $\KX_G$ in terms of its monomial expansion. In the case that $G$ is a claw-free incomparability graph, we then extend Gasharov's \cite{gash} theory of \emph{$P$-arrays} to collect terms in this expansion and show that the coefficient of any $\groth_\lambda$ is nonnegative.
\end{proof}

We would be very interested in a solution to the following.

\begin{problem}\label{prob:Chow}
For each claw-free incomparability graph $G$, find a corresponding subvariety $V_G$ of the Grassmannian such that the cohomology class of $V_G$ is represented in $\Sym$ by $X_G$ and the structure sheaf class of $V_G$ is represented by $\KX_G$.
\end{problem}

\section{Analogues of the Stanley--Stembridge conjecture}\label{sec:StanleyStembridge}

The previous section shows that Schur-positivity of $X_G$ when $G$ is a claw-free incomparability graph lifts to an analogue for $\KX_G$. It is natural to ask if it is similarly possible to lift the \newword{Stanley-Stembridge conjecture} --- claiming that such $X_G$ are $e$-positive --- to the Kromatic setting. However, it appears that the answer is ``no.''

We propose two definitions for a lift of the $e$-basis to the $K$-theoretic setting. On one hand, $e$-basis elements in usual symmetric function theory may be defined in terms of fillings of single-column Young diagrams, so we may lift this formula.
\begin{definition}\label{def:ebox}
The \newword{tableau $K$-elementary symmetric function} $\ebox_\lambda$ is given by
\[
\ebox_n = \groth_{1^n}
\quad \text{and} \quad
\ebox_\lambda = \ebox_{\lm_1} \dots \ebox_{\lm_{\ell(\lm)}}.
\]
\end{definition}

On the other hand, we may also define $e_n = \frac{1}{n!}X_{K_n}$, and lift this characterization.
\begin{definition}\label{def:egraph}
The \newword{graph $K$-elementary symmetric function} is given by 
\[
\estar_n = \frac{1}{n!}\KX_{K_n}
\quad \text{and} \quad
\estar_{\lm} = \estar_{\lm_1} \dots \estar_{\lm_{\ell(\lm)}}.
\]
\end{definition}

It is reasonable to hope (for extending the Stanley--Stembridge conjecture) that $\KX_G$ is positive in one of these $K$-theoretic $e$-bases, whenever $G$ is a claw-free incomparability graph, or even just when $G$ is a unit interval graph. However, one can compute that $\KX_{P_3}$ is not positive in either $K$-theoretic $e$-basis, dashing such hopes.

The terms of $\KX_{P_3}$ that are homogeneous of degree $3$ must come from tableau or graph $K$-elementary symmetric functions of degree $3$, and have coefficients corresponding to $e$-expansion of $X_{P_3}$. Since $X_{P_3} = 3e_3+e_{21}$, one sees that the terms of $\KX_{P_3}$ for $|\lm|=3$ in the $\ebox$-basis are $3\ebox_3+\ebox_{21}$, and in the $\estar$-basis are $3\estar_3+\estar_{21}$.
However, we now run into problems with the $|\lm| = 4$ terms. In particular, both $\ebox_{21}$ and $\estar_{21}$ are supported on the monomial $x_1^2x_2^2$, with two distinct variables each of degree $2$. However, it is easy to check that there is no proper set-coloring of $P_3$ using exactly  $1$ twice and $2$ twice; thus, these monomials must be cancelled by $\ebox$ or $\estar$ terms with strictly negative coefficients.

That this breakdown is so fundamental suggests that it may not be possible to reasonably generalize $e$-positivity to the Kromatic symmetric function, in stark contrast with the generalization of Schur-positivity given in \cref{thm:grot}. This suggests that the Stanley--Stembridge is not amenable to a topological interpretation along the lines of \cref{prob:Chow}.

\section{Acknowledgments}

The authors would like to thank Boris Shapiro, Per Alexandersson, and the anonymous referees for helpful comments.


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