Share This Article:

The Facets of the Bases Polytope of a Matroid and Two Consequences

Full-Text HTML XML Download Download as PDF (Size:229KB) PP. 14-20
DOI: 10.4236/ojdm.2018.81002    349 Downloads   601 Views Citations
Author(s)

ABSTRACT

Let M be a matroid defined on a finite set E and L ⊂ E . L is locked in M if  and  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.

Cite this paper

Chaourar, B. (2018) The Facets of the Bases Polytope of a Matroid and Two Consequences. Open Journal of Discrete Mathematics, 8, 14-20. doi: 10.4236/ojdm.2018.81002.

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.