Matroids (sample post)

A collection M of nonempty subsets of a set E is a matroid on E if (1) no member of M is a proper subset of another, and (2) for a and b two elements of E, given X and Y members of M such that a is in the intersection of X and Y and b in X – Y, there exists a member Z of M such that a is not in Z, b is in Z and Z is contained in the union of X with Y. 

Let E be a fixed set and M be a matroid on E. The members of E are called the cells and the members of M the atoms of the matroid. A dendroid D of M is a minimal subset of E that has nonempty intersection with every atom of M. 

Let G be a graph, denote the set of vertices by V(G) and the set of edges by E(G). A spanning tree of  G is a subgraph of G which is a tree and whose vertex set includes all V(G). Trees are acyclyc connected graphs. A principal forest of G is a subgraph of G whose intersection with each component of G is a spanning  tree of that component. In general G contains a number of cycles. Each cycle is completely described by its set of edges.  Denote the collection of all cycles of G given as nonempty subsets of edges by P(G). This is called the polygon-matroid of G.  

The following is a nice elementary result from the mid-sixties proved by Tutte in his Lectures on Matroids (see Theorem 2.21).

Theorem. The dendroids of P(G) are the complements in E(G) of the edge sets of the principal forest of G.

Advertisements