Positive elementary coefficients for refined graph colorings

← All digests

Family 169 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Counting graph colorings naturally gives positive numbers: every coloring contributes one. But when the same information is rewritten in a different mathematical basis, subtraction can appear. A central question in algebraic combinatorics asks when a more structured expansion still has only nonnegative coefficients.

Family 169 concerns a refinement that remembers an additional statistic of each coloring through a variable $q$. The manuscript claims that the chromatic quasisymmetric function of every natural unit interval graph has nonnegative integer coefficients in the elementary basis, degree by degree in $q$.

It also supplies a combinatorial explanation: a terminating procedure assigns a partition to each admissible permutation, so the elementary coefficients count permutations with specified data. The claim strengthens previously established positivity at $q=1$, but explicitly does not assert elementary unimodality.

2. Background and essential definitions

The graphs and their colorings

A natural unit interval graph can be specified by a weakly increasing integer sequence $h(1),\ldots,h(n)$ satisfying $i\le h(i)\le n$. Its vertices are $1,\ldots,n$, and

$$\{i,j\}\in E(G)\quad\Longleftrightarrow\quad i<j\le h(i)$$

for $i<j$. This ordered graph class includes paths and complete graphs. The labels carry information and are part of the definition of the refined statistic.

A proper coloring $f$ assigns a positive integer color to each vertex, with adjacent vertices receiving different colors. Let $\operatorname{asc}_G(f)$ count edges $\{i,j\}$ with $i<j$ and $f(i)<f(j)$. With variables $X=(x_1,x_2,\ldots)$, define

$$\chi_G(X;q)=\sum_{f\text{ proper}} q^{\operatorname{asc}_G(f)}\prod_{a=1}^n x_{f(a)}.$$

The monomial records how often each color is used; the power of $q$ records ascents. Although there are infinitely many color names, this is a well-defined formal homogeneous function of total degree $n$.

The elementary basis

The elementary symmetric function $e_k(X)$ is the sum of all products of $k$ distinct variables. For example, $e_1=x_1+x_2+\cdots$, while $e_2=\sum_{i<j}x_ix_j$.

A partition $\lambda=(\lambda_1,\ldots,\lambda_\ell)$ of $n$ is a nonincreasing list of positive integers summing to $n$. Put $e_\lambda=\prod_j e_{\lambda_j}$. These products form a basis for symmetric functions of degree $n$.

For the graph class above, $\chi_G$ is symmetric in the color variables and has a unique expansion

$$\chi_G(X;q)=\sum_{\lambda\vdash n}c_\lambda(q)e_\lambda(X).$$

Elementary positivity means $c_\lambda(q)\in\mathbb N[q]$: every coefficient of every power of $q$ is a nonnegative integer. This is stronger than $c_\lambda(q)\ge0$ at every positive real $q$. For instance, $q^2-q+1$ is positive for all real $q$ but has a negative coefficient.

3. Development history and previous partial results

Stanley introduced the chromatic symmetric function as a refinement of the chromatic polynomial. The latter counts proper colorings with a fixed finite palette; the symmetric function also records color multiplicities.

The Stanley–Stembridge conjecture predicts elementary positivity for incomparability graphs of $(3+1)$-free posets. An incomparability graph joins two elements when neither is below the other. The excluded pattern is a chain of three elements together with one element incomparable to all three.

Guay-Paquet’s reduction expresses those chromatic functions as nonnegative combinations of functions associated with unit interval orders. This made the graph class in the present theorem central to the older conjecture.

Shareshian and Wachs introduced the $q$-refinement and formulated elementary positivity together with an additional unimodality prediction. They proved symmetry and positivity in the Schur basis, another important basis of symmetric functions. Positivity in one basis need not survive a change to another, so that achievement did not settle the elementary question.

The refined functions also connect to the cohomology of Hessenberg varieties, spaces of flags satisfying linear-operator constraints. Brosnan–Chow and Guay-Paquet proved the representation-theoretic identity proposed in that connection. This identity is distinct from coefficientwise elementary positivity, even though both are associated with the Shareshian–Wachs program.

Hikita’s proof of the Stanley–Stembridge conjecture established the classical positivity result. M1 explains that Hikita’s formula also supplies numerical nonnegativity at positive real $q$, while its rational weights do not establish membership in $\mathbb N[q]$. The new manuscript targets that remaining graded statement and an individual permutation interpretation.

4. What the new manuscripts claim

Let $D_G^0$ be the permutations $\sigma$ of $1,\ldots,n$ in which every adjacent descent is an edge of $G$. Thus if $\sigma_i>\sigma_{i+1}$, their two labels must be adjacent in the graph.

Define the graph-inversion statistic

$$\operatorname{ginv}_G(\sigma)= \bigl|\{(i,j):i<j,\ \sigma_i>\sigma_j, \ \{\sigma_i,\sigma_j\}\in E(G)\}\bigr|.$$

M1’s Theorem 1.1 gives a deterministic terminating procedure assigning a partition $\theta_G(\sigma)\vdash n$ to each $\sigma\in D_G^0$, with

