I have been learning about Matroids and Matroid Intersection and I've solved a few problems using the algorithm. However, most resources online, academic or competitive, only list a handful of nontrivial matroids that have a forseeable application in competitive programming. I'd like to make this post for two reasons. The first reason is to ask the community for other interesting matroids they've seen in other problems or come up with on their own and proved the matroid property. The second reason is to compile a list of these matroids for others in the future to use, as well as a list of problems that use matroid intersection for further practicing.
Please, if you have anything to contribute, feel free to comment / dm me on cf or on discord @meaf!
List of common Matroids:
- The Graphic / Forest Matroid: Let $$$X$$$ be the set of edges in a graph, and $$$I$$$ be the set of subsets of $$$X$$$ s.t. the edges do not form a cycle.
- The Linear Matroid: Let $$$X$$$ be a set of vectors, and $$$I$$$ be the set of subsets of $$$X$$$ s.t. all vectors are linearly independent.
- The Colorful Matroid: Let $$$X$$$ be a set of elements, each with their own color. Let $$$I$$$ be the set of subsets of $$$X$$$ s.t. all elements have pairwise distinct color.
- The Extended Colorful Matroid: Let $$$X$$$ be a set of elements, each with their own color. Let $$$C$$$ be a list of nonnegative integers, one for each distinct color. Let $$$I$$$ be the set of subsets of $$$X$$$ s.t. for any color $$$i$$$, the number of elements of color $$$i$$$ does not exceed $$$C_i$$$
- The Matching Matroid: Consider a bipartite graph. Let $$$X$$$ be the set of elements on the right side of the bipartition. Let $$$I$$$ be the set of subsets of $$$X$$$ s.t. there exists a matching which contains exactly these elements.
