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

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

\theoremstyle{definition}
\newtheorem{examples}{Examples}
\newtheorem{remark}{Remark}

\usepackage{lipsum}
\usepackage{dsfont}

\usepackage{tikz}
\usetikzlibrary{arrows}

\newcommand{\UT}{\mathrm{UT}}
\newcommand{\cf}{\mathrm{cf}}
\newcommand{\scf}{\mathrm{scf}}
\newcommand{\NCSym}{\mathrm{NCSym}}
\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\ch}{\mathrm{ch}}
\newcommand{\scs}{\scriptstyle}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\module}{\textbf{-mod}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\GL}{\mathrm{GL}}
\newcommand{\dd}{\displaystyle}
\newcommand{\Id}{\mathrm{Id}}
\newcommand{\Inf}{\mathrm{Inf}}
\newcommand{\Irr}{\mathrm{Irr}}
\newcommand{\Res}{\mathrm{Res}}
\newcommand{\bl}{\mathrm{bl}}
\newcommand{\setpartition}{\mathrm{sp}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\scscs}{\scriptscriptstyle}
\newcommand{\shape}{\mathrm{sh}}
\newcommand{\Ind}{\mathrm{Ind}}
\newcommand{\spanning}{\text{-span}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\below}{\mathrm{blw}}
\newcommand{\NST}{\mathrm{NST}}
\newcommand{\CRS}{\mathrm{CRS}}




%% define your title in the usual way
\title[Chromatic functions and unipotent groups]{Stanley chromatic functions and a conjecture in the representation theory of unipotent groups}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Farid Aliniaeifard\thanks{\href{mailto:farid@math.ubc.ca}{farid@math.ubc.ca}.}\addressmark{1} \and Nathaniel Thiem\thanks{\href{mailto:thiemn@colorado.edu}{thiemn@colorado.edu}. Partially supported by Simons Foundation collaboration grant 426594.}\addressmark{2}}


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of British Columbia \\  \addressmark{2}Department of Mathematics, University of Colorado Boulder}

%% 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{This extended abstract is an introduction to a conjecture attempting to relate the representation theory of finite unipotent groups to the representation theory of symmetric groups via combinatorial Hopf algebras.  Chromatic symmetric functions arise naturally through the representation theory of unipotent groups, and a positive answer to the conjecture should have useful things to say about the $e$-positivity of these functions.}

%% 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{set partitions, symmetric functions, graph coloring, combinatorial Hopf algebras, categorification}

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

Stanley chromatic symmetric functions have seen increased attention in recent years with attempts to construct $S_n$-modules via Hessenberg varieties \cite{SW}, and connections to the representation theory of the finite general linear groups via induced characters from unipotent groups \cite{Ga}.  This paper explores a seemingly more direct relationship between the representation theory of the finite groups of unipotent upper-triangular matrices and the representation theory of symmetric groups that has chromatic functions at its core. 
A framework developed by Aguiar--Bergeron-Sottile \cite{ABS} for canonical maps on combinatorial Hopf algebras gives the mechanism underlying this connection.  In particular, for a cocommutative Hopf algebra $\cH$, we get Hopf algebra morphisms
\[
\ch:\cH\rightarrow \Sym\cong \cf(S_\bullet),
\]
where $\Sym$ is the Hopf algebra of symmetric functions and
\[
\cf(S_\bullet)=\bigoplus_{n\geq 0} \cf(S_n)
\]
is the Hopf algebra of class functions of the finite symmetric groups $S_n$ with product given by induction from Young subgroups and coproduct given by restriction to Young subgroups (e.g. \cite{Mac}).  While the function $\ch$ can be given quite explicitly, it unfortunately does not obviously lend itself to representation theoretic interpretations (vis-a-vis $S_n$).

The paper \cite{ABT} established a Hopf algebra structure on
\[
\cf(\UT_\bullet)=\bigoplus_{n\geq 0}\cf(\UT_n),
\]
where $\cf(\UT_n)$ is the set of class functions on the finite group of upper-triangular matrices $\UT_n$ (the product comes from inflation and the coproduct from restriction).  In fact, this paper lifts the Hopf structure from a subHopf algebra 
\[
\scf(\UT_\bullet)=\bigoplus_{n\geq 0}\scf(\UT_n)
\]
defined in \cite{AIM}.  While the latter paper also shows this Hopf algebra is isomorphic to the symmetric functions in non-commuting variables $\NCSym$, this point of view will not be the focus of this abstract.


%The paper \cite{AIM} estabilishes a categorification of the Hopf algebra of symmetric functions in noncommuting variables $\NCSym$ using the representation theory of finite unipotent groups.  Specifically, if $\cf(\UT_n)$ denotes the set of class functions of the finite group of $n\times n$ unipotent uppertriangular matrices, then there is a subspace $\scf(\UT_n)\subseteq \cf(\UT_n)$ with a basis of orthogonal characters such that
%\[
%\scf(\UT_\bullet):=\bigoplus_{n\geq 0}\scf(\UT_n)\cong \NCSym,
%\] 
%where multiplication in $\scf(\UT_\bullet)$ is given by the inflation functor and the coproduct by the restriction functor.  

%While there is a standard Hopf algebra morphism $\ch_{\delta_{(\bullet)}}:\NCSym\rightarrow \Sym$ to the Hopf algebra of symmetric functions $\Sym$, given by letting the variables commute \cite{}, it does not appear to have any representation theoretic content.  Using the ABS framework, however, we explore an alternate Hopf algebra morphism $\ch_{\mathds{1}_\bullet\rangle}:\NCSym\rightarrow \Sym$ that appears to be functorial.  In particular, the image of the character basis of $\scf(\UT_n)$ appears to be very related to the Stanley chromatic symmetric functions.

