I am learning about Matroids, but i think i have some misunderstanding in it. The definition of a matroid is as following:

A finite matroid $M$ is a pair $( E , I )$ where $E$ is a finite set (called the ground set) and $I$ is a family of subsets of E (called the independent sets) with the following properties:

  1. The empty set is independent, i.e., $\emptyset \in I$.
  2. Every subset of an independent set is independent, i.e., for each $A' \subset A \subset E$, if $A \in I$, then $A' \in I$
  3. If $A$ and $B$ are two independent sets of $I$ and $A$ has more elements than $B$, there exists $x \in A\backslash B$ such that $B \cup \{x\} \in I$


I could not really find out there what is means with independent sets, so i found that here:

"Two sets A and B are said to be independent if their intersection $A \cap B=\emptyset$.


This in combination with statement 2 confuses me. If $A'$ is a subset of $A$, then doesn't it mean that $A \cap A' = A'$?

Again, i am quite sure there is an essential part of this which i am understanding completely wrong, but i just have no idea what it is.

Thanks in advance for any help!

  • 3
    $\begingroup$ You are confusing two different notions of independent set. I would advise forgetting about the Wolfram reference... $\endgroup$ – Lord Shark the Unknown Nov 26 '17 at 14:35
  • $\begingroup$ The three properties that you give are the definition of an independent set in this theory. It is a different definition than those you cite. A closer analog here would be a linearly independent set. $\endgroup$ – Xander Henderson Nov 26 '17 at 14:46
  1. There are only finitely many words in the English language, and only a smaller subset that we can easily work with. This means that mathematical English is often forced to use the same words to mean different things in different contexts. The word "normal" comes to mind as a particularly egregious example. In this case, independence means something different in the context of matroids than it does in the context of set theory and/or graph theory and/or probability theory.

  2. Matroids seem to generalize the notion of vector spaces. In particular, the notion of an independent set is a generalization of a linearly independent set. You should have that model in your head when you work with matroids. A finite collection of vectors in $\mathbb{R}^2$ is a finite matroid (as long as you throw in the emptyset). An independent set here is a collection of linearly independent vectors, and any linearly independent set has the property that, if you remove a vector, the remaining set is still linearly independent.

  • $\begingroup$ Thank you for your answer! You are speaking about linear independent vectors, does that mean like this: en.wikipedia.org/wiki/Linear_independence, or is this again a different meaning? $\endgroup$ – user3053216 Nov 26 '17 at 15:29
  • 1
    $\begingroup$ @user3053216 That is what I mean. Independence in a matroid is meant to generalize the notion of a linearly independent set in a vector space. However, note that in vector-land, a set $\{ v_j \}$ is linearly independent if $\sum_j a_j v_j = 0$ if and only if $a_j = 0$ for all $j$. In a matroid, we may not have addition or scalar multiplication, so we need a slightly different definition that still captures the important relations. Hence the definition you give above. $\endgroup$ – Xander Henderson Nov 26 '17 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.