UW Combinatorics and Geometry Seminar: Jeremy Martin

Richard Stanley asked in 1995 whether a tree is determined up to isomorphism by its chromatic symmetric function. This question remains unanswered and frequently keeps the speaker awake at night. Our approach to understanding the strength of the chromatic symmetric function as an invariant is to ask what other information is encoded in it. First, we prove Crew’s conjecture that the chromatic symmetric function of a tree determines its generalized degree sequence, which enumerates vertex subsets by cardinality and the numbers of internal and external edges. Second, we prove that the restriction of the generalized degree sequence to subtrees contains exactly the same information as the subtree polynomial, which enumerates subtrees by cardinality and number of leaves. Third, we construct arbitrarily large families of trees sharing the same subtree polynomial, proving and generalizing a conjecture of Eisenstat and Gordon. This is joint work with José Aliste-Prieto, Jennifer Wagner, and José Zamora.