Many different areas of combinatorics and optimization are interested in objects that admit a rough duality between packing and covering. A classic example is that every bipartite graph either has a matching of size $k$, or has a set of at most $k-1$ vertices which “hit” every edge (i.e. a vertex cover of size $k$; this is Kőnig’s theorem).
Another example where only a rough duality is possible was proven by Erdős and Pósa. They showed that every graph either has $k$ cycles that are pairwise vertex-disjoint, or has a set of $\mathcal{O}(k \log{k})$ many vertices which hit every cycle (i.e. a set of vertices whose deletion yields a forest). Note that this is not an exclusive “or”; some graphs have both. But any graph with a hitting set of size $r$ has at most $r$ pairwise vertex-disjoint cycles.
In general, for any problem which is suitable to study within this framework, the maximum size of a packing should be at most the minimum size of a covering (or at least roughly so). This is typically the easy direction (I would love to hear in the comments about any natural examples where it is not the easy direction!). If the other direction is also (roughly) satisfied, then the set of objects is said to have the Erdős-Pósa property, meaning that if there is no packing of size $k$, then there is a covering of size at most $f(k)$, for some function $f$.
Related Topics
I have discussed examples of exact combinatorial min-max theorems before, and how these problems often have an underlying matroid. One of the most general theorems about which hypergraphs admit a rough duality between packing and covering is due to Ding, Seymour, and Winkler and generalizes well-known results on VC-dimension. Other key terms are LP-rounding, total unimodularity, clutters, … . Erdős-Pósa problems are very actively researched; see for instance the recent workshop in Poland. Geelen and Kabell also proved a different matroidal Erdős-Pósa property.
Binary Matroids
For binary matroids there is a somewhat different notion of covering. It is convenient to think of a graph with a “small vertex cover” as being “close to” a graph whose largest packing has size zero. So instead of deleting a small set of vertices, we add a low-rank matrix. Formally, consider a binary matroid $M$ which is represented by the columns of an $n \times m$ binary matrix $A$. A rank-$k$ perturbation of $M$ is then any matroid $M’$ which can be represented by the columns of $A+B$, where $B$ is an $n \times m$ binary matrix of rank at most $k$. We perform addition over the binary field.
Theorem For any planar graph $H$, there is a function $f_H$ so that for every integer $k$, every binary matroid either has the cycle matroid of $k$ vertex-disjoint copies of $H$ as a minor, or has a rank-$f_H(k)$ perturbation which does not have $M(H)$ as a minor.
This really is an Erdős-Pósa property in the sense that it gives a rough min-max theorem for packing $M(H)$ minors. When $H$ is a cycle and the matroid is graphic, one should roughly think of the theorem as saying the following. Note that this is a conjecture; it does NOT just follow from our theorem. This is because, informally, our perturbations are allowed to leave the graphic world, and the ones below are not.
Conjecture There exists a function $f$ so that for any integer $k$, every multigraph either 1) has a minor with $k$ different blocks, each of which is a cycle, or 2) can be turned into a forest by performing the following operations at most $f(k)$ times:
identify two vertices $u$ and $v$ into a single vertex. This operation does not change the number of edges. So for instance if $u$ and $v$ were adjacent originally, there will be a loop at the new vertex after identification.
split a vertex $v$ into two vertices $v_1$ and $v_2$. This operation is the opposite of identification.
Thank you to Mathieu Rundström for correcting the previous wrong version of the conjecture!
This is a guest post by Donggyu Kim, who discusses the cycles of an embedded graphs (ribbon graphs) and their interactions with the associated delta-matroids. It is based on joint work with Matt Baker and Changxin Ding [1].
Ribbon graphs and quasi-trees
An embedded graph $G$ is a graph cellularly embedded in a closed (possibly non-orientable) surface $\Sigma$. We think of vertices and edges as disks and rectangles, obtained by thickening the points and lines by a sufficiently small $\epsilon>0$ in the surface $\Sigma$. In this sense, embedded graphs are often called ribbon graphs; we will use the two notions interchangeably.
A typical example of an embedded graph is a connected plane graph – but instead of embedding the graph in the plane, let’s embed it on the sphere! One easy exercise is that a spanning subgraph $T$ is a spanning tree if and only if it, viewed as a ribbon graph, has a unique boundary component. However, these two notions diverge when the surface $\Sigma$ is not the sphere. Every spanning tree has a unique boundary component, but the converse doesn’t hold. We call a spanning subgraph with a unique boundary component a quasi-tree. The figure below depicts an embedded graph on the torus $\mathbb{T}^2$; it has a quasi-tree that is not a spanning tree. Since quasi-trees capture topological information, they are the right analog of spanning trees for embedded graphs.
Figure 1. A plane graph (an embedded graph on the sphere $\mathbb{S}^2$, left) and the corresponding ribbon graph (middle). The spanning subgraph with edge set $\{1,4,5\}$ (top right) has a unique boundary component as a ribbon graph, whereas the spanning subgraph with edge set $\{1,2,5\}$ (bottom right) has three boundary components – don’t miss the boundary of the degree-$0$ vertex.
Ribbon cycles
Question. We have seen that quasi-trees are the right analog of spanning trees for embedded graphs. What should play the role of cycles?
Before answering the question, let’s fix a convention. Since we’ll only care about the topological properties – such as whether $\Sigma – H$ is connected for a subgraph $H$ (we’ll make this more precise below) – every subgraph in this post will be assumed to be spanning (i.e., containing all vertices of the original graph). Hence, we will identify an edge set with the corresponding spanning subgraph. Moreover, we may view $\Sigma – H$ either as removing $H$ as a graph or as a ribbon graph. These two viewpoints are homeomorphic, so the reader may adopt whichever is more convenient.
With this convention in place, let’s return to the plane case (Figure 1). For any cycle $C$, the surface $\Sigma – C$ is disconnected; indeed, the cycles are exactly the minimal subgraphs with this property. What happens for general embedded graphs? Consider Figure 2. Even after removing any cycle from the torus $\mathbb{T}^2$, it remains connected. Moreover, there is no subgraph $H$ for which $\Sigma – H$ is disconnected.
Figure 2. A graph embedded on the torus (left) and the corresponding ribbon graph (right). It has four quasi-trees with edge sets $\{1\}$, $\{2\}$, $\{3\}$, and $\{1,2,3\}$.
Ordinary cycles alone cannot be the right answer on a general surface. To fix this, we need to bring the dual graph into the picture. Let us draw both the graph $G$ embedded on the torus, shown in Figure 2, and its geometric dual $G^*$ simultaneously; see Figure 3. The graph $G$ is drawn in black, and the dual $G^*$ is drawn in red. We can then separate the torus $\mathbb{T}^2$ into two components by removing a cycle $\{1,2\}$ of $G$ together with a cycle $\{3^*\}$ of $G^*$.
Figure 3. The embedded graph $G$ in Figure 2 together with its dual $G^*$. It has four ribbon cycles: $\{1,2,3^*\}$, $\{1,2^*,3\}$, $\{1^*,2,3\}$, and $\{1^*,2^*,3^*\}$.
Denote $E:=E(G)$ and $E^*:= E(G^*) = \{e^*:e\in E\}$. A subset $S \subseteq E\cup E^*$ is a subtransversal if it contains at most one of $e$ or $e^*$ for each edge $e\in E$.
Definition. Let $G$ be an embedded graph on $\Sigma$. A ribbon cycle of $G$ is a subtransversal $C \subseteq E\cup E^*$ that minimally separates the surface $\Sigma$, meaning that $\Sigma – C$ is disconnected while $\Sigma – C’$ is connected for every $C’\subsetneq C$.
If $G$ is a plane graph, then the ribbon cycles are exactly the cycles and the stars of bonds. For example, the ribbon cycles of the plane graph in Figure 1 (see also Figure 4) are
$\{1,2,5\}$, $\{3,4,5\}$, $\{1,2,3,4\}$, $\{1^*,2^*\}$, $\{3^*,4^*\}$, $\{1^*,3^*,5^*\}$, $\{1^*,4^*,5^*\}$, $\{2^*,3^*,5^*\}$, and $\{2^*,4^*,5^*\}$.
Figure 4. The plane graph in Figure 1 (black) and its geometric dual (red).
The embedded graph on the torus in Figure 3 has four ribbon cycles:
$\{1,2,3^*\}$, $\{1,2^*,3\}$, $\{1^*,2,3\}$, and $\{1^*,2^*,3^*\}$.
Each ribbon cycle $C$ is a union of cycles in $G$ and cycles in $G^*$. In other words, $C\cap E$ forms an Eulerian subgraph of $G$, and $C\cap E^*$ forms an Eulerian subgraph of $G^*$. The ribbon cycle $\{1^*,2^*,3^*\}$ consists of three cycles – $\{1^*\}$, $\{2^*\}$, and $\{3^*\}$ – which share a common vertex.
The following is an amusing exercise, a counterpart of the orthogonality of cycles and bonds in ordinary graphs. For an edge $e$ of an embedded graph $G$, we denote $(e^*)^* = e$, and write $C^* := \{e^* : e\in C\}$ for any subset $C\subseteq E\cup E^*$.
Exercise (Orthogonality). Let $C_1$ and $C_2$ be two ribbon cycles of $G$. Then $|C_1\cap C_2^*| \ne 1$.
Circuits of ribbon-graphic delta-matroids
Now that we have a topological candidate for the “cycles” of a ribbon graph, the next question is whether the delta-matroid associated with the ribbon graph captures the same objects. Carolyn Chun explained earlier that the quasi-trees of an embedded graph $G$ form the bases of a delta-matroid, denoted $D(G)$.
A graph gives rise to its graphic matroid in (at least) two familiar ways: by collecting maximal acyclic sets, we obtain the bases; by collecting cycles, we obtain the circuits. Thus one may ask whether the ribbon cycles of an embedded graph $G$ are the circuits of $D(G)$. However, there are two hurdles. First, the ground sets do not match, $E$ vs. $E\cup E^*$. Second, the bases of a delta-matroid are not equicardinal—which raises a problem, since bases cannot in general be recovered from circuits if the circuits are defined as minimal subsets not contained in any basis.
These issues can be easily resolved by introducing symmetric matroids [2] (also known as 2-matroids; see Irene Pivotto’s post), which are a homogenized version of delta-matroids.
Let $D = (E,\mathcal{B})$ be a finite set system. Then $D$ is a delta-matroid if and only if $\mathrm{lift}(D) := (E\cup E^*, \mathcal{B}’)$ is a symmetric matroid, where $\mathcal{B}’ := \{B\cup (E\setminus B)^* : B\in \mathcal{B}\}$. Since all bases of a symmetric matroid have the same cardinality, it makes sense to define its circuits. A circuit of a symmetric matroid is a minimal subtransversal that is not contained in any basis.
Now we can state the following:
Theorem. The circuits of $\mathrm{lift}(D(G))$ are exactly the ribbon cycles of an embedded graph $G$.
To prove this, let us first see equivalent characterizations of quasi-trees. Recall that a quasi-tree $Q$ is a spanning subgraph with a unique boundary component. Hence, $\Sigma-Q$ also has a unique boundary component, which implies that $\Sigma-Q$ is connected. The following folklore result says that an even stronger statement holds.
Proposition. For $Q\subseteq E(G)$, the following are equivalent:
$Q$ is a quasi-tree of $G$.
$(E\setminus Q)^*$ is a quasi-tree of the dual $G^*$.
$\Sigma – Q – (E\setminus Q)^*$ is connected.
We also note the following corollary orthogonality.
Exercise. For any subtransversal $S\subseteq E\cup E^*$ such that $\Sigma – S$ is connected, there is a transversal $T$ (that is, a subtransversal of size $|E|$) containing $S$ such that $\Sigma – T$ is still connected.
Hence, quasi-trees $Q$ can be identified with “maximal subtransversals $Q\cup (E\setminus Q)^*$ whose removal does not disconnect the surface,” whereas ribbon cycles are “minimal subtransversals whose removal disconnects the surface.” This proves the theorem above. Great! Ribbon cycles really are the right circuit-like objects.
Representations of ribbon-graphic delta-matroids via signed ribbon cycles
A natural next question is whether other familiar graph/matroid correspondences also survive in the ribbon-graph world. For example, if $G$ is an ordinary connected graph with an arbitrary orientation, we can quickly find a regular representation of $M(G)$ by examining the fundamental bonds with respect to a spanning tree:
Fix a spanning tree $T$.
For each $e\in E(T)$, let $C_e$ be the unique bond in the complement of $T-e$, called the fundamental bond of $e$ with respect to $T$.
Since a reference orientation of $G$ is given, we can identify $C_e$ with a $(0,\pm 1)$-vector (of course, this is determined up to sign, and we may choose either sign).
Construct a real $(|V|-1)$-by-$|E|$ matrix $\mathbf{A}$ by taking the vectors $C_e$ as its rows.
Then $\mathbf{A}$ is a totally unimodular matrix representing $M(G)$. In the same way, one can construct a totally unimodular matrix representing $M^*(G)$ by examining the fundamental cycles.
Remarkably, almost the same construction works for “orientable” ribbon graphs. Fix one of the two orientations of $\Sigma$. Here we choose the counterclockwise orientation with respect to normal vectors, the so-called right-hand rule. Fix a reference orientation for $G$. Then we can assign the corresponding dual reference orientation to $G^*$; see the figure below.
Figure 5. For each oriented edge $e$, we assign the dual orientation of $e^*$ as depicted on the left. The illustration on the right shows a reference orientation of $G$ in Figure 3 together with the corresponding dual reference orientation of $G^*$.
The point of the next four steps is to construct a matrix representing $\mathrm{lift}(D(G))$ from signed ribbon cycles.
Fix a quasi-tree $Q$. Denote $B := Q\cup (E\setminus Q)^*$.
For each $e \in E(G)$, let $C_e$ be the ribbon cycle in $B\triangle\{e,e^*\}$, which always exists and is unique!
We identify $C_e$ with a $(0,\pm 1)$-vector $\mathbf{v}_e$ in $\mathbb{R}^{E\cup E^*}$ defined as follows:
$\Sigma-C_e$ separates the surface into two components. Choose one of them, say $\Sigma’$.
$C_e$ is exactly the boundary of $\Sigma’$. Because $\Sigma’$ is oriented, we obtain a $(0,\pm 1)$-vector $\mathbf{v}_e$ supported on $C_e$ by setting \[\mathbf{v}_e(f) =\begin{cases}+1 & \text{if the orientation of $f\in C_e$ agrees with that of $\Sigma’$}, \\-1 & \text{if the orientation of $f\in C_e$ is opposite to that of $\Sigma’$}, \\0 & \text{if $f\notin C_e$}.\end{cases}\]
Construct a real $|E|$-by-$2|E|$ matrix $\mathbf{A}$ by taking the vectors $\mathbf{v}_e$ as its rows.
Proposition. Let $X$ be a transversal of $E\cup E^*$. Then $X \cap E$ is a quasi-tree of $G$ if and only if the $|E|$-by-$|E|$ submatrix $\mathbf{A}[(E\cup E^*) \setminus X]$ with columns $(E\cup E^*) \setminus X$ is nonsingular; in fact, its determinant is $\pm 1$.
Let’s see an example in the following figure.
Figure 6. Choose a quasi-tree $Q = \{1,2,3\}$. Then the ribbon cycles defined in Step 2 are $C_1 = \{1^*,2,3\}$ (left), $C_2 = \{1,2^*,3\}$ (middle), and $C_3 = \{1,2,3^*\}$ (right). The removal of each ribbon cycle $C_i$ from the torus $\mathbb{T}^2$ disconnects it into two components. In Step 3(a), we color $\Sigma’$ yellow.
The vectors $\mathbf{v}_i$ defined in Step 3(b) are
The entries in the first row are indexed by $1,2,3$ from left to right, and the entries in the second row are indexed by $1^*,2^*,3^*$ from left to right. Thus, the resulting matrix $\mathbf{A}$ in Step 4 is
where the columns are indexed by $1,2,3,1^*,2^*,3^*$ in this order. You can check that the matrix $\mathbf{A}$ satisfies the proposition.
After multiplying some rows by $-1$ and rearranging the columns, the matrix $\mathbf{A}$ in the proposition can be written as a matrix of the form $\left( \begin{array}{c|c} \mathbf{I}_n & \mathbf{S} \end{array} \right)$, where $\mathbf{I}_n$ is the identity matrix with size $n:=|E|$ and $\mathbf{S}$ is a principally unimodular skew-symmetric matrix. An equivalent construction of $\mathbf{S}$ was first given by Bouchet [2] in terms of (principally) unimodular orientations of circle graphs. If you are curious about the relationship between the above matrix construction and Bouchet’s construction, see Appendix A of [1]. Merino, Moffatt, and Noble [3] pointed out that
\[\det(\mathbf{I}_n + \mathbf{S}) = \# \text{quasi-trees of $G$},\]
The above matrix construction depends strongly on the orientability of the surface. This appears explicitly in Step 3, where we choose the signs of the entries of the $(0,\pm 1)$-vector $\mathbf{v}_e$. It is also implicit in Step 2, since we cannot guarantee the existence of $C_e$ when the surface is non-orientable.
Question. How about non-orientable ribbon graphs? Could we also obtain nice representations by unimodular matrices?
The short answer is: yes for some non-orientable ribbon graphs, but not for every ribbon graph. I will continue this discussion in the next post. See you then!
Acknowledgements. I thank Matt Baker, Changxin Ding, and Jorn van der Pol for helpful comments.
References
[1] Matthew Baker, Changxin Din, and Donggyu Kim. The Jacobian of a regular ortogonal matroid and torsor structures of quasi-trees of ribbon graphs, 2025. arXiv preprint.
[2] André Bouchet. Greedy algorithm and symmetric matroids. Math. Program. 38(2):147–159, 1987. doi:10.1007/BF02604639.
[3] Criel Merino, Iain Moffatt, and Steven Noble. The critical group of a combinatorial map. Comb. Theory 5(3), paper no. 2, 41, 2025. doi:10.5070/C65365550.
The goal of this post is to introduce readers to a new construction for matroids from gain graphs [Wal26+]. Given a graph $G$ with oriented edges invertibly labeled by elements of a group $\Gamma$ (a $\Gamma$-gain graph), one can use the labeling to construct two different matroids on the edge set of $G$: the $\Gamma$-frame matroid and the $\Gamma$-lifted-graphic matroid. This post considers the following question.
Question 1. If the edges of $G$ are invertibly labeled by two different groups $\Gamma_1$ and $\Gamma_2$, can one construct a matroid on the edge set of $G$ that recovers the $\Gamma_2$-frame matroid when $\Gamma_1$ is trivial and the $\Gamma_1$-lifted-graphic matroid when $\Gamma_2$ is trivial?
To allow for interactions between $\Gamma_1$ and $\Gamma_2$, it is useful to work with gain graphs over a group $\Gamma$ so that $\Gamma_1$ is a normal subgroup and $\Gamma_2$ is isomorphic to the quotient group $\Gamma/\Gamma_1$. (If one wishes for no interaction between $\Gamma_1$ and $\Gamma_2$ then $\Gamma$ can be taken to be the direct product of $\Gamma_1$ and $\Gamma_2$.) It turns out that such a construction is possible if the group $\Gamma$ has special structure called a Frobenius partition.
Theorem 1. Let $\Gamma$ be a group with a normal subgroup $\Gamma_1$ and a Frobenius partition $\{\Gamma_1\} \cup \mathcal A$. Then every $\Gamma$-gain graph $(G, \psi)$ has a canonical associated matroid on $E(G)$. This matroid is the $(\Gamma/\Gamma_1)$-frame matroid of $(G, \psi)$ if $\Gamma_1$ is trivial, and is the $\Gamma_1$-lifted-graphic matroid of $(G, \psi)$ if $\Gamma/\Gamma_1$ is trivial.
Understanding this theorem statement requires a good deal of background knowledge, so I’ll spend the first half of this post giving the necessary background, with special attention given to Frobenius partitions of groups, which is a new concept developed specifically for this construction. Then I’ll explain how the construction works, and state a theorem (Theorem 4) which says that under one mild assumption, the Frobenius partition is necessary for such a construction to exist. I’ll finish with some directions for future work. All material from this post can be found in more detail in [Wal26+].
2. Gain graphs and their matroids
Let $G$ be a graph and let $\Gamma$ be a (multiplicatively-written) group. I’ll give the necessary definitions for gain graphs in bulleted form:
An oriented edge of $G$ is a triple $(e, u, v)$ where $e$ is an edge with ends $u$ and $v$.
A $\Gamma$-gain function is a function $\psi$ from the set of oriented edges of $G$ to $\Gamma$ so that $\psi(e, u, v) = \psi(e, v, u)^{-1}$ for every oriented edge $(e, u, v)$ with $u \ne v$. The pair $(G, \psi)$ is a $\Gamma$-gain graph.
For a walk $W = v_1, e_1, v_2, \dots, v_k, e_k, v_{k+1}$ in $(G, \psi)$ we write $\psi(W)$ for $\prod_{i = 1}^k \psi(e_i, v_i, v_{i+1})$, the product of the gain values of oriented edges along the walk.
A cycle $C$ of $G$ is $\psi$-balanced if there is a simple closed walk $W$ on $C$ with $\psi(W) = 1$.
Given a function $\eta \colon V(G) \to \Gamma$, the $\Gamma$-gain function $\psi^{\eta}$ defined by $\psi^{\eta}(e, u, v) = \eta(u)^{-1}\psi(e, u, v)\eta(v)$ for each oriented edge $(e, u, v)$ has the same balanced cycles as $\psi$. The function $\eta$ is a switching function, and $\psi$ and $\psi^{\eta}$ are switching-equivalent.
If $\Gamma_1$ is a normal subgroup of $\Gamma$, we write $\psi/\Gamma_1$ for the $(\Gamma/\Gamma_1)$-gain function of $G$ whose value at an oriented edge $(e, u, v)$ is the image of $\psi(e, u, v)$ under the natural homomorphism from $\Gamma$ to $\Gamma/\Gamma_1$.
As a canonical example of a gain graph, if $\Gamma = \{1, -1\}^{\times}$ (the group of order 2 written multiplicatively) and $(G, \psi)$ is a $\Gamma$-gain graph (a signed graph), then a cycle of $G$ is $\psi$-balanced if and only if it has an even number of edges with label $-1$. For an example of a gain function over a quotient group, see Figure 1.
Figure 1: Image (a) shows a $\mathbb Z$-gain graph $(G, \psi)$ with one balanced cycle, (b) shows the $\mathbb Z$-gain graph obtained from $(G, \psi)$ by switching at the top vertex with value $-5$, and (c) shows the $(\mathbb Z/2\mathbb Z)$-gain graph $(G, \psi/2\mathbb Z)$, which has three balanced cycles.
There are two matroids on the edge set of $G$ associated with a $\Gamma$-gain graph $(G, \psi)$, both originally defined by Zaslavsky [Zas91] using the subgraphs shown in Figure 2:
The circuits of the frame matroid $F(G, \psi)$ of $(G, \psi)$ are the $\psi$-balanced cycles, and the theta graphs, tight handcuffs, or loose handcuffs with all cycles unbalanced.
The circuits of the lift matroid $L(G, \psi)$ of $(G, \psi)$ are the $\psi$-balanced cycles, and the theta graphs, tight handcuffs, or bracelets with all cycles unbalanced.
Figure 2: Theta graphs, tight handcuffs, loose handcuffs, and bracelets are subdivisions of the graphs (a), (b), (c), and (d), respectively.
Note that if $\Gamma$ is trivial then $F(G, \psi)$ and $L(G, \psi)$ are both equal to the graphic matroid of $G$. If $\Gamma$ is a subgroup of $\mathbb F^{\times}$ for a field $\mathbb F$ then the frame matroid $F(G, \psi)$ is $\mathbb F$-representable, and if $\Gamma$ is a subgroup of $\mathbb F^+$ then the lift matroid $L(G, \psi)$ is $\mathbb F$-representable [Zas03]. See Figure 3 for an example of a representable lifted-graphic matroid. For broader context that is not relevant for the remainder of this post, frame matroids and lifted-graphic matroids can be defined more generally from biased graphs [Zas89] (as explained elsewhere on this blog), and both are special cases of quasi-graphic matroids [GGW18, BFS20].
Figure 3: A $\textrm{GF}(5)^+$-gain graph $(G, \psi)$ with one balanced cycle and a $\textrm{GF}(5)$-representation of the lifted-graphic matroid $L(G, \psi)$.
The construction of the lift matroid is a special case of the following more general construction, which will also be used to obtain the matroids of Theorem 1.
Theorem 2 [Cra65, Bry86]. Let $M$ be a matroid on ground set $E$ and let $\mathcal C$ be a set of circuits of $M$ so that
if $C_1,C_2$ are circuits in $\mathcal C$ for which $|C_1 \cup C_2| – r_M(C_1 \cup C_2) = 2$, then each circuit $C$ of $M$ contained in $C_1 \cup C_2$ is also in $\mathcal C$.
Then the function $r \colon 2^E \to \mathbb Z$ defined, for all $X \subseteq E$, by
$$r(X) = \bigg\{\begin{array}{cc} r_M(X) & \textrm{if each circuit of $M|X$ is in $\mathcal C$} \\r_M(X) + 1 & \textrm{otherwise} \end{array}$$
is the rank function of a matroid on $E(M)$.
The set $\mathcal C$ is a linear class of circuits of $M$, and the pair $(C_1, C_2)$ is a modular pair of circuits. The matroid $M’$ given by the theorem is an elementary lift of $M$, which means that there is a matroid $K$ with an element $e$ so that $K \!\setminus\! e = M’$ and $K/e = M$. It turns out that the $\psi$-balanced cycles of a gain graph $(G, \psi)$ always form a linear class of circuits of the graphic matroid $M(G)$, and the lift matroid of $(G, \psi)$ is precisely the matroid given by Theorem 2 for this linear class.
3. Frobenius partitions of groups
In order to define the matroid of Theorem 1, the group $\Gamma$ must have special structure.
Definition 1. Let $\Gamma$ be a group. A subgroup $A$ of $\Gamma$ is malnormal if $\gamma^{-1}A\gamma$ and $A$ share only the identity for all $\gamma \in \Gamma – A$. A Frobenius partition of $\Gamma$ is a collection $\{\Gamma_1\} \cup \mathcal A$ of subgroups of $\Gamma$ so that the following hold:
Every non-identity element of $\Gamma$ is in exactly one group in $\{\Gamma_1\} \cup \mathcal A$.
$\Gamma_1$ is a normal subgroup of $\Gamma$.
Each group in $\mathcal A$ is a malnormal subgroup of $\Gamma$ and has all conjugates in $\mathcal A$.
The Frobenius partition is nontrivial if it contains at least two nontrivial subgroups, and is trivial otherwise. Note that every group $\Gamma$ has trivial Frobenius partition $\{\Gamma\}$. While most groups do not have a nontrivial Frobenius partition, the following key example shows that they arise naturally in certain types of permutation groups.
Example 1. Let $\Gamma$ be a transitive group of permutations acting on a set $X$ so that each non-identity permutation has at most one fixed point and some non-identity element has a fixed point. It is straightforward to show that for each $x \in X$, the subgroup of permutations that fix $x$ (the stabilizer of $x$) is malnormal, and that any two stabilizers are conjugates. A famous theorem of Frobenius states that if $X$ is finite, then the subgroup of fixed-point-free permutations (derangements) is always a nontrivial normal subgroup of $\Gamma$. (This is not guaranteed when $X$ is infinite, but may be the case, as in the examples below.) So if $\Gamma_1$ is the subgroup of derangements and $\mathcal A$ is the set of stabilizers, then $\{\Gamma_1\} \cup \mathcal A$ is a Frobenius partition of $\Gamma$. This happens in the following special cases:
$X = \mathbb F$ for a field $\mathbb F$ with at least three elements and $\Gamma$ is the group of functions $x \mapsto a + bx$ with $b \ne 0$. Here the normal subgroup of derangements is isomorphic to $\mathbb F^+$ and each stabilizer is isomorphic to $\mathbb F^{\times}$. I’ll write $\mathbb F^+ \rtimes \mathbb F^{\times}$ for this group.
$X = \mathbb R^2$ and $\Gamma = SE(2)$, the special Euclidean group of distance-preserving transformations (isometries) of $\mathbb R^2$. Here the normal subgroup of derangements is $T(2)$ (the group of translations of $\mathbb R^2$), and each stabilizer is isomorphic to $SO(2)$ (the group of rotations of $\mathbb R^2$).
$X = \Gamma_1$ where $\Gamma_1$ is an abelian (additive) group with no elements of order 2, and $\Gamma$ consists of pairs where $(a,b)$ with $a \in \Gamma_1$ and $b \in \{1, -1\}$ where $(a, b)$ induces the permutation $x \mapsto a + bx$ of $\Gamma_1$. Here the normal subgroup of derangements is isomorphic to $\Gamma_1$, and each stabilizer is isomorphic to $\{1,-1\}^{\times}$. I’ll write $\Gamma_1 \rtimes \{1,-1\}^{\times}$ for this group.
If $X$ is finite in the previous example, then $\Gamma$ is known as a Frobenius group. So every Frobenius group has a nontrivial Frobenius partition, and conversely, it follows from properties of malnormal subgroups that every finite group with a nontrivial Frobenius partition is a Frobenius group. However, the notion of Frobenius partition gives a seemingly new and interesting generalization of Frobenius groups to infinite groups; see Problem 2.13 in [Wal26+].
4. The construction
I’ll now describe how to construct the matroid of Theorem 1. Let $\Gamma$ be a group with a Frobenius partition $\{\Gamma_1\} \cup \mathcal A$. One can use $\{\Gamma_1\} \cup \mathcal A$ to construct a linear class of circuits of the frame matroid $F(G, \Gamma/\Gamma_1)$. The intuition here is that we want the linear class to be invariant under switching equivalence, that a cycle should be in the linear class if and only if it is balanced, and that every handcuff or theta graph with all gain values in the same set in $\mathcal A$ is somehow special and should be in the linear class. With these ideas, we obtain the following theorem.
Theorem 3. Let $\Gamma$ be a group with a Frobenius partition $\{\Gamma_1\} \cup \mathcal A$ and let $(G, \psi)$ be a $\Gamma$-gain graph. Let $\mathcal C$ be the set of circuits of the frame matroid $F(G, \psi/\Gamma_1)$ so that $C \in \mathcal C$ if and only if
$C$ is a $\psi$-balanced cycle, or
$C$ is a handcuff or a theta graph and there is a switching function $\eta$ and a group $A \in \mathcal A$ so that every oriented edge of $C$ has $\psi^{\eta}$-gain value in $A$.
Then $\mathcal C$ is a linear class of circuits of $F(G, \psi/\Gamma_1)$.
Theorem 3 gives a linear class of circuits of $F(G, \psi/\Gamma_1)$, so applying Theorem 2 with this linear class gives a matroid $M$ on $E(G)$. We make the following observations:
If $\Gamma_1$ is trivial, then $\mathcal A = \{\Gamma\}$ and every circuit of $F(G, \psi/\Gamma_1)$ is in $\mathcal C$, so $M = F(G, \psi/\Gamma_1)$.
If $\Gamma/\Gamma_1$ is trivial, then $F(G, \psi/\Gamma_1)$ is the graphic matroid of $G$, so $M$ is the lifted-graphic matroid of $(G, \psi)$.
Therefore $M$ satisfies Theorem 1. These properties give evidence that the constructions of $\mathcal C$ and $M$ are quite natural. As further evidence, it turns out that by setting $\Gamma$ to be one of the three groups of Example 1 we obtain three natural families of matroids:
If $\Gamma = \mathbb F^+ \rtimes \mathbb F^{\times}$ for a field $\mathbb F$, then $M$ has a natural $\mathbb F$-representation. See Figure 4 for an example.
If $\Gamma = SE(2)$ and $\Gamma_1 = T(2)$, then $M$ agrees with a construction of Bernstein [Ber22] that was motivated in part by the study of symmetry-forced rigidity of frameworks.
If $\Gamma = \Gamma_1 \rtimes \{1,-1\}^{\times}$ for an abelian group with no elements of order 2, then $M$ agrees with a construction of Anderson, Su, and Zaslavsky [ASZ24] that was motivated in part by the study of hyperplane arrangements.
Figure 4: A $(\textrm{GF}(5)^+ \rtimes \textrm{GF}(5)^{\times})$-gain graph (writing $(a, b)$ for the permutation $x \mapsto a + bx$) and a $\textrm{GF}(5)$-representation of the associated matroid.
So the matroids of Theorem 1 seem quite natural and have potential for applications, and I hope that the interested reader will explore these matroids for other groups with a Frobenius partition.
5. Why Frobenius partitions?
At this point, the interested reader may be asking the following question: why is a Frobenius partition necessary for Theorem 1? I’ll now address this question and show that for finite groups, the Frobenius partition is in fact necessary under one natural assumption. Suppose we have a finite group $\Gamma$ with a normal subgroup $\Gamma_1$ and we seek a construction that takes in any $\Gamma$-gain graph $(G, \psi)$ and outputs an elementary lift $M$ of the frame matroid $F(G, \psi/\Gamma_1)$, as in Theorem 1. In particular, the construction should apply to the complete n-vertex $\Gamma$-gain graph $(K_n^{\Gamma}, \psi_n^{\Gamma})$ which has all group labels appearing between every pair of vertices. If we make the natural assumption that a cycle of $K_n^{\Gamma}$ is a circuit of $M$ if and only if it is $\psi_n^{\Gamma}$-balanced, it turns out that $\Gamma$ must have a Frobenius partition.
Theorem 4. Let $\Gamma$ be a finite group with a normal subgroup $\Gamma_1$, and let $M$ be an elementary lift of the frame matroid $F(K_n^{\Gamma}, \psi_n^{\Gamma}/\Gamma_1)$ with $n \ge 4$ so that a cycle of $K_n^{\Gamma}$ is a circuit of $M$ if and only if it is $\psi_n^{\Gamma}$-balanced. Then $\Gamma$ has a Frobenius partition $\{\Gamma_1\} \cup \mathcal A$ and $M$ is the matroid of Theorem 1.
Proof. I’ll give a brief proof sketch to show how $\mathcal A$ arises. For all $\alpha \in \Gamma$, let $E_{\alpha}$ be the set of edges of $K_n^{\Gamma}$ labeled by $\alpha$. For $\alpha, \beta \in \Gamma – \Gamma_1$ write $\alpha \sim \beta$ if $E_{\alpha} \cup E_{\beta}$ has the same rank in $F(G, \psi/\Gamma_1)$ and $M$ (this rank is $n$). It turns out that $\sim$ is an equivalence relation, and each equivalence class together with the identity is a malnormal subgroup of $\Gamma$ (see Theorem 6.2 of [Wal26+] for details), giving rise to $\mathcal A$.
So if one wishes to preserve the information given by $\psi$-balanced cycles, then the Frobenius partition is necessary.
6. Future work
Many research directions for frame matroids and lifted-graphic matroids naturally extend to the matroids of Theorem 1. Since this post is already quite long, I’ll list some in bulleted form, writing $\mathcal M(\Gamma, \Gamma_1, \mathcal A)$ for the class of matroids arising from Theorem 1 for the triple $(\Gamma, \Gamma_1, \mathcal A)$:
When $\Gamma$ is finite, the class of $\Gamma$-frame matroids has a sequence of universal models called Dowling geometries [Dow73]. Does $\mathcal M(\Gamma, \Gamma_1, \mathcal A)$ always have a sequence of universal models (likely yes), and what properties do they have?
The class $\mathcal M(\Gamma, \Gamma_1, \mathcal A)$ is minor-closed when $\Gamma/\Gamma_1$ is trivial or isomorphic to a group in $\mathcal A$, which is aways the case when $\Gamma$ is finite and may always be the case when $\Gamma$ is infinite (see Problem 2.13 in [Wal26+]). If $\Gamma$ is infinite (resp., finite), is the set of excluded minors for $\mathcal M(\Gamma, \Gamma_1, \mathcal A)$ infinite (resp., finite)?
Is there a bijection between projective equivalence classes of $\mathbb F$-representations of a matroid $M$ in $\mathcal M(\mathbb F^+ \rtimes \mathbb F^{\times}, \mathbb F^+, \mathcal A)$ and switching-and-scaling classes of $(\mathbb F^+ \rtimes \mathbb F^{\times})$-gain graphs realizing $M$? If so, this would generalize work from [FPS22].
When $\Gamma$ is $SE(2)$ or $\Gamma_1 \rtimes \{1,-1\}^{\times}$, the matroids in $\mathcal M(\Gamma, \Gamma_1, \mathcal A)$ have applications in rigidity theory [Ber22] and hyperplane arrangements [ASZ24], respectively. Are there other choices of $\Gamma$ with applications in these areas?
Theorem 2 was recently generalized in [Wal22]. Can this generalization be combined with Theorem 1 to obtain a more general class of matroids from gain graphs over quotient groups?
I hope that the interested reader will pursue some of these problems.
References
[ASZ24] L. Anderson, T. Su, T. Zaslavsky. Matroids of gain signed graphs. Discrete Comput. Geom., 72(2):503–549, 2024.
[Ber22] D. Bernstein. Generic symmetry-forced infinitesimal rigidity: translations and rotations. SIAM J. Appl. Algebra Geom., 6(2):190–215, 2022.
[BFS20] N. Bowler, D. Funk, D. Slilaty. Describing quasi-graphic matroids. European J. Comb., 85:103062, 26, 2020.
[Bry86] T. H. Brylawski. Constructions. In Theory of matroids (ed. N. White), pp. 127–223. Cambridge University Press, Cambridge, 1986.
[Cra65] H. H. Crapo. Single-element extensions of matroids. J. Res. Nat. Bur. Standards Sect. B, 69B:55–65, 1965.
[Dow73] T. Dowling. A class of geometric lattices based on finite groups. J. Combin. Therory Ser. B, 14:61–86, 1973.
[FPS22] D. Funk, I. Pivotto, D. Slilaty. Matrix representations of frame and lifted-graphic matroids correspond to gain functions. J. Combin. Theory Ser. B, 155:202–255, 2022.
[GGW18] J. Geelen, B. Gerards, G. Whittle. Quasi-graphic matroids. J. Graph Theory, 87(2):253–264, 2018.
[Wal22] Z. Walsh. A new matroid lift construction and an application to group-labeled graphs. Electr. J. Combin., 29, 2022.
[Wal26+] Z. Walsh. Matroids from gain graphs over quotient groups, arXiv:2602.23066, 2026.
[Zas89] T. Zaslavsky. Biased graphs. I. Bias, balance, and gains. J. Combin. Theory Ser. B, 47(1):32–52, 1989.
[Zas91] T. Zaslavsky. Biased graphs. II. The three matroids. J. Combin. Theory Ser. B, 51:46–72, 1991.
[Zas03] T. Zaslavsky. Biased graphs. IV. Geometric realizations. J. Combin. Theory Ser. B, 89(2):231–297, 2003.
Let $E$ be a finite set, let $\mathbb{F}$ be a field and let $\mathbb{F}^E$ denote the vector space with a fixed set of coordinates, indexed by $E$. For each $S \subseteq E$, $\pi_S: \mathbb{F}^E \rightarrow \mathbb{F}^S$ denotes the corresponding coordinate projection.
A variety is a subset of $\mathbb{F}^E$ defined by the vanishing of a system of polynomial functions. A variety is said to be irreducible if it is not the proper union of subvarieties. Each irreducible variety $V \subseteq \mathbb{F}^E$ defines a matroid $\mathcal{M}(V)$ on ground set $E$. In particular, $S \subseteq E$ is independent in $\mathcal{M}(V)$ if $\pi_S(V)$ has dimension $|S|$, and $S \subseteq E$ is spanning in $\mathcal{M}(V)$ if $\pi_S(V)$ has the same dimension as $V$.
Representable matroids can be constructed in this way. In particular, if $A$ is an $\mathbb{F}$-matrix with column set $E$, then its rowspan is a linear subspace $L$ of $\mathbb{F}^E$. Since linear subspaces can be defined by the vanishing of linear polynomials, $L$ is a variety and it is moreover irreducible. The matroid $\mathcal{M}(L)$ is isomorphic to the column matroid of $A$.
An example from rigidity theory
Another example of matroids from irreducible varieties comes from rigidity theory. Fix an integer $n$ and consider the following $(n+1)\times (n+1)$ Cayley-Menger matrix
Every minor of such a matrix is a polynomial in the variables $\{x_{ij} \vert 1 \le i < j \le n\}$, which is in natural bijection with the edge set $E_n$ of the complete graph on vertex set $\{1,\dots,n\}$. The vanishing of the $(d+3)\times (d+3)$ minors of such a matrix define what’s often called the Cayley-Menger variety of $n$ points in $d$-dimensional space, and we denote it by ${\rm CM}_n^d$. It lives in the vector space $\mathbb{C}^{E_n}$ whose coordinates are indexed by $E_n$.
The significance of the variety ${\rm CM}_n^d$ is that if $p_1,\dots,p_n \in \mathbb{R}^d$ and $y_{ij} = \|p_i-p_j\|$, then the point $(y_{ij} | 1 \le i < j \le n)$ lies in ${\rm CM}_n^d$. Its irreducible, so we can talk about the matroid $\mathcal{M}({\rm CM}_n^d)$. A subset $S \subseteq E_n$ is spanning in $\mathcal{M}({\rm CM}_n^d)$ if and only if the graph $([n],S)$ is generically rigid in $d$-dimensional space. Informally speaking, what this means is that if one were to physically construct the graph $([n],S)$ in $d$-dimensional space using rigid bars for edges that are free to move around their incident vertices, then the result would be a rigid structure assuming that the vertices are placed in a sufficiently “generic” way.
Combinatorial shadows of geometric operations
There are many situations in algebraic geometry and its applications where one creates new irreducible varieties from old ones. It can be interesting and useful to study how these operations manifest combinatorially on the varieties’ matroids. For example, let $V \subseteq \mathbb{C}^E$ be an irreducible variety and let $S \subseteq E$. The closure of $\pi_S(V) \subseteq \mathbb{C}^E$ is also an irreducible variety, and its matroid is the restriction of $\mathcal{M}(V)$ to $S$. We will now discuss a more interesting example.
Let $V,W \subseteq \mathbb{C}^E$ be irreducible Varieties. The Hadamard product of $V$ and $W$, denoted ${V \star W}$, is defined to be the closure of the following set
$\left\{(v_e\cdot w_e)_{e \in E} \ | \ v \in V \ {\rm and} \ w \in W \right\}.$
Certain irreducible varieties whose matroids are interesting for rigidity purposes appear as a Hadamard product of two linear spaces, see [1]. The $d= 2$ case ${\rm CM}_{n}^2$ of Cayley-Menger variety is one such example. This raises the question: given two linear spaces, $L_1$ and $L_2$, can the matroid of the Hadamard product $L_1 \star L_2$ be described in terms of the individual matroids $\mathcal{M}(L_1)$ and $\mathcal{M}(L_2)$? And if so, can this be generalized to allow for more than two linear spaces? For varieties other than linear spaces?
For now, all we can say is that an old technique of Edmonds for constructing matroids from submodular functions works for the Hadamard product of two linear spaces. Let $E$ be a finite set, and let $f: 2^E \rightarrow \mathbb{Z}$ be a function satisfying the following properties:
$f(S) \ge 0$ if $S \neq \emptyset$
$f(S) \le f(T)$ if $S \subseteq T$, and
$f$ is submodular.
Then the set of sets $\mathcal{I}$, defined as follows, is the independent sets of a matroid [2], which we denote by $\mathcal{M}(f)$
$\mathcal{I} := \{I \subseteq E: |I’| \le f(I’) \ {\rm for \ all \ } I’ \subseteq I\}$.
If $r_1,r_2: 2^E \rightarrow \mathbb{Z}$ are rank functions of matroids $M_1$ and $M_2$, then $r_1$ and $r_2$ satisfy the necessary properties to apply Edmonds’ construction, and $\mathcal{M}(r_i) = M_i$. The sum $r_1 + r_2$ also satisfies these conditions but is no longer the rank function of a matroid. The matroid $\mathcal{M}(r_1 + r_2)$ should be familiar to readers of this this blog especially – it is the matroid union of $M_1$ and $M_2$. The function $r_1 + r_2 – 1$ also satisfies the conditions required for Edmond’s construction. We can now state how the matroid of a Hadamard product of linear spaces relates to the matroids of the individual linear spaces.
Theorem [1]: Let $L_1,L_2 \subseteq \mathbb{C}^E$ be linear spaces and let $r_i$ denote the rank function of $\mathcal{M}(L_i)$. Then $\mathcal{M}(L_1 \star L_2) = \mathcal{M}(r_1 + r_2 -1)$.
The above theorem fails if one does not require $L_1$ and $L_2$ to be linear spaces. For example, if $L_1 = L_2 = V$ is a toric variety, then $V \star V = V$ and so the formula above cannot work. It also fails if one tries to naively generalize to more than two linear spaces. More specifically, if $L_1,\dots,L_d \subseteq \mathbb{C}^E$ are all linear spaces and $r_i$ denotes the rank function of $\mathcal{M}(L_i)$, then I once conjectured that $\mathcal{M}(L_1 \star \dots \star L_d) = \mathcal{M}(r_1 + \dots + r_d – (d-1))$. This was recently proven false in [3].
References
[1] Bernstein, Daniel Irving. “Generic symmetry-forced infinitesimal rigidity: translations and rotations.” SIAM Journal on Applied Algebra and Geometry 6.2 (2022): 190-215.
[2] Jack Edmonds. Matroids, submodular functions and certain polyhedra. Combinatorial Structures and Their Applications, pages 69–87, 1970.
[3] Antolini, Dario, Sean Dewar, and Shin-ichi Tanigawa. “Dilworth truncations and Hadamard products of linear spaces.” arXiv preprint arXiv:2508.04798 (2025).
