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

• 作者: Brahim Chaourar
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: BASES POLYTOPE FACETS Locked SUBSETS Maximum-Weight Basis Problem Polynomially Locked MATROIDS MATROID Oracle Testing Unformity of a MATROID
• 年，卷（期）: 2018,（1）
• 页码范围: 14-20
• 页数: 7页
• 分类号: O1

摘要

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.