Fully Optimal Bases and the Active Bijection in Graphs,Hyperplane Arrangements,and Oriented Matroids |
| |
Institution: | 1. Banco de México, Mexico City, Mexico;2. Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung 80424, Taiwan |
| |
Abstract: | In this note, we present the main results of a series of forthcoming papers, dealing with bi-jective generalizations of some counting formulas. New intrinsic constructions in oriented matroids on a linearly ordered set of elements establish notably structural links between counting regions and linear programming. We introduce fully optimal bases, which have a simple combinatorial characterization, and strengthen the well-known optimal bases of linear programming. Our main result is that every bounded region of an ordered hyperplane arrangement, or ordered oriented matroid, has a unique fully optimal basis, providing the active bijection between bounded regions and uniactive internal bases. The active bijec-tion is extended to an activity preserving mapping between all reorientations and all bases of an ordered oriented matroid. It gives a bijective interpretation of the equality of two expressions for the Tutte polynomial, as well as a new expression of this polynomial in terms of beta invariants of minors. There are several refinements, such as an activity preserving bijection between regions (acyclic reorientations) and no-broken-circuit subsets, and others in terms of hyperplane arrangements, graphs, and permutations. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|