Fully optimal bases in linear programming, the active
bijection, and applications

by Michel Las Vergnas

C.N.R.S., and University Paris 6


A fully optimal basis of an ordered linear program strengthens
the classical notion of optimal basis. It can be defined from
signs in its tableau. Optimal bases are not unique in general.
Theorem: a bounded feasible region has a unique fully optimal
basis. Several algorithms to construct the fully optimal basis
of a bounded region will be presented.

Fully optimal bases establish a bijection - called the {\it
active bijection} - between the bounded regions of an ordered
hyperplane arrangement and its uniactive internal simplices. By
decomposing activities, this bijection can be extended to the
{\it active mapping} from the set of all regions of the
arrangement onto the set of all internal simplices. The active
mapping provides a bijective version of classical counting
formulas for regions and  bounded regions.

In full generality, the above properties hold for oriented
matroids, which are topologically arrangements of
pseudohyperplanes. The active mapping maps the reorientations
of an ordered oriented matroid onto its bases. It  preserves
activities, a property directly equivalent to the relationship
between two state models of the Tutte polynomial of an ordered
oriented matroid.

For certain linear orderings of the edges of a graph, the active
bijection provides a bijection between acyclic orientations with
a given unique sink and internal spanning trees. In the  particular
case of the complete graph - equivalent to the Coxeter arrangement
$A_n$ - we recover a classical bijection between $n$-permutations
and increasing trees on $n+1$ vertices. Similar results hold for
the Coxeter arrangement $B_n$.

Joint work with Emeric Gioan.