Skip to main content
eScholarship
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

Tutte short exact sequences of graphs

Published Web Location

https://doi.org/10.5070/C62257874Creative Commons 'BY' version 4.0 license
Abstract

We associate two modules, the \(G\)-parking critical module and the toppling critical module, to an undirected connected graph \(G\). The \(G\)-parking critical module and the toppling critical module are canonical modules (with suitable twists) of quotient rings of the well-studied \(G\)-parking function ideal and the toppling ideal, respectively. For each critical module, we establish a Tutte-like short exact sequence relating the modules associated to \(G\), an edge contraction \(G/e\) and an edge deletion \(G \setminus e\) (\(e\) is a non-bridge). We obtain purely combinatorial consequences of Tutte short exact sequences. For instance, we reprove a theorem of Merino that the critical polynomial of a graph is an evaluation of its Tutte polynomial, and relate the vanishing of certain combinatorial invariants (the number of acyclic orientations on connected partition graphs satisfying a unique sink property) of \(G/e\) to the equality of the corresponding invariants of \(G\) and \(G \setminus e\).

Mathematics Subject Classifications: 13D02, 05E40

Keywords: Tutte polynomials, chip firing games, toppling ideals, \(G\)-parking function ideals, canonical modules

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View