The Two-Variable Hypergraph Tutte Polynomial via Embedding Activities and Computation-Tree Activities

Abstract

We generalize Bernardi's embedding activity definition for the Tutte polynomial from graphs to hypergraphs, and Gordon-Traldi-McMahon's computation-tree activities from matroids to polymatroids. Furthermore, we introduce a new variant of computation-tree activities, and show that they also yield a definition for the polymatroid Tutte polynomial. In all three cases, the key is to show that the given activity notion yields a Crapo decomposition. We also examine the relationship of these activity notions, and pose some questions about them.