Minors

There are two basic ways to get "sub-matroids", one of which is rather obvious, the other of which is less so. Given an element x of the ground set E, we can either delete x, or contract it.

To delete x, we just think of knocking x right out of the ground set E; the new independent sets are {T\x | T in I}. The new matroid we get is denoted M\x. If we continually delete elements so that we've deleted an entire set X from the matroid, we denote the new matroid M\X. To delete an element/edge x from a graphic matroid M(G), we just erase that edge from the graph (but we leave its vertices in place).

Contraction isn't so easy. The contraction of M by x, denoted M/x, is defined (not very pleasantly) as M/x = (M*\x)*, but if x is a loop of M, we just delete it normally. To contract a non-loop element x of a graph G, think of shrinking the edge down to nothing, pulling the edge's end-vertices together, so that the edge itself vanishes and its endpoints have been welded together into a single vertex. (To contract a loop, we just delete it.) M/X is defined in the obvious way.

A minor of a matroid M is a matroid gotten from M by contracting some (or none) of M's elements and deleting others. In obtaining a minor, it doesn't matter which order you delete or contract in, or whether you do deleting or contracting first. Thus, we'll always be able to write minors as M\S/T (where we've deleted all the elements in the set S, and contracted out all the elements in the set T).

That's all I'll say about minors. Again, they're not very easy to grasp right off; just think of them as a sort of "sub-matroid" for now, and you'll be fine.

Previous | Matroid Index | Next