Shareshian–Wachs elementary positivity

The explanation

Take three vertices in a row, labeled 1, 2 and 3, with links 1–2 and 2–3. Color each vertex red, green or blue, so linked vertices never match. Such a coloring is called proper, and there are 12 of them. Rank the colors red < green < blue.

Now tag each coloring by its rising edges. An edge rises when its lower-numbered vertex gets the lower color. Coloring 1, 2, 3 red, green, blue makes both edges rise. Blue, green, red makes neither rise. The other ten colorings each have exactly one rising edge. Give each coloring the weight q raised to its number of rising edges. The 12 weights add up to 1 + 10q + q².

Allow any number of colors, and keep track of which colors are used. The result is the chromatic quasisymmetric function of the graph. With q set to 1, it is Stanley's chromatic symmetric function from 1995, which refines the usual count of coloringsSource 1.

Formulas like this can be rewritten in elementary pieces. The piece e_k adds up all products of k different color variables. For the three-vertex path, the paper's expansion is q·e₂e₁ + (1 + q + q²)·e₃Source 2. Check it with three colors. Then e₂e₁ counts 3 × 3 = 9 and e₃ counts 1. So the total is 9q + 1 + q + q², which is the 1 + 10q + q² found above. Every coefficient here is a polynomial in q with nonnegative whole-number coefficients. That property is called elementary positivity over ℕ[q].

Shareshian and Wachs proved that this function is symmetric for natural unit interval graphsSource 3. In such a graph, vertex i links to a run of the next few vertices, and these runs never shrink as i grows. They conjectured that every such graph is elementary-positive over ℕ[q]Source 3. The q = 1 version is the older Stanley–Stembridge conjecture from 1993Source 4. Hikita proved that q = 1 version in 2024. His formula gives positive values for every positive real q, but not whole-number coefficientsSource 5. Griffin, Mellit, Romero, Weigl and Wen gave an independent proof of the q = 1 versionSource 6. Earlier formulas did not give a nonnegative coefficient for each separate elementary pieceSource 7.

This paper proves the refined conjecture for every natural unit interval graphSource 8. It also says what each coefficient counts. Take permutations of the vertex labels where any drop between neighbors in the list is a linked pair. Weight each by q raised to its number of out-of-order linked pairsSource 9. A step-by-step procedure then sends each such permutation to one elementary piece. For the three-vertex path, the permitted lists are 123, 132, 213 and 321, with weights 1, q, q and q². One of the two q lists goes to e₂e₁ and the other three go to e₃Source 10. Setting q to 1 recovers the Stanley–Stembridge theoremSource 11.

The single hard part is subtraction. Counting colorings gives nonnegative numbers, but rewriting in elementary pieces can introduce minus signsSource 12. The paper first matches each coefficient with an algebraic object known to be positive. It then turns those algebraic identities into explicit one-to-one matchings of finite setsSource 13. The procedure always finishes, but its running time may be largeSource 14. The paper makes no claim about unimodality, the second half of the conjectureSource 15.

How sure is this? A computer proof checker called Lean has checked a formal version of the elementary expansion over ℕ[q]. It covers every finite number of color variables, with each permutation weighted as above. No specialist review of the paper has been published.

What it doesn't show. This does not prove the elementary unimodality part of the Shareshian–Wachs conjecture.