Chromatic symmetric functions and polynomial invariants of trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909265005903872 |
|---|---|
| author | Aliste-Prieto, José Martin, Jeremy L. Wagner, Jennifer D. Zamora, José |
| author_facet | Aliste-Prieto, José Martin, Jeremy L. Wagner, Jennifer D. Zamora, José |
| contents | Stanley asked whether a tree is determined up to isomorphism by its chromatic symmetric function. We approach Stanley's problem by studying the relationship between the chromatic symmetric function and other invariants. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_10333 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Chromatic symmetric functions and polynomial invariants of trees Aliste-Prieto, José Martin, Jeremy L. Wagner, Jennifer D. Zamora, José Combinatorics 05C05, 05C31, 05C60, 05E05 Stanley asked whether a tree is determined up to isomorphism by its chromatic symmetric function. We approach Stanley's problem by studying the relationship between the chromatic symmetric function and other invariants. 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. |
| title | Chromatic symmetric functions and polynomial invariants of trees |
| topic | Combinatorics 05C05, 05C31, 05C60, 05E05 |
| url | https://arxiv.org/abs/2402.10333 |