[Tutorial] Matroid intersection in simple words

Revision en2, by ATSTNG, 2019-08-22 16:37:43

[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.

Tags tutorial, matroids, matroid intersection

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru5 Russian ATSTNG 2020-01-05 18:33:20 103
en17 English ATSTNG 2020-01-05 18:24:41 0
en16 English ATSTNG 2020-01-05 18:23:13 277
ru4 Russian ATSTNG 2020-01-05 17:47:13 0 (опубликовано)
ru3 Russian ATSTNG 2020-01-05 17:40:41 474 (сохранено в черновиках)
en15 English ATSTNG 2019-09-03 15:17:37 110
ru2 Russian ATSTNG 2019-09-03 15:11:48 319 Мелкая правка: ' Я надеюсь что эта с' -> ' Я надеюсь, что эта с' (опубликовано)
ru1 Russian ATSTNG 2019-09-03 14:48:49 61112 Первая редакция перевода на Русский (сохранено в черновиках)
en14 English ATSTNG 2019-08-30 18:22:38 11 Tiny change: 'about all bases of matro' -> 'about all circuits of matro'
en13 English ATSTNG 2019-08-30 18:21:03 156
en12 English ATSTNG 2019-08-26 17:39:26 9
en11 English ATSTNG 2019-08-23 12:56:30 0 (published)
en10 English ATSTNG 2019-08-23 11:42:37 20 (saved to drafts)
en9 English ATSTNG 2019-08-22 19:14:53 0 (published)
en8 English ATSTNG 2019-08-22 19:12:10 1 Tiny change: 'gs to in $mathcal{O}' -> 'gs to in $\mathcal{O}'
en7 English ATSTNG 2019-08-22 19:05:09 9090
en6 English ATSTNG 2019-08-22 18:44:06 15980 Tiny change: ' lazily.\n' -> ' lazily.\n\n'
en5 English ATSTNG 2019-08-22 18:23:16 10153 Tiny change: ' of $G$:\n' -> ' of $G$:\n\n![ ](https://codeforces.net/ee3628/matroid_rank.png)'
en4 English ATSTNG 2019-08-22 17:40:55 12804 Tiny change: 't\rangle, $M_2 = \lef' -> 't\rangle, M_2 = \lef'
en3 English ATSTNG 2019-08-22 17:00:45 5100 Tiny change: 'minus B$, C’ = $A \cap B$ ' -> 'minus B$, $C’ = A \cap B$ '
en2 English ATSTNG 2019-08-22 16:37:43 1651 Tiny change: 'n[cut]\n\n**Prer' -> 'n[cut]\n\n\n\n**Prer'
en1 English ATSTNG 2019-08-22 16:17:54 2244 Initial revision (saved to drafts)