{"id":6246,"date":"2026-07-06T17:54:27","date_gmt":"2026-07-06T21:54:27","guid":{"rendered":"https:\/\/matroidunion.org\/?p=6246"},"modified":"2026-07-06T17:54:28","modified_gmt":"2026-07-06T21:54:28","slug":"matroid-varieties","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=6246","title":{"rendered":"Matroid varieties"},"content":{"rendered":"\n

Universal models for graphic and representable matroids<\/h2>\n\n\n\n

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})$.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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$.<\/p>\n\n\n\n

Dowling geometries<\/h2>\n\n\n\n

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<\/a> in the context of biased graphs, but let’s briefly recall their definition.<\/p>\n\n\n\n

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$.<\/p>\n\n\n

\n
\"\"<\/a>
Two $\\mathbb{Z}_3$-gain graphs. In the theta-graph on the left, all cycles are balanced; in the theta-graph on the right, only one cycle is balanced. Group elements are written additively.<\/figcaption><\/figure><\/div>\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Varieties<\/h2>\n\n\n\n

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<\/a> from 1982 states that the answer is, essentially, no.<\/p>\n\n\n\n

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)<\/em> for every $n$, $M_n$ is a rank-$n$ matroid, and (ii)<\/em> 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$.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Theorem (Kahn\u2013Kung, 1982).<\/strong> If $\\mathcal{M}$ is a variety of matroids, then $\\mathcal{M}$ is one of the following classes:<\/p>\n\n\n\n