On the Matroid Isomorphism Problem

Brahim Chaourar

Published 2017-03-10Version 1

Let $M$ to be a matroid defined on a finite set $E$ and $L\subset E$. $L$ is locked in $M$ if $M|L$ and $M^*|(E\backslash L)$ are 2-connected, and $min\{r(L), r^*(E\backslash L)\} \geq 2$. Given a positive integer $k$, $M$ is $k$-locked if the number of its locked subsets is $O(|E|^k)$. $\mathcal L_k$ is the class of $k$-locked matroids (for a fixed k). In this paper, we give a new axiom system for matroids based on locked subsets. We deduce that the matroid isomorphism problem (MIP) for $\mathcal L_k$ is polynomially time reducible to the graph isomorphism problem (GIP). $\mathcal L_k$ is closed under 2-sums and contains the class of uniform matroids, the V\'amos matroid and all the excluded minors of 2-sums of uniform matroids. MIP is coNP-hard even for linear matroids.