The ACO Seminar (2024–2025)

I will introduce a new matroid (graph) invariant: The Arboricity Polynomial. Arboricity is a numerical invariant first introduced by Nash-Williams, Tutte and Edmonds. It captures the minimum number of independent sets (forests) needed to decompose the ground set of a matroid (edges of a graph). The arboricity polynomial enumerates the number of such decompositions. We examine this counting function in terms of scheduling, Ehrhart theory, quasisymmetric functions, matroid polytopes and the permutohedral fan.