The paper by Tatsuyuki Hikita (Hikita 2024), first posted online in 2024, has just been accepted for publication in the Journal of the American Mathematical Society. It proves the Stanley–Stembridge conjecture, a long-standing problem in algebraic combinatorics that had been open for more than thirty years. This seems like a good occasion to explain the statement of the conjecture and Hikita’s theorem.
Let be a finite graph. A proper colouring of assigns a colour to each vertex in such a way that adjacent vertices receive different colours. If we have available colours, the number of proper colourings is denoted by . A classical result states that is a polynomial in , called the chromatic polynomial of .
In 1995, Richard Stanley (Stanley 1995) introduced a remarkable refinement of the chromatic polynomial. Instead of merely counting proper colourings, it records how many vertices receive each colour.
We now allow the colours to be arbitrary positive integers. Given a proper colouring associate with it the monomial in infinitely many variables . The chromatic symmetric function of is
The function is symmetric: permuting the variables does not change it, because this simply amounts to renaming the colours.
It contains the chromatic polynomial as a special case. Indeed, if we put and then every proper colouring using the colours contributes , while all other colourings contribute . Hence where the first variables are equal to .
The chromatic symmetric function therefore contains more information than the chromatic polynomial. The Stanley–Stembridge conjecture concerns the way this function can be expanded in a natural family of symmetric functions.
For every positive integer , define the elementary symmetric function For example, and
A partition of a positive integer is a sequence of positive integers such that We write and define
If has vertices, then its chromatic symmetric function can be written uniquely in the form for certain integers . We say that is -positive if for every partition of .
For example, if is the complete graph on vertices, then all vertices must receive different colours. Every choice of distinct colours can be assigned to the vertices in ways, and therefore Thus is -positive. For general graphs, however, the chromatic symmetric function need not be -positive.
The Stanley–Stembridge conjecture predicted that -positivity always holds for an important family of graphs arising from partially ordered sets.
A partially ordered set, or poset, is a set equipped with a relation which is reflexive, antisymmetric, and transitive. Two distinct elements are called incomparable if neither nor holds.
The incomparability graph of a finite poset is the graph whose vertices are the elements of , with two vertices joined by an edge exactly when the corresponding elements are incomparable.
A poset is called -free if there do not exist four elements such that while is incomparable with each of . Thus a -free poset cannot contain a three-element chain together with another element unrelated to all three.
In 1993, Stanley and Stembridge (Stanley 1995) made a conjecture which Stanley later reformulated using chromatic symmetric functions:
For every finite -free poset , the chromatic symmetric function of its incomparability graph is -positive.
This became known as the Stanley–Stembridge conjecture.
An important breakthrough was obtained by Mathieu Guay-Paquet (Guay-Paquet 2013), who showed that it is enough to prove the conjecture for a much more special family of posets.
A finite poset is called a unit interval order if its elements can be represented by intervals of equal length on the real line, with Thus two elements are incomparable exactly when their corresponding intervals intersect. The incomparability graph is therefore the intersection graph of a collection of intervals of equal length; such a graph is called a unit interval graph.
Guay-Paquet proved that if the chromatic symmetric function is -positive for every unit interval graph, then the Stanley–Stembridge conjecture follows for all finite -free posets.
Even after this substantial reduction, the problem resisted all attempts for more than a decade. Hikita’s paper finally completes the argument.
Let be a finite -free poset, and let be its incomparability graph. Then with for every .
In other words, the Stanley–Stembridge conjecture is true.
Hikita proves -positivity for unit interval graphs and then applies Guay-Paquet’s reduction. An especially striking feature of the proof is that it gives a probabilistic interpretation of suitably normalized coefficients in the elementary symmetric function expansion: the required non-negativity ultimately follows because these quantities arise as probabilities.
The theorem closes a problem originating in the early 1990s, but the subject is far from finished. There is a stronger -analogue of the Stanley–Stembridge conjecture, formulated by Shareshian and Wachs, which remains open. Thus Hikita’s theorem settles the original conjecture while leaving a natural and considerably stronger positivity problem for future work.