Some examples of matroids

I'll just give three of what I perceive to be the most common canonical examples of matroids.

1. Let E be a finite set of vectors from a vector space, and let I be the set of linearly independent subsets of vectors of E. Then M=(E, I) is a matroid. I've seen this called a vectorial matroid. For those of you who have worked with vectors, the three axioms given in the definition of a matroid rather obviously hold when they are applied to a finite collection of vectors for some vector space, taking "independent" to mean "linearly independent". The third of the axioms simply states that the subspace generated by Y (i.e., the smaller independent set) cannot contain all of X (the larger independent set).

It is of great interest to find out what matroids are (isomorphic to) vectorial matroids over a given field, and this is talked about later, in the section on representability. Just keep in mind for now that not all matroids are vectorial matroids.

2. Let r and n be nonnegative integers with r no larger than n. Let E be an n-element set, and let I be the collection of all subsets of E of size r or less. Then it's easy to see that M=(E, I) is a matroid. This is called the uniform matroid of rank r on n elements, and it's denoted U(r, n).

3. Those of you familiar with graphs (meaning graphs from Graph Theory, not Cartesian plane graphs) can skip the rest of this paragraph. A graph can be loosely thought of as a collection of dots on a piece of paper (these dots are called vertices) which are connected by paths that travel from one vertex to another (sometimes the path goes from a vertex back to itself); these paths are called edges, and the places where the edges cross don't count as actual crossings unless they meet at one of the prescribed vertices. A polygon (sometimes called a circle, cycle, or circuit) in a graph G is a path that begins at one vertex, travels along edges to hit other vertices, and eventually comes back to the starting vertex, without repeating any vertices except for the fact that the first and last vertices are the same.

Given a graph G, we let E be the set of all edges of E, and we let I be the subsets of E whose induced subgraphs contain no polygons (meaning, no subset of E is a collection of edges from a polygon). Then M=(E, I) is a matroid again, this one being called the graphic matroid M(G). It's not all that easy to show that I actually satisfies the three axioms given in the definition -- it's much easier to use a later characterization (see the next section).

It's rather interesting that there's this nice connection between graph theory and vector spaces, don't you think? Whitney certainly did, and so do I.

Previous | Matroid Index | Next