Bases, reorientations, and linear programming, in uniform and rank-3 oriented matroids

AbstractA comparison of two expressions of the Tutte polynomial of an ordered oriented matroid, one as a generating function of basis activities, the other as a generating function of reorientation activities, yields a remarkable numerical relation between the number of bases and reorientations with given activities. The object of the paper is a natural activity preserving correspondence with suitable multiplicities between bases and reorientations, constituting a bijective proof of this relation. The general construction will be published elsewhere. In the present self-contained paper, we consider into details two particular cases of special interest: uniform oriented matroids and acyclic oriented matroids of rank 3. In both cases, the construction is simpler than in the general case, but introduces some of the main ideas. The correspondence is closely related to oriented matroid programming, a combinatorial generalization of linear programming. The link is direct in the uniform case: for unitary activities, the correspondence amounts to applying a program or its opposite to all bounded regions of a simple arrangement of pseudohyperplanes. In the rank-3 case, equivalent to pseudoline arrangements, a second step toward the general construction is made: optimizing two nested faces with respect to two lexicographically ordered programs