Proposition 3.1.27 in Oxley's Matroid Theory says that given a matroid $M$ and an element $e\in E(M)$ such that $e$ is not a loop or a coloop, the pair $(M/e, M\setminus e)$ uniquely determines $M$. Is there any known algorithm that reconstructs $M$, given $M/e$ and $M\setminus e$ where $e$ is not a coloop or loop?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ You can always construct all single-element extensions of $M - e$ and contract the newly-added element and test for isomorphism with $M / e$. $\endgroup$– Gordon RoyleCommented Apr 6 at 23:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It may depend on what you mean by reconstructing a matroid. If all we want to do is determine the independent sets of $M$, we can do so as follows:
Let $A$ be a subset of $E(M)$, the ground set of $M$. If $e$ is not contained in $A$, then $A$ is independent in $M$ if and only if $A$ is independent in $M\backslash e$. If $e$ is contained in $A$, then $A$ is independent in $M$ if and only if $A-e$ is independent in $M/e$.
(This fails if $e$ is a loop, but works if $e$ is a coloop.)
