Proper circular arc graphs are e-positive
math.CO
Submitted: 2026-09-27
Updated: 2026-10-26
Code: https://github.com/openai/math
License: http://creativecommons.org/licenses/by/4.0/
The gist: We prove an e-positive formula for the chromatic symmetric function of proper circular arc graphs solving the q=1 case of a conjecture of Ellzey and of Alexandersson and Panova.
Terminology
Abstract
We prove an e-positive formula for the chromatic symmetric function of proper circular arc graphs solving the q=1 case of a conjecture of Ellzey and of Alexandersson and Panova. In doing so, we provide a new proof of the e-positivity of unit interval graphs, which alongside Guay-Paquet's reduction gives a new proof of the Stanley--Stembridge conjecture. We define color matrices, which count proper colorings, and tableau matrices, whose entries are nonnegative rational numbers and ratios of elementary symmetric functions. We prove the two matrices are related by a single family of change of basis matrices, which become invertible after restricting to finitely many colors, and we show the chromatic symmetric function of proper circular arc graphs comes from taking the trace of these matrices. Using Hikita's tableaux, this gives an explicit formula for the chromatic symmetric function of a proper circular arc graph as a weighted sum over tableaux whose first and last k vertices lie in the same columns.
Sources
- Chromatic symmetric functions from the modular law
- LLT polynomials, chromatic quasisymmetric functions and graphs with cycles
- The $e$-positivity of the chromatic symmetric function for twinned paths and cycles
- Unit Interval Orders and the Dot Action on the Cohomology of Regular Semisimple Hessenberg Varieties
- Evaluations of Hecke algebra traces at Kazhdan-Lusztig basis elements
- A directed graph generalization of chromatic quasisymmetric functions
- A modular relation for the chromatic symmetric functions of (3+1)-free posets
- A proof of the Stanley--Stembridge conjecture
- Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs
- Chromatic quasisymmetric functions and Hessenberg varieties
- Chromatic quasisymmetric functions
- Characters and chromatic symmetric functions
- Adjacent cycle-chains are $e$-positive
- The chromatic symmetric function of graphs glued at a single vertex
- The Tutte symmetric matrix of a graph
- All cycle-chords are $e$-positive
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality