Speaker
Sam Bastida
(Victoria University of Wellington)
Description
It is well known that the class of transversal matroids is not closed under contraction or duality. The complexity of deciding whether a minor or dual of a transversal matroid remains transversal is in $\Sigma_2$ and thus far there has been no improvement on this bound. We explore this issue, providing a polynomial time algorithm for determining whether a single element contraction of a transversal matroid remains transversal. If so, our algorithm also provides a transversal representation. We then develop the techniques used in search of a polynomial time algorithm for determining whether the dual of a transversal matroid remains transversal.
Primary author
Sam Bastida
(Victoria University of Wellington)