In summary, we have the following Hopf algebras of interest:
\[
\begin{tikzpicture}
	\node (Sym) at (0,0) {$\Sym\cong\cf(S_\bullet)\cong\Sym^*$};
	\node (scf) at (-6,-1.5) {$\scf(\UT_\bullet)$};
	\node (scf*) at (6,-1.5) {$\scf(\UT_\bullet)^*$};
	\node (cf) at (-6,1.5) {$\cf(\UT_\bullet)$};
	\node (cf*) at (6,1.5) {$\cf(\UT_\bullet)^*$};
	\draw[right hook->] (Sym)-- node [above] {$\scs\tilde\ch_{\mathds{1}_\bullet\rangle}^*$} (scf*);
	\draw[->>] (scf)-- node [above] {$\scs\tilde\ch_{\mathds{1}_\bullet\rangle}$} (Sym);
	\draw[->>] (cf)-- node [above] {$\scs\ch_{\mathds{1}_\bullet\rangle}$} (Sym);
	\draw[->>] (cf*)-- (scf*);
	\draw[right hook->] (scf)-- (cf);
	\draw[right hook->] (Sym)-- node [above] {$\scs\ch_{\mathds{1}_\bullet\rangle}^*$}(cf*);
\end{tikzpicture}
\]
It is worth noting that while $\tilde\ch_{\mathds{1}_\bullet\rangle}$ is the restriction of $\ch_{\mathds{1}_\bullet\rangle}$, the functions $\ch_{\mathds{1}_\bullet\rangle}^*$ and $\tilde\ch_{\mathds{1}_\bullet\rangle}^*$ are fundamentally different, and only $\ch_{\mathds{1}_\bullet\rangle}^*$ seems to be functorial.  The main conjecture of this paper is as follows.

\begin{conjecture}
	The functions $\ch_{\mathds{1}_\bullet\rangle}$ and $\ch_{\mathds{1}_\bullet\rangle}^*$ come from adjoint functors $\UT_n\module\longrightarrow S_n\module$ and $S_n\module\longrightarrow \UT_n\module$.
\end{conjecture}

In particular, if we apply either function to a character we should obtain a character.  By construction, it will be clear that both functions are in fact virtual characters (send a character to a $\ZZ$-linear combination of characters), but all evidence seems to indicate that the signs all cancel.

\section{Setting the stage}

This section reviews the Aguiar--Bergeron--Sottile framework for combinatorial Hopf algebras, and introduces the main Hopf algebra of interest on characters of the unipotent upper-triangular matrices.

\subsection{The Aguiar--Bergeron--Sottile framework}

The framework developed by Aguiar--Bergeron--Sottile \cite{ABS} takes a pair $(\cH,\zeta)$ ---where $\cH$ is a cocommutative, graded, connected Hopf algebra and $\zeta:\cH\rightarrow \CC$ is an algebra morphism--- and constructs a canonical Hopf algebra homomorphism $\ch_\zeta:\cH\rightarrow \Sym$ given explicitly on graded components by
\[
\begin{array}{rccc} \ch_\zeta: & \cH_n & \longrightarrow & \Sym_n\\
	& h & \mapsto & \dd\sum_{\mu\vdash n} \zeta(\Delta^\mu(h)) m_\mu,
\end{array}
\]
where $m_\mu$ is the monomial symmetric functions corresponding to the integer partition $\mu$, and if $\ell(\mu)=\ell$, then $\Delta^\mu$ is the composition of $\Delta^{\ell}$ with the standard projection $\cH^{\otimes\ell}\rightarrow \cH_{\mu_1}\otimes \cdots \otimes \cH_{\mu_\ell}$; in this case, $\zeta$ is applied diagonally.

While often applied to other situations, the framework can in fact be applied to the classical situation of 
\begin{equation}\label{StandardCharacteristic}
\begin{array}{rccc} \ch: & \cf(S_\bullet) & \longrightarrow & \Sym\\
& \psi^\lambda & \mapsto & s_\lambda,	
\end{array}
\end{equation}
where $\lambda$ is an integer partition, $\psi^\lambda$ is the corresponding irreducible character of $S_{|\lambda|}$, and $s_\lambda$ is the corresponding Schur function. Let $\mathds{1}_n$ denote the trivial character of $S_n$, and $\langle\cdot,\cdot\rangle$ the usual inner product on class functions. If $\mathds{1}_\bullet\rangle:\cf(S_\bullet)\rightarrow \CC$ is the algebra morphism on graded components given by
\[
\begin{array}{rccc} \mathds{1}_\bullet\rangle: & \cf(S_n) & \longrightarrow & \CC\\
	& \gamma & \mapsto & \langle \gamma,\mathds{1}_n\rangle,
\end{array}
\]
then $\ch_{\mathds{1}_\bullet\rangle}$ is the same as the standard function (\ref{StandardCharacteristic}).


\subsection{The Hopf algebra $\cf(\UT_\bullet)$}

Fix a power of a prime $q$, and for $n\in \ZZ_{\geq 0}$, let  
\[
\UT_n=\{g\in \GL_n(\FF_q)\mid (g-\Id_n)_{ij}\neq 0 \text{ implies $i<j$}\}
\]
be the subgroup of unipotent upper-triangular matrices with entries in the finite field $\FF_q$. The representation theory of these groups is well-known to be wild, but we won't let that deter us.  In particular, the space of class functions $\cf(\UT_n)$ has a canonical basis given by the irreducible characters $\Irr(G)$.