$$\chi_G(X;q)=\sum_{\sigma\in D_G^0} q^{\operatorname{ginv}_G(\sigma)}e_{\theta_G(\sigma)}(X).$$

Each elementary coefficient therefore counts admissible permutations of the appropriate partition type and inversion degree. The procedure acts on an individual permutation; it does not first compute the coefficient list and distribute permutations to fit it. Its running time may be large.

For the path $1\! -\!2\! -\!3$, the stated expansion is

$$\chi_G(X;q)=q\,e_{(2,1)}(X) +(1+q+q^2)e_{(3)}(X).$$

The admissible permutations are $123,132,213,321$, with inversion degrees $0,1,1,2$. One degree-one permutation contributes to $(2,1)$, and the remaining three contribute to $(3)$.

Using the established geometric identity, the source also obtains degreewise decompositions of Hessenberg cohomology representations into Young permutation modules. These modules have bases permuted by the symmetric group, with multiplicities given by the same counts. The conclusion is an abstract representation isomorphism, not a preferred geometric basis or compatibility with multiplication of cohomology classes.

5. Why the advance matters

Importance: 4/5. Coefficientwise positivity is a substantial strengthening of numerical positivity and the classical $q=1$ theorem. It says that every separate graded contribution admits a nonnegative count, rather than relying on cancellations between degrees.

The permutation rule adds explanatory value. A polynomial identity can prove that coefficients are nonnegative without revealing what they count. Here the source claims a finite assignment that connects each count to an individual combinatorial object.

The geometric consequence gives the positivity a representation-theoretic meaning as well. The rating reflects a major advance in algebraic combinatorics, while recognizing that the classical Stanley–Stembridge theorem is already established and the additional unimodality claim remains separate.

6. The main idea

Move the coefficient question to another algebra

The first reduction uses an algebra whose monomials encode vertex multiplicities. Multiplication keeps track of the graph’s ordered edges through powers of an auxiliary variable $v$, with $q=v^2$. This is a quantum torus: monomials multiply with a prescribed commutation factor rather than simply commuting.

Sums indexed by independent vertex sets nevertheless commute in the required way. They can therefore play the role of elementary symmetric functions in a formal new alphabet. The source translates the desired elementary coefficient into a monomial coefficient in this graph-based algebra.

This change does not prove positivity by itself. It creates a setting where graded vector spaces and positive factorization can control the coefficients.

Identify the exact positive object

The manuscript constructs systems of algebraic transformations attached to walls between regions. Compatible expressions on those regions are called sections. Earlier Hall-algebra and scattering-diagram ideas motivate this framework, where factorization can reveal nonnegative graded dimensions.

The essential graph-specific step is an identification: the symmetric expression arising from the graph must equal a particular positive section. General positivity elsewhere in the algebra would be insufficient.

An auxiliary triangular graph with distinguished independent vertices, called anchors, provides the coordinates. Repeated interval rotations and support bounds show that the required expression has precisely the anchor form of the positive section. Graded vector-space dimensions then give nonnegative integer coefficients.

Turn algebraic positivity into a permutation assignment

The final stage returns to individual words. It groups vertices into packets, each an independent set in increasing order. Local bijections transport packets to subsets of the anchors while recording weighted changes.

The source uses finite ordering and cancellation procedures to pass from conditions requiring certain ascents to conditions specifying the exact ascent pattern. The surviving terminal data determine a partition for each admissible permutation and preserve its graph-inversion degree.

Thus the two main outputs have separate roles: positive algebraic objects establish coefficientwise positivity, and the packet procedure realizes it as a rule on individual permutations. The latter is stronger than simply knowing the final coefficient totals.

7. Scope, limitations, and open questions

The theorem concerns natural unit interval graphs with their specified labels. It does not assert elementary positivity of the same refined function for every graph or every arbitrary relabeling.

Specializing $q=1$ recovers classical positivity, but the theorem makes no assertion of elementary unimodality. Unimodality would require each coefficient sequence to increase and then decrease in the prescribed way, a restriction beyond nonnegativity.

The permutation procedure terminates, yet no efficient running-time bound is claimed. Nor does its existence supply a simple closed formula for the partition assigned to every input without performing that procedure.

The cohomological consequence is an abstract decomposition over the complex numbers. It does not automatically identify a canonical basis, a geometric partition of the variety, or a decomposition compatible with the cup product. These stronger interpretations need their own constructions.

8. Sources and further reading

M1’s Theorem 1.1 states the positive expansion and permutation rule; Corollary 1.2 gives the representation consequence. Section 2 makes the algebraic reduction, Sections 3–5 establish positivity and the graph-specific identification, and Section 6 constructs the individual witness before Section 7 completes the expansion.

The primary papers linked in Section 3 distinguish the original symmetric function, the refined conjecture, the reduction and Hikita’s theorem. Wikipedia’s symmetric function and elementary symmetric polynomial pages offer optional background.

Source manuscripts

• M1. OpenAI, Elementary positivity of chromatic quasisymmetric functions (September 24, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.