|
|
Circuits, bases, rank, closure |
|
|
|
||
|
Circuits are minimal dependent sets. A 1-element circuit is a loop.Bases (singular: basis) are maximal independent sets. The rank of a subset X of E, denoted r(X), is the size of the largest independent set contained within X. The closure of a subset X of E, denoted cl(X), is the set X itself, union all the elements of E that can be added to X without increasing the rank.
One can characterize a matroid in terms of its collection of circuits (its independent sets are those sets containing no circuits), its collection of bases (the independent sets are all sets contained within at least one basis), its rank operator (the independent sets are those sets which have rank equal to their own size), or its closure operator (the independent sets are those sets X for which cl(X\x) is not equal to cl(X) for all x in X). In fact, it's desirable (and possible) to have a collection of axioms a matroid given in terms of just one of these four items (in other words, we'd like to be able to define a matroid just in terms of its set of circuits, and not make any reference to any independent sets or anything like that). The only one of these definitions I'll mention -- and there are a handful for each of these four "other objects" -- is the following one, given for circuits: Given a set E and a collection of its subsets C, the set C is a collection of circuits for a matroid if and only if C is such that
I'll conclude this section by mentioning that we can use this circuit characterization to come up with an easier (read: less-impossible) proof that given a graph G, the collection C of all polygons of G forms a collection of circuits for a matroid. This matroid is just the graphic matroid I mentioned in the last section. |
||
|
|
||