==== TABLE OF CONTENTS ====
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//01-introduction.tex
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//02-graphs.tex
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//03-reordering.tex
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//04-walls.tex
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//05-triangle.tex
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//06-witness.tex
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//07-completion.tex
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//paper.tex
Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//references.bib
===========================
==== BEGIN Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//01-introduction.tex ====
\section{Introduction}
\label{main:introduction}
Let $h=(h(1),\ldots,h(n))$ be a weakly increasing integer sequence with
$i\le h(i)\le n$. The associated \emph{natural unit interval graph} has
vertex set $[n]=\{1,\ldots,n\}$ and edges
\[
E(G)=\bigl\{\{i,j\}:i0}$ that has distinct values on adjacent vertices. In the
variable alphabet $X=(x_1,x_2,\ldots)$ put
\begin{equation}
\chi_G(X;q)=\sum_{f\text{ proper}}
q^{\operatorname{asc}_G(f)}\prod_{a=1}^n x_{f(a)},
\qquad
\operatorname{asc}_G(f)=
\#\{\{a,b\}\in E(G):a\sigma_{i+1}\Longrightarrow
\{\sigma_i,\sigma_{i+1}\}\in E(G)\},\\
\ginv_G(\sigma)&=\#\{(i,j):i\sigma_j,
\{\sigma_i,\sigma_j\}\in E(G)\}.
\end{align*}
Thus $D_G^0$ forbids adjacent descents between nonneighbors, and
$\ginv_G$ counts only inversions supported on edges.
\begin{theorem}[Elementary positivity and a permutation witness]
\label{main:theorem}
There is a deterministic terminating procedure which, given a natural
unit interval graph $G$ on $[n]$ and $\sigma\in D_G^0$, returns a partition
$\theta_G(\sigma)\vdash n$ such that
\begin{equation}
\chi_G(X;q)=\sum_{\sigma\in D_G^0}
q^{\ginv_G(\sigma)}e_{\theta_G(\sigma)}(X).
\label{main:witness}
\end{equation}
In particular every elementary coefficient of $\chi_G(X;q)$ belongs to
$\N[q]$. The assertion holds as a formal symmetric-function identity,
uniformly in $n$ and $G$.
\end{theorem}
This proves the elementary-positivity part of the Shareshian--Wachs
conjecture. The theorem makes no assertion of elementary unimodality.
The construction specifies a map on individual inputs: it does not take
the elementary coefficient list as input and redistribute permutations
according to that list. Its running time may nevertheless be large.
For example, let $G$ be the path $1$--$2$--$3$. Its expansion is
\begin{equation}
\chi_G(X;q)=q\,e_{(2,1)}(X)+(1+q+q^2)e_{(3)}(X).
\label{main:path-example}
\end{equation}
Write $m_\lambda$ for the sum of the distinct monomials with exponent
multiset $\lambda$. To check this directly, the colorings with a repeated color contribute
$q\,m_{(2,1)}(X)$, while those with three distinct colors contribute
$(1+4q+q^2)m_{(1,1,1)}(X)$. Now use
$e_{(2,1)}=m_{(2,1)}+3m_{(1,1,1)}$ and
$e_{(3)}=m_{(1,1,1)}$.
The domain $D_G^0$ consists of $123,132,213,321$, with graph-inversion
degrees $0,1,1,2$. The theorem assigns one of the two degree-one
permutations to $(2,1)$ and the other three permutations to $(3)$.
Thus the map refines the degree count by an entire elementary partition.
Equation~\eqref{main:path-example} alone does not specify which of
$132$ and $213$ receives which partition; the procedure in
Section~\ref{route:section} makes that individual choice.
The positivity question is difficult because the coloring definition
already has nonnegative coefficients in the monomial variables, whereas
rewriting it in the elementary basis can involve subtraction. Our proof
separates this issue from the individual assignment. It first identifies
each relevant elementary coefficient with a positive algebraic object.
It then realizes the algebraic identities by finite bijections between
ordered collections of independent sets. Neither stage uses the sought elementary
coefficient list as input to the permutation rule.
\subsection{History and significance}
The problem grew out of positivity questions for immanants of
Jacobi--Trudi matrices, studied by Haiman and by Stanley and Stembridge
\cite{Hai93,SS93}. Stanley introduced the chromatic symmetric function
as a symmetric-function refinement of the chromatic polynomial
\cite{Sta95}; it is the specialization of
Equation~\eqref{main:csf} at $q=1$. In this language, the
Stanley--Stembridge conjecture asks for elementary positivity of the
incomparability graphs of $(3+1)$-free posets
\cite[Conjecture~5.5]{SS93}. The incomparability graph joins two
elements exactly when neither is below the other. A poset is
$(3+1)$-free if it has no induced three-element chain together with
an element incomparable to that chain.
Guay-Paquet's reduction expresses its chromatic symmetric function as
a nonnegative rational combination of those of unit interval orders
\cite[Theorem~5.1]{GP13}. Their naturally labeled incomparability
graphs are the graphs in Theorem~\ref{main:theorem}. Specializing our
theorem at $q=1$ therefore also proves the classical positivity
theorem, previously established by Hikita \cite{Hik24}.
Positive expansions in other bases provided important earlier
structure. Haiman's immanant results imply Schur positivity for
incomparability graphs of $(3+1)$-free posets \cite{Hai93}; Gasharov
gave a positive formula using poset tableaux \cite{Gas96}. Chow's
quasisymmetric expansion related chromatic symmetric functions to
permutation descents \cite{Cho99}. Shareshian and Wachs introduced the
$q$-refinement in Equation~\eqref{main:csf}, proved its symmetry and
Schur positivity for natural unit interval graphs, and formulated the
elementary-positivity and elementary-unimodality conjecture
\cite{SW12,SW16}. Their acyclic-orientation formula gives elementary
coefficients after grouping partitions by their number of parts
\cite[Theorem~5.3]{SW16}; Athanasiadis supplied a power-sum expansion
\cite{Ath15}. These descriptions do not determine a nonnegative
coefficient formula for each elementary partition.
The geometric connection gives another reason to study the
$q$-grading. Tymoczko constructed permutation actions on equivariant
cohomology \cite{Tym08}, and Shareshian and Wachs related their
chromatic functions conjecturally to the graded representation on
regular semisimple Hessenberg varieties \cite{SW12,SW16}.
Brosnan--Chow and Guay-Paquet proved this representation-theoretic
identity \cite{BC18,GP16}. That result is distinct from the
elementary-positivity assertion addressed here. Geometric,
combinatorial and algebraic approaches subsequently established
positivity for substantial families: abelian Hessenberg varieties
\cite{HP19}, classes treated by explicit elementary expansions
\cite{CH19}, melting lollipops \cite{HNY20}, and the $q$-rook
formulas for abelian Dyck paths \cite{CMP23}. The modular law also
provided a systematic tool for organizing chromatic functions and
their relations \cite{AN21}.
Hikita's proof uses a probabilistic formula \cite{Hik24}. His formula gives numerical
nonnegativity for every positive real $q$, while its rational
$q$-weights do not establish coefficientwise nonnegativity in $\N[q]$;
the refined conjecture remains explicitly distinguished in
\cite[Section~1.3]{Hik24}. Griffin, Mellit, Romero, Weigl and Wen gave
an independent proof through Macdonald expansions, recovering Hikita's
elementary formula \cite{GMRWW25}. Further developments include
positivity at $q=1$ of the Abreu--Nigro $g$-functions, proved by
Huh, Hwang, Kim, Kim and Oh as a refinement of Hikita's theorem
\cite{HHKKO25},
Chow's combinatorial interpretation of the probabilities \cite{Chow26},
and lower bounds for elementary coefficients studied by Siegl
\cite{Siegl26}. Theorem~\ref{main:theorem} gives a formal polynomial
formula with nonnegative integer coefficients and an individual
assignment preserving the specified graph-inversion weight.
The representation identity and Theorem~\ref{main:theorem} give the
following degreewise consequence.
\begin{corollary}[Young permutation modules in Hessenberg cohomology]
\label{main:hessenberg}
Let $n\ge1$, let $h$ be as above with graph $G=G(h)$, and let
$S\in M_n(\C)$ be regular semisimple. Write
\[
\operatorname{Hess}(S,h)=
\{F_\bullet\in\operatorname{Flag}(\C^n):
SF_i\subseteq F_{h(i)}\text{ for all }i\}.
\]
For $\lambda=(\lambda_1,\ldots,\lambda_\ell)\vdash n$, let
$M^\lambda=\operatorname{Ind}_{S_\lambda}^{S_n}\mathbf{1}_{\C}$ be the
Young permutation module, where
$S_\lambda=S_{\lambda_1}\times\cdots\times S_{\lambda_\ell}$ is the
standard Young subgroup, and put
\[
m_{\lambda,d}(h)=
\#\{\sigma\in D_G^0:\theta_G(\sigma)=\lambda,\ \ginv_G(\sigma)=d\}.
\]
Then for every integer $d\ge0$, under Tymoczko's dot action on ordinary
cohomology there is an abstract $\C[S_n]$-module isomorphism
\[
H^{2d}(\operatorname{Hess}(S,h);\C)
\cong\bigoplus_{\lambda\vdash n}(M^\lambda)^{\oplus m_{\lambda,d}(h)}.
\]
\end{corollary}
\begin{proof}
Write $\operatorname{ch}$ for the Frobenius characteristic and $\omega$
for the usual symmetric-function involution, so
$\omega(e_\lambda)=h_\lambda$, the product of complete homogeneous
symmetric functions. The identity of Brosnan--Chow
\cite[Theorem~129]{BC18} and Guay-Paquet \cite{GP16}, followed by
Equation~\eqref{main:witness}, gives
\[
\operatorname{ch}H^{2d}(\operatorname{Hess}(S,h);\C)
=[q^d]\,\omega\chi_G(X;q)
=\sum_{\lambda\vdash n}m_{\lambda,d}(h)h_\lambda.
\]
Since $\operatorname{ch}M^\lambda=h_\lambda$
\cite[proof of Proposition~10]{BC18}, injectivity of the Frobenius
characteristic and complete reducibility of finite-dimensional complex
$S_n$-modules give the isomorphism.
The argument supplies no preferred isomorphism, geometric basis, or
compatibility with cup product.
\end{proof}
There is also a direct precedent for asking for a partition-valued
permutation rule. Stanley and Stembridge proposed such an assignment
on their compatible permutations \cite[Remark~5.6]{SS93}. That proposal
concerns the ungraded elementary expansion. The rule here retains the
full graph-inversion degree and specifies a terminating procedure on
each input. The finite cancellation used to pass from required
ascents to exact ascents belongs to the bijective-cancellation
tradition represented by the Garsia--Milne involution principle
\cite{GM81}.
Our algebraic reduction likewise has substantial antecedents.
Stanley's graph specialization \cite[Section~2]{Sta98}, chromatic functions in
noncommuting variables \cite{GS01}, and the noncommutative
symmetric-function methods of Fomin--Greene and Blasiak--Fomin
\cite{FG98,BF17} provide a framework for commuting symmetric expressions
inside a noncommutative algebra. Hwang's noncommutative
$P$-symmetric functions \cite{Hwa24} and the poset algebras of Blasiak,
Eriksson, Pylyavskyy and Siegl \cite{BEPS25} provide direct predecessors
of the graph-alphabet evaluation and its elementary/monomial
coefficient pairing. We give a short proof in the centered quantum
torus conventions needed for the subsequent argument.
The positive factorization and transport stages use the mathematical
framework of Hall algebras and scattering diagrams. Ordered slope
factorization and polynomial shuffle products were developed in
\cite{Rei03,KS11}, with semistable quotient and integrality results in
\cite{Ef12,FR18,DMe20}. The connection from Hall factorization to
wall transformations appears in Reineke's Poisson automorphisms and
Bridgeland's stability scattering diagrams \cite{Rei10,Bri17}.
Scattering constructions originate in work of Kontsevich--Soibelman
and Gross--Siebert \cite{KS06,GS11,KS14}; theta bases and mutation are
central to the cluster framework of Gross--Hacking--Keel--Kontsevich
\cite{GHKK18}, and Davison--Mandel prove strong quantum positivity
\cite{DM21}. We prove the particular reordering, completion and
transport statements needed here with their explicit gradings and
finite coefficient bounds. The graph-specific step is then an
identification: general positivity of theta sections does not itself
show that a graph-alphabet monomial symmetric function is one such
section. The triangular chart below proves that identity before the
packet construction extracts the individual witness.
\subsection{Proof structure}
The first reduction replaces colorings by coefficients in an algebra
whose monomials record vertex multiplicities. Write $q=v^2$ and let
$X_m$ denote the basis monomial indexed by a vertex-multiplicity
vector $m$. Multiplication of these monomials is
twisted by an alternating form recording ordered edges. For a larger unit
interval graph $\Gamma$ containing $G$, let $E_k$ be the sum of the
monomials of independent $k$-sets. We prove that the $E_k$ commute, so
they may be evaluated as elementary symmetric functions $e_k(Y)$ of a
formal alphabet $Y$. If $u$ is the sum of the original vertex exponents
and $M=|E(G)|$, the elementary coefficient becomes
\begin{equation}
[e_\lambda(X)]\chi_G(X;v^2)
=v^M[X_u]m_\lambda(Y).
\label{main:reduction}
\end{equation}
Here $m_\lambda$ is the monomial symmetric function. The identity is
proved in Proposition~\ref{graph:kernel}.
The central step is to identify $m_\lambda(Y)$ as a chamber value of a
single positive section of a system of wall transformations. A wall is
a portion of a hyperplane in the real dual of the exponent lattice,
equipped with conjugation by a formal series. A section is a family of
chamber values related by these transformations. We construct sections $\Theta_m$,
indexed by lattice exponents, by prescribing their coefficients in test
directions determined by the alternating form. The auxiliary graph is
arranged in a triangle with distinguished independent vertices
$d_1,\ldots,d_D$, called anchors. For a partition $\lambda$ of length
at most $D$, padded by zeroes to length $D$, the essential identification in the all-negative chamber is
\begin{equation}
m_\lambda(Y)=\Theta_{\lambda_1d_1+\cdots+\lambda_Dd_D}.
\label{main:identification}
\end{equation}
Repeated interval rotations establish this identity. A support argument
using positive powers of $E_1$ is essential: stationarity under the
rotations alone does not force an exponent to involve anchors only.
The proof has three main components. First, positive quantum factors
remain positive when their order is reversed. We realize the new
multiplicities as dimensions of explicit graded vector spaces, and
prove the coefficient bounds needed for all infinite series.
Second, the interval rotations identify a family of graph symmetric
functions with single positive theta sections. Together with
Equation~\eqref{main:reduction}, this already proves coefficientwise
elementary positivity. Third, we extract the individual assignment.
After reversing an input permutation, we group vertices into packets,
each an independent set written in increasing order. A local packet
bijection transports them to subsets of the independent anchors and
records weighted jumps. The total jump histories are independent of
packet sizes. Finite matching cancellation refines required nonedge
ascents of input words and required strict ascents of anchor words to
exact sets of such positions. The empty set on the anchor side leaves
a weakly decreasing word, whose multiplicities give the output partition. The finite
matching argument supplies termination without consulting the desired
final shape counts.
Section~\ref{graph:section} proves the coloring reduction and fixes
permutation conventions. Section~\ref{alg:section} proves the
reordering result. Section~\ref{wall:section} constructs the wall
sections and proves their positivity and mutation rules.
Section~\ref{tri:section} establishes
Equation~\eqref{main:identification}, and
Section~\ref{route:section} constructs the individual permutation map.
Section~\ref{main:completion} returns to the original graph and proves
Theorem~\ref{main:theorem}, including the reversal needed for the
convention in $D_G^0$.
==== END Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//01-introduction.tex ====
==== BEGIN Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//02-graphs.tex ====
\section{Graph alphabets and the coloring reduction}
\label{graph:section}
This section reduces the elementary expansion to coefficients of
monomial symmetric functions evaluated in a quantum torus. It also
fixes the permutation convention used by the transport construction.
\subsection{Admissible words and insertion digits}
For the graph $G$ in the introduction put
$l_a=\#\{bc$, so the newly consecutive pair $(b,c)$ is allowed.
The cases without a predecessor or successor are immediate. Conversely,
$a$ can be inserted at the beginning or immediately after any earlier
neighbor, and these are exactly the allowed positions. At such a
position the new inversions are the earlier neighbors lying to its
right. Reading those neighbors in their order in the shorter word
shows that the available counts are $l_a,l_a-1,\ldots,0$, each once.
Successive insertion and deletion prove the bijection and degree
formula. Reversal exchanges nonedge descents and nonedge ascents and
reverses the order of the endpoints of every edge, proving
Equation~\eqref{graph:reverse}.
\end{proof}
The relation $aD$.
We denote its value on a symmetric polynomial $F$ by $F(Y)$, and
write $e_k(Y)=E_k$. The symbol $Y$ denotes this evaluation; no
individual roots $y_i$ in the quantum torus are being asserted.
In particular, $m_\lambda(Y)$ is well defined for partitions of length
at most $D$, where $m_\lambda$ is the sum of distinct monomials with
exponent multiset $\lambda$.
\subsection{The elementary coefficient identity}
Let $G$ be the induced ordered graph on distinct vertices
$a_1,\ldots,a_n$ of $\Gamma$, and put $u=a_1+\cdots+a_n$.
For a proper coloring $f$ define
$\operatorname{inv}_G(f)=\#\{af(b)\}$
and let $X_G(X;q)$ be the corresponding proper-color inversion
generating function.
The following coefficient reduction is the elementary/monomial form
of the noncommutative Cauchy pairing in
\cite[Theorem~4.4, Corollary~4.5 and Proposition~4.25]{Hwa24} and
\cite[Proposition~2.9 and Corollary~2.10]{BEPS25}. We include its
proof to fix the graph-inversion and centered-monomial factors.
\begin{proposition}[Coloring kernel]
\label{graph:kernel}
If $\alpha(\Gamma)\le D$, then $X_G(X;q)$ is symmetric and
\begin{equation}
X_G(X;v^2)=\sum_{\substack{\lambda\vdash n\\\ell(\lambda)\le D}}
v^M[X_u]m_\lambda(Y)\,e_\lambda(X).
\label{graph:coefficient}
\end{equation}
The equality is independent of the extra vertices of $\Gamma$.
\end{proposition}
\begin{proof}
Work first with $r$ colors. Expand the product, in increasing color
order,
\[
\prod_{c=1}^r\left(\sum_{k=0}^D x_c^k E_k\right).
\]
Its $X_u$ coefficient chooses a disjoint independent set for each
color, covering precisely the original vertices. Extra vertices
cannot occur because each exponent in each factor has nonnegative
vertex coordinates. These choices are exactly the proper colorings.
An edge whose later vertex has smaller color contributes $+1$ to the
torus exponent, and an edge whose earlier vertex has smaller color
contributes $-1$. The total exponent is
$2\operatorname{inv}_G(f)-M$. Hence multiplying this coefficient by
$v^M$ gives $X_G(x_1,\ldots,x_r;v^2)$.
For ordinary variables $y_1,\ldots,y_D$ the elementary dual kernel
identity is
\[
\prod_{c=1}^r\prod_{i=1}^D(1+x_cy_i)
=\sum_\lambda e_\lambda(x_1,\ldots,x_r)m_\lambda(y_1,\ldots,y_D).
\]
Indeed, select for each labeled $y_i$ a subset of the $x$ variables;
grouping its subset sizes by their multiset gives the displayed sum.
Evaluate the symmetric $y$ polynomials at $Y$, extract $X_u$, and
multiply by $v^M$. This proves Equation~\eqref{graph:coefficient} for
every $r$, and therefore as a symmetric-function identity. The
coloring interpretation proves independence of the ambient graph.
\end{proof}
\begin{example}[The centered normalization on two vertices]
Let $\Gamma=G$ have ordered vertices $a0$ whenever the ray of $p_i$ precedes the
distinct ray of $p_j$. Its factorization in the opposite ray order is
again a product of elementary units, with nonnegative integral
multiplicities. The output list is admissible.
Every coefficient at fixed exponent and fixed $v$-degree is a finite
sum of nonnegative integers, and each exponent has bounded upper
$v$-degree. The assertion also holds modulo any fixed charge cutoff.
For the algorithmic assertion, assume that lattice operations, the form
$\Omega$ and the charge are effectively computable, that input occurrences
at bounded charge and above a given parameter threshold can be listed
effectively, and that for every $B$ one can compute an integer $A_B\ge1$
such that
\[
|\Omega(p,q)|\le A_B
\qquad\text{whenever }p,q\in C,\quad c(p),c(q)\le B.
\]
Then every prescribed coefficient and every bounded part of the output
unit list can be calculated by finite rational linear algebra.
\end{theorem}
We first decompose shuffle spaces by slope and use separated-center
restrictions to construct a coproduct on an auxiliary associated graded
space. Polynomiality of the restriction symbols removes negative
separation powers before evaluation at zero. A signed vector-space PBW
decomposition and primitive strings then give the positive elementary
factors. Throughout, polynomial degree with its shifts records powers of
$v$; the final energy bounds control infinite input lists.
A ray factorization with constant term one exists uniquely over
$\Q((v^{-1}))$: at charge $B$, subtract the contributions already
determined at smaller charges, and assign the remaining coefficient of
$X_p$ to the ray of $p$. Products involving that new coefficient and a
nonconstant term have larger charge. We shall prove that, in the order
specified in Theorem~\ref{alg:reordering}, each resulting ray factor
has the stronger form asserted there.
\subsection{Shuffle spaces and destabilizing quotients}
Begin with finitely many input occurrences, indexed by $1,\ldots,t$ in
input ray order. Units on one ray may be ordered arbitrarily. Set
$a_{ii}=0$ for $E_{p_i,k_i}$ and $a_{ii}=1$ for $H_{p_i,k_i}$. For
$i\ne j$, put
\[
a_{ji}=\max\{\Omega(p_i,p_j),0\}.
\]
For dimension vectors $d,e\in\N^t$, define
\begin{align}
p(d)&=\sum_i d_ip_i,&
\chi(d,e)&=\sum_i d_ie_i-\sum_{i,j}a_{ij}d_ie_j,
\label{alg:euler}\\
s(d)&=\tfrac12\chi(d,d),&
u(d)&=\sum_i d_i(k_i+1-a_{ii}).
\label{alg:shifts}
\end{align}
Then
\begin{equation}\label{alg:skew}
\chi(d,e)-\chi(e,d)=\Omega(p(d),p(e)).
\end{equation}
Choose a linear functional $\eta$ on the plane so that
$\mu(d)=\eta(p(d))/c(p(d))$ increases in input ray order.
This is possible by intersecting the strictly convex cone with
$c=1$. Dimension vectors of a common slope have symmetric pairings
under $\chi$. We use $|d|_1=\sum_i d_i$ only to count variables and to
perform inductions; it is different from charge.
Let
\[
S_d=\Q[x_{i,\alpha}:1\le i\le t,\ 1\le\alpha\le d_i]
^{\prod_i\mathfrak S_{d_i}},\qquad S_0=\Q,
\]
with every variable of polynomial degree one. Variables with a fixed
$i$ form a pack. The polynomial shuffle presentation is the cohomological Hall product
of Kontsevich--Soibelman \cite[Section~2.4, Theorem~2]{KS11}; see also
\cite[Theorem~2.2]{Ef12}. In our normalization it is
\begin{equation}\label{alg:shuffle}
f*g=\sum_{\text{pack shuffles}}f(x)g(y)K_{d,e}(x,y),\qquad
K_{d,e}(x,y)=
\prod_{i,j}\prod_{\alpha\le d_i,\,\beta\le e_j}
(y_{j,\beta}-x_{i,\alpha})^{a_{ij}-\boldsymbol1_{i=j}}.
\end{equation}
Each shuffle chooses, in each output pack, the variables assigned to
the first input; there is no factorial normalization. The only
possible poles are simple poles between two variables of the same
output pack. Interchanging those two variables pairs the residues
with opposite signs. After taking a common denominator, the
numerator is therefore divisible by every such difference. The
differences are relatively prime irreducible polynomials, so all poles
cancel. Consequently $f*g\in S_{d+e}$. A simultaneous shuffle of
three input groups proves associativity: each pair of groups
contributes exactly one kernel in either parenthesization. Polynomial
degree changes by $-\chi(d,e)$.
The destabilizing quotient below is the polynomial form of the
semistable restriction quotient in \cite[Theorem~8.1]{FR18}. We
establish its needed properties directly for our charge-weighted slope.
For $d\ne0$, put
\begin{equation}\label{alg:quotient}
I_d=\sum_{\substack{a+b=d,\ a,b\ne0\\\mu(a)>\mu(d)}}S_a*S_b,
\qquad B_d=S_d/I_d,
\qquad B_0=\Q.
\end{equation}
Every image $S_a*S_b$ is an ordinary $S_d$-submodule. Indeed an
output symmetric polynomial, restricted to the two input packs, is a
finite sum of polynomial tensors; multiplication by it can be moved
inside the shuffle. Thus $I_d$ is an ordinary homogeneous ideal.
The product descends to $B_d\otimes B_e\to B_{d+e}$ when
$\mu(d)=\mu(e)=\theta$. If $a+b=d$ and $\mu(a)>\theta$, a term
$(S_a*S_b)*S_e$ has the same destabilizing first group $a$. If
$a+b=e$ and $\mu(a)>\theta$, a term
$S_d*(S_a*S_b)=(S_d*S_a)*S_b$ has destabilizing first group $d+a$.
This proves descent in both arguments. Give $B_d$ shifted degree
\begin{equation}\label{alg:shifted-degree}
\deg_{\mathrm{sh}}f=\deg_{\mathrm{pol}}f+s(d).
\end{equation}
On a common slope,
$s(d+e)=s(d)+s(e)+\chi(d,e)$, so the descended product preserves the
sum of shifted degrees.
\subsection{Separated centers and ordered decomposition}
We record carefully the restriction operation used throughout the
proof. For an ordered list $P=(r_1,\ldots,r_m)$ of nonzero dimension
vectors summing to $d$, divide each pack of $d$ into labeled groups
with multiplicities $r_\ell$, replace the variables in group $\ell$
by $x^\ell+z_\ell$, and reduce modulo $I_{r_\ell}$ in every group.
This defines
\begin{equation}\label{alg:restriction-S}
\widetilde R_P^z:S_d\longrightarrow
\left(\bigotimes_{\ell=1}^m B_{r_\ell}\right)
[z_1,\ldots,z_m].
\end{equation}
The choices inside a pack do not matter because its input is
symmetric. Common translation preserves $I_d$: all kernels in
Equation~\eqref{alg:shuffle} depend on differences. Hence translation
also defines an automorphism of $B_d[z]$.
Here is the useful way to apply Equation~\eqref{alg:restriction-S} to
a shuffle expression. Split each source group into subgroups assigned
to the target groups. At distinct centers expand the kernels between
different targets in their internal variables, over
$\Q(z_1,\ldots,z_m)$. Each coefficient is separately symmetric in
the source subgroups and is a finite sum of polynomial tensors.
The kernels within one target are left unexpanded and give its
ordinary shuffle product. If a prefix of the source groups has
dimension $b$ inside a target of dimension $r$, with
$\mu(b)>\mu(r)$, that target contribution is in $I_r$ by
associativity and vanishes. All these operations are legitimate in
the product of homogeneous internal-degree spaces. Vanishing of the
Taylor expansion implies vanishing of the original polynomial
restriction, since its target ideals are homogeneous and extension of
scalars to $\Q(z_1,\ldots,z_m)$ is injective.
The slope ordering follows the Harder--Narasimhan factorization
formalism \cite[Propositions~4.8 and 4.12]{Rei03},
\cite[Sections~5.2--5.3]{KS11}. Ordered multiplication of semistable
pieces is established in \cite[Theorem~6.2]{FR18}; the next argument
proves the required decomposition for the explicit quotients above.
Here the locator for \cite{FR18} refers to its published version.
\begin{lemma}[Ordered decomposition]\label{alg:ordered}
Choose graded vector-space sections $B_d\to S_d$ of all quotient
maps. For every $d$, multiplication induces a vector-space
isomorphism
\begin{equation}\label{alg:ordered-sum}
S_d\cong
\bigoplus_{\substack{d^{(1)}+\cdots+d^{(m)}=d\\
\mu(d^{(1)})>\cdots>\mu(d^{(m)})}}
B_{d^{(1)}}\otimes\cdots\otimes B_{d^{(m)}},
\end{equation}
with the polynomial-degree shifts prescribed by the shuffle kernels.
\end{lemma}
\begin{proof}
Induct on $|d|_1$. Modulo the chosen lift of $B_d$, every element is a
sum of destabilizing products. Expand their two factors by induction.
Draw a polygon for a resulting list by joining the successive points
\[
\left(c(p(d^{(1)}+\cdots+d^{(j)})),
\eta(p(d^{(1)}+\cdots+d^{(j)}))\right).
\]
The original destabilizing cut lies strictly above the chord joining
the endpoints. If adjacent slopes are nondecreasing, merge those two
factors and apply the induction hypothesis to their product. Their
total dimension is smaller than $d$: a list of only two such factors
could not have a destabilizing cut. The replacement polygons are
concave and lie above the chord of the merged pair, hence above the
old pair. Equality can occur only for a straight pair, in which case
the number of segments decreases. The polygon remains strictly above
the total chord somewhere. There are only finitely many lists of
nonzero subdimension vectors of $d$, so this process terminates at
strictly decreasing slopes. This proves spanning.
For independence, restrict an ordered product to targets
$r_1,\ldots,r_m$ of strictly decreasing slopes. A surviving split has
no destabilizing source prefix in any target. At a source cut, if
the portion in target $r_j$ has charge $b_j$, its height is at most
$b_j\mu(r_j)$. Among all choices with fixed sum $\sum_jb_j$, this
upper bound is maximized by filling the targets in decreasing slope
order. Thus the source polygon lies below the target polygon at
every source corner, and hence everywhere: the target polygon is
concave. If the polygons coincide, strictness of their slopes forces
equality at each corner. The first target must be completely filled
at the first corner, the first two at the second, and so on.
Consequently the only surviving split assigns whole source groups to
the matching whole targets. In particular the \emph{dimension
vectors}, not only their charges and slopes, must agree.
In a finite relation choose a polygon minimal under pointwise
comparison. Restriction to its dimension-vector list kills every
other list: a surviving source polygon would have to be smaller, or
equal with that same list. For the matching list the restriction is
the tensor of the translated lifts, multiplied by all intergroup
kernels. These kernels are invertible Taylor series at separated
centers. They act on the quotient tensor because they are separately
symmetric in each whole target group. Cancel them. Translation is
an automorphism of each quotient, and the chosen lifts identify with
the quotient vector spaces. Thus the original tensor in that summand
must be zero. Applying this to a minimal nonzero summand contradicts
the proposed relation.
\end{proof}
\begin{lemma}[Restrictions on a slope]\label{alg:restrictions}
If all $r_\ell$ have the slope of $d$,
Equation~\eqref{alg:restriction-S} factors through a map
\begin{equation}\label{alg:restriction}
R_P^z:B_d\longrightarrow
\left(\bigotimes_\ell B_{r_\ell}\right)[z].
\end{equation}
These maps compose under refinement, with the successive centers
added. When a same-slope product is restricted, only splits whose
nonempty subgroups have this slope survive; the restrictions of its
two factors may already be taken in their respective quotients.
\end{lemma}
\begin{proof}
Consider a destabilizing product with first dimension $a$. If every
piece of $a$ in a target had slope at most the common slope, their sum
would too, contrary to $\mu(a)>\mu(d)$. Some target is therefore
destabilized, and the preceding Taylor test kills the term. This
proves descent. Refinement is composition of polynomial substitutions;
the descended maps therefore compose as claimed.
For a product with first total dimension of the common slope, split
that dimension among equal-slope targets. If any nonempty piece is
off the slope, some piece must lie above it, by the weighted-average
identity for slopes. That target is destabilized. In every remaining
split both pieces of a target have the common slope. Internal shuffle
products descend by Equation~\eqref{alg:quotient}; multiplication by
the Taylor coefficients preserves the quotient ideals because they
are ordinary ideals. This justifies taking all input subgroups in
their quotients before the remaining computation.
\end{proof}
\subsection{The Hilbert-series target}
The ordered decomposition gives a formula for each factor in the
reversed ray order. We derive that formula now, so that the remaining
problem is a precise statement about graded dimensions.
The Hilbert series of the ordinary pack-symmetric polynomial space is
\begin{equation}\label{alg:ordinary-hilbert}
\Hilb_{S_d}(t)=\prod_i\prod_{j=1}^{d_i}(1-t^j)^{-1}.
\end{equation}
Indeed monomial orbit sums are indexed by weakly decreasing exponent
lists in each pack, and their successive differences contribute
independent degrees $1,\ldots,d_i$.
The coefficient of $X_{mp}$ in $E_{p,k}$ is the generating series of
$0\le j_1<\cdotsj}\chi(d_i',e_j')}
(*^{\otimes R})
\bigl(L_{(d_i')}(f)\otimes L_{(e_i')}(g)\bigr).
\end{equation}
All nonzero entries in this sum have slope $\theta$; zero entries in
a list of symbols are omitted. The operator $*^{\otimes R}$ places
the two factors belonging to each target group next to each other,
without a sign, and applies its shuffle product.
\end{lemma}
\begin{proof}
Use Lemma~\ref{alg:restrictions} and expand intergroup kernels at
separated centers. Every nonconstant internal Taylor term increases
internal degree. In target $i$, internal shuffling changes
polynomial degree by $-\chi(d_i',e_i')$, exactly compensated by
\[
s(r_i)-s(d_i')-s(e_i')=\chi(d_i',e_i').
\]
This proves the filtration bound. On its leading grade only the
scalar intergroup kernels remain. For $i\ell+\chi(a,b)$.
Apply arbitrary refinements $R=(r_i)$ of $a$ and $S=(s_j)$ of $b$ to
each coefficient. Their centers in the first list are shifted by
$Z$. The internal-degree-zero part of the inverse kernel is
\begin{equation}\label{alg:inverse-scalar}
\prod_{i,j}(z_j^S-z_i^R-Z)^{\chi(r_i,s_j)},
\end{equation}
and all its other internal terms have positive degree. The
restriction of $f$ to the concatenated list has internal shifted
degree at least $w$, by its defining filtration tests. Thus the
refined tests of every $C_j(f)$ have the same lower bound. Tensor
detection in Lemma~\ref{alg:detection} proves
$C_j(f)\in\cF_w(B_a\otimes B_b)$, coefficient by coefficient.
On the weight-$w$ grade only Equation~\eqref{alg:inverse-scalar}
contributes. Multiplying by the two separate symbol prefactors
supplies exactly the missing cross-list factors, so
\begin{equation}\label{alg:polynomial-Z}
(L_R\otimes L_S)
\left(\sum_j[C_j(f)]Z^j\right)
=L_{R,S}([f])(z^R+Z,z^S).
\end{equation}
By Lemma~\ref{alg:detection}, the right side is a polynomial in all
its centers and in $Z$. Consequently every $j<0$ has zero image
under every tensor symbol. The same Lemma implies
$[C_j(f)]=0$ for each $j<0$. This conclusion holds in the actual
associated graded tensor space; it is not a conclusion drawn after
a specialization of a rational kernel.
Equation~\eqref{alg:coefficient-degree} leaves only finitely many
nonnegative $Z$-powers. We may therefore evaluate this finite tensor
polynomial at zero and define
\[
\Delta_{a,b}[f]=[C_0(f)].
\]
Changing $f$ by $\cF_{w+1/2}$ changes every coefficient by that higher
tensor filtration, so the definition is independent of the
representative. Setting $Z=0$ in
Equation~\eqref{alg:polynomial-Z} proves
Equation~\eqref{alg:coproduct-symbol}. Finally the original shifted
degree of $C_0(f)$ is
\[
\ell+\chi(a,b)+s(a)+s(b)=\ell+s(d),
\]
as required.
\end{proof}
Write $\varepsilon(a,b)=(-1)^{\chi(a,b)}$. Symmetry of $\chi$ on
the slope makes this a symmetric bilinear interchange sign. Give
tensor products the multiplication
\begin{equation}\label{alg:signed-tensor}
(x\otimes y)(x'\otimes y')
=\varepsilon(\deg y,\deg x')\,(x*x')\otimes(y*y'),
\end{equation}
where degrees in this formula are dimension vectors.
\begin{proposition}\label{alg:bialgebra}
With $\Delta=\sum_{a+b=d}\Delta_{a,b}$,
$\mathcal H$ is a connected dimension-graded bialgebra, and its
coproduct is cocommutative with the interchange sign
$\varepsilon(a,b)$.
\end{proposition}
\begin{proof}
Testing either iterated coproduct against three independent lists of
symbols gives the symbol for their concatenation. Joint tensor
detection gives coassociativity. Swapping two lists changes their
cross-list prefactor by
$(-1)^{\chi(a,b)}$; the underlying restriction is simply permuted.
Detection therefore gives signed cocommutativity. The empty-list
components give the counit and the unit identities.
For multiplicativity apply
Equation~\eqref{alg:product-symbol-formula} to the two tensor factors
separately. If the first input contributes dimensions $d_R,d_S$ to
the two lists, and the second contributes $e_R,e_S$, concatenating
the lists adds to the two separate symbol signs exactly
\[
\sum_{i\in S,\ j\in R}\chi(d_i',e_j')=\chi(d_S,e_R).
\]
This is the interchange sign in
Equation~\eqref{alg:signed-tensor}. Both sides therefore have the
symbols of the product restricted to the concatenation, and
detection proves multiplicativity. Positive dimension grading and
$\mathcal H_0=\Q$ give connectedness.
\end{proof}
\subsection{Primitive vectors and polynomial strings}
The symmetric-algebra form of the graded dimensions is the
cohomological-integrality and PBW phenomenon developed in
\cite{KS11,Ef12,DMe20}. Efimov's freeness theorem assumes a symmetric
quiver, whereas our quiver need only have symmetric Euler pairing on
the selected slope. Davison--Meinhardt use a perverse associated
graded in \cite[Theorem~C]{DMe20}; the separated-center filtration here
has its own explicit construction. We include the vector-space
argument needed from our bialgebra, because its conclusion does not
require commutativity of the product.
Let $\mathcal P\subset\mathcal H$ be the primitive subspace, namely
the positive-dimensional elements killed by every proper
$\Delta_{a,b}$. By Equation~\eqref{alg:coproduct-symbol} and tensor
detection, these are exactly the elements killed by all proper
symbols $L_P$, where a proper list has at least two nonempty entries.
The convolution-logarithm proof below is the signed/braided
Eulerian-idempotent argument. For the classical cocommutative
characteristic-zero method, see
\cite[Sections~3--4, Theorem~3.5 and Lemma~4.1]{Patras93};
the proof here supplies the bilinear-sign adaptation.
\begin{lemma}[Signed vector-space PBW]\label{alg:pbw}
Symmetrized multiplication gives an isomorphism of graded vector
spaces
\begin{equation}\label{alg:pbw-map}
\operatorname{Sym}_{\varepsilon}(\mathcal P)
\longrightarrow\mathcal H.
\end{equation}
Here the left side is the signed symmetric vector space: exchanging
homogeneous vectors of dimensions $a,b$ multiplies a tensor by
$\varepsilon(a,b)$. The gradings retained are dimension, original
shifted degree, and filtration weight; tensor length is summed over.
\end{lemma}
\begin{proof}
For linear maps out of $\mathcal H$, convolution uses its coproduct
and multiplication in the target. Let $e$ be augmentation followed
by inclusion of the unit, and put
\[
J=\id-e,\qquad
\mathsf P=\log^*(\id)=
\sum_{r\ge1}\frac{(-1)^{r-1}}rJ^{*r}.
\]
On dimension $d$, a nonzero term has at most $|d|_1$ positive
dimensions, so this sum and all subsequent convolution series are
finite there. In the target algebra $\mathcal H\otimes\mathcal H$ define
$\alpha(h)=h\otimes1$ and $\beta(h)=1\otimes h$.
Then $\alpha*\beta=\Delta$, while signed cocommutativity gives
$\beta*\alpha=\Delta$ as well. Since $\Delta$ is multiplicative,
\[
\Delta\circ\mathsf P
=\log^*(\Delta)
=\log^*(\alpha)+\log^*(\beta)
=\mathsf P\otimes1+1\otimes\mathsf P.
\]
Thus $\mathsf P$ takes values in $\mathcal P$. Exponentiating,
\[
\id=e+\sum_{r\ge1}\frac1{r!}\mathsf P^{*r}.
\]
The iterated coproduct is invariant under signed permutations, and
$\mathsf P$ preserves all gradings. This expression therefore
spans $\mathcal H$ by signed symmetrized products of primitives.
To prove independence, identify signed symmetric tensors in
characteristic zero with the invariant tensors obtained by averaging
over signed permutations. In a finite relation among their
products, let $r$ be the largest tensor length. Apply the iterated
coproduct with $r$ factors and project each factor to positive
dimension. Terms of length less than $r$ vanish. A product of $r$
primitives gives the sum of their $r!$ signed permutations; on its
symmetrized tensor this is $r!$ times that tensor. Hence the
length-$r$ part of the relation is zero. Descending on $r$ proves
independence.
For a homogeneous basis of $\mathcal P$, a multiset contributes one
signed symmetric tensor unless an element with self-sign $-1$
repeats, in which case it contributes zero. This proves the stated
description of dimensions. In particular, an odd primitive may have
a nonzero square in $\mathcal H$. Its square is then an even
primitive, since the two middle coproduct terms cancel, and is
accounted for in the even primitive subspace. No assertion that raw odd
squares vanish is used in Equation~\eqref{alg:pbw-map}.
\end{proof}
\begin{lemma}[Primitive strings]\label{alg:strings}
For each nonzero dimension $d$, the primitive space is a direct sum
of strings with original shifted degrees
\[
h,h+1,h+2,\ldots,
\qquad h-s(d)\in\N.
\]
Each degree has finite dimension. Every vector in these strings has
self-interchange sign $(-1)^{\chi(d,d)}$.
\end{lemma}
\begin{proof}
On $S_d$, consider common differentiation and multiplication by the
variable mean,
\[
D_d=\sum_{i,\alpha}\frac{\partial}{\partial x_{i,\alpha}},
\qquad
T_d f=\left(\frac1{|d|_1}\sum_{i,\alpha}x_{i,\alpha}\right)f.
\]
The translation invariance of the shuffle kernels implies
$D_d(I_d)\subset I_d$. The ideal property implies
$T_d(I_d)\subset I_d$. Thus both operators descend to $B_d$.
For $P=(r_1,\ldots,r_m)$, restriction gives
\begin{align*}
R_P^z(D_df)&=\left(\sum_\ell\partial_{z_\ell}\right)R_P^zf,\\
R_P^z(T_df)&=
\left(\frac{\sum_\ell|r_\ell|_1z_\ell}{|d|_1}
+\frac{\sum_{\ell,i,\alpha}x^\ell_{i,\alpha}}{|d|_1}
\right)R_P^zf.
\end{align*}
Both preserve the filtration lower bound. On the associated grade,
the internal-variable term in the second line raises internal degree
and disappears. The prefactor of $L_P$ depends only on center
differences, so its common center derivative vanishes. Consequently
\begin{align*}
L_P(D_df)&=\left(\sum_\ell\partial_{z_\ell}\right)L_P(f),\\
L_P(T_df)&=
\frac{\sum_\ell|r_\ell|_1z_\ell}{|d|_1}L_P(f).
\end{align*}
They preserve the common kernel of all proper symbols, hence the
primitive space. They satisfy $D_dT_d-T_dD_d=\id$ there; $D_d$ is
locally nilpotent, and $T_d$ raises original shifted degree by one.
Here is an explicit string decomposition. On a space with these
operators define the finite-on-each-vector operator
\[
\pi(f)=\sum_{j\ge0}\frac{(-1)^j}{j!}T_d^jD_d^jf.
\]
The commutator identity gives $D_d\pi=0$. Binomial cancellation
gives
\[
f=\sum_{j\ge0}\frac{T_d^j}{j!}\pi(D_d^jf).
\]
Choose a homogeneous basis of $\ker D_d$ in the primitive space.
Its $T_d$-iterates therefore span. They are independent: in a finite
relation $\sum_{j=0}^rT_d^jb_j=0$ with $D_db_j=0$, applying
$D_d^r$ gives $r!b_r=0$, and induction removes the other terms.
Every component of $\mathcal H_d$ is a subquotient of $B_d$, with
original shifted degree equal to nonnegative polynomial degree plus
$s(d)$. Thus every string begins at $h\ge s(d)$ with the indicated
integral difference. The polynomial spaces in any fixed degree are
finite-dimensional, and the filtration is finite there, proving
the finiteness assertion. Finally the self-sign depends only on the
dimension vector, as stated.
\end{proof}
Combining Lemmas~\ref{alg:pbw} and~\ref{alg:strings}, the shifted
Hilbert series on a slope is the Hilbert series of independent
polynomial strings when $\chi(d,d)$ is even and exterior strings
when it is odd. Passing to the auxiliary associated grade has not
changed any original shifted graded dimension.
\subsection{Elementary factors and the infinite-list bounds}
We now finish the finite-input case of
Theorem~\ref{alg:reordering} using the slope factor
\eqref{alg:slope-factor}. Lemmas~\ref{alg:pbw}
and~\ref{alg:strings} give exactly the polynomial and exterior
strings required above. In shifted degree $h$, their weight is
$v^{u(d)-2h}$.
A primitive
string beginning at $h$ contributes one elementary unit with
\begin{equation}\label{alg:output-parameter}
p=p(d),\qquad k=u(d)-2h,
\end{equation}
of type $E$ if $\chi(d,d)$ is odd and type $H$ if it is even.
These are integer parameters because $2h$ is an integer. The
primitive-basis dimensions give nonnegative integral multiplicities.
Finiteness of each original graded piece proves that, for a fixed
finite list and bounded dimension, only finitely many output
parameters lie above any threshold. This proves the finite-input
case.
Now allow an admissible infinite input list. Give each occurrence
its own index and use finite-support dimension vectors $d$. All
polynomial spaces, ideals, restrictions, filtrations, and primitive
spaces for a fixed $d$ use only the finitely many indices in its
support. Adding other indices changes none of them. The preceding
constructions are consequently compatible as the finite input list
increases.
We give uniform bounds to justify this passage. Fix an integer
charge cutoff $B\ge1$. Every active $p_i$ belongs to the finite set
$C_B=\{p\in C:00$ the ratio is $\prod_{\ell=1}^t f(v^{k+2\ell}X_a)$.
For $t<0$ the inverse adjoint has ratio
$\prod_{\ell=t+1}^{0}f(v^{k+2\ell}X_a)$.
Thus $\Ad(U_{a,k,f})^\varepsilon X_m$ has nonnegative integral
Laurent-series coefficients whenever $\varepsilon t\ge0$.
Its constant, or no-jump, coefficient is one.
\end{lemma}
\begin{proof}
Choosing $j$ distinct indices $0\le i_1<\cdots0}r$, follow a generic line in $r^\perp$, parallel
to $V(r)$, from far in the positive direction towards the specified
cell. The initial element is the incoming element just proved.
At the finitely many joints met by the line, all relevant normals
lie in a two-dimensional plane containing $r$. A normal $s$ with
$\Omega(s,r)=0$ gives a hyperplane parallel to the line, which a
generic offset avoids. Thus a joint at which a change occurs has
nonzero skew form on its plane. The offset can also avoid every
intersection involving three independent normals.
Order the positive rays in this plane so that the skew pairing of
an earlier ray with a later ray is positive. At the incoming end
$V(a)$ of a ray $a$, earlier normals evaluate positively and later
ones negatively. The local middle element is therefore the
ordered product of its incoming ray elements in this order. Its
factorization in the reverse order gives its outgoing ray elements.
Theorem~\ref{alg:reordering} applies to precisely this positive
ordering and to the pointed monoid obtained by intersecting the
plane with $C^+$.
There is a small induction issue at degree $d$. The incoming
element on the ray being followed is already known through degree
$d$ from the previous segment. On all other incoming rays it is
enough to know positive factorizations through degree $d-1$.
Indeed, a degree-$d$ input term can affect an output term of degree
$d$ only linearly: multiplication with any nonconstant term raises
the degree. Its linear contribution remains on its own ray.
Unknown degree-$d$ terms on other rays consequently do not affect
the ray under consideration. Extend their known positive lists
arbitrarily to the required truncation, apply
Theorem~\ref{alg:reordering}, and use uniqueness of ray
factorization. This proves the assertion at each successive joint
and completes the induction.
For the last assertion, a positive-to-negative crossing has
$\Omega(r,m)>0$ and uses the adjoint of the wall element; a
negative-to-positive crossing has $\Omega(r,m)<0$ and uses its
inverse. All elementary arguments are positive multiples of $r$,
so Lemma~\ref{wall:unit} applies to every factor.
We spell out why infinite lists still give finite integer
coefficients at a specified energy. At a fixed root bound there
are finitely many possible arguments, the total multiplicity of
selected nonconstant factors is bounded, and all skew-pairing
shifts between these factors are bounded. Their parameters have a
common upper bound $K_0$. If a contribution has energy $E$, no
selected parameter can tend to $-\infty$: the bounded number of
other parameters and the bounded interaction shifts could not
compensate for it. Every selected parameter is therefore above
an explicit lower threshold depending on the root bound and $E$.
Only finitely many occurrences lie above that threshold. Their
nonnegative string indices are then bounded as well. This proves
both finite multiplicity at each energy and a common upper energy
bound. The corresponding output-list bounds are supplied by
Theorem~\ref{alg:reordering}. Thus all the asserted coefficients
belong to $\N((v^{-1}))$, rather than merely being formal infinite
sums of nonnegative integers.
\end{proof}
A \emph{section} is a family of values transported by these
consistent wall operations. Any value with the stipulated support
in one generic chamber determines a section. Its \emph{incoming
coefficient} is
\begin{equation}
A_n(F)=[X_n]F(V(n)+\epsilon),
\label{wall:incoming-coordinate}
\end{equation}
where a sufficiently small generic perturbation is chosen at the
finite order needed for that coefficient. This does not depend on
the perturbation. A wall that can separate two such choices has
normal $r$ with $\Omega(r,n)=0$, and its action cannot alter the
$X_n$-coefficient: a possible contributing input $n-jr$ also has
zero pairing with $r$, so that monomial is fixed.
In any fixed chamber $H$, transport adds only positive roots.
Consequently $A_n(F)$ equals $[X_n]F(H)$ plus a linear combination
of coefficients at strictly smaller exponents. On every finite
interval this is a triangular change of coordinates with diagonal
one. It defines a unique section $\Theta_m$, supported in
$m+C^+$, such that
\begin{equation}
A_n(\Theta_m)=\begin{cases}1,&n=m,\\0,&n\ne m.\end{cases}
\label{wall:theta-definition}
\end{equation}
Its leading monomial is $X_m$ in every chamber. This incoming-coordinate
description plays the role of the theta functions in the scattering
framework of \cite{GHKK18,DM21}. The definition and positivity argument
below use only the explicit coefficient recursion in our convention. More generally,
within any fixed finite union of translates of $C^+$,
\begin{equation}
F=\sum_n A_n(F)\Theta_n.
\label{wall:theta-expansion}
\end{equation}
For a requested exponent this is a finite sum, by the interval
property of the free cone.
\begin{lemma}[The positive coefficient recursion]
\label{wall:recursion}
Fix a generic target chamber $H$, represented by $h$, and a target
exponent $n$. At sufficient finite root order, follow
$h+sV(n)$ from sufficiently large $s$ down to $s=0$. Let its
successive crossings be $W_i:I_i\longrightarrow I_{i+1}$, with
primitive positive wall normal $p_i$. Define
\[
J_i(a,j)=[X_{a+jp_i}]W_i(X_a),\qquad j\ge0.
\]
Then $J_i(a,0)=1$, and for the exponents $a=n-jp_i$ that can
contribute one has $J_i(a,j)\in\N((v^{-1}))$. Moreover,
\begin{equation}
[X_n]F(H)=A_n(F)+
\sum_i\ \sum_{\substack{j>0\\n-jp_i\ \text{in the support bound}}}
J_i(n-jp_i,j)[X_{n-jp_i}]F(I_i).
\label{wall:coefficient-recursion}
\end{equation}
All sums are finite at a fixed exponent. With the simple data
\eqref{wall:initial-unit}, the jump coefficients are effectively
computable at every fixed energy by finite rational arithmetic and
Laurent expansion in $v^{-1}$. The same holds for the section
coefficients when its initial value is a specified finite Laurent
polynomial, or when its incoming data are finitely specified
rational functions of $v$.
\end{lemma}
\begin{proof}
After rescaling by $s$, the initial point tends to $V(n)$, so its
$X_n$-coefficient is $A_n(F)$. Hyperplanes whose normals pair
trivially with $n$ are parallel to this line and are avoided by
choosing $h$ generically. Every actual crossing has the sign of
$-V(n)$; the input $n-jp_i$ has the same pairing with the wall as
$n$. Proposition~\ref{wall:factors} proves the stated positivity
and the no-jump assertion. Taking the $X_n$-coefficient in each
crossing identity and summing the successive differences proves
\eqref{wall:coefficient-recursion}. The exponents in each inner
sum lie in a finite cone interval. The arrangement contains only
the roots needed for those intervals, so the outer sum is finite
as well.
For effectivity, \eqref{wall:unit-coefficient} gives rational
functions of $v$ for the input coefficients. The triangular
equations \eqref{wall:incoming-prescription} and
\eqref{wall:three-factors}, followed by inversion and multiplication
at bounded root order, therefore give rational functions of $v$
for every required wall coefficient. Their Laurent expansions
at $v^{-1}=0$ compute the requested jump coefficients and their
upper energy bounds. No positive factorization needs to be
found by the algorithm. A finite polynomial initial value can
be transported by these same finite rational operations; finitely
specified incoming data can instead be used in
\eqref{wall:coefficient-recursion}. Recursing on its strictly
smaller exponents terminates, since the cone intervals are finite.
At fixed total energy, upper
bounds on the finitely many factor energies also give lower
bounds on each of them. Hence the required integer coefficient
is obtained by a finite computation.
\end{proof}
\begin{theorem}[Positive sections]
\label{wall:positivity}
Every $\Theta_m$ has coefficients in $\N((v^{-1}))$ in every
chamber. More generally, the same is true of a section $F$ all
of whose incoming coefficients belong to $\N((v^{-1}))$.
\end{theorem}
\begin{proof}
Fix a target exponent and its finite interval above the support
lower bounds. Induct on the addition order in this interval,
using \eqref{wall:coefficient-recursion}. Its initial term is
nonnegative by hypothesis, and every other term is a nonnegative
jump coefficient times a coefficient at a strictly smaller
exponent. The induction proves positivity. The energy bounds
in Proposition~\ref{wall:factors} and Lemma~\ref{wall:recursion}
justify each multiplication and sum in the Laurent completion.
Equation~\eqref{wall:theta-definition} gives the special case.
\end{proof}
\begin{corollary}[Positive products]
\label{wall:product}
The structure coefficients in
\[
\Theta_{m_1}\cdots\Theta_{m_b}
=\sum_n A_n(\Theta_{m_1}\cdots\Theta_{m_b})\Theta_n
\]
belong to $\N((v^{-1}))$. Products and expansions are locally
finite at every specified exponent.
\end{corollary}
\begin{proof}
Evaluate the product near $V(n)$ to compute its incoming
$n$-coefficient. Each factor is positive by
Theorem~\ref{wall:positivity}; the scalar contributed by torus
multiplication is a power of $v$. For fixed total exponent there
are only finitely many tuples of factor exponents above their
specified lower bounds. Their Laurent products have finite
coefficients at each energy. Thus the incoming coefficient is
nonnegative, and \eqref{wall:theta-expansion} proves the assertion.
\end{proof}
\subsection{A finite bound in the mutation direction}
Mutation compatibility is a basic feature of classical cluster theta
functions \cite[Theorem~1.24 and Proposition~3.6]{GHKK18} and their
quantum counterparts \cite[Appendix~A]{DM21}. We next compare two
different cone completions, keeping the finite-fiber argument needed
for equality of actual coefficients. From this point
the simple incoming data are exactly
\eqref{wall:initial-unit}. Fix $p\in C$ and put
\begin{equation}
\alpha_c=\Omega(p,c),\qquad
c'=c+[-\alpha_c]_+p\quad(c\ne p),\qquad
C'=\{-p\}\cup\{c':c\in C\setminus\{p\}\},
\label{wall:mutated-roots}
\end{equation}
where $[x]_+=\max(x,0)$. The set $C'$ is again part of a
lattice basis. Define
\begin{equation}
S(m)=m-\Omega(p,m)p,
\qquad S^\vee h=h\circ S^{-1}.
\label{wall:linear-mutation}
\end{equation}
The map $S$ preserves $\Omega$ and hence acts on the quantum torus
by $X_m\mapsto X_{S(m)}$. On covectors, the change of chart is
\begin{equation}
T(h)=\begin{cases}
h,&h(p)\ge0,\\
S^\vee h,&h(p)\le0.
\end{cases}
\label{wall:piecewise-mutation}
\end{equation}
The two definitions coincide on $p^\perp$.
For a non-pure root, write
\[
r=kp+u,\qquad u=\sum_{c\ne p}u_cc\ne0,
\qquad k,u_c\in\N.
\]
Its \emph{non-$p$ degree} is $|u|=\sum_{c\ne p}u_c$. For
$\sigma\in\{+1,-1\}$ set
\begin{equation}
M_\sigma(u)=\sum_{c\ne p}[-\sigma\alpha_c]_+u_c.
\label{wall:fiber-bound-function}
\end{equation}
\begin{lemma}[Finite support in each $p$-fiber]
\label{wall:fiber-bound}
On the open side $\operatorname{sign}h(p)=\sigma$, a non-pure
root $kp+u$ occurring in a wall element or its logarithm satisfies
\begin{equation}
0\le k\le M_\sigma(u).
\label{wall:fiber-bound-equation}
\end{equation}
The pure $p$-wall has element $D_p$ everywhere on the cut where
no other wall direction is present.
\end{lemma}
\begin{proof}
Projection to the face $\N p$ is an algebra homomorphism: a sum
of roots with a nonzero non-$p$ component cannot be pure. At any
point of $p^\perp$, the pure part of the middle factor is thus
the pure part of $g$, which is $D_p$ by
\eqref{wall:incoming-prescription}. This proves the last
assertion.
We prove \eqref{wall:fiber-bound-equation} by induction on
$|u|$, not on $k+|u|$. During this induction, an assertion about
an individual coefficient at $kp+u$ is always checked first in a
finite full-degree truncation containing that coefficient. No
uniform finiteness in $k$ is presumed.
Put $t=\Omega(p,u)=\sum_c\alpha_cu_c$. If $t\ne0$, call the
side $\sigma=\operatorname{sign}(t)$ upstream. A line in
$(kp+u)^\perp$, followed from the incoming direction
$V(kp+u)$ to a point on that side, never crosses $p^\perp$:
the evaluation on $p$ along its forward tail is $h(p)+st$ with
$s\ge0$. If $t=0$, the line is parallel to the cut and the
same argument applies on either side. At its incoming end the
bound holds, since the only nontrivial incoming rays are simple
ones, with $k=0$.
Consider a joint off the cut along this line. Every normal
involved has positive non-$p$ degree. In an ordered
refactorization, a genuinely new contribution of non-$p$ degree
$|u|$ is a product of at least two such terms and therefore
uses only smaller non-$p$ degrees. A term already of degree
$|u|$ contributes linearly on its own ray, so it is merely
carried to the next segment. By induction every smaller term
satisfies \eqref{wall:fiber-bound-equation}. The bound is
additive in $u$: sums of supported exponents are still
supported in
\[
\{kp+u:0\le k\le M_\sigma(u)\}.
\]
It follows, by the coefficient recursion for ray
factorization, that the bound persists at this joint. This
proves the upstream assertion for each $k$ separately, through
finitely many joints at the order needed for that $k$.
Only now do we conclude that the entire upstream fiber has
finite support, since the numerical upper bound
$M_\sigma(u)$ is independent of the truncation.
Suppose $t\ne0$ and continue to the other side. At a generic
transverse joint on $p^\perp\cap u^\perp$, the normals lie
in the plane spanned by $p$ and $u$. Their non-pure
projections are positive multiples of the same ray through
$u$. Their pairings with $p$ are consequently nonzero and
have the common sign $\sigma$. Such genericity is imposed
only through the finite non-$p$ degrees currently needed;
the upstream bounds just proved make the corresponding
full-degree arrangement finite.
Separate the pure factor $D_p$ from the incoming ordered
product of non-pure factors. If $\sigma=+1$, $p$ is first
in the incoming order, and refactorization conjugates the
non-pure product by $D_p$. If $\sigma=-1$, $p$ is last,
and it conjugates that product by $D_p^{-1}$. Formula
\eqref{wall:binomial} shows that an input monomial $X_{kp+w}$
acquires only additional exponents $jp$ with
\[
0\le j\le |\Omega(p,w)|.
\]
All relevant $w$ have the same pairing sign. On this ray,
\[
M_{-\sigma}(w)=M_\sigma(w)+|\Omega(p,w)|.
\]
Thus the whole conjugated non-pure product has the downstream
bound. So do its ray factors: coefficientwise factorization
cannot introduce an exponent outside an additive support
monoid containing the product's support. Explicitly, for the
first putative such exponent the defining coefficient is zero
in the product, and every term subtracted from it is a sum of
already permitted exponents, a contradiction.
At the current degree, the coefficients needed at the cut
are either of smaller non-$p$ degree, or already established
upstream coefficients of the current degree. This avoids a
circular appeal to downstream finiteness. Further joints
off the cut are treated by the same smaller-degree argument
as before. Finally, the support monoid is additive, so its
bound is preserved by both logarithm and exponential. The
statement holds for wall elements and their logarithms.
\end{proof}
The numerical bound also controls the change of completion.
Let $L_+=\id$ and $L_-=S$. A direct calculation gives
\begin{equation}
L_\sigma(kp+u)
=\sum_{c\ne p}u_cc'+(M_\sigma(u)-k)(-p).
\label{wall:root-image}
\end{equation}
Thus every supported root off the cut maps into $C'^+$.
Put $B=\max_{c\ne p}|\alpha_c|$, with $B=0$ if the index
set is empty. Since $M_\sigma(u)\le B|u|$, a root of new
degree at most $d$ comes from one with $|u|\le d$ and old
degree at most $(B+1)d$. In particular, the pushed wall
elements and their cells at bounded new order are determined
by finite old data.
\subsection{Mutation and equality of actual coefficients}
\begin{theorem}[Change of chart]
\label{wall:mutation}
The wall system for $C$, with simple data $D_c$, is carried
to the wall system for $C'$, with simple data $D_{c'}$, as
follows. Off the cut $p^\perp$, use the covector map $T$
from \eqref{wall:piecewise-mutation} and act on exponents
by $L_\sigma$ on the side of sign $\sigma$. On the cut,
replace the pure wall by $D_{-p}$.
Suppose $F$ and $F'$ are sections specified by finite Laurent
polynomials in the respective all-negative chambers, and
these initial polynomials satisfy the rational identity
\begin{equation}
F=\Ad(D_p)F'.
\label{wall:initial-comparison}
\end{equation}
For $h(p)>0$ their transported values agree coefficientwise
under the identity; for $h(p)<0$ they agree coefficientwise
under $S$. In particular,
\begin{equation}
A_n(F)=A_{\mu_p(n)}(F'),\qquad
\mu_p(n)=n+[-\Omega(p,n)]_+p.
\label{wall:incoming-mutation}
\end{equation}
The map $\mu_p:M\to M$ is a bijection.
\end{theorem}
\begin{proof}
First we establish the identity of transformations at the
cut, with the normalization of Lemma~\ref{wall:unit}:
\begin{equation}
S\circ\Ad(D_p)=\Ad(D_{-p})^{-1}.
\label{wall:cut-identity}
\end{equation}
For $t=\Omega(p,m)\ge0$, the coefficient of $X_{m+jp}$
in $\Ad(D_p)X_m$ is
\[
b_{t,j}=e_j(v^{1-t},v^{3-t},\ldots,v^{t-1}).
\]
The displayed letters are invariant under inversion and
have product one, so $b_{t,j}=b_{t,t-j}$. Applying $S$
sends the exponent $m+jp$ to $m-(t-j)p$.
On the other hand, the finite formula for
$\Ad(D_{-p})^{-1}X_m$ has coefficients $b_{t,j}$ at
$m-jp$. This proves \eqref{wall:cut-identity} on $X_m$.
When $t<0$, apply the proved identity to $X_{-m}$ and take
its inverse. Both sides are algebra homomorphisms, so the
identity follows on all rational monomial expressions.
\emph{A common ring for the comparison.}
Set $Z=X_p$, choose a lattice complement $M=\Z p\oplus L$
containing $C\setminus\{p\}$, and allow coefficients in
$K(Z)$ on the monomials $X_\ell$, $\ell\in L$. Complete
in the free positive monoid generated by the images of
$C\setminus\{p\}$ modulo $p$, allowing a finite union of
translates for section values. Multiplication is specified
by \eqref{wall:torus} and the rule
\begin{equation}
X_\ell f(Z)=f(v^{-2\Omega(p,\ell)}Z)X_\ell.
\label{wall:rational-commutation}
\end{equation}
Consequently a coefficient at each specified non-$p$
exponent is a rational function of $Z$. Products use
finitely many decompositions of that non-$p$ exponent.
This ring will be used only for comparisons; it does not
identify the two Laurent completions in $Z$.
By Lemma~\ref{wall:fiber-bound}, a non-cut wall element is
polynomial in $Z$ at each fixed non-$p$ degree. Its
constant term in non-$p$ degree is one. Its inverse,
computed by the geometric series in positive non-$p$
degree, is therefore polynomial in $Z$ at each such degree
as well. The same assertions hold with Laurent
polynomials after applying either linear piece of the
chart map. Conjugation by these elements is thus a
well-defined operation on the common ring. Pure
conjugation by $D_p^{\pm1}$ fixes $Z$ and sends any
$X_\ell$ to a rational function of $Z$ times $X_\ell$,
by \eqref{wall:unit-ratio}. It, too, acts on this ring.
The map $S$ is the identity modulo $p$, so it preserves
the non-$p$ degree and acts in the same ring.
We justify importing the old consistency into this ring.
The expansion homomorphism
\[
K(Z)\longrightarrow K((Z))
\]
at $Z=0$ is injective. On a monomial input, expansion of
every old crossing operation agrees with its operation
in the old positive completion: its increments lie in
$C^+$, and the pure ratios have their usual power-series
expansions at zero. At bounded non-$p$ degree, all
non-cut wall elements are controlled by finitely many
old roots by Lemma~\ref{wall:fiber-bound}. The path may
be made generic for these data. To test a further
coefficient in its expansion in $Z$, perturb through
the additional finite old order needed for that
coefficient; this does not alter the already specified
projected operations. Old path independence holds at
each such full order. Hence a rational difference
between two path operations has zero Laurent
expansion in every non-$p$ degree, and injectivity
forces that difference to be zero. This proves old
consistency in the common ring, on every monomial and
therefore on its completed modules.
\emph{Consistency and incoming data after mutation.}
Push the non-cut elements by $L_\sigma$ and put
$D_{-p}$ on the pure cut. Equation~\eqref{wall:root-image}
shows that this is a system in the new cone completion,
finite to every new root order. On any loop, the
linear identifications on successive open sides
cancel; at a cut crossing their discrepancy is
exactly corrected by \eqref{wall:cut-identity}. Thus
the pushed path operations are consistent in the
common rational ring. Expand now at $Z^{-1}=0$ to
obtain their operations in the new cone completion.
Replacing $c$ by $c'=c+[-\alpha_c]_+p$ changes the
coefficient at a fixed projected exponent only by a
Laurent monomial in $Z$ and a scalar power of $v$.
Equation~\eqref{wall:root-image} ensures that every
pushed increment is $C'^+$-positive, so this fiberwise
expansion is precisely the one in the new completion.
The finite-order bounds already proved make this
expansion coefficientwise legitimate. They are
consistent there as well. Since the form is
nondegenerate, adjoint actions detect the wall group
elements: for a nonzero first root $r$ in the
logarithm of an element, choose $m$ with
$\Omega(r,m)\ne0$; its commutator with $X_m$ is
nonzero. Consequently consistency of the actions
also gives consistency of the wall products.
It remains to identify this system by its incoming
prescription. A symplectic linear map $L$ satisfies
$V(Lr)=L^\vee V(r)$. Thus on each eventual open side,
the incoming direction of a pushed ray is the image
of its old incoming direction. For a simple $c\ne p$,
$V(c)(p)=\alpha_c$, so that the relevant piece sends
$c$ to exactly $c'=c+[-\alpha_c]_+p$. Its unit is
therefore $D_{c'}$. All other non-pure incoming
logarithmic coefficients vanish. If an incoming
direction is parallel to the cut, its pairing with
$p$ is zero; the two pieces agree on its exponent,
and either sufficiently small generic offset gives
the same conclusion by the trace argument
\eqref{wall:trace}. A component with no preimage
wall has zero coefficient. The pure incoming
element is $D_{-p}$ by construction. Uniqueness of
\eqref{wall:incoming-prescription} identifies the
pushed system with the system for $C'$.
\emph{Actual coefficients of polynomial sections.}
We now use the finite-polynomial hypothesis in
\eqref{wall:initial-comparison}. Choose a point on
the cut with $h(c)<-1$ for all $c\ne p$, and take
$h(p)$ very small on either side. Such covectors
exist because $C$ is part of a basis. With the
constant $B$ defined after
\eqref{wall:root-image}, choosing
$|h(p)|<(B+1)^{-1}$ ensures that every non-pure
supported root off the cut has negative evaluation:
\[
h(kp+u)\le B|u|\,|h(p)|-|u|<0.
\]
At the cut itself $h(u)<0$. Hence the short
crossing between these points meets only the pure
wall. The negative side is in the old all-negative
chamber. The positive side is in the new
all-negative chamber, since $h(-p)<0$ and
$h(c')<0$.
On the positive side, the old value is
\[
\Ad(D_p)^{-1}F=F',
\]
which is the actual finite Laurent polynomial
specified in the new chamber. On the negative
side the pushed old value is $SF$, while
\eqref{wall:cut-identity} and
\eqref{wall:initial-comparison} give
\[
SF=\Ad(D_{-p})^{-1}F'.
\]
This too is a finite Laurent polynomial, because
$F$ is one and $S$ is linear. We have therefore
established equality of actual finite values on
both sides near the cut.
To reach any other chamber on a fixed open side,
transport entirely within that half-space.
Only non-cut walls occur. Their elements and
inverses have finite Laurent support in the
$p$-fiber at every fixed non-$p$ degree, as proved
above. Starting from a finite Laurent polynomial,
successive transport consequently retains finite
Laurent support in each such fiber: the required
coefficient uses finitely many decompositions of
the non-$p$ degree and finitely many crossings in
its bounded arrangement. Applying $L_\sigma$
preserves this property. The compared fiber is
therefore the same finite Laurent polynomial on
the two sides of the identification. Its
coefficient equality is independent of whether
it is regarded in the old or the new completion.
This establishes the claimed equality of actual
section coefficients throughout both open
sides. In particular, the argument never
equates the expansions at zero and infinity
of an arbitrary rational function.
Finally, put $t=\Omega(p,n)$. The incoming
direction $V(n)$ lies on the side of sign $t$.
The relevant linear piece sends $n$ to $n$ if
$t>0$, and to $S(n)=n-tp$ if $t<0$. If $t=0$,
both pieces fix $n$, and either generic
perturbation computes the same incoming
coefficient. This proves
\eqref{wall:incoming-mutation}. Its label map
preserves $\Omega(p,n)$, so its inverse subtracts
$[-\Omega(p,n)]_+p$. The label map is thus a
bijection, as asserted.
\end{proof}
==== END Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//04-walls.tex ====
==== BEGIN Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//05-triangle.tex ====
\section{The triangular chart and monomial sections}\label{tri:section}
We now identify the evaluated monomial symmetric polynomials with single
positive sections. The auxiliary graph used for this purpose contains every
naturally labeled unit interval graph as an ordered induced subgraph.
All lattice vectors in this section belong to the free lattice on the
vertices; the extra dual directions, if used to make the skew form
nondegenerate, never occur in their support.
Positive theta sections do not yet give elementary positivity: we must
identify each evaluated monomial symmetric function with a single such
section. We first introduce an auxiliary graph with a distinguished
independent set of vertices. Repeated rotations constrain the incoming
coefficients, but those constraints alone do not force the desired
identity. A separate analysis of the degree-one symmetric function
will give a positive support bound for its higher-degree analogues;
that bound is what makes the final subtraction argument possible.
\subsection{The chart and its rotations}
Fix an integer $D\geq 1$, and put $n_0=D-1$. There are anchors
$d_1,\ldots,d_D$ at the integer times $1,\ldots,D$. For each
$1\leq j\leq i\leq n_0$ there is a bridge $b_{j,i}$ at time
$i+\theta_{j,i}$, where $0<\theta_{j,i}<1$. The phases are distinct.
For $D>1$, their increasing order is
\begin{equation}\label{tri:phase-order}
(n_0,n_0);\quad (n_0-1,n_0-1),(n_0-1,n_0);\quad\ldots;\quad
(1,1),(1,2),\ldots,(1,n_0).
\end{equation}
The index $i$ is the \emph{level}, and $j$ is the \emph{row}.
Two vertices are adjacent precisely when their times differ by less than
$1$. In particular, the anchors are independent, bridges on one level
form a clique, and bridges on neighboring levels are adjacent precisely
when the bridge on the higher level has the earlier phase.
Use the vertex names also for their independent lattice vectors. The
skew form has $\Omega(b,a)=1$ when $a$ precedes $b$ and they are adjacent,
and is zero on nonedges. We use the quantum torus normalization
$X_aX_b=v^{\Omega(a,b)}X_{a+b}$.
The independent-set elements
\[
E_k=e_k(Y)=\sum_{\substack{I\text{ independent}\\ |I|=k}}
X_{\sum_{a\in I}a},\qquad U=E_1,
\]
commute by Proposition~\ref{graph:commutation}. An independent set has at
most $D$ vertices: its ordered times have successive differences at least
$1$ and lie in $[1,D]$. Thus $P(Y)$ is defined for every symmetric
polynomial $P$ in $D$ variables.
\begin{lemma}[Embedding]\label{tri:embedding}
Every naturally labeled unit interval graph on $n$ vertices occurs as
an ordered induced subgraph on $n$ selected bridges of a triangular
chart. The times and phases may all be chosen rationally.
\end{lemma}
\begin{proof}
For $n=0$ take $D=1$. For $n>0$, first construct strictly increasing
positive rational times
$t_1,\ldots,t_n$, with distinct nonzero fractional parts, such that
$at_{k-1}+1$. Otherwise choose
\[
\max\{t_{k-1},t_{s-1}+1\}1$ we have $t_{s-1}1$.
Track the nonzero coefficient using~\eqref{tri:incoming-rotation}.
At each stage use the current vertex basis to write its current label
as $\sum\nu_i d_i+\sum\kappa_b b$.
When $b$ on level $i$ is moved, put
$t=[-\Omega(b-d_i,m)]_+$. Reexpressing
$m+t(b-d_i)$ using $b'=b+d_{i+1}-d_i$ gives
\begin{equation}\label{tri:coordinate-step}
\kappa_b'=\kappa_b+t,\qquad
\nu_i'=\nu_i+\kappa_b,\qquad
\nu_{i+1}'=\nu_{i+1}-\kappa_b',
\end{equation}
with all other coordinates unchanged.
Thus every individual bridge coordinate, and every $K_i$, is a
nondecreasing integer along the tracked sequence.
In every chart the current polynomial has support
$Nd_1+C^+$. Triangularity of incoming coordinates preserves this
lower support bound. In particular the cut just before $d_{i+1}$
gives the nonnegative deficit
\begin{equation}\label{tri:cut-deficit}
B_i=N-\sum_{j\leq i}(\nu_j+K_j)\geq0.
\end{equation}
Equation~\eqref{tri:coordinate-step} shows that $B_i$ changes only at
moves on level $i$, and then changes by $-\kappa_b'$.
If $K_i$ were positive at any stage, each subsequent complete period
would decrease $B_i$ by at least this positive integer: each bridge's
coordinate at its next move is at least its coordinate at the start
of the period. This contradicts~\eqref{tri:cut-deficit}. Therefore
$K_i\leq0$ at every stage.
Since each $\kappa_b$ is nondecreasing and their level sum is bounded
above by zero, each $\kappa_b$ is bounded above as well; one may use
the initial lower bounds for the other bridge coordinates on its
level. All these integer sequences stabilize. From that time on
every $t$ is zero, and the \emph{lattice vector} of the tracked label
is a fixed vector $m_*$. Its anchor coordinates in the moving
vertex basis need not be fixed.
At the event originally named $b$ on level $i$, the root in period
$L$ is $b-d_i+L\delta_i$. For all sufficiently large $L$ its pairing
with $m_*$ is nonnegative. Its slope as a function of $L$ is
\begin{equation}\label{tri:concavity}
\Omega(\delta_i,m_*)=2K_i-K_{i-1}-K_{i+1}\geq0.
\end{equation}
Indeed $\delta_i$ pairs by $2$ with a bridge on level $i$, by $-1$
with a bridge on either neighboring level, and by zero with all
other vertices. The sequence $K_0,\ldots,K_D$ is therefore discretely
concave. With zero endpoints it lies above the zero chord, so
$K_i\geq0$. Together with $K_i\leq0$, this proves $K_i=0$.
The slopes in~\eqref{tri:concavity} now vanish. Consequently $m_*$
pairs with every original event root just as it does with its late
counterparts; all these pairings are nonnegative. It is fixed by
every tropical step, including the earlier ones. Each map
$T_p(x)=x+[-\Omega(p,x)]_+p$ is invertible, with inverse
$x\mapsto x-[-\Omega(p,x)]_+p$, because adding $p$ leaves its pairing
with $p$ unchanged. Applying these inverses recovers the same $m_*$
at every earlier stage. This proves~\eqref{tri:stationary-conditions}
for the original label.
For a pure label, $\xi_{j,i}=\mu_i-\mu_{i+1}$, so its coordinates
decrease. The last cut in~\eqref{tri:cut-deficit} says $\mu_D\geq0$.
Weight is unchanged by every operation, hence $\sum_i\mu_i=N$.
\end{proof}
\begin{example}\label{tri:mixed-stationary}
Stationarity permits mixed labels. For $D=3$ the phase order is
$b_{2,2},b_{1,1},b_{1,2}$, and
\[
m=d_2+b_{1,2}-b_{2,2}
\]
satisfies $K_1=K_2=0$ and
$\xi_{1,1}=\xi_{2,2}=\xi_{1,2}=0$. Moreover,
\[
m-d_1=(b_{1,1}-d_1)+(d_2-b_{1,1})+(b_{1,2}-b_{2,2})\in C^+.
\]
It is therefore a stationary candidate of weight $1$, although its
$b_{2,2}$ coordinate is negative. Its incoming coefficient in $U$
will be excluded by a separate argument.
\end{example}
\begin{lemma}[Pure coefficient extraction]\label{tri:pure}
Let $P$ be a homogeneous symmetric polynomial of degree $N$, and let
$m=\sum_i\mu_i d_i$ with
$\mu_1\geq\cdots\geq\mu_D\geq0$ and $\sum_i\mu_i=N$.
For commuting indeterminates $z_1,\ldots,z_D$,
\begin{equation}\label{tri:pure-formula}
A_m(P(Y))=[z_1^{\mu_1}\cdots z_D^{\mu_D}]P(z_1,\ldots,z_D).
\end{equation}
\end{lemma}
\begin{proof}
We choose a single sufficiently large integer $L$ after fixing the
finite set of possible increments for this coefficient.
Since $m-Nd_1\in C^+$, that set is
\begin{equation}\label{tri:finite-candidates}
\mathcal R_m=\{r\in C^+:00,
\qquad \Omega(p_b^{(\ell)},m)=\mu_i-\mu_{i+1}\geq0.
\]
Hence the entire ray $Q_L+sV(m)$, $s\geq0$, lies on the identity
side of all these cuts. Repeated application of
Theorem~\ref{wall:mutation} identifies the wall systems there by
the identity on lattice vectors, and identifies the section at
$Q_L$ with the finite graph polynomial in the chart after $L$
periods.
Consider a wall capable of changing the coefficient of $X_m$ along
this ray. Any positive increment on its ray belongs to
$\mathcal R_m$: the starting exponent is at least $Nd_1$ in the
original cone. Furthermore an actual contributing wall root belongs
to $C_L^+$, by the successive identity-side wall identifications.
This assertion concerns the roots on those walls; it does not assert
an inclusion between the entire old and new cones.
For $r\in\mathcal R_m$, write its original coordinates as
$\nu_i(r),\kappa_b(r)$ and put
\[
P_i(r)=\sum_{j\leq i}(\nu_j(r)+K_j(r)).
\]
As a \emph{fixed vector} reexpressed after $L$ periods, $r$ has
unchanged bridge coordinates and anchor coordinates
\begin{equation}\label{tri:moving-prefix}
\nu_i^{(L)}(r)=\nu_i(r)+L\bigl(K_i(r)-K_{i-1}(r)\bigr).
\end{equation}
Thus its moved prefix is $P_i(r)+LK_i(r)$. A weight-zero member of
$C_L^+$ has nonpositive prefixes, giving
$P_i(r)+LK_i(r)\leq0$.
Choose $L$ larger than all $-P_i(r)$ for $r\in\mathcal R_m$ and
$1\leq i1$, as the assertion for $D=1$ is immediate. Take any
label $m$ with $A_m(U)\ne0$. By the support bound and
Lemma~\ref{tri:stationary}, the vector $m-d_1$ is a nonnegative
integer combination of the forward gaps, its bridge totals $K_i$
vanish, and all $\xi_{j,i}$ are nonnegative.
On level $i$, let $u_{j,i}$ be the coefficient of the gap immediately
following $b_{j,i}$ in~\eqref{tri:level-list}. Put $a_i=u_{1,i}$,
and $a_0=0$. The sum of the bridge coordinates on that level is
the first gap coefficient minus the last gap coefficient. Thus
$K_i=0$ says that the initial gap $b_{i,i}-d_i$ also has coefficient
$a_i$. In particular both end gaps are included in this notation.
Figure~\ref{tri:gap-figure} illustrates these coefficients.
All the $u_{j,i}$ and $a_i$ are nonnegative integers.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[x=0.9cm,y=0.8cm,>=stealth]
\foreach \x/\name in {0/d_1,2/b_{1,1},4/d_2,6/b_{2,2},8/b_{1,2},10/d_3}
{\fill (\x,0) circle (1.6pt);\node[above=5pt] at (\x,0) {$\name$};}
\draw[->] (0.12,0)--node[below=5pt] {$a_1$}(1.88,0);
\draw[->] (2.12,0)--node[below=5pt] {$a_1$}(3.88,0);
\draw[->] (4.12,0)--node[below=5pt] {$a_2$}(5.88,0);
\draw[->] (6.12,0)--node[below=5pt] {$u_{2,2}$}(7.88,0);
\draw[->] (8.12,0)--node[below=5pt] {$a_2$}(9.88,0);
\node at (2,-1.1) {level $1$};
\node at (7,-1.1) {level $2$};
\end{tikzpicture}
\caption{The gap coefficients for $D=3$. The horizontal order is time
order, drawn schematically; phase order is
$b_{2,2},b_{1,1},b_{1,2}$. Vanishing bridge totals equate the two
end coefficients on each level.}
\label{tri:gap-figure}
\end{figure}
We spell out the pairing calculation underlying the recurrence.
For $p=b_{j,i}-d_i$, its values on the same-level bridges are $2$
before $b_{j,i}$, $1$ at $b_{j,i}$, and $0$ after it. On bridges
of a neighboring level its values are $-1$ before this phase and
$0$ after it. Its anchor values are $1$ at $d_i$, $-1$ at
$d_{i+1}$, and zero elsewhere.
Evaluate these values on successive differences.
The contribution on its own level is minus the two gaps adjacent to
$b_{j,i}$: the additional contributions from the two end gaps cancel
because their coefficients agree. On level $i-1$ the same endpoint
cancellation leaves the coefficient of the gap containing the phase
of $b_{j,i}$; on level $i+1$ that coefficient is obtained directly.
The contribution of the initial $d_1$ is $\boldsymbol1_{i=1}$.
With nonexistent terms interpreted as zero, this gives
\begin{equation}\label{tri:gap-pairing}
\begin{split}
\xi_{j,i}={}&\boldsymbol1_{i=1}-u_{j,i}
-\begin{cases}u_{j+1,i},&jj).
\end{aligned}
\end{equation}
Each row of $T$ is weakly decreasing and ends in
$T_{j,n_0}=u_{j,n_0}\geq0$. Hence every $T_{j,i}\geq0$.
The row-start inequalities then give $a_1\leq1$ and
$a_j\leq a_{j-1}$ for $j>1$. Integrality shows that
\[
a_1,\ldots,a_{n_0}=\underbrace{1,\ldots,1}_{e},0,\ldots,0
\]
for some $0\leq e\leq n_0$.
The case $e=n_0$ is impossible: every row-start upper bound in
Equation~\eqref{tri:gap-recurrence} would be zero, giving $T=0$
and then $u=0$, contrary to $a_1=1$.
All rows of $T$ except row $e+1$ have zero row-start upper bound.
Row $e+1$ has upper bound $1$, so its nonzero entries form an
initial stretch of ones in columns $e+1,\ldots,t$, for some
$e\leq t\leq n_0$; $t=e$ denotes an empty stretch.
The definition of $T$ telescopes along southeast diagonals:
\begin{equation}\label{tri:diagonal-recovery}
u_{j,i}=\sum_{a\geq0}T_{j+a,i+a}.
\end{equation}
In particular $u_{1,i}=a_i$ is $1$ exactly for $1\leq i\leq t-e$.
Comparison with its already known run of length $e$ gives
$t=2e$. Thus every positive gap coefficient is on a level
$i\leq2e$. From~\eqref{tri:gap-recurrence}, a positive $\xi_{j,i}$
can occur only at the drop after this stretch, in level $2e+1$
(if that level exists). In particular all $\xi_{j,i}$ on a
positively used level are zero. When $e=0$, every gap coefficient is
zero and the possible positive value is the initial term $\xi_{1,1}$;
thus the same conclusion includes the empty stretch.
Every positively used forward root therefore pairs trivially with
$m$. For an interior gap its pairing is the difference of the
two adjacent $\xi$ values; for the first gap it is $\xi_{i,i}$.
For the last gap it is
\[
\Omega(d_{i+1}-b_{1,i},m)
=\Omega(\delta_i,m)-\xi_{1,i}=0,
\]
since $K=0$ gives $\Omega(\delta_i,m)=0$ by
Equation~\eqref{tri:concavity}. This verifies both end gaps as well
as the interior ones.
A wall increment capable of changing $[X_m]$ lies in the finite
interval $00.
\]
Every section in this expansion has nonnegative coefficients in
every chamber by Theorem~\ref{wall:positivity}. Retaining the one
displayed summand therefore gives~\eqref{tri:positive-domination}.
The right side is a finite Laurent polynomial with nonnegative
vertex exponents and nonnegative integral coefficients in $v$.
No coefficient outside that finite support, and no negative
vertex coordinate, can occur in the retained positive summand.
This proves all the claims, including finiteness of its Laurent
coefficients. The case $N=0$ is the identity section.
\end{proof}
\begin{theorem}[Monomial sections]\label{tri:monomial}
For every partition $\lambda$ with at most $D$ parts, padded by
zeroes to length $D$, one has in the all-negative chamber
\begin{equation}\label{tri:monomial-identity}
m_\lambda(Y)=\Theta_{\sum_{i=1}^D\lambda_i d_i}.
\end{equation}
In particular,
\begin{equation}\label{tri:elementary-identity}
E_k=\Theta_{d_1+\cdots+d_k}\qquad(0\leq k\leq D).
\end{equation}
\end{theorem}
\begin{proof}
For $D=1$ the cone is trivial and the assertion is immediate.
Otherwise set $N=|\lambda|$ and $x_\lambda=\sum_i\lambda_i d_i$.
The polynomial $m_\lambda(Y)$ has nonnegative vertex exponents:
it is a polynomial in the independent-set generators, each of
which has this support property. This assertion concerns its
exponent support and does not assume coefficient positivity.
Lemma~\ref{tri:domination} already gives the same support property
for $\Theta_{x_\lambda}$.
By Lemmas~\ref{tri:stationary} and~\ref{tri:pure}, the pure
incoming coefficients of $m_\lambda(Y)$ are $1$ at $x_\lambda$
and zero at every other pure label. Indeed $m_\lambda$ is the
sum of the distinct ordinary monomials in the orbit of $\lambda$,
and that orbit contains exactly one dominant vector.
Subtract the indicated section and write
\[
F=m_\lambda(Y)-\Theta_{x_\lambda}.
\]
Its ordinary support still has nonnegative vertex coordinates,
all its pure incoming coefficients vanish, and both its ordinary
and incoming support lie in $Nd_1+C^+$.
If an incoming coefficient remains nonzero, its label $m$ is
mixed and satisfies $K_i(m)=0$ by Lemma~\ref{tri:stationary};
subtracting $\Theta_{x_\lambda}$ changes only one pure incoming
coefficient. A nonzero bridge-coordinate vector with zero sum
on each level has some negative bridge coordinate.
Among all remaining labels choose one with minimum height in
$Nd_1+C^+$, where the height is the sum of its nonnegative simple
root coordinates. A minimum exists in $\N$, even if the incoming
expansion is infinite. Incoming triangularity says that the
ordinary coefficient at this label equals its incoming
coefficient plus contributions from strictly lower incoming
labels. There are no such nonzero lower terms by the choice of
height. Hence $[X_m]F=A_m(F)\ne0$, contradicting the negative
bridge coordinate of $m$ and the vertex support already proved.
No coefficient remains, proving~\eqref{tri:monomial-identity}.
Finally $m_{(1^k)}=e_k$ gives~\eqref{tri:elementary-identity}.
\end{proof}
\begin{corollary}[Elementary positivity]\label{tri:positivity}
Let $G$ be a natural unit interval graph on $n$ vertices, and put
$M=|E(G)|$. In its elementary expansion
\[
\chi_G(X;q)=\sum_{\lambda\vdash n}c_\lambda(q)e_\lambda(X),
\]
every $c_\lambda(q)$ belongs to $\N[q]$ and has degree at most $M$.
For a triangular embedding with $D\geq n$, let $u$ be the sum of the
selected vertex exponents and set $x_\lambda=\sum_i\lambda_i d_i$,
padding $\lambda$ by zeroes. Then
\begin{equation}\label{tri:positive-coefficient}
[X_u]\Theta_{x_\lambda}^{H_-}
=v^{-M}c_\lambda(v^2)
\in\sum_{d=0}^{M}\N v^{2d-M},
\end{equation}
where $H_-$ is the all-negative chamber.
\end{corollary}
\begin{proof}
Choose the embedding of Lemma~\ref{tri:embedding}, taking $D\geq n$.
Proposition~\ref{graph:kernel}, Lemma~\ref{graph:reciprocity}, and
Theorem~\ref{tri:monomial} give
\[
c_\lambda(v^2)=v^M[X_u]m_\lambda(Y)
=v^M[X_u]\Theta_{x_\lambda}^{H_-}.
\]
The last expression has nonnegative integral coefficients at every
power of $v$ by Theorem~\ref{wall:positivity}.
On the other hand, the coloring definition has $q$-degree at most
$M$. In any number of variables at least $n$, the elementary
monomials form an integral basis in degree $n$; symmetry therefore
gives $c_\lambda(q)\in\Z[q]$ of degree at most $M$.
Comparing these finite polynomials with the displayed Laurent-series
identity proves coefficientwise nonnegativity and
Equation~\eqref{tri:positive-coefficient}.
\end{proof}
This completes the coefficientwise positivity assertion. The remaining
construction assigns a partition to each individual graph-nondescent
permutation and proves the weight-preserving formula in
Theorem~\ref{main:theorem}. The finite coefficient bounds in
Equation~\eqref{tri:positive-coefficient} will also bound the histories
used by that construction.
==== END Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//05-triangle.tex ====
==== BEGIN Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//06-witness.tex ====
\section{A finite witness on individual words}
\label{route:section}
Corollary~\ref{tri:positivity} proves positivity of the elementary
coefficients. We now construct the partition assigned to each individual
word. The construction matches ordered packets of vertices with finite
wall histories and anchor words; the anchor multiplicities specify the
partition. Its local matchings use coefficients of elementary sections
and individual wall operators, without taking the final elementary
coefficient list as input.
Fix a triangular embedding with $D\geq\max\{1,n\}$, put $N=n$, and
let $u$ be the sum of the indicated vertex exponents. Write $H_-$ for its all-negative chamber,
$M=|E(G)|$, and
\[
R=u-Nd_1\in C^+,
\qquad B=\{y:Nd_1\leq y\leq u\}.
\]
The order in this display is the free-cone order. If
$R=\sum_{c\in C}R_c c$, set $h(R)=\sum_c R_c$.
The set $B$ has $\prod_c(R_c+1)$ elements. Only wall roots $00$, and the crossing is from positive to negative.
At each crossing, the coefficient of $X_x$ gains only nonnegative
contributions from lower exponents, with its old coefficient
retained by the zero jump. Its starting and ending coefficients
are the same constant $a_{\boldsymbol k,\mu}$. Coefficientwise
positivity forces every gain along this finite path to be zero.
It follows that, in Equation~\eqref{route:switch-equation} for these product
states at $x$, only the zero-total-jump part occurs at every wall.
The switches consequently give bijections all the way to the
literal anchor tuples in $H_-$. Reversing the selected path gives
the inverse. All intermediate choices can be fixed by the rational
ordering above; they may use the composition but add no total jump
to the recorded history. The history determines its terminal
testing chamber, so the inverse loses no data.
\end{proof}
\begin{proposition}[Formal degree bounds]
\label{route:parity}
For every partition $\mu\vdash N$, histories in $T_{x_\mu}$ have
\begin{equation}
\label{route:parity-range}
-M\leq E(t)\leq M,\qquad E(t)\equiv M\pmod 2.
\end{equation}
Consequently $T_{x_\mu}$ is finite, and
$v^M[X_u]\Theta_{x_\mu}^{H_-}$ belongs to $\N[q]$ with $q=v^2$
and degree at most $M$.
\end{proposition}
\begin{proof}
Equation~\eqref{route:history-series} identifies the history enumerator
with $[X_u]\Theta_{x_\mu}^{H_-}$. By
Equation~\eqref{tri:positive-coefficient}, this coefficient is
$v^{-M}c_\mu(v^2)$, where $c_\mu(q)\in\N[q]$ has degree at most $M$.
Its allowed powers of $v$ are therefore exactly among
$-M,-M+2,\ldots,M$. Histories have nonnegative multiplicities, so
none can occur at any other energy. Each of these finitely many
energy slices is finite by Lemma~\ref{route:finite}; hence their
union $T_{x_\mu}$ is finite as well. Multiplication by $v^M$ changes
each history weight to $q^{(E(t)+M)/2}$, proving the assertion.
\end{proof}
\subsection{Required masks and exact masks}
\label{route:masks}
For a permutation word $w=w_1\cdots w_N$ on the indicated vertices,
define its nonedge ascent mask by
\[
\mathcal P_G(w)=
\{j: w_j=Latex,
vertex/.style={draw,rounded corners,inner sep=4pt,font=\small}]
\node[vertex] (l0) at (0,1.3) {$w:\ J$};
\node[vertex] (r1) at (2,0) {$(t_1,s_1):K_1$};
\node[vertex] (l1) at (4,1.3) {$w_1:K_1$};
\node[vertex] (r2) at (6,0) {$(t_2,s_2):K_2$};
\node[vertex] (l2) at (8,1.3) {$w_2:K_2$};
\node[vertex] (r0) at (10,0) {$(t,s):J$};
\draw[->,thick] (l0)--node[above,sloped,font=\small] {$B_J$} (r1);
\draw[->,thick,dashed] (r1)--node[above,sloped,font=\small]
{$\Phi_{K_1}^{-1}$} (l1);
\draw[->,thick] (l1)--node[above,sloped,font=\small] {$B_J$} (r2);
\draw[->,thick,dashed] (r2)--node[above,sloped,font=\small]
{$\Phi_{K_2}^{-1}$} (l2);
\draw[->,thick] (l2)--node[above,sloped,font=\small] {$B_J$} (r0);
\node[font=\small,align=center] at (5,-0.9)
{$K_i\supsetneq J$ at every interior pair; endpoints have exact mask $J$.\\
Solid: required-mask matching.\quad Dashed: larger exact-mask matching.};
\end{tikzpicture}
\caption{The exact-mask algorithm follows a finite alternating path.
An endpoint cannot enter a cycle in the union of two matchings.}
\label{route:matching-figure}
\end{figure}
\subsection{The partition assigned to a word}
\label{route:algorithm}
Let $\mathcal A_G=\{w:\mathcal P_G(w)=\varnothing\}$ be the
admissible domain. For $w\in\mathcal A_G$, compute
\[
\Phi_{\varnothing}(w)=(t,s),\qquad t\in T_{x_\mu},
\qquad \Lambda_G(w)=\mu.
\]
The finite algorithm on an individual input has four steps.
\begin{enumerate}
\item Construct the triangular embedding and finite cone interval, and
fix the common rational path representatives for every required $(H,y)$
before choosing any packet composition.
\item For each required mask encountered, form its packets and evaluate
$B_J$ through the local packet switches, common histories, and return
to anchor subsets. Positive and negative packets use the two directions
of the local switch, although the total jump has the positive sign.
\item Evaluate $\Phi_{\varnothing}$ by the exact-mask recursion in
Lemma~\ref{route:exact}, following its alternating walk until the output
has exact empty mask.
\item Read the multiplicities of the resulting weakly decreasing anchor
word as the partition $\Lambda_G(w)$.
\end{enumerate}
Nested calls strictly increase mask size, while each outer repetition
follows an endpoint path in the finite union of two matchings. Thus the
call depth is bounded and each alternating walk terminates. There is
no need to enumerate the final fibers of $\Lambda_G$ or to supply the
final elementary coefficients. Section~\ref{main:completion} gives the
reversal for the original input convention.
If the input is supplied in the insertion digits of
Lemma~\ref{graph:digits}, first decode those digits by largest-vertex
insertions. The construction then uses the resulting admissible
word. Empty input is assigned the empty partition.
\begin{theorem}[Permutation witness]
\label{route:witness}
For every naturally labeled unit interval graph $G$, the preceding
finite rule assigns a partition $\Lambda_G(w)\vdash n$ to each
$w\in\mathcal A_G$ and satisfies the formal polynomial identity
\begin{equation}
\label{route:witness-identity}
X_G(X;q)=\sum_{w\in\mathcal A_G}
q^{\inv_G(w)}e_{\Lambda_G(w)}(X).
\end{equation}
In particular, every elementary coefficient is in $\N[q]$ and has
degree at most $|E(G)|$.
\end{theorem}
\begin{proof}
For any padded partition $\mu$, exactly one word of multiplicities
$(\mu_1,\ldots,\mu_D)$ has no strict ascent: the weakly decreasing
word. This remains true when parts of $\mu$ repeat, since the
anchor indices themselves are distinct labels. Consequently
$\Phi_{\varnothing}$ identifies the individual words of shape
$\mu$ with $T_{x_\mu}$. Energy preservation,
Equation~\eqref{route:word-energy}, and Equation~\eqref{route:history-series} give
\[
\sum_{\substack{w\in\mathcal A_G\\\Lambda_G(w)=\mu}}
v^{2\inv_G(w)-M}
=\sum_{t\in T_{x_\mu}}v^{E(t)}
=[X_u]\Theta_{x_\mu}^{H_-}
=[X_u]m_\mu(Y).
\]
Multiply by $v^M$. The conversion $q=v^2$ is legitimate as a
formal polynomial conversion by
Proposition~\ref{route:parity}, including both its parity and its
degree bounds. The coefficient identity of
Proposition~\ref{graph:kernel} now identifies the right side with
$[e_\mu]X_G(X;q)$. This proves the identity for each shape and
hence Equation~\eqref{route:witness-identity}. The algorithms producing
$\Lambda_G(w)$ use only elementary packets and local wall jumps;
the coefficient identity certifies their output.
\end{proof}
==== END Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//06-witness.tex ====
==== BEGIN Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//07-completion.tex ====
\section{The chromatic expansion}
\label{main:completion}
We return to the original graph and its graph-nondescent permutations.
\begin{proof}[Proof of Theorem~\ref{main:theorem}]
Choose the triangular embedding of Lemma~\ref{tri:embedding}, and
fix the rational generic choices and finite local orders in
Section~\ref{route:section} by the enumeration specified there.
Theorem~\ref{route:witness} gives a terminating map
$\Lambda_G:\mathcal A_G\to\{\lambda:\lambda\vdash n\}$ with
\[
\sum_{\substack{w\in\mathcal A_G\\\Lambda_G(w)=\lambda}}
q^{\inv_G(w)}
=[e_\lambda]X_G(X;q)=c_\lambda(q).
\]
For $\sigma\in D_G^0$ define
\[
\theta_G(\sigma)=\Lambda_G(\operatorname{reverse}\sigma).
\]
By Lemma~\ref{graph:digits}, reversal gives the required input to
$\Lambda_G$ and complements graph inversions. Lemma~\ref{graph:reciprocity}
then gives, for every $\lambda$,
\[
\sum_{\substack{\sigma\in D_G^0\\\theta_G(\sigma)=\lambda}}
q^{\ginv_G(\sigma)}
=q^M c_\lambda(q^{-1})=c_\lambda(q).
\]
Together with $X_G=\chi_G$, this proves
Equation~\eqref{main:witness}. Every coefficient is the generating
polynomial of a finite set, so it belongs to $\N[q]$. All choices and
all recursions are finite procedures for each input. For $n=0$, take
the empty graph, the empty permutation and the empty partition.
\end{proof}
\begin{remark}[Scope of the algorithm]
The map uses the graph, the input permutation, finite wall recursions
and local coefficient indexings. The elementary coefficient list is
not supplied to it. The result proves termination, but gives no
polynomial-time bound. The construction is a mathematical algorithm
based on finite rational arithmetic and ordered finite sets.
\end{remark}
==== END Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//07-completion.tex ====
==== BEGIN Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//paper.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1.05in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{booktabs,array}
\usepackage{graphicx}
\usepackage{flafter}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc,decorations.pathreplacing}
\usepackage[numbers,sort&compress]{natbib}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\hypersetup{pdftitle={Elementary positivity of chromatic quasisymmetric functions},pdfauthor={OpenAI},pdfsubject={Elementary positivity and terminating permutation witnesses for natural unit interval graphs}}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\cF}{\mathcal F}
\DeclareMathOperator{\gr}{gr}
\DeclareMathOperator{\Hilb}{Hilb}
\DeclareMathOperator{\Ad}{Ad}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\ginv}{ginv}
\DeclareMathOperator{\inv}{inv}
\setlist{itemsep=3pt,topsep=5pt}
\setlength{\emergencystretch}{2em}
\title{Elementary positivity of chromatic\\quasisymmetric functions}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that the chromatic quasisymmetric function of every natural unit
interval graph is elementary-positive over $\N[q]$. This resolves the
elementary-positivity part of the Shareshian--Wachs conjecture.
\end{abstract}
\tableofcontents
\input{sections/01-introduction}
\input{sections/02-graphs}
\input{sections/03-reordering}
\input{sections/04-walls}
\input{sections/05-triangle}
\input{sections/06-witness}
\input{sections/07-completion}
\clearpage
\bibliographystyle{plainnat}
\bibliography{references}
\end{document}
==== END Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//paper.tex ====
==== BEGIN Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//references.bib ====
@article{SW16,
author = {Shareshian, John and Wachs, Michelle L.},
title = {Chromatic quasisymmetric functions},
journal = {Advances in Mathematics},
volume = {295},
year = {2016},
pages = {497--551},
doi = {10.1016/j.aim.2015.12.018},
eprint = {1405.4629v2},
archivePrefix = {arXiv},
primaryClass = {math.CO},
url = {https://arxiv.org/abs/1405.4629v2},
note = {Version consulted: arXiv:1405.4629v2, 29 March 2016}
}
@article{SS93,
author = {Stanley, Richard P. and Stembridge, John R.},
title = {On immanants of {Jacobi--Trudi} matrices and permutations
with restricted position},
journal = {Journal of Combinatorial Theory, Series A},
volume = {62},
year = {1993},
pages = {261--279},
doi = {10.1016/0097-3165(93)90048-D},
url = {https://math.mit.edu/~rstan/pubs/pubfiles/87.pdf}
}
@misc{GP13,
author = {Guay-Paquet, Mathieu},
title = {A modular law for the chromatic symmetric functions
of {$(3+1)$}-free posets},
year = {2013},
eprint = {1306.2400v1},
archivePrefix = {arXiv},
primaryClass = {math.CO},
doi = {10.48550/arXiv.1306.2400},
url = {https://arxiv.org/abs/1306.2400v1},
note = {arXiv:1306.2400v1, 11 June 2013}
}
@misc{Hik24,
author = {Hikita, Tatsuyuki},
title = {A proof of the {Stanley--Stembridge} conjecture},
year = {2025},
eprint = {2410.12758v2},
archivePrefix = {arXiv},
primaryClass = {math.CO},
doi = {10.48550/arXiv.2410.12758},
url = {https://arxiv.org/abs/2410.12758v2},
note = {arXiv:2410.12758v2, 25 December 2025; first posted in 2024}
}
@article{Ath15,
author = {Athanasiadis, Christos A.},
title = {Power sum expansion of chromatic quasisymmetric functions},
journal = {The Electronic Journal of Combinatorics},
volume = {22},
number = {2},
year = {2015},
pages = {P2.7},
doi = {10.37236/4761},
eprint = {1409.2595v2},
archivePrefix = {arXiv},
primaryClass = {math.CO},
url = {https://arxiv.org/abs/1409.2595v2},
note = {Version consulted: arXiv:1409.2595v2, 26 April 2015}
}
@article{DM21,
author = {Davison, Ben and Mandel, Travis},
title = {Strong positivity for quantum theta bases of quantum
cluster algebras},
journal = {Inventiones mathematicae},
volume = {226},
year = {2021},
pages = {725--843},
doi = {10.1007/s00222-021-01061-1},
eprint = {1910.12915v3},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1910.12915v3},
note = {Version consulted: arXiv:1910.12915v3, 15 June 2021}
}
@article{Ef12,
author = {Efimov, Alexander I.},
title = {Cohomological {Hall} algebra of a symmetric quiver},
journal = {Compositio Mathematica},
volume = {148},
year = {2012},
pages = {1133--1146},
doi = {10.1112/S0010437X12000152},
eprint = {1103.2736v2},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1103.2736v2},
note = {Version consulted: arXiv:1103.2736v2, 24 March 2011}
}
@article{DMe20,
author = {Davison, Ben and Meinhardt, Sven},
title = {Cohomological {Donaldson--Thomas} theory of a quiver
with potential and quantum enveloping algebras},
journal = {Inventiones mathematicae},
volume = {221},
year = {2020},
pages = {777--871},
doi = {10.1007/s00222-020-00961-y},
eprint = {1601.02479v5},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1601.02479v5},
note = {Version consulted: arXiv:1601.02479v5, 6 March 2020}
}
@article{FR18,
author = {Franzen, Hans and Reineke, Markus},
title = {Semistable {Chow--Hall} algebras of quivers and quantized
{Donaldson--Thomas} invariants},
journal = {Algebra \& Number Theory},
volume = {12},
number = {5},
year = {2018},
pages = {1001--1025},
doi = {10.2140/ant.2018.12.1001},
eprint = {1512.03748v2},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1512.03748v2},
note = {Versions consulted: arXiv:1512.03748v2, 21 April 2016,
and the published article; theorem numbering follows the latter}
}
@article{Sta95,
author={Stanley, Richard P.},
title={A symmetric function generalization of the chromatic polynomial of a graph},
journal={Advances in Mathematics}, volume={111}, number={1}, year={1995}, pages={166--194},
doi={10.1006/aima.1995.1020}, url={https://math.mit.edu/~rstan/pubs/pubfiles/100.pdf}
}
@article{Hai93,
author={Haiman, Mark}, title={Hecke algebra characters and immanant conjectures},
journal={Journal of the American Mathematical Society}, volume={6}, number={3}, year={1993}, pages={569--595},
doi={10.1090/S0894-0347-1993-1186961-9}, url={https://math.berkeley.edu/~mhaiman/ftp/heckeimm/jams1.pdf}
}
@article{Gas96,
author={Gasharov, Vesselin}, title={Incomparability graphs of {$(3+1)$}-free posets are {$s$}-positive},
journal={Discrete Mathematics}, volume={157}, number={1--3}, year={1996}, pages={193--197},
doi={10.1016/S0012-365X(96)83014-7}
}
@article{Cho99,
author={Chow, Timothy Y.},
title={Descents, quasi-symmetric functions, {Robinson--Schensted} for posets, and the chromatic symmetric function},
journal={Journal of Algebraic Combinatorics}, volume={10}, number={3}, year={1999}, pages={227--240},
doi={10.1023/A:1018719315718}, url={https://timothychow.net/descents.pdf}
}
@incollection{SW12,
author={Shareshian, John and Wachs, Michelle L.}, title={Chromatic quasisymmetric functions and {Hessenberg} varieties},
booktitle={Configuration Spaces}, series={CRM Series}, publisher={Edizioni della Normale}, address={Pisa},
year={2012}, pages={433--460}, doi={10.1007/978-88-7642-431-1_20},
eprint={1106.4287}, archivePrefix={arXiv}, url={https://arxiv.org/abs/1106.4287}
}
@incollection{Tym08,
author={Tymoczko, Julianna S.}, title={Permutation actions on equivariant cohomology of flag varieties},
booktitle={Toric Topology}, series={Contemporary Mathematics}, volume={460}, publisher={American Mathematical Society},
year={2008}, pages={365--384}, doi={10.1090/conm/460/09030},
eprint={0706.0460}, archivePrefix={arXiv}, url={https://arxiv.org/abs/0706.0460},
note={Preprint title: Permutation actions on equivariant cohomology}
}
@article{BC18,
author={Brosnan, Patrick and Chow, Timothy Y.},
title={Unit interval orders and the dot action on the cohomology of regular semisimple {Hessenberg} varieties},
journal={Advances in Mathematics}, volume={329}, year={2018}, pages={955--1001},
doi={10.1016/j.aim.2018.02.020}, eprint={1511.00773}, archivePrefix={arXiv},
url={https://timothychow.net/hessenberg.pdf}
}
@misc{GP16,
author={Guay-Paquet, Mathieu}, title={A second proof of the {Shareshian--Wachs} conjecture, by way of a new {Hopf} algebra},
year={2016}, eprint={1601.05498}, archivePrefix={arXiv}, url={https://arxiv.org/abs/1601.05498}
}
@article{HP19,
author={Harada, Megumi and Precup, Martha E.},
title={The cohomology of abelian {Hessenberg} varieties and the {Stanley--Stembridge} conjecture},
journal={Algebraic Combinatorics}, volume={2}, number={6}, year={2019}, pages={1059--1108},
doi={10.5802/alco.76}, eprint={1709.06736}, archivePrefix={arXiv}, url={https://www.numdam.org/articles/10.5802/alco.76/}
}
@article{CH19,
author={Cho, Soojin and Huh, JiSun},
title={On {$e$}-positivity and {$e$}-unimodality of chromatic quasi-symmetric functions},
journal={SIAM Journal on Discrete Mathematics}, volume={33}, number={4}, year={2019}, pages={2286--2315},
doi={10.1137/18M1216201}, eprint={1711.07152v2}, archivePrefix={arXiv}, url={https://arxiv.org/abs/1711.07152v2}
}
@article{HNY20,
author={Huh, JiSun and Nam, Sun-Young and Yoo, Meesue},
title={Melting lollipop chromatic quasisymmetric functions and {Schur} expansion of unicellular {LLT} polynomials},
journal={Discrete Mathematics}, volume={343}, number={3}, year={2020}, pages={111728},
doi={10.1016/j.disc.2019.111728}, eprint={1812.03445}, archivePrefix={arXiv}, url={https://meesue.github.io/LLT_DM.pdf}
}
@article{AN21,
author={Abreu, Alex and Nigro, Antonio}, title={Chromatic symmetric functions from the modular law},
journal={Journal of Combinatorial Theory, Series A}, volume={180}, year={2021}, pages={105407},
doi={10.1016/j.jcta.2021.105407}, eprint={2006.00657v2}, archivePrefix={arXiv}, url={https://arxiv.org/abs/2006.00657v2}
}
@article{CMP23,
author={Colmenarejo, Laura and Morales, Alejandro H. and Panova, Greta},
title={Chromatic symmetric functions of {Dyck} paths and {$q$}-rook theory},
journal={European Journal of Combinatorics}, volume={107}, year={2023}, pages={103595},
doi={10.1016/j.ejc.2022.103595}, eprint={2104.07599}, archivePrefix={arXiv}, url={https://arxiv.org/abs/2104.07599}
}
@article{GS01,
author={Gebhard, David D. and Sagan, Bruce E.}, title={A chromatic symmetric function in noncommuting variables},
journal={Journal of Algebraic Combinatorics}, volume={13}, number={3}, year={2001}, pages={227--255},
doi={10.1023/A:1011258714032}, eprint={math/9907076}, archivePrefix={arXiv},
url={https://arxiv.org/abs/math/9907076}
}
@article{KS11,
author = {Kontsevich, Maxim and Soibelman, Yan},
title = {Cohomological {Hall} algebra, exponential {Hodge} structures and motivic {Donaldson--Thomas} invariants},
journal = {Communications in Number Theory and Physics},
volume = {5},
number = {2},
year = {2011},
pages = {231--352},
doi = {10.4310/CNTP.2011.v5.n2.a1},
eprint = {1006.2706v2},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1006.2706v2},
note = {Version consulted: arXiv:1006.2706v2, 11 July 2011}
}
@article{Rei03,
author = {Reineke, Markus},
title = {The {Harder--Narasimhan} system in quantum groups and cohomology of quiver moduli},
journal = {Inventiones mathematicae},
volume = {152},
year = {2003},
pages = {349--368},
doi = {10.1007/s00222-002-0273-4},
eprint = {math/0204059v1},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/math/0204059v1},
note = {Version consulted: arXiv:math/0204059v1, 4 April 2002}
}
@article{Rei10,
author = {Reineke, Markus},
title = {{Poisson} automorphisms and quiver moduli},
journal = {Journal of the Institute of Mathematics of Jussieu},
volume = {9},
number = {3},
year = {2010},
pages = {653--667},
doi = {10.1017/S1474748009000176},
eprint = {0804.3214v2},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/0804.3214v2},
note = {Version consulted: arXiv:0804.3214v2}
}
@incollection{KS06,
author = {Kontsevich, Maxim and Soibelman, Yan},
title = {Affine structures and non-{Archimedean} analytic spaces},
booktitle = {The Unity of Mathematics},
series = {Progress in Mathematics},
volume = {244},
publisher = {Birkh{\"a}user},
year = {2006},
pages = {321--385},
doi = {10.1007/0-8176-4467-9_9},
eprint = {math/0406564},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/math/0406564}
}
@article{GS11,
author = {Gross, Mark and Siebert, Bernd},
title = {From real affine geometry to complex geometry},
journal = {Annals of Mathematics},
volume = {174},
number = {3},
year = {2011},
pages = {1301--1428},
doi = {10.4007/annals.2011.174.3.1},
eprint = {math/0703822},
archivePrefix = {arXiv},
url = {https://annals.math.princeton.edu/2011/174-3/p01}
}
@incollection{KS14,
author = {Kontsevich, Maxim and Soibelman, Yan},
title = {Wall-crossing structures in {Donaldson--Thomas} invariants, integrable systems and mirror symmetry},
booktitle = {Homological Mirror Symmetry and Tropical Geometry},
series = {Lecture Notes of the Unione Matematica Italiana},
volume = {15},
publisher = {Springer},
year = {2014},
pages = {197--308},
doi = {10.1007/978-3-319-06514-4_6},
eprint = {1303.3253v2},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1303.3253v2},
note = {Theorem locators checked in arXiv:1303.3253v2, 12 May 2013}
}
@article{GHKK18,
author = {Gross, Mark and Hacking, Paul and Keel, Sean and Kontsevich, Maxim},
title = {Canonical bases for cluster algebras},
journal = {Journal of the American Mathematical Society},
volume = {31},
number = {2},
year = {2018},
pages = {497--608},
doi = {10.1090/jams/890},
eprint = {1411.1394v2},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1411.1394v2},
note = {Version consulted: arXiv:1411.1394v2, 28 October 2016}
}
@article{Bri17,
author = {Bridgeland, Tom},
title = {Scattering diagrams, {Hall} algebras and stability conditions},
journal = {Algebraic Geometry},
volume = {4},
number = {5},
year = {2017},
pages = {523--561},
doi = {10.14231/AG-2017-027},
eprint = {1603.00416},
archivePrefix = {arXiv},
url = {https://content.algebraicgeometry.nl/2017-5/2017-5-027.pdf}
}
@article{GM81,
author = {Garsia, Adriano M. and Milne, Stephen C.},
title = {Method for constructing bijections for classical partition identities},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
volume = {78},
number = {4},
year = {1981},
pages = {2026--2028},
doi = {10.1073/pnas.78.4.2026},
url = {https://pubmed.ncbi.nlm.nih.gov/16593004/}
}
@article{FG98,
author = {Fomin, Sergey and Greene, Curtis},
title = {Noncommutative {Schur} functions and their applications},
journal = {Discrete Mathematics},
volume = {193},
number = {1--3},
pages = {179--200},
year = {1998},
doi = {10.1016/S0012-365X(98)00140-X}
}
@article{BF17,
author = {Blasiak, Jonah and Fomin, Sergey},
title = {Noncommutative {Schur} functions, switchboards, and {Schur} positivity},
journal = {Selecta Mathematica (N.S.)},
volume = {23},
number = {1},
pages = {727--766},
year = {2017},
doi = {10.1007/s00029-016-0253-y},
eprint = {1510.00657v3},
archivePrefix = {arXiv},
primaryClass = {math.CO}
}
@article{Hwa24,
author = {Hwang, Byung-Hak},
title = {Chromatic quasisymmetric functions and noncommutative {$P$}-symmetric functions},
journal = {Transactions of the American Mathematical Society},
volume = {377},
number = {4},
pages = {2855--2896},
year = {2024},
eprint = {2208.09857v2},
archivePrefix = {arXiv},
primaryClass = {math.CO},
url = {https://arxiv.org/abs/2208.09857v2}
}
@article{BEPS25,
author = {Blasiak, Jonah and Eriksson, Holden and Pylyavskyy, Pavlo and Siegl, Isaiah},
title = {Noncommutative {Schur} functions for posets},
journal = {Selecta Mathematica (N.S.)},
volume = {31},
number = {1},
year = {2025},
note = {Article 21; version consulted: arXiv:2211.03967v2},
url = {https://arxiv.org/abs/2211.03967v2},
doi = {10.1007/s00029-024-01010-9},
eprint = {2211.03967v2},
archivePrefix = {arXiv},
primaryClass = {math.CO}
}
@misc{GMRWW25,
author = {Griffin, Sean T. and Mellit, Anton and Romero, Marino and
Weigl, Kevin and Wen, Joshua Jeishing},
title = {On {Macdonald} expansions of $q$-chromatic symmetric functions
and the {Stanley--Stembridge} Conjecture},
year = {2025},
eprint = {2504.06936},
archivePrefix = {arXiv},
primaryClass = {math.CO},
note = {Version 1, April 9, 2025},
doi = {10.48550/arXiv.2504.06936},
url = {https://arxiv.org/abs/2504.06936v1}
}
@misc{HHKKO25,
author = {Huh, JiSun and Hwang, Byung-Hak and Kim, Donghyun and
Kim, Jang Soo and Oh, Jaeseong},
title = {Refinement of {Hikita}'s $e$-positivity theorem via
{Abreu--Nigro}'s $g$-functions and restricted modular law},
year = {2025},
eprint = {2504.09123},
archivePrefix = {arXiv},
primaryClass = {math.CO},
note = {Version 1, April 12, 2025},
doi = {10.48550/arXiv.2504.09123},
url = {https://arxiv.org/abs/2504.09123v1}
}
@misc{Siegl26,
author = {Siegl, Isaiah},
title = {Toward Lower Bounds for Chromatic Symmetric Functions
in the Elementary Basis},
year = {2026},
eprint = {2509.02841},
archivePrefix = {arXiv},
primaryClass = {math.CO},
note = {Version 3, July 31, 2026},
doi = {10.48550/arXiv.2509.02841},
url = {https://arxiv.org/abs/2509.02841v3}
}
@misc{Chow26,
author = {Chow, Timothy Y.},
title = {{Foata}, {Hikita}, and the Bulldozer Problem},
year = {2026},
eprint = {2603.23879},
archivePrefix = {arXiv},
primaryClass = {math.CO},
note = {Version 3, April 10, 2026},
doi = {10.48550/arXiv.2603.23879},
url = {https://arxiv.org/abs/2603.23879v3}
}
@article{Sta98,
author = {Stanley, Richard P.},
title = {Graph colorings and related symmetric functions: ideas and applications},
journal = {Discrete Mathematics},
volume = {193},
number = {1--3},
year = {1998},
pages = {267--286},
doi = {10.1016/S0012-365X(98)00146-0},
url = {https://math.mit.edu/~rstan/papers/taor.pdf}
}
@article{Patras93,
author = {Patras, Fr{\'e}d{\'e}ric},
title = {La d{\'e}composition en poids des alg{\`e}bres de {Hopf}},
journal = {Annales de l'Institut Fourier},
volume = {43},
number = {4},
year = {1993},
pages = {1067--1087},
doi = {10.5802/aif.1365},
url = {https://www.numdam.org/item/10.5802/aif.1365.pdf}
}
==== END Elementary-Positivity-of-Chromatic-Quasisymmetric-Functions//references.bib ====