TITLE:
The Facets of the Bases Polytope of a Matroid and Two Consequences
AUTHORS:
Brahim Chaourar
KEYWORDS:
Bases Polytope, Facets, Locked Subsets, Maximum-Weight Basis Problem, Polynomially Locked Matroids, Matroid Oracle, Testing Unformity of a Matroid
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.8 No.1,
January
11,
2018
ABSTRACT:
Let M be a
matroid defined on a finite set E and L⊂E. L is
locked in M ifand are
2-connected, and . In this paper, we prove that the nontrivial facets
of the bases polytope of M are
described by the locked subsets. We deduce that finding the maximum-weight
basis of M is a polynomial time
problem for matroids with a polynomial number of locked subsets. This class of
matroids is closed under 2-sums and contains the class of uniform matroids, the
Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We
deduce also a matroid oracle for testing uniformity of matroids after one call
of this oracle.