The definition of a matroid

This post continues my series about definitions.

It has been obvious from the earliest days of the subject that matroids can be defined in very many different ways: in terms of their independent sets, their bases (maximal independent sets), their circuits (minimal dependent sets), their rank function, their hyperplanes, and so on. Indeed, so varied are the definitions, and so unobvious are the connections in some cases, that Garrett Birkhoff coined the term “cryptomorphic” to define this situation: two classes of objects are cryptomorphic if they are “really” the same thing but the link is not clear.

I want to discuss here three rather different definitions of matroids.

The greedy algorithm

The “greedy algorithm” is the most local optimization algorithm possible: at each step, make the move that increases the objective function as much as possible. Of course it doesn’t always work: it is possible to get trapped at a local maximum which is not the global maximum.

More formally, we are given a set E of points with a weight function w from E to the non-negative real numbers; we are also given a family B of subsets of X, and asked to find a member of B of maximum weight. We can suppose that B is closed downwards. Then we start with the empty set, and at each stage add the point of E whose addition yields a set of B and, subject to this, whose weight is maximal. The algorithm terminates when no further point can be chosen.

Now it can be shown that the greedy algorithm succeeds for every possible weight function if and only if B is the set of bases of a matroid. So matroids are the structures in which the greedy algorithm always works.

Ibis families

In this post, I described IBIS families of sets. To recap briefly: let (Si : iE) be a family of sets indexed by E. We assume that E is ordered; say E = {1,…n}. A base for the family is a subset B of E such that the intersection of the sets with indices in B is equal to the intersection of all the sets; it is irredundant if no set contains the intersection of its predecessors. Dima Fon-Der-Flaass and I proved that the three conditions

  • all irredundant bases have the same cardinality;
  • the irredundant bases are preserved by re-ordering;
  • the irredundant bases satisfy the exchange property;

are equivalent; a family of sets with these properties is an IBIS family (an acronym for Irredundent Bases of Invariant Size). According to the third condition, the irredundant bases of an IBIS family are the bases of a matroid on E. Furthermore, every matroid is represented by an IBIS family. This definition allows us to pose some simple questions which are all unanswered as yet. For example, which matroids are represented by IBIS families of subgroups of a group, or subrings of a ring, for example?

Polytopes

In the first of two recent talks by Alex Fink at Queen Mary (which I will say more about at some point), he gave us his favourite definition of a matroid.

Let Δ(n,r) denote the convex hull of the set of zero-one vectors of length n having exactly r ones. A matroid is a polytope whose 1-skeleton is contained in the 1-skeleton of Δ(n,r). This beautifully simple definition hides a lot, not least: where are the elements of the matroid, and where are the independent sets?

The elements of the matroid form the set {1,…n} indexing the coordinates. The vertices of the polytope are the bases of the matroid; the edges are the allowable exchanges (according to the exchange axiom). The rank of a subset A is the maximum, over the polytope, of the sum of the coordinates with indices in A.

For example, Δ(4,2) is a regular octahedron, and represents the uniform matroid of rank 2 on four points. If we modify the matroid by making two elements dependent (that is, take the cycle matroid of a triangle with a double edge), the polytope is the square pyramid formed by cutting the octahedron in two; its edges are still edges of the original octahedron, but it has only five bases, not six.

Footnote

Alex Fink also pointed out to us that the little-known Japanese mathematician Takeo Nakasawa shares with Hassler Whitney the distinction of founding the theory of matroids.

Previous

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s