Question 1.<\/strong> 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?<\/p>\n 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.<\/em><\/p>\n Theorem 1.<\/strong> 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.<\/p>\n 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+].\u00a0<\/p>\n\n\n\n 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:<\/p>\n 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<\/em>), 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.<\/p>\n\n\n\n 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:<\/p>\n 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<\/em> [Zas89] (as explained elsewhere on this blog<\/a>), and both are special cases of quasi-graphic matroids <\/em>[GGW18, BFS20]. <\/p>\n\n\n\n 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. <\/p>\n Theorem 2<\/strong> [Cra65, Bry86]. <\/strong>Let $M$ be a matroid on ground set $E$ and let $\\mathcal C$ be a set of circuits of $M$ so that<\/p>\n 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$.<\/p>\n<\/li>\n<\/ul>\n Then the function $r \\colon 2^E \\to \\mathbb Z$ defined, for all $X \\subseteq E$, by<\/p>\n $$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}$$<\/span><\/p>\n is the rank function of a matroid on $E(M)$. <\/p>\n The set $\\mathcal C$ is a linear class<\/em> of circuits of $M$, and the pair $(C_1, C_2)$ is a modular pair<\/em> of circuits. The matroid $M’$ given by the theorem is an elementary lift<\/em> 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. <\/p>\n\n\n\n In order to define the matroid of Theorem 1, the group $\\Gamma$ must have special structure.<\/p>\n Definition 1. <\/strong>Let $\\Gamma$ be a group. A subgroup $A$ of $\\Gamma$ is malnormal <\/em>if $\\gamma^{-1}A\\gamma$ and $A$ share only the identity for all $\\gamma \\in \\Gamma – A$. A Frobenius partition\u00a0<\/em>of $\\Gamma$ is a collection $\\{\\Gamma_1\\} \\cup \\mathcal A$ of subgroups of $\\Gamma$ so that the following hold:<\/p>\n The Frobenius partition is\u00a0nontrivial\u00a0<\/em>if it contains at least two nontrivial subgroups, and is\u00a0trivial<\/em> 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.<\/p>\n Example 1. <\/strong>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 <\/em>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) <\/em>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:<\/p>\n If $X$ is finite in the previous example, then $\\Gamma$ is known as a Frobenius group<\/em>. 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+].<\/p>\n\n\n\n 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.<\/p>\n Theorem 3. <\/strong>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\u00a0<\/p>\n Then $\\mathcal C$ is a linear class of circuits of $F(G, \\psi\/\\Gamma_1)$.<\/p>\n 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:<\/p>\n 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:<\/p>\n 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.<\/p>\n\n\n\n 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<\/em> $(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.<\/p>\n Theorem 4.\u00a0<\/strong>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.<\/p>\n Proof.\u00a0<\/strong>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$.<\/p>\n So if one wishes to preserve the information given by $\\psi$-balanced cycles, then the Frobenius partition is necessary.<\/p>\n\n\n\n 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)$:<\/p>\n I hope that the interested reader will pursue some of these problems.<\/p>\n\n\n\n [ASZ24] L. Anderson, T. Su, T. Zaslavsky. Matroids of gain signed graphs. Discrete Comput. Geom.<\/em>, 72(2):503–549, 2024.<\/p>\n [Ber22] D. Bernstein. Generic symmetry-forced infinitesimal rigidity: translations and rotations. SIAM J. Appl. Algebra Geom.<\/em>, 6(2):190–215, 2022.<\/p>\n [BFS20] N. Bowler, D. Funk, D. Slilaty. Describing quasi-graphic matroids. European J. Comb.<\/em>, 85:103062, 26, 2020.<\/p>\n [Bry86] T. H. Brylawski. Constructions. In Theory of matroids<\/em> (ed. N. White), pp. 127–223. Cambridge University Press, Cambridge, 1986.<\/p>\n [Cra65] H. H. Crapo. Single-element extensions of matroids. J. Res. Nat. Bur. Standards Sect. B<\/em>, 69B:55–65, 1965.<\/p>\n [Dow73] T. Dowling. A class of geometric lattices based on finite groups. J. Combin. Therory Ser. B<\/em>, 14:61–86, 1973.<\/p>\n [FPS22] D. Funk, I. Pivotto, D. Slilaty. Matrix representations of frame and lifted-graphic matroids correspond to gain functions. J. Combin. Theory Ser. B<\/em>, 155:202–255, 2022.<\/p>\n [GGW18] J. Geelen, B. Gerards, G. Whittle. Quasi-graphic matroids. J. Graph Theory<\/em>, 87(2):253–264, 2018.<\/p>\n [Wal22] Z. Walsh. A new matroid lift construction and an application to group-labeled graphs. Electr. J. Combin.<\/em>, 29, 2022.<\/p>\n [Wal26+] Z. Walsh. Matroids from gain graphs over quotient groups, arXiv:2602.23066, 2026.<\/p>\n [Zas89] T. Zaslavsky. Biased graphs. I. Bias, balance, and gains. J. Combin. Theory Ser. B<\/em>, 47(1):32–52, 1989.<\/p>\n [Zas91] T. Zaslavsky. Biased graphs. II. The three matroids. J. Combin. Theory Ser. B<\/em>, 51:46–72, 1991.<\/p>\n [Zas03] T. Zaslavsky. Biased graphs. IV. Geometric realizations. J. Combin. Theory Ser. B<\/em>, 89(2):231–297, 2003.<\/p>\n","protected":false},"excerpt":{"rendered":" 1. Introduction 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 … Continue reading 2. Gain graphs and their matroids<\/h2>\n\n\n\n
\n
![\"\"](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2026\/02\/Gain_graphs.png\")
<\/a>\n
<\/a><\/a>\n
3. Frobenius partitions of groups<\/h2>\n\n\n\n
\n
\n
4. The construction<\/h2>\n\n\n\n
\n
\n
\n
<\/a>5. Why Frobenius partitions?<\/h2>\n\n\n\n
6. Future work<\/h2>\n\n\n\n
\n
References<\/h2>\n\n\n\n