Tutte Polynomial Activities
From MaRDI portal
Publication:6320107
DOI10.1201/9780429161612-5zbMATH Open1512.05204arXiv1906.02781MaRDI QIDQ6320107FDOQ6320107
Publication date: 6 June 2019
Abstract: Unlike Whitney's definition of the corank-nullity generating function , Tutte's definition of his now eponymous polynomial requires a total order on the edges of which the polynomial is a posteriori independent. Tutte presented his definition in terms of internal and external activities of maximal spanning forests. Although Tutte's original definition may appear somewhat ad hoc upon first inspection, subsequent work by various researchers has demonstrated that activity is a deep combinatorial concept. In this survey, we provide an introduction to activities for graphs and matroids. Our primary goal is to survey several notions of activity for graphs which admit expansions of the Tutte polynomial. Additionally, we describe some fundamental structural theorems, and outline connections to the topological notion of shellability as well as several topics in algebraic combinatorics.
Graph polynomials (05C31) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)
This page was built for publication: Tutte Polynomial Activities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320107)
