The Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids - 1 - The fully Optimal Basis of a Bounded Region

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 : The present paper is the first in a series of four introducing a mapping from orientations to spanning trees in graphs, from regions to simplices in real hyperplane arrangements, from reorientations to bases in oriented matroids (in order of increasing generality). We call it the active orientation-to-basis mapping, in reference to an extensive use of activities, a notion depending on a linear ordering, first introduced by W.T. Tutte for spanning trees in graphs. The active mapping, which preserves activities, can be considered as a bijective generalization of a polynomial identity relating two expressions - one in terms of activities of reorientations, and the other in terms of activities of bases - of the Tutte polynomial of a graph, a hyperplane arrangement or an oriented matroid. Specializations include bijective versions of well-known enumerative results related to the counting of acyclic orientations in graphs or of regions in hyperplane arrangements. Other interesting features of the active mapping are links established between linear programming and the Tutte polynomial. We consider here the bounded case of the active mapping, where bounded corresponds to bipolar orientations in the case of graphs, and refers to bounded regions in the case of real hyperplane arrangements, or of oriented matroids. In terms of activities, this is the uniactive internal case. We introduce fully optimal bases, simply defined in terms of signs, strengthening optimal bases of linear programming. An optimal basis is associated with one flat with a maximality property, whereas a fully optimal basis is equivalent to a complete flag of flats, each with a maximality property. The main results of the paper are that a bounded region has a unique fully optimal basis, and that, up to negating all signs, fully optimal bases provide a bijection between bounded regions and uniactive internal bases. In the bounded case, up to negating all signs, the active mapping is a bijection.
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2009, 30 (8 (special issue: Combinatorial Geometries and Applications: Oriented Matroids and Matroids)), pp.1868-1886
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00395073
Contributeur : Emeric Gioan <>
Soumis le : dimanche 14 juin 2009 - 17:02:39
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00395073, version 1

Collections

Citation

Emeric Gioan, Michel Las Vergnas. The Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids - 1 - The fully Optimal Basis of a Bounded Region. European Journal of Combinatorics, Elsevier, 2009, 30 (8 (special issue: Combinatorial Geometries and Applications: Oriented Matroids and Matroids)), pp.1868-1886. 〈lirmm-00395073〉

Partager

Métriques

Consultations de la notice

259