Fully optimal bases and the active bijection in graphs, hyperplane arrangements, and oriented matroids

Emeric Gioan 1 Michel Las Vergnas 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this note, we present the main results of a series of forthcoming papers, dealing with bijective generalizations of some counting formulas. New intrinsic constructions in oriented matroids on a linearly ordered set of elements establish notably structural links between counting regions and linear programming. We introduce 'fully optimal bases', which have a simple combinatorial characterization, and strengthen the well-known optimal bases of linear programming. Our main result is that every bounded region of an ordered hyperplane arrangement, or ordered oriented matroid, has a unique fully optimal basis, providing the 'active bijection' between bounded regions and uniactive internal bases. The active bijection is extended to an activity preserving mapping between all reorientations and all bases of an ordered oriented matroid. It gives a bijective interpretation of the equality of two expressions for the Tutte polynomial, as well as a new expression of this polynomial in terms of beta invariants of minors. There are several refinements, such as an activity preserving bijection between regions (acyclic reorientations) and no-broken-circuit subsets, and others in terms of hyperplane arrangements, graphs, and permutations.
Type de document :
Communication dans un congrès
EuroComb'07: European Conference on Combinatorics, Graph Theory and Applications, Sep 2007, Sevilla, Electronic Notes in Discrete Mathematics 29, pp.365-371, 2007, 〈http://www.lirmm.fr/~gioan〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00154521
Contributeur : Emeric Gioan <>
Soumis le : mercredi 13 juin 2007 - 23:55:44
Dernière modification le : mercredi 21 mars 2018 - 18:57:06

Identifiants

  • HAL Id : lirmm-00154521, version 1

Collections

Citation

Emeric Gioan, Michel Las Vergnas. Fully optimal bases and the active bijection in graphs, hyperplane arrangements, and oriented matroids. EuroComb'07: European Conference on Combinatorics, Graph Theory and Applications, Sep 2007, Sevilla, Electronic Notes in Discrete Mathematics 29, pp.365-371, 2007, 〈http://www.lirmm.fr/~gioan〉. 〈lirmm-00154521〉

Partager

Métriques

Consultations de la notice

127