Graphs, Matroids


Like many graph theoretic concepts, the cycles of a graph have a generalization in set theory.

Let a matroid be a set of elements M, and a family of nonempty subsets C1, C2, etc, which we will call cycles. No cycle is a proper subset of another cycle, and the union of two different cycles, minus their intersection, is or contains another cycle.

Every graph has an associated matroid (although matroids do not necessarily map back to graphs). Let M be the set of edges, while each cycle in the graph corresponds to a cycle in the matroid. Review the properties of cycles and verify that the matroid properties are satisfied.

An equivalent definition of matroid establishes a family of subsets S1, S2, etc, which we shall call independent sets. The subset of an independent set is always independent, and maximal independent sets have the same cardinality. To map a graph onto a matroid in this sense, let each acyclic subgraph determine an independent set. Each maximal acyclic subgraph is a tree or forest, having a fixed number of edges.

To show equivalence, begin with a matroid defined in terms of cycles, and let independent sets be subsets of M that contain no cycles. Clearly the subset of an independent set contains no cycles, hence it is another independent set. Let V be the largest independent set. Adding any element x to V will produce at least one cycle. However, adding x cannot produce more than one cycle, since the set C1+C2, with x crossed out, would be a subset of V, and V would contain a cycle. Therefore adding x and deleting one of the other elements in the resulting cycle produces a new maximal independent set. Thus V can be gradually transformed into any other independent set U, by taking any element x in U-V, adding it to V, and deleting an element from V-U. Once all elements are transferred, the new independent set contains U, and is as large as V.

Using similar arguments, independent sets imply cycles. A cycle is a minimal nonempty set that is not contained in an independent set. By definition, a cycle cannot contain another cycle. Merge two cycles and delete their intersection, and you have a set that does not intersect the independent sets. If it isn't a cycle, it has a minimal cycle inside it. You'll notice that cycles lead to independent sets, which map back to the same cycles.