Chromatic Symmetric Functions
In 1995, Richard Stanley introduced the chromatic symmetric function
(CSF) of a graph and proposed the following problem:
Do there exist two nonisomorphic trees with the same CSF?
The problem seems to be very hard. Here is what is known:
- Stanley gave an example of two 5-vertex non-tree graphs
and the kite)
with the same CSF. By gluing together copies of this,
I think you can get infinitely many pairs with the same CSF.
(I've written down a construction twice and have forgotten it both times.)
- Matt Morin, Jennifer Wagner and I proved that you
can recover the degree sequence of a tree from its CSF,
as well as the number of vertices at each given distance.
More generally, for each \(i,j\), you can recover the number of subtrees
with \(i\) edges and \(j\) leaves. But that data only suffices to distinguish
trees of 10 or fewer vertices.
- My student Keeler Russell carried out a brute-force search of all
trees on 25 or fewer vertices and determined that they all had different
CSF's. Keeler's code used the degree-sequence result mentioned above to
break the problem into more feasible chunks, as well as a lot of fancy
footwork with data structures (think about it: how do you efficiently
represent an unlabeled tree and compute its CSF, and how do you generate
all unlabeled trees? on \(n\) vertices?) Keeler's code, written
in C++, is freely available either from his GitHub repository or a mirror on my website. If you have any questions about
using the code, please contact Keeler:
Last updated Tue 1/7/14