The Arboricity Polynomial
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916725814984704 |
|---|---|
| author | Breuer, Felix Klivans, Caroline J |
| author_facet | Breuer, Felix Klivans, Caroline J |
| contents | We introduce a new matroid (graph) invariant, the arboricity polynomial. Given a matroid, the arboricity polynomial enumerates the number of covers of the ground set by disjoint independent sets. We establish the polynomiality of the counting function as a special case of a scheduling polynomial, i.e. both in terms of quasisymmetric functions and via Ehrhart theory of the normal fan of the matroid base polytope. We show basic properties of the polynomial and demonstrate that it is not a Tutte invariant. Namely, the arboricity polynomial does not satisfy a contraction / deletion recursion. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02822 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Arboricity Polynomial Breuer, Felix Klivans, Caroline J Combinatorics 05B35, 05E99, 05C30 We introduce a new matroid (graph) invariant, the arboricity polynomial. Given a matroid, the arboricity polynomial enumerates the number of covers of the ground set by disjoint independent sets. We establish the polynomiality of the counting function as a special case of a scheduling polynomial, i.e. both in terms of quasisymmetric functions and via Ehrhart theory of the normal fan of the matroid base polytope. We show basic properties of the polynomial and demonstrate that it is not a Tutte invariant. Namely, the arboricity polynomial does not satisfy a contraction / deletion recursion. |
| title | The Arboricity Polynomial |
| topic | Combinatorics 05B35, 05E99, 05C30 |
| url | https://arxiv.org/abs/2505.02822 |