An improved algorithm for recognizing matroids

Abstract

Let $M$ be a matroid defined on a finite set $E$ and $L\subset E$. $L$ is locked in $M$ if $M|L$ and $M^{\ast }|(E\backslash L)$ are 2-connected, and $min\{r(L),r^{\ast }(E\backslash L)\}\ge 2$. Locked subsets characterize nontrivial facets of the bases polytope. In this paper, we give a new axiom system for matroids based on locked subsets. We deduce an algorithm for recognizing matroids improving the running time complexity of the best known till today. This algorithm induces a polynomial time algorithm for recognizing uniform matroids. This latter problem is intractable if we use an independence oracle.

10 pages. arXiv admin note: substantial text overlap with arXiv:1703.03744