What is a matroid?
A matroid is a mathematical construct, just as a group, a field, or a topology is a construct. It has a somewhat surprisingly large number of associated operators or special collections of subsets, and perhaps just as surprisingly, one can use any one of these to "define" what a matroid actually is. I'll be using the following definition, set forth by Oxley (see
References).A matroid M is a finite set E, along with a set I of subsets of E, such that:
- The empty set is in I.
- If X is in I, then every subset of X is also in I.
- If X and Y are both in I, and |X| is larger than |Y|, then there is some element x of X\Y such that Y(union){x} is also in I.
Some other notation: E is called the ground set of M, and the set I is the collection of independent subsets of E. Those subsets of E which are not in I are called dependent. Also, it's common to write the set Y(union){x} as Y(union)x, dropping the brackets.
Some of you are doubtless thinking now of vectors, because of the word independent. Yes, some of matroid theory came about as a result of its link to the study of vectors and vector spaces, but matroids have links to a great number of surprisingly different topics, some of which you'll see in the next section.
As a last note in this section, I'll just say that isomorphism of matroids is defined in the obvious manner, and so the literature often simply considers all isomorphic matroids to me the same matroid, regardless of the names one gives to the elements of the ground set E. This is much the same as we say that there is only one field of order three -- in actuality, there are an infinite number of them, but they're all isomorphic, and so we just consider them to be one and the same.