2024 Workshop on (Mostly) Matroids

Contracting a Single Element in a Transversal Matroid

23 Aug 2024, 09:45

25m

S236 (IBS Science Culture Center)

Presentation (25 min)

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 ${\mathrm{\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.