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 Accéder directement au contenu
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 principal
Vignette du fichier
Tutte-workshop-2015-Gioan-A-survey-on-the-active-bijection.pdf (759.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01265667 , version 1 (23-01-2018)

Identifiants

  • HAL Id : lirmm-01265667 , version 1

Citer

Emeric Gioan. A survey on the active bijection in graphs, hyperplane arrangements and oriented matroids. Workshop on the Tutte polynomial, Jul 2015, London, United Kingdom. ⟨lirmm-01265667⟩
154 Consultations
80 Téléchargements

Partager

Gmail Facebook X LinkedIn More