The Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids

We introduce a mapping from orientations to spanning trees in graphs, from regions to hyperplane bases 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 of the Tutte polynomial of a graph, a hyperplane arrangement or an oriented matroid - one in terms of activities of reorientations, and the other in terms of activities of bases. Specializations include bijective versions of well-known enumerative results related to the counting of acyclic orientations in graphs, or of regions in hyperplane arrangements. Another interesting feature of the active mapping is a tight relationship it establishes between linear programming and the Tutte polynomial. (joint work with Emeric Gioan)