Skip to Main content Skip to Navigation
Journal articles

On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids

Emeric Gioan 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We introduce the active partition of the ground set of an oriented matroid perspective (or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into Boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into Boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set, and applies to graph and directed graph homomorphisms on a linearly ordered edge-set. Dedicated to Michel Las Vergnas' spirit.
Complete list of metadata
Contributor : Emeric Gioan Connect in order to contact the contributor
Submitted on : Thursday, June 24, 2021 - 1:11:19 PM
Last modification on : Monday, October 11, 2021 - 1:24:08 PM
Long-term archiving on: : Saturday, September 25, 2021 - 6:25:02 PM


Files produced by the author(s)


  • HAL Id : lirmm-03269872, version 1
  • ARXIV : 1807.06559



Emeric Gioan. On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids. Discrete Mathematics, Elsevier, In press. ⟨lirmm-03269872⟩



Record views


Files downloads