A survey on the active bijection in graphs, hyperplane arrangements, 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 : The active bijection maps any directed graph, resp. signed hyperplane arrangement or oriented matroid, defined on a linearly ordered edge set, resp. ground set, onto one of its spanning trees, resp. bases. It relates all spanning trees to all orientations of a graph, all bases to all reorientations of an hyperplane arrangement or, more generally, an oriented matroid. It preserves activities: for bases in the sense of Tutte, for orientations in the sense of Las Vergnas, yielding a bijective interpretation of the equality of two expressions of the Tutte polynomial. It preserves also some active partitions associated with orientations and bases. It can be mathematically defined in a short way, and can be built, characterized, particularized, or refined in several ways. Notably, we get a bijection between bounded regions (bipolar orientations in the case of a graph) and bases with internal activity one and external activity zero, which can be seen as an advanced refinement of real (pseudo)linear programming. We get a bijection between classes of reorientations and bases, using a decomposition into bounded regions of minors of the primal and the dual, which also has a counterpart for decomposing matroid bases, and yields an expression of the Tutte polynomial using only beta invariants of minors. We also get activity preserving bijections between all reorientations and all subsets (related to a four-variable expression of the Tutte polynomial), between regions and no-broken-circuit subsets (acyclic case), between reorientations with fixed orientations for smallest elements of positive circuits/cocircuits (directed cycles/cocycles) and bases (spanning trees), between increasing trees and permutations (complete graph case), et cetera. It is the subject of a series of paper, joint with Michel Las Vergnas.
Type de document :
Communication dans un congrès
ALEA-Network Workshop, Nov 2015, Bordeaux, France. 2015, 〈www.labri.fr/perso/marckert/Alea-Network_LaBRI_2015.html〉
Liste complète des métadonnées

Contributeur : Emeric Gioan <>
Soumis le : lundi 1 février 2016 - 14:04:43
Dernière modification le : mardi 23 janvier 2018 - 15:39:50


  • HAL Id : lirmm-01265673, version 1



Emeric Gioan. A survey on the active bijection in graphs, hyperplane arrangements, and oriented matroids . ALEA-Network Workshop, Nov 2015, Bordeaux, France. 2015, 〈www.labri.fr/perso/marckert/Alea-Network_LaBRI_2015.html〉. 〈lirmm-01265673〉



Consultations de la notice