[Russian version is in progress now, will be published ASAP]

Hello, CodeForces.

I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming.

I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets AC on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.)

Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only key points in whole theory, omitting a lot of intermediate results, logical steps and examples. In some article I’ve encountered this heavy-formula proof:

That was nowhere close to being clear for me. (Probably I’m not mathematician enough, yet.) But still, I’m sure there is a way to make this more clear and detailed.

I am sure, there are a lot of people in CP who will also like to get familiar with matroids. So, I’ve decided to review this topic from very beginning focusing more on explanations, logical steps and providing more examples. This is the goal of this article, and you do not need to know anything about matroids beforehand. .

Prerequisites. You are not required to know well everything listed here, but it is good to be familiar with some of these concepts for better and faster understanding:

1. Basics of set theory and set operations
2. Spanning trees in graphs
3. Matchings in bipartite graphs
4. Linear independence in vector spaces
5. Rank and basis of set of vectors
6. Gaussian elimination
7. Kruskal’s minimum spanning tree algorithm
8. Kuhn’s bipartite matching algorithm
9. Enjoying discrete math

All the information that used in this article is my own understanding of this topic, that I’ve learned from other articles found on the web. And as we know, proof by passing various tests is not a proper proof. So if you find something illogical or wrong, that should mean that I’ve made a mistake or misinterpret something, please point it out.

What matroid is?

Matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces.

Here goes the formal definition. Matroid is a pair $$$\left\langle X, I \right\rangle$$$ where $$$X$$$ is called ground set and $$$I$$$ is set of all independent subsets of $$$X$$$. In other words matroid $$$\left\langle X, I \right\rangle$$$ gives a classification for each subset of $$$X$$$ to be either independent or dependent (included in $$$I$$$ or not included in $$$I$$$).

Of course, we are not speaking about arbitrary classifications. These $$$3$$$ properties must hold for any matroid:

1. Empty set is independent.
2. Any subset of independent set is independent.
3. If independent set $$$A$$$ has smaller size than independent set $$$B$$$, there exist at least one element in $$$B$$$ that can be added into $$$A$$$ without loss of independency.

These are axiomatic properties of matroid. To prove that we are dealing with matroid, we generally have to prove these three properties.

For example, explicit presentation of matroid on ground set $$$\{x, y, z\}$$$ which considers $$$\{y, z\}$$$ and $$$\{x, y, x\}$$$ to be dependent and marked red. Other sets are independent and marked green.