Click to enlarge
The purpose of this thesis is to define and study, intrinsically and constructively, a natural application which associates a distinguished basis with any ordered oriented matroid. For a given ordered oriented matroid, it induces a correspondence, determined by some conditions, between the set of its reorientations and the set of its bases.
A fundamental condition to be satisfied is that activities are preserved. Activities of a basis in an ordered matroid, defined by Tutte, are two dual integer parameters, just as activities of an ordered oriented matroid, defined by Las Vergnas. Briefly, they situate these objects with respect to the minimal and maximal bases for the lexicographic order. The correspondence is thus called called the canonical active correspondence of the ordered oriented matroid. It constitutes a bijective proof of known numerical properties of the Tutte polynomial.
Another condition is invariance under duality. Duality is used everywhere in an essential way, in fundamental characterizations as well as in algorithms.
The correspondence has remarkable geometrical properties, and can be constructed inductively, either using minors with respect to the greatest element, or using a decomposition of activities which reduces the problem to activities (1,0). In terms of bases, this decomposition gives a new expression of the Tutte polynomial using beta invariants of some minors. In terms of reorientations, this decomposition leads to a notion of activity classes of reorientations, which are in active bijection with bases. Moreover, this bijection can be refined into an active bijection between all subsets, which induces an active bijection between regions of the oriented matroid and subsets with no broken circuit of the matroid (faces of the NBC complex).
In the graphical case, we get notably an active bijection between internal spanning trees and acyclic orientations with a unique given sink, and a bijection between spanning trees with activities (1,0) and acyclic orientations with unique given adjacent source and sink.
In the case of an hyperplane arrangement, we get notably an active bijection between internal simplices and activity classes of regions, and a bijection between simplices with activities (1,0) and bounded regions.
If the hyperplanes are in general position, this last bijection comes down to apply the same linear program simultaneously to all bounded regions, on each side of a distinguished hyperplane, kernel of the linear form to be optimized.
The general application appears thus as an extension of the combinatorial version of linear programming in oriented matroids. First, each reorientation is decomposed into bounded regions in some minors of the oriented matroid and its dual, and, secondly, for each bounded region, instead of optimizing one vertex for one objective function, we optimize a sequence of nested faces for a sequence of objective functions.
This application arises naturally when one considers a linear ordering on the sets of elements of oriented matroids. It describes, intuitively, a phenomenon of directed attraction with respect to the ordering, and could be called the (attr)active mapping of ordered oriented matroids.
Keywords: oriented matroid, hyperplane arrangement, matroid, point configuration, NBC complex, pseudoline arrangement, uniform oriented matroid, supersolvable arrangement, base, reorientation, region, Tutte polynomial, activity, beta invariant, bijection, algorithm, duality, graph, spanning tree, orientation, acyclic orientation, source, sink, bipolar orientation, canonical active correspondence, decomposing sequence, active partition, attractive function of ordered oriented matroids, combinatorial optimization, linear programming, multiprogramming, flag programming.
AMS classification: 05A15, 05B35, 05B40, 05C, 52B40, 52C30, 52C35, 52C40, 90C05, 90C27, 90C46.