We form a graded vector space,
\[
\cf(\UT_\bullet)=\bigoplus_{n\geq 0}\cf(\UT_n),
\]
which has an inner product 
\begin{equation}\label{InnerProduct}
\langle \gamma,\psi\rangle=\left\{
\begin{array}{ll}
	\dd \frac{1}{|\UT_n|}\sum_{u\in \UT_n} \gamma(u)\overline{\psi(u)} & \text{if $\gamma,\psi\in \cf(\UT_n)$,}\\
	0 & \text{otherwise.}
\end{array}
\right.
\end{equation}
The basis of irreducible characters forms an orthonormal basis of this space. We upgrade to a graded Hopf algebra with the graded product
\[
\begin{array}{r@{\ }c@{\ }c@{\ }c}\cdot:&\cf(\UT_m)\otimes \cf(\UT_n) & \longrightarrow & \cf(\UT_{m+n}) \\
& \psi\otimes \gamma & \mapsto & \Inf_{\UT_m\oplus \UT_n}^{\UT_{m+n}}(\psi\otimes \gamma),	
\end{array}\]
where $\UT_m\oplus \UT_n$ is the block diagonal quotient (and inflation $\Inf$ lifts functions up from that quotient), and coproduct
\[\begin{array}{r@{\ }c@{\ }c@{\ }c}\Delta:& \cf(\UT_n) & \longrightarrow & \dd\bigoplus_{j=0}^n\cf(\UT_{j})\otimes  \cf(\UT_{n-j})\\
& \psi & \mapsto & \dd\sum_{A\subseteq \{1,2,\ldots, n\}}\Res_{\UT_A\times \UT_{\overline{A}}}^{\UT_{n}}(\psi),	
\end{array}
\]
where $\bar{A}$ is the complement of $A$ and $\UT_A$ ($\cong \UT_{|A|}$) is the subset of matrices whose nonzero entries above the diagonal only occur in the rows and columns in $A$. 

We obtain the dual Hopf algebra $\cf(\UT_\bullet)^*$ by dualizing using the inner product (\ref{InnerProduct}). The underlying space is the same, but uses the adjoint functor induction for the product and deflation for the coproduct.   

Returning to the ABS framework, we have an algebra morphism suggested by the symmetric group case given by
\[
\begin{array}{rccc} \mathds{1}_\bullet\rangle: & \cf(\UT_n) & \longrightarrow & \CC\\
	& \gamma & \mapsto & \langle \gamma,\mathds{1}_n\rangle,
\end{array}
\]
which gives a corresponding canonical map $\ch_{\mathds{1}_\bullet\rangle}:\cf(\UT_\bullet)\longrightarrow \Sym$.  In particular, for $\gamma\in \cf(\UT_n)$,
\[
\ch_{\mathds{1}_\bullet\rangle}(\gamma)=\sum_{\underline{A}\vDash \{1,2,\ldots,n\}\atop \bl(\underline{A})\vdash n} \langle \Res_{\UT_{\underline{A}}}^{\UT_n}(\gamma),\mathds{1}\rangle m_{\bl(\underline{A})},
\]
where $\underline{A}=(A_1,\ldots, A_\ell)\vDash\{1,2,\ldots,n\}$ is a set composition (an ordered list of nonempty subsets that partition $\{1,2,\ldots, n\}$) and $\bl(\underline{A})=(|A_1|,|A_2|,\ldots,|A_\ell|)$ is a composition of $n$.  In particular, since the transition matrix from monomial to symmetric functions is integral, we see that the image of a character will be a virtual character.

\section{Evidence for the conjecture}

In this section we gather some evidence for the conjecture (though we omit complete computations of smaller examples).  We begin by examining some natural $\UT_n$ characters that are more understandable than the basis $\Irr(\UT_n)$.  Then we examine the two functions $\ch_{\mathds{1}_\bullet\rangle}$ and $\ch_{\mathds{1}_\bullet\rangle}^*$, individually.

\subsection{More combinatorial spaces of characters}

%Since the representation theory of $\UT_n$ is wild in general, we consider other families of characters that are more computable.

An \emph{$\FF_q^\times$-set partition} of $\{1,2,\ldots,n\}$ is a subset
\[
\lambda\subseteq \{(i,j;a)\mid 1\leq i<j\leq n, a\in \FF_q^\times\}
\] 
such that if $(i,k;a),(j,l;b)\in \lambda$, then $i=j$ or $k=l$ implies $(i,k;a)=(j,l;b)$.  Let 
\[
\cP_n(q)=\{\text{$\FF_q^\times$-set partitions of $\{1,2,\ldots, n\}$}\}.
\]
We typically view $\lambda$ as an edge labeled graph $\Gamma_\lambda$ on vertices $\{1,2,\ldots,n\}$ with an edge (called an \emph{arc}) labeled by $a$ from $i$ to $j$ if $(i,j;a)\in \lambda$.  For example,
\[
\left\{\begin{array}{@{}c@{}} (1,3;a),(2,7;b),(3,5;c),\\(7,8;d),(8,9;e)\end{array}\right\}
\leftrightarrow
\begin{tikzpicture}[scale=.5,baseline=.2cm]
\foreach \x in {1,2,...,9}
	{\node (\x) at (\x,0)[inner sep = -1pt] {$\bullet$};
	\node at (\x,-.5cm) {$\scs \x$};}
\foreach \x/\y/\z in {1/3/a,2/7/b,3/5/c,8/9/e,7/8/d}
	\draw (\x) to [out=70, in=110] node [above] {$\scs \z$} (\y);
\end{tikzpicture}\ .
\]
In practice, the labels are not particularly important for our purposes, so we will usually omit the edge labels in the graph $\Gamma_\lambda$, and we obtain a more standard interpretation of set partition if we let the blocks of the set partition be the connected components of $\Gamma_\lambda$. 

We say an element $\lambda\in \cP_n(q)$ is 
\begin{itemize}
\item	\emph{non-nesting} if the set of nestings $\NST_\lambda=\emptyset$, where
\[
\NST_\lambda=\{((i,l;a),(j,k;b))\in \lambda\times \lambda\mid i< j<k< l\}.
\]
\item \emph{non-crossing} if the set of crossings $\CRS_\lambda=\emptyset$, where
\[
\CRS_\lambda= \{((i,k;a),(j,l;b))\in \lambda\times \lambda\mid i< j<k< l\}.
\]
\end{itemize}
In either case, we can evaluate in the graph $\Gamma_\lambda$ whether the edges have any nestings or crossings.

Using this combinatorics we construct two families of characters by inducing from families of subgroups.  Fix a non-trivial homomorphism $\vartheta:\FF_q^+\rightarrow \CC^\times$. For $\lambda\in \cP_n(q)$, define 
\[
\begin{array}{rccc}\vartheta_\lambda:&\UT_n & \longrightarrow & \CC\\
& u & \mapsto & \dd \prod_{(i,j;a)\in \lambda}\vartheta(au_{ij}),
\end{array}
\]
which restricts to a linear character of the subgroup
\[
\UT_\lambda=\{u\in \UT_n\mid u_{ij}=0\text{ if $(i,k;a)\in \lambda$, $i<j<k$}\}.
\]
This gives us an induced character
\[
\chi^\lambda=\Ind_{\UT_\lambda}^{\UT_n}(\vartheta_\lambda).
\]
For $\lambda, \mu\in \cP_n(q)$, these characters are orthogonal
\begin{equation}\label{Orthogonality}
\langle \chi^\lambda,\chi^\mu\rangle=q^{|\CRS_\lambda|} \delta_{\lambda\mu},
\end{equation}
and every irreducible character in $\Irr(G)$ is a constituent of exactly one such character \cite{DI}.  Here, $\chi^\emptyset=\mathds{1}_{\UT_n}$ is the trivial character.

If we take the space spanned by these characters we get a subspace
\[
\scf(\UT_\bullet)=\bigoplus_{n\geq 0}\scf(\UT_n),\quad \text{where}\quad \scf(\UT_n)=\CC\spanning\{\chi^\lambda\mid \lambda\in \cP_n(q)\},
\]
that forms a subHopf algebra of $\cf(\UT_\bullet)$ \cite{AIM}.


Another family of characters comes from $\lambda\in \cP_n(2)$ non-nesting.  Define
\[
\bar{\chi}^\lambda=\Ind_{\overline{\UT}_\lambda}^{\UT_n}(\mathds{1})\quad \text{where}\quad \overline{\UT}_\lambda=\{u\in \UT_n\mid u_{jk}=0, \text{ if $i\leq j<k\leq l$, $(i,l;a)\in \lambda$}\}.
\]
For example, if $\lambda=\{(1,4;1),(3,5;1),(5,6;1)\}\in \cP_6(2)$, then
\[\overline{\UT}_\lambda=
\left[\begin{array}{cccccc}
1 & 0 & 0 & \mathbf{0} & \ast & \ast\\
0 & 1 & 0 & 0 & \ast & \ast\\	
0 & 0 & 1 & 0 & \mathbf{0} & \ast\\	
0 & 0 & 0 & 1 & 0 & \ast  \\	
0 & 0 & 0 & 0 & 1 & \mathbf{0}  \\
0 & 0 & 0 & 0 & 0 &  1 
\end{array}
\right]
\subseteq 
\UT_\lambda=\left[\begin{array}{cccccc}
1 & 0 & 0 & \circledast & \ast & \ast\\
0 & 1 & \ast & \ast & \ast & \ast\\	
0 & 0 & 1 & 0 & \circledast & \ast\\	
0 & 0 & 0 & 1 & \ast & \ast  \\	
0 & 0 & 0 & 0 & 1 & \circledast  \\
0 & 0 & 0 & 0 & 0 &  1 
\end{array}
\right],
\]
where the coordinates of $\lambda$ are indicated by bold $\mathbf{0}$ or circled $\circledast$.
Both the regular character $\bar{\chi}^{\{(1,n;1)\}}$ and the trivial character $\bar\chi^\emptyset$ of $\UT_n$ are of this form. 

While these characters are no longer pairwise orthogonal, we still have that
\[
\overline{\scf}(\UT_\bullet)=\bigoplus_{n\geq 0}\overline{\scf}(\UT_n),\quad \text{where}\quad \overline{\scf}(\UT_n)=\CC\spanning\{\bar\chi^\lambda\mid \lambda\in \cP_n(2),\text{ non-nesting}\},
\]
is a subHopf algebra of $\scf(\UT_\bullet)$ \cite{AT20}.


\subsection{The function $\ch_{\mathds{1}_\bullet\rangle}$}

We begin by considering the image of the characters $\chi^\lambda$ for $\lambda\in \cP_n(q)$.  Our most complete answer is for those characters $\chi^\lambda$ corresponding to elements $\lambda\in \cP_n(q)$ that are both non-nesting and non-crossing.  By (\ref{Orthogonality}), these are also irreducible characters.      

Chromatic symmetric functions arise naturally in the image.  Recall, a proper coloring of a graph $\Gamma=(V,E)$ is a function $c:V\rightarrow \ZZ_{\geq 1}$ such that if $(a,b)\in E$ then $c(a)\neq c(b)$.  Stanley \cite{St} defined the chromatic symmetric function
\[
X_\Gamma=\sum_{c:V\rightarrow \ZZ_{\geq 1}\atop \text{a proper coloring}} X_c,\quad \text{where}\quad X_c=X_1^{|c^{-1}(1)|}X_2^{|c^{-1}(2)|}\cdots.
\]

For $\lambda\in \cP_n(q)$, let 
\[
\cN_\lambda=\{1\leq j\leq n\mid i<j<k, (i,k,a)\in \lambda\},
\]
and for any subset $M\subseteq \cN_\lambda$ define a graph $\Gamma_\lambda^M$ with vertices $\{1,2,\ldots,n\}$ and edges
\[
\{\{j,k\}\mid i\leq j<k\leq l, (i,l,a)\in \lambda, j,k\in M\cup\{i,l\}\}.
\] 
For example, if $\lambda=\{(1,5;a),(5,6;b),(8,10;c)\}$, then
\[
\cN_\lambda=\{2,3,4,9\}\quad \text{and}\quad \Gamma_{\lambda}^{\{2,4,9\}}=
\begin{tikzpicture}[scale=.5,baseline=0cm]
\foreach \x in {1,3,5,6,7,8,10}
	{\node (\x) at (\x,0)[inner sep = -1pt] {$\bullet$};
	\node at (\x,-.5cm) {$\scs \x$};}
\foreach \x in {2,3,4,9}
	\node at (\x,-.8) {$-$};
\foreach \x in {2,4,9}
	{\node (\x) at (\x,0)[inner sep = -1pt] {$\bullet$};
	\node at (\x,-.5cm) {$\scs \mathbf{\x}$};}
\foreach \x/\y in {1/5,5/6,8/10,1/2,1/4,2/4,2/5,4/5,8/9,9/10}
	\draw (\x) to [out=70, in=110] (\y);
\end{tikzpicture}\ .
\]
Note that $\Gamma_\lambda$ is a subgraph of $\Gamma_\lambda^M$ for every subset $M$.  We now get the image of some of the irreducible characters of $\UT_n$.

\begin{theorem}\label{ImageSupercharacter} Let $t=q-1$.
For $\lambda\in \cP_n(q)$  non-nesting and non-crossing,
\[
\ch_{\mathds{1}_\bullet\rangle}(\chi^\lambda)=\sum_{M\subseteq \cN_\lambda} t^{|M|}X_{\Gamma_\lambda^M}.
\]	
\end{theorem}

The following lemma gives an essential outline for how to compute the restriction of characters with an eye towards finding a copy of the trivial character.  Heuristically, we can think of restriction as picking a subset of vertices in our graph $\Gamma_\lambda$. If an edge has endpoints in the subset, that edge remains.  If an edge is missing one or two endpoints, we either re-attach the unattached endpoints in all possible ways such that the new edge weakly nests in the original edge or remove the edge.

\begin{lemma}[\cite{Th}] 
\begin{description}
	\item[(a) Factorization.] For $\lambda\in \cP_n(q)$  and $\underline{A}=(A_1,A_2,\ldots,A_\ell)\vDash n$,
	\[
\Res^{\UT_n}_{\UT_{\underline{A}}}\Big(\frac{\chi^\lambda}{\chi^\lambda(1)}\Big)= \bigodot_{1\leq j\leq \ell\atop (i,l;a)\in \lambda} \Res^{\UT_n}_{\UT_{A_j}}\Big(\frac{\chi^{(i,l;a)}}{\chi^{(i,l;a)}(1)}\Big),
\]
where $\odot$ denotes the pointwise product on functions.
\item[(b) Local restriction.] For $(i,l,a)\in \lambda$ and $A\subseteq \{1,2,\ldots,n\}$, 
\[
\hspace*{-.5cm}\Res^{\UT_n}_{\UT_{A}}(\chi^{(i,l;a)})=\left\{\begin{array}{ll} 
	q^{\#\{1\leq j\leq l\mid j\notin A\}}\chi^{(i,l;a)} & \text{if $i,l\in A$,}\\
	\dd q^{\#\{1\leq j\leq l\mid j\notin A\}}\Big(\mathds{1}+\sum_{i<k<l, \atop k\in A, b\in \FF_q^\times}\chi^{(i,k;b)}\Big) & \text{if $i\in A$, $l\notin A$,}\\
	\dd q^{\#\{1\leq j\leq l\mid j\notin A\}}\Big(\mathds{1}+\sum_{i<k<l\atop k\in A, b\in \FF_q^\times}\chi^{(k,l;b)}\Big) & \text{if $i\notin A$, $l\in A$,}\\
\dd q^{\#\{1\leq j\leq l\mid j\notin A\}}\Big((|A\cap [i,l]|t+1)\mathds{1}+\hspace{-.3cm}\sum_{i<j<k<l\atop j,k\in A,b\in \FF_q^\times} \hspace{-.3cm}\chi^{(j,k;b)}\Big) & \text{if $i,l\notin A$.}
\end{array}
\right.
\]
\item[(c) Conflict resolution.]  For $i\leq j<k\leq l$,
\[
\chi^{(i,k;a)}\odot \chi^{(j,l,b)}= \left\{\begin{array}{ll} 
\chi^{\{(i,k;a),(j,l;b)\}} & \text{if $i\neq j$ and $k\neq l$,}\\
\dd\chi^{(i,l;b)}+\sum_{i<i'<k\atop c\in \FF_q^\times}\chi^{\{(i',k;c),(i,l;b)\}} & \text{if $i=j$ and $k\neq l$,}\\
\dd\chi^{(i,k;a)}+\sum_{j<l'<l\atop c\in \FF_q^\times}\chi^{\{(i,k;a),(i,l';c)\}} & \text{if $i\neq j$ and $k=l$.}
\end{array}
\right.
\]
\end{description}
\end{lemma}

Using this lemma we see that to get the trivial character (corresponding to the graph with no edges) when $\lambda\in \cP_n(q)$ is non-nesting, we must detach an endpoint of every arc.  

\begin{lemma}\label{LemmaEndpointsRelease}
Suppose $\lambda\in \cP_n(q)$, and $\underline{A}\vDash n$.  Then 
\begin{enumerate}	
\item[(a)] If $(i,j,a)\in \lambda$ implies $i$ and $j$ are in different blocks of $\underline{A}$, then
\[
\langle \Res_{\UT_{\underline{A}}}^{\UT_n}(\chi^\lambda),\mathds{1}\rangle\neq 0.
\]
\item[(b)] If $\lambda$ is non-nesting and 
\[
\langle \Res_{\UT_{\underline{A}}}^{\UT_n}(\chi^\lambda),\mathds{1}\rangle\neq 0,
\]
 then $(i,j,a)\in \lambda$ implies $i$ and $j$ are in different blocks of $\underline{A}$.
 \end{enumerate}
\end{lemma}


Note that if $\lambda\in \cP_n(q)$, then every $\underline{A}$ specifies a function
\[
\begin{array}{rccc}
	c_{\underline{A}}: & \{1,2,\ldots,n\} & \longrightarrow & \{1,2,\ldots, \ell(\underline{A})\}\\
	& j & \mapsto & i,\text{ where $j\in A_i$} 
\end{array}
\]
By the Lemma \ref{LemmaEndpointsRelease}, when $\lambda$ is also non-nesting, this function is a proper coloring of the graph $\Gamma_\lambda$ if and only if 
\[
\langle \Res_{\UT_{\underline{A}}}^{\UT_n}(\chi^\lambda),\mathds{1}\rangle\neq 0.
\]

\begin{lemma}
If $\lambda\in \cP_n(q)$ is a non-nesting and non-crossing, then
\[
\ch_{\mathds{1}\rangle} (\chi^\lambda)=\hspace{-.25cm}\sum_{c:V_\lambda\rightarrow \ZZ_{\geq 1}\atop{ \text{a proper coloring}\atop \text{of $\Gamma_\lambda$}}}\prod_{(i, k;a)\in \lambda\atop d\notin \{c(i),c(k)\}} \hspace{-.25cm}\Big(\#\{i<j< k\mid c(j)=d\}t+1\Big) X_c.
\]
\end{lemma}


Since the graphs in question are unit interval graphs, from Gasharov \cite{Gsh} we obtain the following corollary to Theorem \ref{ImageSupercharacter}.

\begin{corollary}
For $\lambda\in \cP_n(q)$ non-nesting and non-crossing, $\ch_{\mathds{1}_\bullet\rangle}(\chi^\lambda)$ is a non-negative linear combination of schur functions with coefficients in $\ZZ_{\geq 0}[t]$.	
\end{corollary}

\begin{examples}
Some easy examples include:
\begin{enumerate}
\item[(a)] Since the trivial character $\mathds{1}_n\in \cf(\UT_n)$ is in fact $\Inf_{\{1\}}^{\UT_n}(\mathds{1})$, by the multiplicativity of the canonical map,	
\[
\ch_{\mathds{1}_\bullet\rangle}(\mathds{1}_{\UT_n})=\Ind_{S_1\times S_1\times \cdots\times S_1}^{S_n}(\mathds{1}_1\otimes \mathds{1}_1\otimes \cdots\otimes \mathds{1}_{1}),
\]
or the regular character of $S_n$.
\item[(b)] The linear characters of $\UT_n$ are all obtained from $\FF_q^\times$-set partitions and they correspond to $\lambda\in \cP_n(q)$ such that $(i,j;a)\in \lambda$ implies $j-i=1$. At $q=2$ these are in bijective correspondence with integer compositions and give a subHopf algebra of $\cf(\UT_n)$ isomorphic to the Hopf algebra of noncommutative symmetric functions $\mathrm{NSym}$.  For the single block partition $\sigma_n$, we have
\[
\ch_{\mathds{1}_\bullet\rangle}(\chi^{\sigma_n})=X_{P_n},
\]
where $P_n$ is the path graph.  In general, we get a product of path graphs corresponding to the composition part lengths. 
\item[(c)] The minimal $n$ such that $\scf(\UT_n)\neq\cf(\UT_n)$ is $n=4$.  In particular, for $a,b\in \FF_q^\times$,
\[
\chi^{\{(1,3;a),(2,4;b)\}}=\sum_{c\in \FF_q} \chi_c^{\{(1,3;a),(2,4;b)\}},
\]
is a decomposition into irreducible characters, where
\[
\chi_c^{\{(1,3;a),(2,4;b)\}}(u)=\left\{\begin{array}{ll}
	q\vartheta_c(u_{12})\vartheta_a(u_{13})\vartheta_b(u_{24}) & \text{if $u_{23}=0$ and $u_{12}a=u_{34}b$, }\\
	0, & \text{otherwise.}
\end{array}
\right.
\]
Then direct computation gives
\begin{align*}
\ch_{\mathds{1}_\bullet\rangle}(\chi_c^{\{(1,3;a),(2,4;b)\}})&=2(1+\delta_{c,0})m_{(2,2)}+(6+2q)m_{(2,1,1)}+24q m_{(1^4)}\\
&=\left\{\begin{array}{ll}
4s_{(2,2)}+ 2(2+t) s_{(2,1,1)} + (18t+4)s_{(1^4)} & \text{if $c=0$,}\\
  2s_{(2,2)}+ 2(3+t) s_{(2,1,1)} + (18t+2)s_{(1^4)} & \text{if $c\neq 0$.}
\end{array}\right.
\end{align*}
\end{enumerate}
\end{examples}

For the permutation modules $\bar\chi^\lambda$ we again get a sum of chromatic symmetric functions with coefficients powers of $t=q-1$.

\begin{theorem} \label{ImagePermutationCharacters}
For $\lambda\in\cP_n$  non-nesting,
\[
\ch_{\mathds{1}_\bullet\rangle}(\bar{\chi}^\lambda)=\sum_{E\subseteq E_\lambda^{\cN_\lambda}} t^{|E|} X_{(\{1,2,\ldots,n\},E)},
\]	
where $E_\lambda^{\cN_\lambda}$ is the edge set of $\Gamma_\lambda^{\cN_\lambda}$.
\end{theorem}

The key step to this theorem is the following lemma that writes the image of $\ch_{\mathds{1}_\bullet\rangle}$ in terms of monomials.  Given a coloring $c:\{1,2,\ldots,n\}\rightarrow\ZZ_{\geq 1}$ of a graph $\Gamma_\lambda^{\cN_\lambda}$ (not necessarily proper), we define 
\[
M_c(\lambda)=\max\{E\mid c\text{ is a proper coloring of $(\{1,2,\ldots,n\},E)$}\},
\]
where maximality is with respect to containment.

\begin{lemma} For $\lambda\in\cP_n$  non-nesting,
\[
\ch_{\mathds{1}_\bullet\rangle}(\bar{\chi}^\lambda)=\sum_{c:\{1,2,\ldots, n\} \rightarrow \ZZ_{\geq 1}} q^{|M_c(\lambda)|} X_c.
\]	
\end{lemma}





Note that Theorem \ref{ImagePermutationCharacters} hardly seems like evidence, since we get plenty of graphs showing up that are not unit-interval graphs.  In fact, in the case of $\lambda=\{(1,n;a)\}$, we get all possible graphs appearing in the sum, since $\Gamma_\lambda^{\cN_\lambda}$ is the complete graph.  However, it appears that we still get positive sums, as the bad graphs get corrected by good ones.  For example,
\begin{align*}
\ch_{\mathds{1}_\bullet\rangle}(\bar\chi^{\{(1,4;a)\}})=&
t^0(s_{(4)}+3s_{(3,1)}+2s_{(2,2)}+3s_{(2,1,1)}+s_{(1,1,1,1)})\\
&+t^1 12(s_{(3,1)}+s_{(2,2)}+2s_{(2,1,1)}+1s_{(1,1,1,1)})\\
&+t^2 12(s_{(3,1)}+2s_{(2,2)}+6s_{(2,1,1)}+5s_{(1,1,1,1)})\\
&+t^3 4(s_{(3,1)}+5s_{(2,2)}+23s_{(2,1,1)}+38s_{(1,1,1,1)})\\
&+t^4 6(s_{(2,2)}+9s_{(2,1,1)}+31s_{(1,1,1,1)})\\
&+t^5 12 (s_{(2,1,1)}+9s_{(1,1,1,1)})+t^6 24 s_{(1,1,1,1)}.
\end{align*}
In fact, the constant term is a familiar module.
\begin{proposition}
For $\lambda\in \cP_n(2)$ non-nesting,
\[
\lim_{t\rightarrow 0}\ch_{\mathds{1}_\bullet\rangle}(\bar\chi^\lambda)=h_{(1^n)},
\]	
or the symmetric function corresponding to the regular character of $S_n$.
\end{proposition}





\subsection{The function $\ch_{\mathds{1}_\bullet\rangle}^*$}

In this section, we investigate the dual map $\ch_{\mathds{1}_\bullet\rangle}^*:\Sym\rightarrow \cf(\UT_\bullet)^*$, given by
\[
\langle \ch_{\mathds{1}_\bullet\rangle}^*(f(\underline{X})),\gamma\rangle=\langle f(\underline{X}), \ch_{\mathds{1}_\bullet\rangle}(\gamma)\rangle.
\]

The previous section allows us to quickly compute the image of $h_n$ by duality.
\begin{proposition} \label{hnimage}
For $n\in \ZZ_{\geq 0}$,
\[
\ch_{\mathds{1}_\bullet\rangle}^*(h_n)=\mathds{1}_{\UT_n}.
\]	
\end{proposition}


Note that the codomain is in fact the dual to $\cf(\UT_\bullet)$, so has product given by
\[
\gamma_m\cdot \varphi_n=\sum_{\underline{A}=(A_1,A_2)\vDash m+n\atop |A_1|=m,|A_2|=n}\Ind_{\UT_{\underline{A}}}^{\UT_{m+n}}(\gamma_m\otimes \varphi_n)\quad \text{for $\gamma_m\in \cf(\UT_m)^*$, $\varphi_n\in \cf(\UT_n)^*$.}\]


\begin{remark}
Here we note that while $\scf(\UT_\bullet)\subseteq \cf(\UT_\bullet)$ as Hopf algebras, the same does not hold for the dual spaces, as we instead obtain quotient Hopf algebras.  While the coproduct is defined in the same way for both dual spaces, the product will use different adjoint functors to restriction in each case.  In this paper we are therefore using the dual of $\cf(\UT_\bullet)$, since it preserves modules unlike the variant of induction used in the dual to $\scf(\UT_\bullet)$.  However, it is worth noting that Proposition \ref{hnimage} holds for the dual of $\scf(\UT_\bullet)$ as well.
\end{remark}

By Proposition \ref{hnimage} and because $\ch_{\mathds{1}_\bullet\rangle}^* $ is a Hopf algebra morphism, for any integer partition $\lambda\vdash n$ of length $k$,
\[
\ch_{\mathds{1}_\bullet\rangle}^*(h_\lambda)=\sum_{\underline{A}=(A_1,\ldots,A_k)\vDash \{1,2,\ldots,n\}\atop |A_j|=\lambda_j}\Ind_{\UT_{\underline{A}}}^{\UT_n}(\mathds{1}).
\]
In particular, we get that the permutation module $\Ind_{S_\lambda}^{S_n}(\mathds{1})$ gets sent to a $\UT_n$-module.

If we add the Jacobi--Trudi formula we obtain that for an integer partition $\lambda\vdash n$ of length $k$,
\begin{equation}
\ch_{\mathds{1}_\bullet\rangle}^*(s_\lambda)=\sum_{w\in S_k}(-1)^{\ell(w)} \sum_{\underline{A}=(A_1,A_2,\ldots,A_k)\vDash \{1,2,\ldots,n\}\atop |A_j|=\lambda_{w(j)}-w(j)+j}	 \Ind_{\UT_{\underline{A}}}^{\UT_n}(\mathds{1}).
\end{equation}
In particular, it is evident that $\ch_{\mathds{1}_\bullet\rangle}^*(s_\lambda)$ will be a virtual character.


A particular case of interest is the sign character or $e_n$.

\begin{lemma} For $n\in \ZZ_{\geq 0}$
\[
e_n=\sum_{\mu\vDash n} (-1)^{n-\ell(\mu)} h_\mu.
\]	
\end{lemma}

We conclude with the following intriguing consequence concerning the antipode $S^*$ of the dual Hopf algebra $\cf(\UT_\bullet)^*$.

\begin{corollary}
	For $n\in \ZZ_{\geq 0}$,
	\[
	\ch_{\mathds{1}_\bullet\rangle}^*(e_n)=(-1)^nS^*(\mathds{1}_n).
	\]
\end{corollary}

\begin{remark}
Note that if one could show that $\ch_{\mathds{1}_\bullet\rangle}^*(e_n)$ is a character, then this would imply that $\ch_{\mathds{1}_\bullet\rangle}(\chi)$ is $e$-positive for all $\chi \in \Irr(\UT_n)$. 
\end{remark}
















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


\textsc{Perhaps do partitions and non-nestings?}

\[
\scf(\UT_\bullet)=\bigoplus_{n\in \ZZ_{\geq 0}} \scf(\UT_n),
\]
where
\[
\scf(\UT_n)=\{\psi:\UT_n\rightarrow \CC\mid \psi(a(u-1)b+1)=\psi(u), a,b,u\in \UT_n\}.
\]
An \emph{$\FF_q^\times$-set partition} of $\{1,2,\ldots,n\}$ is a subset
\[
\lambda\subseteq \{(i,j,a)\mid 1\leq i<j\leq n, a\in \FF_q^\times\}
\] 
such that if $(i,k,a),(j,l,b)\in \lambda$, then $i=j$ or $k=l$ implies $(i,k,a)=(j,l,b)$. We let 
\[
\cP_n(q)=\{\text{$\FF_q^\times$-set partitions of $\{1,2,\ldots, n\}$}\}.
\]
We have a functions to more traditional set partitions
\[
\begin{array}{rccc}
	\setpartition_q: & \cP_n(q) & \longrightarrow & \left\{\begin{array}{c} \text{set partitions}\\ \text{of $\{1,2,\ldots,n\}$}\end{array}\right\}\\
	& \{(i,j,a)\in \lambda\} & \mapsto & \begin{array}{c}\text{blocks are connected components of}\\ \text{graph with edges $(i,j)$ for $(i,j,a)\in \lambda$,}\end{array} 
\end{array}
\]
which is a bijection when $q=2$.  For any subset $A\subseteq  \{(i,j,a)\mid 1\leq i<j\leq n, a\in \FF_q^\times\}$, define
\[
\shape(A)=\setpartition_2^{-1}\left(\begin{array}{c}\text{blocks are connected components of}\\ \text{graph with edges $(i,j)$ for $(i,j,a)\in A$}\end{array} \right)
\]
For example,
\[\shape\left(
\begin{tikzpicture}[scale=.5,baseline=.2cm]
\foreach \x in {1,2,...,9}
	{\node (\x) at (\x,0)[inner sep = -1pt] {$\bullet$};
	\node at (\x,-.35cm) {$\scs \x$};}
\foreach \x/\y/\z in {1/3/a,2/8/b,1/5/c,7/9/d,7/8/e}
	\draw (\x) to [out=70, in=110] node [above] {$\scscs\z$} (\y);
\end{tikzpicture}\right)= \begin{tikzpicture}[scale=.5,baseline=.2cm]
\foreach \x in {1,2,...,9}
	{\node (\x) at (\x,0)[inner sep = -1pt] {$\bullet$};
	\node at (\x,-.35cm) {$\scs \x$};}
\foreach \x/\y/\z in {1/3/1,2/7/1,3/5/1,8/9/1,7/8/1}
	\draw (\x) to [out=70, in=110] node [above] {$\scscs\z$} (\y);
\end{tikzpicture},
\]
and on any element in $\cP_n(q)$ the shape is just the same set of elements with all the labels set to 1.


Given $\lambda\in \cP_n(q)$, define $u_\lambda\in \UT_n$ by
\[
(u_\lambda)_{ij}=\left\{\begin{array}{ll}
1 & \text{if $i=j$,}\\
a & \text{if $(i,j,a)\in \lambda$},\\
0 & \text{otherwise.}	
\end{array}
\right.
\]
We say a matrix $u\in \UT_n$ has \emph{type} $\lambda$ if there exist $a,b\in \UT_n$ such that
\[
u_\lambda=a(u-1)b+1.
\]
Then the space $\scf(\UT_n)$ has basis
\[
\{\delta_\lambda\mid  \lambda\in \cP_n(q)\}\quad \text{where}\quad \delta_\lambda(u)=\left\{\begin{array}{ll}
	1 & \text{if $u$ has type $\lambda$}\\
	0 & \text{otherwise.}
\end{array}
\right.
\]
In particular, $\dim(\scf(\UT_n))=|\cP_n(q)|$.
