Universal models for graphic and representable matroids

Graphs have the useful property that each of them is a restriction of a complete graph on the same set of vertices. This property makes it easy, for example, to generate a random graph: simply flip a coin for each edge in the complete graph, and include the edge if the coin turns up heads. In matroidal terms, the property is that every rank-$n$ simple graphic matroid is a restriction of $M(K_{n+1})$.

There is another well known class of matroids for which a similar observation holds: those representable over a fixed finite field, in which case the projective geometry of a given rank serves as a “universal model”, in the sense that every simple rank-$n$ matroid that is representable over the finite field $\mathbb{F}_q$ can be obtained from $\text{PG}(n-1,\mathbb{F}_q)$ by restriction.

On the other hand, the same is not true for the class of all matroids. Even for matroids of rank 2, there is no universal model $M$ such that each such matroid is a restriction of $M$.

Dowling geometries

The class of graphic matroids is only one member of a family of classes with the same property: the Dowling matroids. These have been discussed before on the blog in the context of biased graphs, but let’s briefly recall their definition.

The rank-$n$ Dowling geometry $\text{DG}(n, \Gamma)$ is determined by a finite group $\Gamma$, similar to how projective geometries are determined by a field, and a Dowling matroid is simply any matroid that can be obtained by restricting $\text{DG}(n, \Gamma)$. Let’s assume that the operation in $\Gamma$ is multiplication. A $\Gamma$-gain graph is a graph $G$, together with an orientation of the edges of $G$ and a gain function $\varphi\colon E(G)\to\Gamma$. For a cycle $C$ of $G$, we pick a starting point an an orientation of $C$, which gives us an order of the edges of $C$, say $C = e_1e_2\ldots e_k$. Define $\varphi(C) = \varphi(e_1)^{s_1} \varphi(e_2)^{s_2} \ldots \varphi(e_k)^{s_k}$, where $s_i = 1$ if the orientation of $e_i$ agrees with the orientation of $C$, and $s_i = -1$ otherwise. The cycle $C$ is called “balanced” if $\varphi(C)$ is the identity in the group; it is a straightforward exercise to check that balance of $C$ does not depend on the orientation or starting point of $C$.

A $\Gamma$-gain graph $G$ gives rise to a matroid on $E(G)$ whose circuits are the balanced cycles of $G$, as well as the theta-subgraphs with three unbalanced cycles, and subgraphs formed by two edge-disjoint unbalanced cycles connected by a (possibly empty) path that is disjoint from the two cycles except for its first and last vertex.

We can now define the Dowling geometry $\text{DG}(n,\Gamma)$ as the matroid obtained from the biased graph $K_n^\Gamma$ whose vertices are labelled $1, 2, \ldots, n$, which has one (unbalanced) loop attached at each vertex, and which has $|\Gamma|$ edges between vertices $i$ and $j$ (directed in towards the largest label, say), each labelled with a different group element.

If every (non-loop) edge is labelled by the identity in $\Gamma$, then every cycle is balanced. In particular, $\text{DG}(n,\langle 1\rangle) \cong M(K_{n+1})$, where we write $\langle 1\rangle$ for the trivial group. So, graphic matroids are Dowling matroids.

Varieties

Apart from graphic matroids, matroids representable over finite fields, and Dowling matroids, are there any other natural classes of matroids that have a sequence of universal models? It turns out that we have to be a bit careful with our definitions, but a beautiful result by Kahn and Kung from 1982 states that the answer is, essentially, no.

First, we need to define precisely what we mean by a universal model. Let $\mathcal{M}$ be a class of matroids. A sequence $M_1, M_2, M_3, \ldots$ of matroids is called a sequence of universal models for $\mathcal{M}$ if (i) for every $n$, $M_n$ is a rank-$n$ matroid, and (ii) for every $n$, every simple rank-$n$ matroid in $\mathcal{M}$ is isomorphic to a restriction of $M_n$. Thus, $\text{PG}(0,\mathbb{F}_q), \text{PG}(1,\mathbb{F}_q), \text{PG}(2, \mathbb{F}_q), \ldots$ is a sequence of universal models for the $\mathbb{F}_q$-representable matroids, and $\text{DG}(1,\Gamma), \text{DG}(2,\Gamma), \text{DG}(3,\Gamma), \ldots$ is a sequence of universal models for the Dowling matroids over the group $\Gamma$.

Second, we need to be careful about our definition of “natural” class of matroids. A class $\mathcal{M}$ is called a hereditary class if it is closed under isomorphism, as well as under taking minors and direct sums; so, if $M,N \in \mathcal{M}$ and $e$ is an element of $M$, then each of $M\backslash e$, $M/e$, and $M\oplus N$ are in $\mathcal{M}$ as well.

A variety of matroids is a hereditary class with a sequence of universal models. We are now ready to state Kahn and Kung’s result.

Theorem (Kahn–Kung, 1982). If $\mathcal{M}$ is a variety of matroids, then $\mathcal{M}$ is one of the following classes:

• Matroids representable over a finite field;
• Dowling matroids over a finite group; or
• Matchstick geometries or Origami geometries.

The classes of matchstick and origami geometries have low connectivity. The universal models for matchstick geometries are $U_{2,n+1}^{\oplus k}$ and $U_{2,n+1}^{\oplus k} \oplus U_{1,1}$, depending on the parity of the rank, while the universal models for origami matroids are obtained from a basis ${b_1, …, b_r}$ by adding $n$ points freely to each of the lines spanned by pairs $\{b_i, b_{i+1}\}$.

Each of the assumptions (that the class of matroids be minor-closed, closed under direct sum, and have a sequence of universal models) in Kahn and Kung’s theorem is necessary for its conclusion. It is an amusing exercise to come up with classes of matroids that satisfy only a subset of these assumptions but not the others.