2024/05/15 by Samuel Bastida, Bastida, Samuel
Engineering · Materials Science · #05B35 #Advanced Surface Polishing Techniques #Combinatorics (math.CO) #FOS: Mathematics #Material Properties and Applications
paper · pdf · doi:10.48550/arxiv.2405.09088
openalex publication_date 2024/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well known that the class of transversal matroids is not closed under contraction or duality. In particular, after contracting a set of elements from a transversal matroid, the resulting matroid may or may not be transversal, and the computational complexity of determining whether it is transversal is not well understood. As a step toward resolving this, we provide a polynomial-time algorithm for determining whether a single-element contraction of a transversal matroid is transversal. In the case that the single-element contraction is transversal, the algorithm also provides a transversal representation. We then discuss possible applications of our techniques toward finding a polynomial-time algorithm to determine if the dual of a transversal matroid is transversal.