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

% AMS style packages
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{amssymb,amsfonts,stmaryrd,mathrsfs}
\usepackage{latexsym,amsthm,mathtools,bbm}
\usepackage{subcaption}
\usepackage{hyperref}
\usepackage{footmisc}

\usepackage{algorithm}
\usepackage{algpseudocode}

\algrenewcommand\algorithmicrequire{\textbf{Input:}}
\algrenewcommand\algorithmicensure{\textbf{Output:}}

% Standard useful packages
%
%\usepackage[shortlabels]{enumitem}
%\usepackage{graphicx}
%\usepackage{hyperref}
%\usepackage{listings}
%\usepackage{mathrsfs}
%\usepackage{mathtools}
%\usepackage{multicol}
%%\usepackage{shuffle}
%\usepackage{stmaryrd}

% Tikz package and libraries
\usepackage{tikz}
\usepackage{tikz-cd}
%\usepackage{tikzducks}
\usetikzlibrary{arrows,backgrounds,chains,decorations.pathreplacing,patterns,shapes, calc, positioning}


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

\newtheorem{manualtheoreminner}{Theorem}
\newenvironment{manualtheorem}[1]{%
	\renewcommand\themanualtheoreminner{#1}%
	\manualtheoreminner
}{\endmanualtheoreminner}

\newtheorem{manualconjinner}{Conjecture}
\newenvironment{manualconj}[1]{%
	\renewcommand\themanualconjinner{#1}%
	\manualconjinner
}{\endmanualconjinner}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{definitions}[theorem]{Definitions}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

% Functions
\newcommand{\area}{\mathsf{area}}
\newcommand{\dinv}{\mathsf{dinv}}
\newcommand{\Dinv}{\mathsf{Dinv}}
\newcommand{\inv}{\mathsf{inv}}
\newcommand{\Inv}{\mathsf{Inv}}

\newcommand{\pmaj}{\mathsf{pmaj}}
\newcommand{\maj}{\mathsf{maj}}
\newcommand{\ides}{\mathsf{ides}}



\newcommand{\dcomp}{\mathsf{dcomp}}
\newcommand{\comp}{\mathsf{comp}}
\newcommand{\st}{\mathsf{st}}
\newcommand{\set}{\mathsf{set}}
\newcommand{\asc}{\mathsf{asc}}
\newcommand{\des}{\mathsf{des}}
\newcommand{\LLT}{\mathrm{LLT}}


% sets

\newcommand{\D}{\mathsf{D}} % Dyck paths (new)
\newcommand{\W}{\mathsf{W}} % Labellings

\newcommand{\LD}{\mathsf{LD}} % labelled Dyck paths


\newcommand{\ISF}{\mathsf{ISF}}
\newcommand{\wt}{\mathsf{wt}}





\newcommand{\cN}{\mathcal N}
\newcommand{\cM}{\mathcal M}

\newcommand{\bN}{\mathbb N}
\newcommand{\bZ}{\mathbb Z}

\newcommand{\e}{\underline{e}}
\newcommand{\PPi}{\mathbf{\Pi}}


% q-binomials
\newcommand{\qbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}
\newcommand{\dqbinom}[2]{\genfrac{[}{]}{0pt}{0}{#1}{#2}}

\usepackage{lipsum}


\DeclareMathOperator{\ric}{Ric}
\DeclareMathOperator{\Ric}{Ric}
%% define your title in the usual way
\title{Chromatic functions, interval orders, and increasing forests}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Michele D'Adderio\thanks{\href{mailto:michele.dadderio@unipi.it}{michele.dadderio@unipi.it}}\addressmark{1}, Roberto Riccardi\thanks{\href{mailto:roberto.riccardi@sns.it}{roberto.riccardi@sns.it}}\addressmark{2}, \and Viola Siconolfi\thanks{\href{mailto:siconolf@mat.uniroma2.it}{siconolf@mat.uniroma2.it}}\addressmark{3}}
%% then use \addressmark to match authors to institutions here
\address{
\addressmark{1}Universit\`a di Pisa, Dipartimento di Matematica, Largo Bruno Pontecorvo 5, 56127 Pisa, Italy\\
\addressmark{2}Scuola Normale Superiore,
	Piazza dei Cavalieri 7,
	56126 Pisa,  Italy\\
\addressmark{3}Politecnico di Bari, Dipartimento di Meccanica, Matematica e Managment, Via Orabona 4, 70125 Bari,  Italy
}




%% put the date of submission here
\received{}

%% 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{
The chromatic quasisymmetric functions (csf) of Shareshian and Wachs associated to unit interval orders have attracted a lot of interest since their introduction in 2016, both in combinatorics and geometry, because of their relation to the famous Stanley-Stembridge conjecture (1993) and to the topology of Hessenberg varieties, respectively. In the present work we study the csf associated to the larger class of interval orders with no restriction on the length of the intervals. Inspired by an article of Abreu and Nigro, we show that these csf are weighted sums of certain quasisymmetric functions associated to the increasing spanning forests of the associated incomparability graphs. Furthermore, we define quasisymmetric functions that include the unicellular LLT symmetric functions and generalize an identity due to Carlsson and Mellit. Finally we conjecture a formula giving their expansion in the type 1 power sum quasisymmetric functions which should extend a theorem of Athanasiadis. 




  }
%% put your French abstract here, or comment this out if you don't have one
%\resume{prova di abstract francese???}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Chromatic quasisymmetric functions, LLT quasisymmetric functions, increasing spanning forests}

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

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{biblebib.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}

In \cite{Shareshian_Wachs_Advances} Shareshian and Wachs introduced the \emph{chromatic quasisymmetric function} $\chi_G[X;q]$ associated to every graph $G$ whose vertices are totally ordered, as a sum over proper colorings of $G$ of suitable monomials. At $q=1$ the series $\chi_G[X;q]$ reduces to the well-known chromatic symmetric function $\chi_G[X;1]=\chi_G(x)$ introduced by Stanley in \cite{Stanley_Chrom_Sym}. A famous conjecture of Stanley and Stembridge (\cite[Conjecture~5.1]{Stanley_Chrom_Sym}, \cite[Conjecture~5.5]{Stanley_Stembridge}) states that if $G$ is the incomparability graph of a $(\mathbf{3}+\mathbf{1})$-free poset, then $\chi_G[X;1]$ is $e$-positive, i.e.\ its expansion in the elementary symmetric functions has coefficients in $\mathbb{N}$. Shareshian and Wachs showed (cf.\ \cite[Theorem~4.5]{Shareshian_Wachs_Advances}) that if $G$ is the incomparability graph of a poset that is both $(\mathbf{3}+\mathbf{1})$-free and $(\mathbf{2}+\mathbf{2})$-free, then $\chi_G[X;q]$ is a symmetric function, and they conjecture that it is $e$-positive, i.e.\ its expansion in the elementary symmetric functions has coefficients in $\mathbb{N}[q]$. Thanks to a result of Guay-Paquet \cite{guaypaquet_modular_law}, it is known that the Shareshian-Wachs conjecture implies the Stanley-Stembridge conjecture. The former problem attracted a lot of attention recently: see e.g.\ \cite{Huh_Nam_Yoo,Abreu_Nigro_Modular_Law,Skandera,Cho_Hong,Nadeau_Tewari_Downup,Colmenarejo_Morales_Panova}.

The posets that are  $(\mathbf{3}+\mathbf{1})$-free and $(\mathbf{2}+\mathbf{2})$-free are precisely the \emph{unit interval orders} (see \cite{Scott_Suppes}), whose elements are intervals in $\mathbb{R}$ of the same length, and an interval $a$ is smaller than an interval $b$ if all the points of $a$ are strictly smaller than all the points of $b$. If in such a poset we order the intervals increasingly according to their left endpoints, then we get a total order on them, and now the incomparability graphs of these posets will inherit this total order on the vertices, giving the labelled graphs $G$ involved in the Shareshian-Wachs conjecture. In our article we call these labelled graphs \emph{Dyck graphs}, as they are in a natural bijection with Dyck paths.

\smallskip

If in the definition of unit interval orders we drop the condition on the intervals to have all the same length, then we get the \emph{interval orders}. The incomparability graphs of these posets will be called \emph{interval graphs} in our article, and their chromatic quasisymmetric functions $\chi_G[X;q]$ are the object of our study.

Inspired by the work of Abreu and Nigro \cite{Abreu_Nigro_Forests}, given an interval graph $G$, for every increasing spanning forest $F$ of $G$ we will define a quasisymmetric function $\mathcal{Q}_F^{(G)}$ so that the following formula holds (the statistic $\mathsf{wt}_G(F)$ is essentially the one in \cite{Abreu_Nigro_Forests}, while $\mathsf{ISF}(G)$ is the set of increasing spanning forests of $G$).
\begin{manualtheorem}{\ref{thm:chrom_forests_formula}}
Given an interval graph $G$ on $n$ vertices, we have
\begin{equation}
	\chi_G[X;q]=\sum_{F\in \mathsf{ISF}(G)}q^{\mathsf{wt}_G(F)}\mathcal{Q}_F^{(G)}.
\end{equation}
\end{manualtheorem}

For every simple graph $G$ with totally ordered vertices we introduce the quasisymmetric function $\mathrm{LLT}_G[X;q]$,
analogous to $\chi_G[X;q]$ but defined as a sum over all (not necessarily proper) colorings of $G$ of suitable monomials.

%Recall the well-known involutions $\rho$ and $\psi$ of the algebra $\mathrm{QSym}$ of quasisymmetric functions defined by $\psi(L_{\alpha}):=L_{\alpha^c}$ and $\rho(L_{\alpha})=L_{\alpha^r}$, where $\{L_{\alpha}\mid n\in \mathbb{N},\alpha\vDash n\}$ is the basis of the fundamental (Gessel) quasisymmetric functions.

The main result of this article is the following theorem, stated in plethystic notation ($\rho$ and $\psi$ are well-known involutions of the algebra $\mathrm{QSym}$ of quasisymmetric functions).

\begin{manualtheorem}{\ref{thm:main_theorem}}
	Given $G$ an interval graph on $n$ vertices, we have
	\begin{equation*} %\label{eq:main_identity}
	(1-q)^n \rho \left(\psi \chi_G\left[X\frac{1}{1-q}\right]\right)=\mathrm{LLT}_G[X;q].
	\end{equation*}
\end{manualtheorem}

This result extends the identity in \cite[Proposition~3.5]{Carlsson-Mellit-ShuffleConj-2015} proved by Carlsson and Mellit when $G$ is a Dyck graph.

%, which can be restated as follows using \emph{plethystic notation} (for which we refer to \cite{Loehr-Remmel-plethystic-2011}).
%
%\begin{theorem}[Carlsson, Mellit]
%If $G$ is a Dyck graph on $n$ vertices, then
%\begin{equation} \label{eq:CM_identity}
%(1-q)^n  \omega \chi_G\left[X\frac{1}{1-q}\right] =\mathrm{LLT}_G[X;q].
%\end{equation}
%\end{theorem}

In \cite{Ballantine_et_al} the authors study a family of quasisymmetric functions that they call \emph{type 1 quasisymmetric power sums}, denoted $\Psi_\alpha$. Actually $\{\Psi_\alpha\mid \alpha\text{ composition}\}$ is a basis of $\mathrm{QSym}$ that refines the power symmetric function basis.

We state the following conjecture which is supposed to provide an extension of the formula proved by Athanasiadis in \cite{Athanasiadis}.

\begin{manualconj}{\ref{conj:interval_psi_exp}}
	For any interval graph $G$ on $n$ vertices we have
	\[\rho\psi \chi_G[X;q]=\sum_{\alpha\vDash n}\frac{\Psi_\alpha}{z_{\alpha}}\sum_{\sigma \in \mathcal{N}_{G,\alpha}}q^{\widetilde{\mathsf{inv}}_G(\sigma)}.\]
\end{manualconj}

%\medskip
%
%The rest of the this work is organized in the following way. In Section~2 we give the preliminaries about interval graphs, quasisymmetric functions, colorings and their inversions, proving related formulas for proper colorings and (co)inversions in the case of interval graphs. In Section~3 we introduce the increasing spanning forests of interval graphs $G$, their weight $\mathsf{wt}_G$ and the function $\Phi_G$. In Section~4 we show Theorem~\ref{thm:main_theorem}, introducing the objects of the main identity and a fundamental formula that is at the heart of our proof of Theorem~\ref{thm:main_theorem}, which is based on a result of Kasraoui \cite{Kasraoui_maj-inv}. In Section~5 we will talk about our conjectures about the type 1 quasisymmetric power sums basis (for example, Conjecture~\ref{conj:interval_psi_exp}).


\section{Preliminaries}

For every $n\in \mathbb{Z}_{>0}:=\{1,2,3,\dots\}$ we will use the notation $[n]:=\{1,2,\dots,n\}$. 

\subsection{Interval graphs}

In this abstract a graph will always be simple, i.e.\ no loops and no multiple edges.



In our work a (\emph{labelled}) \emph{graph} $G=([n],E)$ will be called \emph{interval} if whenever $\{i,j\}\in E$ and $i<j$, then $\{i,k\}\in E$ for every $i<k\leq j$. We will call $\mathcal{IG}_n$ the set of all interval graphs with vertex set $[n]$.


We can represent an interval graph $G=([n],E)$ in the following way: in a $n\times n$ square grid we order the columns from left to right with numbers $1,2,\dots,n$ and similarly the rows from bottom to top; then we color the cells $\{i,j\}\in E$ with $i<j$. See Figure~\ref{fig:interval_graph}, on the left, for an example\footnote{\label{note:edges}Sometimes we denote by $(i,j)$ an edge $\{i,j\}\in E$ with $i<j$, like in the caption of Figure~\ref{fig:interval_graph}.}.

\begin{figure}%[!ht]
	\centering
	\begin{tikzpicture}[scale=0.5]
		\draw[gray!60, thin](0,0) grid (8,8);
		%\draw[gray!60, thin] (0,0)--(8,8);
		\filldraw[red, opacity=0.3] (1,2) -- (2,2)--(2,7)--(1,7)-- cycle;
		\filldraw[red, opacity=0.3] (0,1) -- (0,3)--(1,3)--(1,1)-- cycle;
		\filldraw[red, opacity=0.3] (2,3) -- (2,6)--(3,6)--(3,3)-- cycle;
		\filldraw[red, opacity=0.3] (4,5) -- (4,7)--(5,7)--(5,5)-- cycle;
		\filldraw[red, opacity=0.3] (5,6) -- (5,8)--(7,8)--(7,7)--(6,7)--(6,6)-- cycle;
		%\draw[gray!60, dashed, line width=1.6pt] (5,8)--(5,5)--(2,5);
		%\draw[blue!60, line width=1.6pt] (4,8)--(6,8);
		%\draw[blue!60, line width=1.6pt] (1,4)--(1,5)--(2,5)--(2,6);
		%	
		\node at (0.5,0.5) {$1$};	
		\node at (1.5,1.5) {$2$};
		\node at (2.5,2.5) {$3$};
		\node at (3.5,3.5) {$4$};
		\node at (4.5,4.5) {$5$};
		\node at (5.5,5.5) {$6$};
		\node at (6.5,6.5) {$7$};
		\node at (7.5,7.5) {$8$};
	\end{tikzpicture}\hspace{2.3cm} \begin{tikzpicture}[scale=0.5]
	\draw[gray!60, thin](0,0) grid (8,8);
	%\draw[gray!60, thin] (0,0)--(8,8);
	\filldraw[red, opacity=0.3] (1,2) -- (2,2)--(2,4)--(1,4)-- cycle;
	\filldraw[red, opacity=0.3] (0,1) -- (0,3)--(1,3)--(1,1)-- cycle;
	\filldraw[red, opacity=0.3] (2,3) -- (2,4)--(3,4)--(3,3)-- cycle;
	\filldraw[red, opacity=0.3] (4,5) -- (4,7)--(5,7)--(5,5)-- cycle;
	\filldraw[red, opacity=0.3] (5,6) -- (5,7)--(6,7)--(6,8)--(7,8)--(7,7)--(6,7)--(6,6)-- cycle;
	%\draw[gray!60, dashed, line width=1.6pt] (5,8)--(5,5)--(2,5);
	\draw[blue!60, line width=1.6pt] (0,0)--(0,3)--(1,3)--(1,4)--(4,4)--(4,7)--(6,7)--(6,8)--(8,8);
	%\draw[blue!60, line width=1.6pt] (1,4)--(1,5)--(2,5)--(2,6);
	%	
	\node at (0.5,0.5) {$1$};	
	\node at (1.5,1.5) {$2$};
	\node at (2.5,2.5) {$3$};
	\node at (3.5,3.5) {$4$};
	\node at (4.5,4.5) {$5$};
	\node at (5.5,5.5) {$6$};
	\node at (6.5,6.5) {$7$};
	\node at (7.5,7.5) {$8$};
	
\end{tikzpicture}
	\caption{The interval graph $G=([8],\{(1,2),(1,3),(2,3),(2,4),(2,5),(2,6),(2,7),$ $(3,4),(3,5),(3,6),(5,6),(5,7),(6,7),(6,8),(7,8)\})$, on the left. On the right, the Dyck graph $G_2=([8],\{(1,2),(1,3),(2,3),(2,4),(3,4),(5,6),(5,7),(6,7),(7,8)\})$.} \label{fig:interval_graph}
\end{figure}



Notice that in these pictures we simply obtain a bunch of (possibly empty) colored columns, starting just above the diagonal cells. Hence clearly there are $n!$ interval graphs on $n$ vertices.

Given an interval graph $G$ on $n$ vertices, we can consider its \emph{flipped}, obtained from $G$ by replacing each edge $\{i,j\}$ with an edge $\{n+1-i,n+1-j\}$: in terms of pictures, this corresponds to flip the picture of $G$ around the line $y=-x$.

An interval graph  $G$ on $n$ vertices such that its flipped is still an interval graph is called a \emph{Dyck graph}. The explanation of the name is obvious, since the picture of a Dyck graph determines a Dyck path: see the graph $G_2$ in Figure~\ref{fig:interval_graph}, on the right (the Dyck path is the thicker one).
\smallskip

It turns out that the interval graphs are the incomparability graphs of certain posets called \emph{interval orders} (hence their name).

Given a (naturally labelled) poset $P=([n],<_P)$, its \emph{incomparability (labelled) graph} $\mathrm{Inc(P)}=([n],E_P)$ is defined by setting $\{i,j\}\in E_P$ if and only if $i$ and $j$ are incomparable in $P$.

Let $\mathcal{I}$ be the set of all bounded closed intervals of $\mathbb{R}$, and given $I=[a,b]$ and $J=[c,d]$ we set $I \prec J$ if and only if $b < c$. Clearly $(\mathcal{I}, \prec)$ is a poset. Any subposet of $(\mathcal{I}, \prec)$ is called an \emph{interval order}. %An example of interval order is given in Figure~\ref{fig:poset_intervals}: on the right there are the intervals, while on the left there is the corresponding Hasse diagram (in which node $i$ corresponds to interval $I_i$ for every $i$).

%
%The following propositions are probably well known.
%
%\begin{proposition} \label{prop:interval_poset_graphs}
%	For every $\mathcal{H} \subseteq \mathcal{I}$ such that $|\mathcal{H}|=n \in \mathbb{N}$, there exists an order-preserving bijection $\phi:(\mathcal{H}, \prec) \longrightarrow ([n],<)$ such that $\mathrm{Inc}(\phi(\mathcal{H}, \prec)) \in \mathcal{IG}_n$.
%\end{proposition}
%
%On the contrary, every graph in $\mathcal{IG}_n$ is the incomparability graph of a finite subposet of $\mathcal{I}$.
%
%\begin{proposition} \label{prop:Interval_graph_to_intervals}
%	For every $G=([n], E) \in \mathcal{IG}_n$ there exist a finite subset $\mathcal{H} \subseteq \mathcal{I}$ and an order-preserving bijection $\phi: (\mathcal{H},\prec) \longrightarrow ([n],<)$ such that $\mathrm{Inc}(\phi(\mathcal{H}, \prec))=G$.
%\end{proposition}
%
%\begin{figure}[ht]
%	\centering
%	%\tikzset{every loop/.style={min distance=10mm,in=0,out=60,looseness=10}}
%	\begin{tikzpicture}[auto,node distance=3cm,
%		thick,root node/.style={shape=circle, inner sep=3pt, fill=red,draw},main node/.style={shape=circle, inner sep=3pt, fill=black,draw},external node/.style={shape=circle, inner sep=6pt,draw},scale=.35]
%		
%		%\node[root node] (1) at (0,0) {};
%		%\node[main node] (2) at (-5,3) {};
%		\node[external node] (1) at (-3,0) {};
%		%\node[main node] (4) at (5,3) {};
%		\node[external node] (2) at (3,0) {};
%		\node[external node] (3) at (0,0) {};
%		%\node[main node] (7) at (-3,6) {};
%		\node[external node] (4) at (-3,3) {};
%		\node[external node] (5) at (-6,6) {};
%		\node[external node] (6) at (-3,6) {};
%		\node[external node] (7) at (0,6) {};
%		\node[external node] (8) at (0,11) {};
%		
%		\node at (0,0) {$3$};
%		\node at (-3,0) {$1$};
%		\node at (3,0) {$2$};
%		\node at (-3,3) {$4$};
%		\node at (-6,6) {$5$};
%		\node at (-3,6) {$6$};
%		\node at (0,6) {$7$};
%		\node at (0,11) {$8$};
%		
%		\draw[gray!90, line width=0.32mm] (6,0)--(22,0);
%		\draw[gray!90, line width=0.32mm] (6,-0.3)--(6,0.3);
%		\draw[gray!90, line width=0.32mm] (8,-0.3)--(8,0.3);
%		\draw[gray!90, line width=0.32mm] (10,-0.3)--(10,0.3);
%		\draw[gray!90, line width=0.32mm] (12,-0.3)--(12,0.3);
%		\draw[gray!90, line width=0.32mm] (14,-0.3)--(14,0.3);
%		\draw[gray!90, line width=0.32mm] (16,-0.3)--(16,0.3);
%		\draw[gray!90, line width=0.32mm] (18,-0.3)--(18,0.3);
%		\draw[gray!90, line width=0.32mm] (20,-0.3)--(20,0.3);
%		\draw[gray!90, line width=0.32mm] (22,-0.3)--(22,0.3);
%		
%		\draw[black, line width=0.4mm] (20,1)--(22,1);
%		\draw[black, line width=0.4mm] (20,1-0.3)--(20,1+0.3);
%		\draw[black, line width=0.4mm] (22,1-0.3)--(22,1+0.3);
%		\node at (21,1.5) {$I_8$};
%		
%		\draw[black, line width=0.4mm] (18,1)--(19,1);
%		\draw[black, line width=0.4mm] (18,1-0.3)--(18,1+0.3);
%		\draw[black, line width=0.4mm] (19,1-0.3)--(19,1+0.3);
%		\node at (18.5,1.5) {$I_7$};
%		
%		\draw[black, line width=0.4mm] (16,2.5)--(22,2.5);
%		\draw[black, line width=0.4mm] (16,2.5-0.3)--(16,2.5+0.3);
%		\draw[black, line width=0.4mm] (22,2.5-0.3)--(22,2.5+0.3);
%		\node at (19,3) {$I_6$};
%		
%		\draw[black, line width=0.4mm] (14,4)--(19,4);
%		\draw[black, line width=0.4mm] (14,4-0.3)--(14,4+0.3);
%		\draw[black, line width=0.4mm] (19,4-0.3)--(19,4+0.3);
%		\node at (16.5,4.5) {$I_5$};
%		
%		\draw[black, line width=0.4mm] (12,4)--(13,4);
%		\draw[black, line width=0.4mm] (12,4-0.3)--(12,4+0.3);
%		\draw[black, line width=0.4mm] (13,4-0.3)--(13,4+0.3);
%		\node at (12.5,4.5) {$I_4$};
%		
%		\draw[black, line width=0.4mm] (10,5.5)--(17,5.5);
%		\draw[black, line width=0.4mm] (10,5.5-0.3)--(10,5.5+0.3);
%		\draw[black, line width=0.4mm] (17,5.5-0.3)--(17,5.5+0.3);
%		\node at (13.5,6) {$I_3$};
%		
%		\draw[black, line width=0.4mm] (8,7)--(19,7);
%		\draw[black, line width=0.4mm] (8,7-0.3)--(8,7+0.3);
%		\draw[black, line width=0.4mm] (19,7-0.3)--(19,7+0.3);
%		\node at (13.5,7.5) {$I_2$};
%		
%		\draw[black, line width=0.4mm] (6,8.5)--(11,8.5);
%		\draw[black, line width=0.4mm] (6,8.5-0.3)--(6,8.5+0.3);
%		\draw[black, line width=0.4mm] (11,8.5-0.3)--(11,8.5+0.3);
%		\node at (8.5,9) {$I_1$};
%		
%		\node[gray!90] at (6,0-0.8) {$1$};
%		\node[gray!90] at (8,0-0.8) {$2$};
%		\node[gray!90] at (10,0-0.8) {$3$};
%		\node[gray!90] at (12,0-0.8) {$4$};
%		\node[gray!90] at (14,0-0.8) {$5$};
%		\node[gray!90] at (16,0-0.8) {$6$};
%		\node[gray!90] at (18,0-0.8) {$7$};
%		\node[gray!90] at (20,0-0.8) {$8$};
%		\node[gray!90] at (22,0-0.8) {$9$};
%		
%		\path
%		(1) edge node {} (4)
%		(4) edge node {} (5)
%		(4) edge node {} (6)
%		(4) edge node {} (7)
%		(5) edge node {} (8)
%		(7) edge node {} (8)
%		(3) edge node {} (7)
%		(2) edge node {} (8);
%	\end{tikzpicture}
%	\caption{On the left the poset whose incomparability graph is the $G$ in Figure~\ref{fig:interval_graph}. On the right the family of intervals associated to the $G$ in Figure~\ref{fig:interval_graph} by the proof of Proposition~\ref{prop:Interval_graph_to_intervals}.}
%	\label{fig:poset_intervals}
%\end{figure} 


\subsection{Symmetric and quasisymmetric functions} \label{sec:qsym}

In this section we recall a few basic facts of symmetric and quasisymmetric functions, mainly to fix the notation.

Given a composition $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$ of $n\in \mathbb{N}$ (denoted $\alpha\vDash n$), we denote its \emph{size} by $|\alpha|=\sum_i\alpha_i=n$ and its \emph{length} by $\ell(\alpha)=k$. For brevity, sometimes we will use the \emph{exponential notation}, so that for example we will write $(1^4)$ for $(1,1,1,1)$, or $(1^3,2^2,1,3)$ for $(1,1,1,2,2,1,3)$.


To a composition $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$ of $n$ we associate a set $\mathsf{set}(\alpha)=\mathsf{set}_n(\alpha)\subseteq [n-1]$:
\[\mathsf{set}(\alpha)=\{\alpha_1,\alpha_1+\alpha_2,\dots,\alpha_1+\cdots +\alpha_{k-1}\}.\]
Viceversa, to a subset $S\subseteq [n-1]$ whose elements are $i_1<i_2<\cdots <i_k$ we associate the composition \[\mathsf{comp}(S)=\mathsf{comp}_n(S)=(i_1,i_2-i_1,i_3-i_2,\dots,i_k-i_{k-1},n-i_k)\vDash n.\]
Notice that the functions $\mathsf{set}_n$ and $\mathsf{comp}_n$ are inverse of each others.

Given a composition $\alpha\vDash n$, $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$, its \emph{reversal} is $\alpha^r=(\alpha_k,\alpha_{k-1},\dots,\alpha_1)$, its \emph{complement} is $\alpha^c=\mathsf{comp}([n-1]\setminus \mathsf{set}(\alpha))$, and its \emph{transpose} is $\alpha^t=(\alpha^r)^c=(\alpha^c)^r$.

\smallskip

We denote by $\mathrm{QSym}$ the algebra of quasisymmetric functions in the variables $x_1,x_2,\!\dots$ and coefficients in $\mathbb{Q}(q)$, where $q$ is a variable. %Given a composition $\alpha\!=\!(\alpha_1,\alpha_2,\dots,\alpha_k)$, we define the \emph{monomial quasisymmetric function} $M_\alpha$ as
%\[M_{\alpha}=\sum_{i_1<i_2<\cdots <i_k}x_{i_1}^{\alpha_1}x_{i_2}^{\alpha_2}\cdots x_{i_k}^{\alpha_k}.\]
%
%The set $\{M_\alpha\mid \alpha\text{ composition}\}$ is clearly a basis of $\mathrm{QSym}$.

Given $n\in \mathbb{N}$ and $S\subseteq [n-1]$, we define the \emph{fundamental (Gessel) quasisymmetric function} $L_{n,S}$ as
\[L_{n,S}:=\mathop{\sum_{i_1\leq i_2\leq \cdots \leq i_n}}_{j\in S\Rightarrow i_j\neq i_{j+1}}x_{i_1}x_{i_2}\cdots x_{i_n}\] 
and for every $\alpha\vDash n$, we define $L_\alpha:=L_{n,\mathsf{set}(\alpha)}$. 

It is well known that 
$\{L_{\alpha}\mid \alpha\text{ composition}\}$ is a basis of $\mathrm{QSym}$.

We have the following three involutions of $\mathrm{QSym}$: $\psi: \mathrm{QSym}\to \mathrm{QSym}$, defined by $\psi(L_{\alpha}):=L_{\alpha^c}$, $\rho: \mathrm{QSym}\to \mathrm{QSym}$ defined by $\rho(L_{\alpha})=L_{\alpha^r}$, and $\omega: \mathrm{QSym}\to \mathrm{QSym}$ defined by $\omega(L_{\alpha})=L_{\alpha^t}$.

\smallskip 

We will use the \emph{plethysm} of quasisymmetric functions: cf.\ \cite{Loehr-Remmel-plethystic-2011}.

%Given a quasisymmetric function $f\in \mathrm{QSym}$, we denote its dependence on the \emph{alphabet} of variables $x_1,x_2,\dots$ by writing $f[X]$; it is useful to thing of $X$ as the series $x_1+x_2+\cdots$.
%
%For any composition $\alpha$ we define the plethysm $L_\alpha\left[XY\right]$ where the alphabet $XY=\sum_{i,j\geq 1}x_iy_j$ is considered in lexicographic order, i.e.
%\[ x_1y_1<x_1y_2<x_1y_3<\cdots < x_2y_1<x_2y_2<x_2y_3<\cdots, \]
%by setting
%\[ L_\alpha[XY]:=\mathop{\sum_{a_1\leq a_2\leq \cdots \leq a_n}}_{a_j=a_{j+1}\Rightarrow j\notin \mathsf{set}(\alpha)}a_1a_2\cdots a_n \]
%where each $a_i$ is an element of our alphabet $XY\equiv \{x_iy_j\}_{i,j\geq 1}$ and the inequalities $a_i\leq a_{i+1}$ are determined by the total order that we fixed on the alphabet.
%
%For any $f\in \mathrm{QSym}$ we define $f[XY]$ extending the above definition by linearity.
%
%\smallskip 
%
%We observe that with the given order, the resulting series $L_\alpha[XY]$ is quasisymmetric separately in the alphabet $X$ and in the alphabet $Y$.


\subsection{Colorings and (co)inversions}


Given $n\in \mathbb{Z}_{>0}$, let $G=([n],E)$ be a (simple) graph. 

A \emph{coloring} of $G$ is simply a function $\kappa:[n]\to \mathbb{Z}_{>0}$. We call $\mathsf{C}(G)$ the set of colorings of $G$. We can and will identify a coloring $\kappa\in \mathsf{C}(G)$ with the word $\kappa(1)\kappa(2)\cdots \kappa(n)$ in the alphabet $\mathbb{Z}_{>0}$.

A \emph{coloring} of $G$ is called \emph{proper} if $\{i,j\}\in E$ implies $\kappa(i)\neq \kappa(j)$. We call $\mathsf{PC}(G)$ the set of proper colorings of $G$. Notice that with the above identifications we always have that the symmetric group $\mathfrak{S}_n$ is a subset of $\mathsf{PC}(G)$.

Given $\kappa\in \mathsf{C}(G)$ a \emph{$G$-inversion} of $\kappa$ is a pair $(i,j)$ with $\{i,j\}\in E$, $i<j$ and $\kappa(i)>\kappa(j)$. Similarly, a  \emph{$G$-coinversion} of $\kappa$ is a pair $(i,j)$ with $\{i,j\}\in E$, $i<j$ and $\kappa(i)<\kappa(j)$. We denote by $\mathsf{Inv}_G(\kappa)$, respectively $\mathsf{CoInv}_G(\kappa)$, the set of $G$-inversions, respectively $G$-coinversions, of $\kappa$. Let us denote by $\mathsf{Inv}(G)$ the (finite) set of possible sets of $G$-inversions of a coloring of $G$: in other words $\mathsf{Inv}(G):=\{\mathsf{Inv}_G(\sigma)\mid \sigma\in \mathfrak{S}_n\}$.
Similarly, we set
$\mathsf{CoInv}(G):=\{\mathsf{CoInv}_G(\sigma)\mid \sigma\in \mathfrak{S}_n\}$.


We can now set for every $\kappa\in \mathsf{C}(G)$
\[ \mathsf{inv}_G(\kappa):=|\mathsf{Inv}_G(\kappa)|\quad \text{ and }\quad \mathsf{coinv}_G(\kappa):=|\mathsf{CoInv}_G(\kappa)|.\]
\begin{example} \label{ex:coinv_computation}
Consider the graph $G$ in Figure~\ref{fig:interval_graph}, and $\sigma=31852647\in \mathfrak{S}_8\subseteq \mathsf{PC}(G)$. Then 
\begin{align*}
	\mathsf{Inv}_G(\sigma) & =\{(1,2), (3,4),(3,5),(3,6),(6,7)\}\text{ and}\\
	\mathsf{CoInv}_G(\sigma)& =\{(1,3),(2,3),(2,4),(2,5),(2,6),(2,7),(5,6),(5,7),(6,8),(7,8)\},
\end{align*}
so that $\mathsf{inv}_G(\sigma)=5$ and $\mathsf{coinv}_G(\sigma)=10$.
\end{example}

Let $\phi:\mathsf{C}(G)\to \mathfrak{S}_n$ be the \emph{standardization} from left to right: given $\kappa(1)\kappa(2)\cdots\kappa(n)$, if $c_1<c_2<\cdots<c_k$ is the ordered set of values $\kappa(i)$, then $\phi(\kappa)$ is the permutation obtained by replacing the $d_1$ occurrences of $c_1$ with the numbers $1,2,\dots,d_1$ from left to right, then the $d_2$ occurrences of $c_2$ with the numbers $d_1+1,d_1+2,\dots,d_1+d_2$ from left to right, and so on. For example $\phi(3253353)=216 347 5$.

\begin{remark} \label{rem:Inv_CoInv}
	Observe that for any $\kappa\in \mathsf{C}(G)$, 
	\[\mathsf{CoInv}_G(\kappa)\subseteq \mathsf{CoInv}_G(\phi(\kappa))\quad \text{and}\quad \mathsf{Inv}_G(\kappa)= \mathsf{Inv}_G(\phi(\kappa)).\]
	The asymmetry is due to the fact that the standardization $\phi$ is from left to right. But observe that if $\kappa\in \mathsf{PC}(G)$, then in fact $\mathsf{CoInv}_G(\kappa)= \mathsf{CoInv}_G(\phi(\kappa))$ as well.
\end{remark}

\subsection{Interval graphs and (co)inversions}

Given $n\in \mathbb{Z}_{>0}$, let $G=([n],E)$ be an interval graph.

Given $\tau \in \mathfrak{S}_n$, set \[\mathsf{Des}_G(\tau):=\{i\in [n-1]\mid \tau(i)>\tau(i+1)\text{ or } \{\tau(i),\tau(i+1)\}\in E\} \subseteq [n-1]. \]

The next proposition is sort of implicit in the work of Shareshian and Wachs \cite{Shareshian_Wachs_Advances}.
%The next two lemmas are implicit in the work of Shareshian and Wachs \cite{Shareshian_Wachs_Advances}. We will relate them to the results in \cite{Shareshian_Wachs_Advances} in Section~\ref{sec:chromatic_LLT}. 
%
%\begin{lemma}
%	Given $G=([n],E)$ an interval graph and given $\sigma\in \mathfrak{S}_n$, the following statements about $\kappa\in \mathsf{C}(G)$ are equivalent:
%	\begin{enumerate}
%		\item $\kappa\in \mathsf{PC}(G)$ and $\phi(\kappa)=\sigma$;
%		\item $\kappa(\sigma^{-1}(i))\leq \kappa(\sigma^{-1}(i+1))$ for every $i\in [n-1]$ and\\
%		$\kappa(\sigma^{-1}(i))< \kappa(\sigma^{-1}(i+1))$ for every $i\in \mathsf{Des}_G(\sigma^{-1})$.
%	\end{enumerate}
%\end{lemma}
%
%An immediate corollary of the previous lemma is the following result.
%\begin{lemma}
%	Given $G=([n],E)$ an interval graph and given $\sigma\in \mathfrak{S}_n$, we have
%	\[\mathop{\sum_{\kappa\in \mathsf{PC}(G)}}_{\phi(\kappa)=\sigma}x_\kappa=L_{n,\mathsf{Des}_G(\sigma^{-1})}.\]	
%\end{lemma}



%Combining the previous lemmas with Remark~\ref{rem:Inv_CoInv}, we get the following formulas.
\begin{proposition} \label{prop:inv_coinv_formulae}
	Given $G=([n],E)$ an interval graph, for every $S\in \mathsf{Inv}(G)$ we have
	\[\mathop{\sum_{\kappa\in \mathsf{PC}(G)}}_{\mathsf{Inv}_G(\kappa)=S}q^{\mathsf{inv}_G(\kappa)}x_\kappa=\mathop{\sum_{\sigma\in \mathfrak{S}_n}}_{\mathsf{Inv}_G(\sigma)=S}q^{\mathsf{inv}_G(\sigma)}L_{n,\mathsf{Des}_G(\sigma^{-1})}=q^{|S|}\mathop{\sum_{\sigma\in \mathfrak{S}_n}}_{\mathsf{Inv}_G(\sigma)=S}L_{n,\mathsf{Des}_G(\sigma^{-1})},\]
	and for every $S\in \mathsf{CoInv}(G)$ we have
	\[\mathop{\sum_{\kappa\in \mathsf{PC}(G)}}_{\mathsf{CoInv}_G(\kappa)=S}q^{\mathsf{coinv}_G(\kappa)}x_\kappa=\mathop{\sum_{\sigma\in \mathfrak{S}_n}}_{\mathsf{CoInv}_G(\sigma)=S}q^{\mathsf{coinv}_G(\sigma)}L_{n,\mathsf{Des}_G(\sigma^{-1})}=q^{|S|}\mathop{\sum_{\sigma\in \mathfrak{S}_n}}_{\mathsf{CoInv}_G(\sigma)=S}L_{n,\mathsf{Des}_G(\sigma^{-1})}.\]
\end{proposition}


\section{Increasing spanning forests and quasisymmetric functions}
Given a graph $G=([n],E)$, we say that a subgraph $F\subseteq G$ is a \emph{spanning forest} if $F$ is a forest on the vertices $[n]$. In this case, the connected components are labelled trees, with the vertex set contained in $[n]$. Given such a tree $T$, we call $root(T)$ its minimal vertex. Then $T$ is called \emph{increasing} if in the paths stemming from $root(T)$ the other vertices appear in increasing order. 

A spanning forest $F$ of a graph $G=([n],E)$ is called \emph{increasing} if all its connected components are increasing trees. In this case, we think of $F$ as the ordered collection $F=(T_1,T_2,\dots,T_k)$, where the $T_i$ are its connected components, ordered so that
\[
root(T_1)<root(T_2)<\cdots <root(T_k).
\]

E.g.\ the forest $F=(T_1,T_2)$ in Figure~\ref{fig:isf_example}, with\footref{note:edges} $T_1\!=\!(V(T_1),E(T_1))\!=\!(\{1,3\},\{(1,3)\})$ and $T_2\!=\!(V(T_2),E(T_2))\!=\!(\{2,4,5,6,7,8\},\{(2,4),(2,5),(2,6),(5,7),(6,8)\})$, is an increasing spanning forest of the graph $G$ in Figure~\ref{fig:interval_graph}, .

\begin{figure}[ht]
	\centering
	%\tikzset{every loop/.style={min distance=10mm,in=0,out=60,looseness=10}}
	\begin{tikzpicture}[auto,node distance=3cm,
		thick,root node/.style={shape=circle, inner sep=3pt, fill=red,draw},main node/.style={shape=circle, inner sep=3pt, fill=black,draw},external node/.style={shape=circle, inner sep=6pt,draw},scale=.35]
		
		%\node[root node] (1) at (0,0) {};
		%\node[main node] (2) at (-5,3) {};
		\node[external node] (1) at (0,0) {};
		%\node[main node] (4) at (5,3) {};
		\node[external node] (2) at (8,0) {};
		\node[external node] (3) at (0,3) {};
		%\node[main node] (7) at (-3,6) {};
		\node[external node] (4) at (5,3) {};
		\node[external node] (5) at (8,3) {};
		\node[external node] (6) at (11,3) {};
		\node[external node] (7) at (8,6) {};
		\node[external node] (8) at (11,6) {};
		
		\node at (0,3) {$3$};
		\node at (0,0) {$1$};
		\node at (8,0) {$2$};
		\node at (5,3) {$4$};
		\node at (8,3) {$5$};
		\node at (11,3) {$6$};
		\node at (8,6) {$7$};
		\node at (11,6) {$8$};

		
		\path
		(1) edge node {} (3)
		(2) edge node {} (4)
		(2) edge node {} (5)
		(2) edge node {} (6)
		(5) edge node {} (7)
%		(7) edge node {} (8)
%		(3) edge node {} (7)
		(6) edge node {} (8);
	\end{tikzpicture}
	\caption{An example of increasing spanning forest of the graph $G$ in Figure~\ref{fig:interval_graph}. }
	\label{fig:isf_example}
\end{figure} 




 We denote by $\mathsf{ISF}(G)$ the set of increasing spanning forests of $G$.
 
 \smallskip

Given a graph $G=([n],E)$ and an $F\in \mathsf{ISF}(G)$, $F=(T_1,T_2,\dots,T_k)$, we say that a pair $(u,v)$ with $u,v\in [n]$ is a \emph{$G$-inversion} of $F$ if $u\in V(T_i)$, $v\in V(T_j)$, $i>j$ and $(u,v)\in E$ (so that $u<v$). Given an edge $(u,v)\in E(T_i)$ of $T_i$ we define its \emph{weight} in $G$, denoted $\mathsf{wt}_G((u,v))$, to be the number of $w\in V(T_i)$ vertex of $T_i$ such that $u\leq w<v$ and $(w,v)\in E(G)$. So for every tree $T_i$ we define its \emph{weight} in $G$ as
\[ \mathsf{wt}_G(T_i)=\sum_{(u,v)\in E(T_i)}\mathsf{wt}_G((u,v))\]
and finally the \emph{weight} of $F$ (in $G$) as
\[\mathsf{wt}_G(F):=\# \{G\text{-inversions of }F \}+\sum_{i=1}^k \mathsf{wt}_G(T_i).\]



\begin{example}\label{ex:wtG_computation}
The forest $F=(T_1,T_2)$ in Figure~\ref{fig:isf_example} is an increasing spanning forest of the graph $G$ in Figure~\ref{fig:interval_graph}: we observe that its only $G$-inversion is $(2,3)$ (as $3$ occurs in $T_1$, $2$ occurs in $T_2$ and $(2,3)\in E$), $\mathsf{wt}_G(T_1)=\mathsf{wt}_G((1,3))=1$, and \begin{align*}
\mathsf{wt}_G(T_2)& =\mathsf{wt}_G((2,4))+\mathsf{wt}_G((2,5))+\mathsf{wt}_G((2,6))+\mathsf{wt}_G((5,7))+\mathsf{wt}_G((6,8))\\
& = 1+1+2+2+2=8,
\end{align*}
so that $\mathsf{wt}_G(F)=1+1+8=10$. 
\end{example}



Let $G=([n],E)$ be an interval graph, i.e.\ $G\in \mathcal{IG}_n$. We define a function $\Phi_G:\mathsf{PC}(G)\to \mathsf{ISF}(G)$ via Algorithm~\ref{alg:getW} and Algorithm~\ref{alg:main}.


\begin{algorithm}
	\caption{Algorithm defining the function $\mathrm{getW}(G,v,S,\kappa)$}\label{alg:getW}
	\begin{algorithmic}
		\Require A graph $G=([n],E)$, $S\subset [n]$, $v\in [n]\setminus S$, and $\kappa\in \mathsf{PC}(G)$
		\Ensure $W$\Comment{It will be $W\subseteq S\cup\{v\}$}
		\State $W \gets \{v\}$
		\For{$w\in S$}
		\If{$\{u\in W\mid u<w, (u,w)\in E\text{ and }\kappa(u)<\kappa(w)\}\neq \varnothing$}
		\State $W\gets W\cup\{w\}$
		\EndIf
		\EndFor
	\end{algorithmic}
\end{algorithm}





\begin{algorithm}
	\caption{The algorithm defining the function $\Phi_G(\kappa)$}\label{alg:main}
	\begin{algorithmic}
		\Require A graph $G=([n],E)$ and $\kappa\in \mathsf{PC}(G)$
		\Ensure $F=(T_1,T_2,\dots)$ \Comment{It will be $F\in \mathsf{ISF}(G)$}
		\State $S \gets [n]$
		\State $F \gets (\ )$ \Comment{Empty list}
		\While{$S \neq \varnothing$}
		\State $v\gets \min(S)$
		\State $S\gets S\setminus\{v\}$
		\State $T=(V(T),E(T))\gets (\{v\},\varnothing)$ \Comment{The tree we are going to build}
		\State $W\gets \mathrm{getW}(G,v,S,\kappa)$ \Comment{Defined in Algorithm \ref{alg:getW}}
		\For{$i\in \{2,\dots,\# W \}$}
		\State $L \gets \{u\in V(T)\mid u<W_i\text{ and }(u,W_i)\in E\}$ \Comment{$W=\{W_1<W_2<\cdots <W_{\# W}\}$}
		\State $r \gets \# \{u\in L\mid (u,W_i)\in E\text{ and }\kappa(u)<\kappa(W_i)\}$
		\State $T \gets (V(T)\cup\{W_i\},E(T)\cup\{(L_{\# L-r+1},W_i)\})$   \Comment{$L=\{L_1<L_2<\cdots <L_{\# L}\}$}
		\State $S\gets S\setminus\{W_i\}$
		\EndFor
		\State Append $T$ to the right of $F$
		\EndWhile
	\end{algorithmic}
\end{algorithm}

%Our function $f_G$ has also the following property.
%\begin{proposition}
%	For every graph $G=([n],E)$ the function $f_G:\mathsf{ISF}(G)\to \mathfrak{S}_n$ defined by Algorithm~\ref{alg:PhiG_inverse} is such that $\mathsf{Des}_G(f_G(F)^{-1})=[n-1]$ for every $F\in \mathsf{ISF}(G)$.
%\end{proposition}

\begin{proposition} \label{prop:PhiG_welldefined}
	Given a graph $G=([n],E)$, the Algorithm~\ref{alg:main} defines a function $\Phi_G:\mathsf{PC}(G)\to \mathsf{ISF}(G)$.
\end{proposition}

The first nontrivial property of the function $\Phi_G$ is its surjectivity.

%We start by defining a function $\mathrm{colortree}(G,T,d)$ that takes as input a graph $G=([n],E)$, an increasing subtree $T$ of $G$ of size $k\leq n$, and an integer $d$, and it returns a permutation $\sigma$ of the numbers $\{d,d+1,\dots,d+k-1\}$. Furthermore, if $T$ is an increasing spanning tree of $G$, then $\Phi_G(\mathrm{colortree}(G,T,d))=F:=(T)$. 

%Now we define a function  $f_G:\mathsf{ISF}(G)\to \mathfrak{S}_n\subset \mathsf{PC}(G)$ such that $\Phi_G \circ f_G(F)=F$ for every $F\in \mathsf{ISF}(G)$ via Algorithm~\ref{alg:PhiG_inverse}.
%
%\begin{algorithm}
%	\caption{The algorithm defining the section $f_G:\mathsf{ISF}(G)$ of $\Phi_G$}\label{alg:PhiG_inverse}
%	\begin{algorithmic}
	%		\Require A graph $G=([n],E)$ and $F=(T_1,T_2,\dots,T_k)\in \mathsf{ISF}(G)$
	%		\Ensure $\sigma\in \mathfrak{S}_n$ \Comment{It will be $\Phi_G(\sigma)=F$}
	%		\State $clrT\gets ()$ \Comment{empty vector}
	%		\For{$i$ from $1$ to $k$}
	%		\State $d\gets n+1-\sum_{j=1}^{i-1}|V(T_j)|$
	%		\State $clrT_i\gets \mathrm{colortree}(G,T_i,d)$
	%		\State Append $clrT_i$ to the right of $clrT$ 
	%		\EndFor
	%		\State $\sigma\gets ()$ \Comment{empty vector}
	%		\For{$i$ from $1$ to $n$}
	%		\For{$j$ from $1$ to $k$}
	%		\If{$i\in V(T_j)$}
	%		\State $r=\#\{k\in V(T_j)\mid k\leq i\}$
	%		\State Append $c_r$ to the right of $\sigma$, where $clrT_j=\{c_1<c_2<\cdots \}$
	%		\EndIf
	%		\EndFor
	%		\EndFor
	%	\end{algorithmic}
%\end{algorithm}	




\begin{theorem} \label{thm:PhiG_surjective}
	Let $G=([n],E)$ a graph. There exists an explicit function $f_G:\mathsf{ISF}(G)\to \mathfrak{S}_n\subset \mathsf{PC}(G)$ such that $\Phi_G \circ f_G(F)=F$ for every $F\in \mathsf{ISF}(G)$. In particular $\Phi_G$ is surjective, $f_G$ is injective, and $\mathsf{ISF}(G)=\{\Phi_G(\sigma)\mid \sigma\in \mathfrak{S}_n\}=\{\Phi_G(\sigma)\mid \sigma\in f_G(\mathsf{ISF}(G))\}$.
\end{theorem}


When $G=([n],E)$ is an interval graph, $\Phi_G$ has also the following property.

\begin{proposition} \label{prop:Phi_Coinv_inverval}
Given an interval graph $G=([n],E)$, the function $\Phi_G:\mathsf{PC}(G)\to \mathsf{ISF}(G)$ defined by Algorithm~\ref{alg:main} is such that for every $\kappa,\kappa'\in \mathsf{PC}(G)$, $\Phi_G(\kappa)=\Phi_G(\kappa')$ if and only if $\mathsf{CoInv}_G(\kappa)=\mathsf{CoInv}_G(\kappa')$. Moreover $\mathsf{wt}_G(\Phi_G(\kappa))= \mathsf{coinv}_G(\kappa)$ for every $\kappa\in \mathsf{PC}(G)$.
\end{proposition}

We are now ready to define quasisymmetric functions associated to increasing spanning forests of interval graphs.

\begin{definition}
Given an interval graph $G=([n],E)$, and given $F\in \mathsf{ISF}(G)$, we define the formal power series
\[\mathcal{Q}_F^{(G)}=\mathcal{Q}_F^{(G)}[X]:=\mathop{\sum_{\kappa\in \mathsf{PC}(G)}}_{\Phi_G(\kappa)=F}x_\kappa.\]
\end{definition}

We have the following fundamental formula.
\begin{theorem} \label{thm:forest_fundamental}
	Given an interval graph $G=([n],E)\in \mathcal{IG}_n$, and given $F\in \mathsf{ISF}(G)$, we have
	\begin{equation}
		\mathcal{Q}_F^{(G)}=\mathop{\sum_{\sigma\in \mathfrak{S}_n}}_{\mathsf{CoInv}_G(\sigma)=\mathsf{CoInv}_G(F)}L_{n,\mathsf{Des}_G(\sigma^{-1})},
	\end{equation}
	where
	\[
	\mathsf{CoInv}_G(F):=\mathsf{CoInv}_G(f_G(F)).
	\]
\end{theorem}

%\section{The main identity}
\section{Interval orders, chromatic functions and LLT} \label{sec:chromatic_LLT}

%\begin{enumerate}
%	\item Definisci $\chi_G[X,q]$ e $\textrm{LLT}_G[X,q]$.
%	\item Usa la sezione precedente per dare la formula per $\chi_G[X,q]$ in termini di foreste e di permutazioni.
%\end{enumerate}
%
%****

Given any simple graph $G=([n],E)$, Shareshian and Wachs defined in \cite{Shareshian_Wachs_Advances} its \emph{chromatic quasisymmetric function} as
\[\chi_G[X;q]:=\sum_{\kappa \in \mathsf{PC}(G)}q^{\mathsf{coinv}_G(\kappa)}x_\kappa.\]

The following theorem is a direct consequence of Proposition~\ref{prop:Phi_Coinv_inverval} and Theorem~\ref{thm:PhiG_surjective}.
\begin{theorem} \label{thm:chrom_forests_formula}
Given an interval graph $G=([n],E)$, we have
\begin{equation}
\chi_G[X;q]=\sum_{F\in \mathsf{ISF}(G)}q^{\mathsf{wt}_G(F)}\mathcal{Q}_F^{(G)}.
\end{equation}
\end{theorem} 
\begin{example}\label{ex:chrom_csf}
For $G=([3],\{(1,2),(1,3)\})$, the increasing spanning forests of $G$ are 
\begin{align*}
	& F_1=(([3],\{(1,2),(1,3)\})),\quad  F_2=((\{1,3\},\{(1,3)\}),(\{2\},\varnothing)),\\  &F_3=((\{1,2\},\{(1,2)\}),(\{3\},\varnothing)),\quad  F_4=((\{1\},\varnothing),(\{2\},\varnothing),(\{3\},\varnothing)),
\end{align*} 
and we compute
\[\mathsf{wt}_G(F_1)=2,\quad \mathsf{wt}_G(F_2)=\mathsf{wt}_G(F_3)=1,\quad  \mathsf{wt}_G(F_4)=0,\]  \[\mathcal{Q}_{F_1}^{(G)}=L_{(1,2)}+L_{(1^3)}, \quad  \mathcal{Q}_{F_2}^{(G)}=\mathcal{Q}_{F_3}^{(G)}=L_{(1^3)},\quad \mathcal{Q}_{F_4}^{(G)}=L_{(2,1)}+L_{(1^3)},\] hence finally \[\chi_G[X;q]=L_{(2,1)}+q^2L_{(1,2)}+(1+2q+q^2)L_{(1^3)}.\]
\end{example}

The following corollary is a reformulation of \cite[Theorem~3.1]{Shareshian_Wachs_Advances} in our cases, and it follows immediately from Theorems~\ref{thm:chrom_forests_formula} and \ref{thm:forest_fundamental}. 
\begin{corollary} \label{cor:chrom_fundamentals}
Given an interval graph $G$ on $n$ vertices, we have
\begin{equation} \label{eq:cor_chiG_coinv}
	\chi_G[X;q]=\sum_{\sigma\in \mathfrak{S}_n}q^{\mathsf{coinv}_G(\sigma)}L_{n,\mathsf{Des}_G(\sigma^{-1})}.
\end{equation}
\end{corollary}

\smallskip

Given any simple graph $G=([n],E)\in \mathcal{IG}_n$, we define its \emph{LLT quasisymmetric function} as
\[\mathrm{LLT}_G[X;q]:=\sum_{\kappa \in \mathsf{C}(G)}q^{\mathsf{inv}_G(\kappa)}x_\kappa.\]

The following formula is an immediate consequence of Proposition~\ref{prop:inv_coinv_formulae}.
\begin{theorem}\label{thm:LLT_fundamental}
Given any interval graph $G=([n],E)$, we have
\[\mathrm{LLT}_G[X;q]=\sum_{\sigma\in \mathfrak{S}_n}q^{\mathsf{inv}_G(\sigma)}L_{n,\mathsf{Des}(\sigma^{-1})}.\]
\end{theorem}

\smallskip 

The name LLT of these quasisymmetric functions comes from the following well-known facts: when $G$ is a Dyck graph, $\mathrm{LLT}_G[X;q]$ is a symmetric function, and in fact it is a so called \emph{unicellular LLT symmetric functions} (see e.g.\ \cite[Section~3]{Alexandersson-Panova}). In this case the formula in Theorem~\ref{thm:LLT_fundamental} is well known (e.g.\ it can be deduced from \cite[Theorem~8.6]{Novelli_Thibon_NoncommLLT}).

\section{The main identity}

Recall from Section~\ref{sec:qsym} the involutions $\psi$ and $\rho$. We use the plethysm of quasisymmetric functions: cf.\ \cite{Loehr-Remmel-plethystic-2011}.

\begin{theorem} \label{thm:main_theorem}
Let $G=([n],E)$ be an interval graph. Then
\begin{equation} \label{eq:main_identity}
(1-q)^n \rho \left(\psi \chi_G\left[X\frac{1}{1-q}\right]\right)=\mathrm{LLT}_G[X;q].
\end{equation}
\end{theorem}

%In our proof of this result, we consider the expression of $\mathrm{LLT}_G[X;q]$ and $\chi_G[X,q]$ in terms of the Gessel basis given by Theorem \ref{thm:LLT_fundamental} and Corollary \ref{cor:chrom_fundamentals} and we apply the plethysm for $\chi_G$. Next, we deduce a chain of identities using in particular a fundamental formula that holds for the interval graphs. 
%
%\begin{theorem} \label{thm:MainFormula_beta_(n)}
%For every interval graph $G=([n],E)\in \mathcal{IG}_n$ we have
%\[\sum_{\sigma\in\mathfrak{S}_n}q^{\widetilde{\maj}_{G^c}(\sigma)+\widetilde{\inv}_G(\sigma)}=[n]_q!\ .\]
%\end{theorem}
%
%In the theorem above,
%$\widetilde{\mathsf{inv}}_G(\sigma)  :=\{\{\sigma(i),\sigma(j)\}\in E\mid i<j \text{ and } \sigma(i)>\sigma(i+1)\},$ and $\widetilde{\maj}_{G^c}(\sigma) :=\sum_{i\in \widetilde{\mathsf{Des}}_G(\sigma)}i,$ where
%\[
%\widetilde{\mathsf{Des}}_G(\sigma)  :=\{i\in [n-1]\mid \sigma(i)>\sigma(i+1)\text{ and }\{\sigma(i),\sigma(i+1)\}\notin E\}.
%\]
%
%Theorem \ref{thm:MainFormula_beta_(n)} is a reformulation of a theorem in \cite{Kasraoui_maj-inv} (cf. \cite{Kasraoui_maj-inv}*{Corollary~1.11}).
%
%\begin{proposition}[Kasraoui]\label{prop:foata_mod}
%	If $G=([n],E)$ is an interval graph, then
%	\[
%	\varphi_G|_{\mathfrak{S}_n}:\mathfrak{S}_n\rightarrow \mathfrak{S}_n
%	\]
%	is a bijection such that for every $\sigma\in \mathfrak{S}_n$ we have  \[\inv(\varphi_G(\sigma))=\widetilde{\inv}_G(\sigma)+\widetilde{\maj}_{G^c}(\sigma).\]
%\end{proposition}
\begin{remark}
This is really an extension of \cite[Proposition~3.5]{Carlsson-Mellit-ShuffleConj-2015}. Indeed, when $G$ is a Dyck graph, $\chi_G[X;q]$ is symmetric (by \cite[Theorem~4.5]{Shareshian_Wachs_Advances}), the plethysm reduces to the usual plethysm of symmetric functions (cf.\ \cite{Loehr-Remmel-plethystic-2011}), $\rho$ fixes the symmetric functions while $\psi$ gives the usual $\omega$ involution of symmetric functions, and $\mathrm{LLT}_G[X;q]$ is precisely the unicellular LLT symmetric function corresponding to the Dyck graph $G$, so, our \eqref{eq:main_identity} is just a rewriting of \cite[Proposition~3.5]{Carlsson-Mellit-ShuffleConj-2015}.
\end{remark}

\section{Expansions in the $\Psi_\alpha$}

In \cite{Ballantine_et_al} the authors study a family of quasisymmetric functions that they call \emph{type 1 quasisymmetric power sums}, and they denote $\Psi_\alpha$. Actually $\{\Psi_\alpha\mid \alpha\text{ composition}\}$ is a basis of $\mathrm{QSym}$, and these quasisymmetric functions refine the power symmetric functions, i.e.\ for any partition $\lambda\vdash n$
\begin{equation} \label{eq:psi_plambda}
\mathop{\sum_{\alpha\vDash n}}_{\lambda(\alpha)=\lambda}\Psi_\alpha=p_\lambda\ ,
\end{equation}
where $\lambda(\alpha)$ is the unique partition obtained by rearranging in weakly decreasing order the parts of $\alpha$, and the $p_\lambda=p_{\lambda_1}p_{\lambda_2}\cdots$ are the usual \emph{power symmetric functions}.

Given $G=([n],E)$ a graph and $\sigma\in\mathfrak{S}_n$ a permutation, we say that $r\in [n]$ is a \emph{left-to-right $G$-maximum} if for every $s\in [r-1]$ we have $\sigma(s)<\sigma(r)$ and $\{\sigma(s),\sigma(r)\}\notin E$. Notice that $1$ is always a left-to-right $G$-maximum, that we call \emph{trivial}. 
We set
\[\widetilde{\mathsf{inv}}_G(\sigma)  :=\{\{\sigma(i),\sigma(j)\}\in E\mid i<j \text{ and } \sigma(i)>\sigma(i+1)\},\] and% $\widetilde{\maj}_{G^c}(\sigma) :=\sum_{i\in \widetilde{\mathsf{Des}}_G(\sigma)}i,$ where
\[
\widetilde{\mathsf{Des}}_G(\sigma)  :=\{i\in [n-1]\mid \sigma(i)>\sigma(i+1)\text{ and }\{\sigma(i),\sigma(i+1)\}\notin E\}.
\]

We say that $i\in [n-1]$ is a \emph{$G$-descent} if $i\in \widetilde{\mathsf{Des}}_G(\sigma)$.

Given a composition $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)\vDash n$, let $\mathcal{N}_{G,\alpha}$ be the set of $\sigma\in \mathfrak{S}_n$ such that if we break $\sigma=\sigma(1)\sigma(2)\cdots \sigma(n)$ into contiguous segments of lengths $\alpha_1,\alpha_2,\dots,\alpha_k$, each contiguous segment has neither a $G$-descent nor a nontrivial left-to-right $G$-maximum. 

Given a composition $\alpha$, define $z_\alpha:=z_{\lambda(\alpha)}$, where, as usual, for every partition $\lambda\vdash n$, if $m_i$ denotes the number of parts of $\lambda$ equal to $i$, then $z_\lambda:=\prod_{i=1}^nm_i!\cdot i^{m_i}$.

Finally, recall the involution $\omega:\mathrm{QSym}\to \mathrm{QSym}$ from Section~\ref{sec:qsym}.

We state our conjecture.

\begin{conjecture} \label{conj:interval_psi_exp}
	For any interval graph $G=([n],E)$ we have
	\[\omega \chi_G[X;q]=\sum_{\alpha\vDash n}\frac{\Psi_\alpha}{z_{\alpha}}\sum_{\sigma \in \mathcal{N}_{G,\alpha}}q^{\widetilde{\mathsf{inv}}_G(\sigma)}.\]
\end{conjecture}

This conjecture should generalize the following formula, proposed by Shareshian and Wachs \cite[Conjecture~7.6]{Shareshian_Wachs_Advances} and later proved by Athanasiadis \cite{Athanasiadis}.
\begin{theorem} \label{thm:athanasiadis}
	For any Dyck graph $G=([n],E)$ we have
\[\omega \chi_G[X;q]=\sum_{\lambda\vdash n}\frac{p_\lambda}{z_{\lambda}}\sum_{\sigma \in \mathcal{N}_{G,\lambda}}q^{\widetilde{\mathsf{inv}}_G(\sigma)}.\]
\end{theorem}
%Notice that thanks to Theorem~\ref{thm:athanasiadis} and \eqref{eq:psi_plambda}, our Conjecture~\ref{conj:interval_psi_exp} is equivalent to the following tempting conjecture.
%\begin{conjecture}
%For any Dyck graph $G=([n],E)$ and any composition $\alpha\vDash n$ we have
%\[ \sum_{\sigma \in \mathcal{N}_{G,\alpha}}q^{\widetilde{\mathsf{inv}}_G(\sigma)}=\sum_{\sigma \in \mathcal{N}_{G,\lambda(\alpha)}}q^{\widetilde{\mathsf{inv}}_G(\sigma)}. \]
%\end{conjecture}





\acknowledgements

The authors are partially supported by PRIN 2017YRA3LK\_005 \emph{Moduli and Lie Theory} and PRIN 2022A7L229 \emph{ALgebraic and TOPological combinatorics (ALTOP)}. We thank Philippe Nadeau for useful discussions.

%functioning DOI: MR0000004. Finally, a reference to equation~\eqref{eqn:eq1}. And a reference to Figure~\ref{fig:plot}.


%\nocite{Dyer, hump,BB, bakem}
%% 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}
.