A survey on the active bijection in graphs, hyperplane arrangements, and oriented matroids - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2015

A survey on the active bijection in graphs, hyperplane arrangements, and oriented matroids

Emeric Gioan

Résumé

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.
Fichier non déposé

Dates et versions

lirmm-01265673 , version 1 (01-02-2016)

Identifiants

  • HAL Id : lirmm-01265673 , version 1

Citer

Emeric Gioan. A survey on the active bijection in graphs, hyperplane arrangements, and oriented matroids . ALEA-Network Workshop, Nov 2015, Bordeaux, France. ⟨lirmm-01265673⟩
113 Consultations
0 Téléchargements

Partager

More