Skip to Main content Skip to Navigation
Journal articles

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
2 C&O - Equipe combinatoire et optimisation
IMJ-PRG - Institut de Mathématiques de Jussieu - Paris Rive Gauche
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.
Document type :
Journal articles
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00395073
Contributor : Emeric Gioan <>
Submitted on : Sunday, June 14, 2009 - 5:02:39 PM
Last modification on : Monday, November 30, 2020 - 5:32:04 PM

Identifiers

  • HAL Id : lirmm-00395073, version 1

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⟩

Share

Metrics

Record views

635