The Facets of the Bases Polytope of a Matroid and Two Consequences - Open Journal of Discrete Mathematics

OJDM > Vol.8 No.1, January 2018

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

HTML XML

Download as PDF (Size: 229KB) PP. 14-20

DOI: 10.4236/ojdm.2018.81002 752 Downloads 1,370 Views Citations

Author(s)

Brahim Chaourar

Affiliation(s)

Department of Mathematics and Statistics, Al Imam Mohamed Ibn Saud University (IMSIU), Riyadh, Saudi Arabia.

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.

KEYWORDS

Bases Polytope, Facets, Locked Subsets, Maximum-Weight Basis Problem, Polynomially Locked Matroids, Matroid Oracle, Testing Unformity of a Matroid

Share and Cite:

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.

Journals Menu

Follow SCIRP

	+1 323-425-8868
	customer@scirp.org
	+86 18163351462(WhatsApp)
	1655362766

	Paper Publishing WeChat

Journals Menu

Home

About SCIRP

Service

Policies