New matroids from gain graphs

Posted on by
Reply

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 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.

Matroids of Hadamard Products

Posted on by
Reply

Matroids from irreducible varieties

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

$\begin{pmatrix} 0 & 1 & 1 & 1 & \cdots & 1 \\ 1 & 0 & x_{12} & x_{13} & \cdots & x_{1n} \\ 1 & x_{12} & 0 & x_{23} & \cdots & x_{2n} \\ 1& x_{13} & x_{23} & 0 & \cdots & x_{3n} \\ \vdots & \vdots &\vdots &\vdots & \ddots & \vdots \\ 1 & x_{1n} & x_{2n} & x_{3n} & \cdots & 0 \end{pmatrix}$

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:

  1. $f(S) \ge 0$ if $S \neq \emptyset$
  2. $f(S) \le f(T)$ if $S \subseteq T$, and
  3. $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).

Presentations of avoiding transversal (q-)matroids

Posted on by
Reply

This post is based on joint work with Gianira N. Alfarano.

Last June, Mark Saaltink wrote on this blog about the q-analogue of transversal matroids. Key to this definition is the rather ingenious idea to not consider transversals, but avoiding transversals. This post explores this idea further. Our goal is to sketch a proof for Saaltink’s conjecture that every (avoiding) transversal q-matroid has a unique minimal presentation. However, we will ignore the q-analogue most of the time, because the setting is also valid for plain old transversal matroids. We describe what appears to be a new algorithm to find maximal / minimal presentations.

Cyclic sets and flats

Before we consider transversals, a quick recap of flats and cyclic sets. Consider a matroid with ground set $E$. The closure operator $\mathop{cl} : 2^E \to 2^E$ is defined by
\[ \mathop{cl}(X) = \{e \in E : r(X \cup e) = r(X)\}, \]
and the cyclic operator $\mathop{cyc} : 2^E \to 2^E$ is defined by
\[ \mathop{cyc}(X) = \{e \in X : r(X \setminus{e}) = r(X)\}.\]
For every $X\in 2^E$, we say that $\mathop{cl}(X)$ is the closure of $X$ and $\mathop{cyc}(X)$ is the cyclic core of $X$. A subset $X \subseteq E$ is a flat if $\mathop{cl}(X) = X$ and a cyclic set if $\mathop{cyc}(X) = X$. Therefore, $X$ is a cyclic flat if for all $y \in E\setminus X$ and $x \in X$,
\[ r(X \cup y) > r(X) \quad \text{and} \quad r(X \setminus {x}) = r(X). \]

Both the closure and the cyclic core are uniquely defined. To find the closure of a set, simply keep adding elements until adding any other element will increase the rank. For the cyclic closure, take away elements such that the rank decreases until there are only elements left that, when deleted, will not change the rank.

It is well known that closure and cyclic core are dual operations: the complement of the closure of a set is the cyclic core of the complement of this set in the dual matroid. We mention also the following.

Lemma. For any set $X\subseteq E$, we have that both $\mathop{cyc}(\mathop{cl}(X))$ and $\mathop{cl}(\mathop{cyc}(X))$ are cyclic flats. In particular, both the cyclic core of a flat and the closure of a cyclic set are cyclic flats.

Avoiding transversals

The definition of an avoiding transversal is due to Saaltink [Saa2025].

Definition. Given an indexed family $\mathcal{X}=(X_1,\ldots,X_k)$ of subsets of some given set $E$, an avoiding transversal of $ \mathcal{X}$ is a set of elements $x_1,x_2,\ldots,x_k$ of $E$, all distinct, with each $x_i\notin X_i$. A partial avoiding transversal of $\mathcal{X}$ is an avoiding transversal of some subfamily of $\mathcal{X}$.

We can make a matroid out of every avoiding transversal.

Theorem. Let $\mathcal{X}$ be an avoiding transversal of a finite set $E$. Then the set of avoiding transversals of $\mathcal{X}$ forms the set of bases of a matroid with ground set $E$.

Let $X_i=E\setminus A_i$. Since every avoiding transversal of $\mathcal{X}=(X_1,\ldots,X_k)$ is a transversal of $\mathcal{A}=(A_1,A_2,\ldots,A_k)$, the class of transversal matroids and the class of avoiding transversal matroids are the same. In the q-analogue, only the class of avoiding transversal q-matroids has a sensible definition. (Saaltink uses the term “transversal q-matroids” for them; we add “avoiding” here to emphasise the link with avoiding transversals and remove confusion.) This is why in the search for more results about q-analogues of transversal matroids, one needs to study avoiding transversals.

Presentations

When the independent sets of a matroid are exactly the partial transversals of $\mathcal{A}=(A_1,A_2,\ldots,A_k)$, we call $\mathcal{A}$ a presentation of $M$. (We will assume that all presentations contain $r(M)=k$ sets.) The representation of a transversal matroid is not necessarily unique, as the next result shows.

Proposition A. Let $\mathcal{A} = (A_1, A_2, \ldots , A_k )$ be a presentation of the transversal matroid $M$ of rank $k$, and let $a\in E\setminus A_1$. Then $\mathcal{A}’ = (A_1\cup \{a\}, A_2, \ldots , A_k )$ is also a presentation of $M$ if and only if $a$ is an isthmus of the restriction $M|(E \setminus A_1)$.

This proposition is due to [BW1971]. If we can add isthmusses to presentations without changing the corresponding matroid, the question arises if a matroid has a maximal presentation, that is, a presentation where adding any element to one of its subsets gives a new matroid. The answer is yes, as was first shown in [Mas1969] and [Bon1972]. Proposition A is a first step in proving this. We will see that the rest of the proof is immediate if we translate Proposition A to avoiding transversals. First, we need a definition.

Definition. Given $A\subseteq E$, we say that a subset $H\subseteq A$ with $|H|=|A|-1$ is a non-spanning $(|A|-1)$-set if it does not contain any basis of $M|A$.

This definition might feel overly complicated and in a sense, it is: a non-spanning $(|E|-1)$-set is the complement of an isthmus. However, with an eye on the q-analogue, we want to avoid isthmusses, because in the q-analogue they do not exist (that is, there can be no 1-dimensional space contained in every basis; see Lemma 5.4 of [JPR2025]). But we can talk about non-spanning $(\dim(E)-1)$-spaces.

We can now translate Proposition A to avoiding transversals.

Proposition B. Let $\mathcal{X} = (X_1, X_2, \ldots , X_k )$ be a presentation of the avoiding transversal matroid $M$ of rank $k$, and let $A\subseteq X_1$ of size $|X_1|-1$. Then $\mathcal{X}’ = (X_1\cap A, X_2, \ldots , X_k )$ is also a presentation of $M$ if and only if $A$ is a non-spanning $(|X_1|-1)$-set of the restriction $M|X_1$.

This point of view now gives us a direct proof of the existence and uniqueness of a minimal presentation of an avoiding transversal matroid: simply take the cyclic core of every set in the presentation! Indeed, intersecting with a non-spanning $(|A|-1)$-set repeatedly produces the cyclic core of a set.

With some extra taking of complements, we can find the maximal representation of a transversal matroid, as we illustrate with an example. It comes from exercise 3 op p.47 of [Oxl2011].

Example. Let $E=\{1,2,3,4,5,6\}$ and $\mathcal{A}=(A_1,A_2,A_3)$ where $A_1=\{1,2,3\}$, $A_2=\{2,3,4\}$ and $A_3=\{4,5,6\}$. The cyclic flats of $M$ are $\emptyset$, $\{5,6\}$, $\{1,2,3\}$ and $E$.

Now $M$ can also be viewed as the avoiding transversal matroid corresponding to $\mathcal{X}=(\{4,5,6\},\{1,5,6\},\{1,2,3\})$. Taking the cyclic core of these subsets gives that $\mathcal{X}’=(\{5,6\},\{5,6\},\{1,2,3\})$ is a minimal presentation of $M$ as an avoiding transversal matroid. Hence, $\mathcal{A}’=(\{1,2,3,4\},\{1,2,3,4\},\{4,5,6\})$ is a maximal presentation of $M$ as a transversal matroid.

This leads us to the question: is this a known procedure to obtain a maximal presentation? Classic texts like [Bru1987] and [BKdM2011] do not mention the cyclic core, but use a much more involved procedure that requires knowing not only the cyclic flats, but also their ranks, and calculating a function that gives the multiplicity of these cyclic flats in the maximal presentation. It feels like the procedure as in the Example is much shorter. Please let us know if we are re-inventing the wheel! We admit to having read only a fraction of the literature on transversal matroids.

Finally, we can now prove Saaltink’s conjecture, because we have exactly the same results for avoiding transversal q-matroids. We can first prove Proposition B by taking a lot of complements in the proof of Proposition A. This is a non-trivial task! But as a result, we get a proof that has a straightforward q-analogue. The conjecture then follows by the same reasoning as above.

Theorem. Let $(X_1,X_2,\ldots,X_k)$ be a presentation of the avoiding transversal q-matroid $M$. Then $(\mathop{cyc}(X_1),\mathop{cyc}(X_2),\ldots,\mathop{cyc}(X_k))$ is the unique minimal presentation of $M$.

References

[BKdM2011] J.E. Bonin, J.P.S. Kung and A. de Mier. Characterizations of Transversal and Fundamental Transversal Matroids. Electronic Journal of Combinatorics, 18(1): P106, 2011.

[Bon1972] J.A. Bondy. Presentations of transversal matroids, Journal of the London Mathematical Society, 5(2): 289-292, 1972.

[Bru1987] R.A. Brualdi. Transversal matroids. In: N. White, editor, Combinatorial geometries, pages 72–97, Cambridge University Press, Cambridge, 1987.

[BW1971] J.A. Bondy and D.J.A. Welsh. Some results on transversal matroids and constructions for identically self-dual matroids, Quarterly Journal of Mathematics, 22(3): 435-451, 1971.

[JPR2025] T. Johnsen, R. Pratihar and T. H. Randrianarisoa. The Euler characteristic, q-matroids, and a Möbius function. Journal of Algebra and Its Applications, 2025.

[Mas1969] J. Mason. Representations of independent spaces. PhD dissertation, University of Wisconsin, Madison WI, 1969.

[Oxl2011] J.G. Oxley. Matroid Theory. Oxford University Press, USA, 2011.

[Saa2025] M. Saaltink. A theory of q-transversals. arXiv:2503.12201, 2025.

Lattice path matroids

Posted on by
Reply

From lattice paths to matroids

Lattice paths and Catalan numbers were some of the favourite topics in my recent combinatorics course. And while we didn’t cover them in class, I was reminded of lattice path matroids.

The systematic study of lattice path matroids was initiated by Joe Bonin, Anna de Mier, and Marc Noy. The results I describe here (as well as their proofs) can all be found in this paper by Bonin and De Mier.

A north-east lattice path (I will call them lattice paths for simplicity) is a sequence $v_0 = (0,0), v_1, \ldots, v_\ell$ of points in the lattice $\mathbb{Z}^2$ such that each step $P_i = v_i – v_{i-1}$ is either in the east direction $E = (1,0)$ or in the north direction $N = (0,1)$. As such lattice paths always start at the origin, they are in one-to-one correspondence with words over the alphabet $\{E,N\}$.

A lattice path
The lattice path of length 8 encoded by the word $NEEENENE$.

There are exactly $\binom{a+b}{b}$ lattice paths to $(a,b)$, as all such paths have $a+b$ steps, and identifying the $b$ north steps among them suffices to describe the path.

Given a lattice path $P$ to $(a,b)$, written as a sequence $P_1P_2\ldots P_{a+b}$ of $a$ east steps and $b$ north steps, we can record the north steps as follows: $$\mathcal{N}(P) = \{i : P_i = N\}.$$

All $b$-element subsets of $[a+b]$ appear as $\mathcal{N}(P)$ for some lattice path $P$ to $(a,b)$; in other words, the set of all $\mathcal{N}(P)$, as $P$ ranges over the lattice paths to $(a,b)$, is the set of bases of the rank-$b$ uniform matroid on $[a+b]$. Lattice path matroids generalise this construction.

Let $P$ and $Q$ be two lattice paths to $(a,b)$. We say that $P \le Q$ if $P$ never goes above $Q$; this defines a partial order on the set of all lattice paths to $(a,b)$. For $P \le Q$, we define the matroid $M[P,Q]$ on $[a,b]$ with set of bases $$\{\mathcal{N}(R) : P \le R \le Q\}.$$

Proposition. $M[P,Q]$ is a matroid.

The matroid $M[P,Q]$ records (the north steps of) all lattice paths between $P$ and $Q$; an arbitrary matroid is called a lattice path matroid if it is isomorphic to $M[P,Q]$ for some $P$ and $Q$. Here are some examples:

  • $M[E^aN^b, N^bE^a]$ is the rank-$b$ uniform matroid on $[a+b]$. Here, the first boundary path is the one formed by $a$ east steps followed by $b$ north steps, and the second boundary path is the one formed by $b$ north steps folled by $a$ east steps.
  • $M[P,P] \cong U_{b,b} \oplus U_{0,a}$ for any lattice path $P$ to $(a,b)$.
  • $M[E^nN^n, (EN)^n]$ is the Catalan matroid with exactly $\frac{1}{n+1}\binom{2n}{n}$ bases.
Pairs of lattice paths encoding the uniform matroid $M[P,Q] \cong U_{3,8}$ (left) and the rank-3 Catalan matroid $M[P,Q] \cong C_3$ (right).

Properties of $M[P,Q]$ can (in principle) be explained in terms of $P$ and $Q$ alone. We will need the following result later.

Proposition. The element $i$ is a coloop of $M[P,Q]$ if and only if $P_{i-1} = Q_{i-1}$ and $P_i – P_{i-1} = Q_i – Q_{i-1} = N$. The element $i$ is a loop of $M[P,Q]$ if and only if $P_{i-1} = Q_{i-1}$ and $P_i – P_{i-1} = Q_i – Q_{i-1} = E$.

Loops and coloops in lattice path matroids
The element 6 is a coloop, and the element 10 is a loop, of $M[P,Q]$.

An attractive property of the class of lattice path matroids is that it is closed under duality and minors. Both of these operations have interpretations in terms of lattice paths.

Duality

Let $\mathcal{N}(R)$ be a basis of $M[P,Q]$. Then the complement of $\mathcal{N}(R)$ in $[a+b]$ is a basis of the dual matroid $M[P,Q]^*$: its elements correspond precisely to the east steps in $R$. This inspires the following definition.

For a lattice path $R$, let $R^*$ be the lattice path obtained from $R$ by flipping the roles of north and east steps. If $R$ is a lattice path to $(a,b)$, then $R^*$ is a lattice path to $(b,a)$. Geometrically, $R^*$ is obtained from $R$ by reflecting it in the line $y=x$. It is clear from the geometric perspective that if $P \le R \le Q$, then $Q^* \le R^* \le P^*$, from which it can be shown that the dual of $M[P,Q]$ is again a lattice path matroid.

Proposition. $M[P,Q]^* = M[Q^*, P^*]$.

The dual of a lattice path matroid is again a lattice path matroid
The dual of the lattice path matroid $M[P,Q]$ is the lattice path matroid $M[Q^*,P^*]$.

Minors

Showing that the class of lattice path matroids is minor-closed requires a bit more work. Fortunately, in view of the previous result, it suffices to show that deleting a single element from $M[P,Q]$ results in a new lattice path matroid.

So let $M = M[P,Q]$ be a lattice path matroid and let $i$ be an element of $M$. If $i$ is a loop or coloop of $M$, then $P$ and $Q$ coincide in the $i$-th step; a lattice path representation can be obtained from $P$ and $Q$ by deleting this step from both paths. (When drawing $P$ and $Q$ in $\mathbb{Z}^2$, the resulting disconnected parts of the lattice paths should be connected up again by “sliding” the north-east component one unit to the south (when $i$ is a coloop) or to the west (when $i$ is a loop).)

When $i$ is neither a loop nor a coloop, the bases of $M\backslash i$ are the bases of $M$ that do not contain $i$. In terms of lattice paths, this means that the lattice paths $R$ corresponding to bases of $M\backslash i$ satisfy $P \le R \le Q$ and $R_i – R_{i-1} = E$: we disallow north steps starting from any point $(u,v)$ such that $u+v=i-1$. We obtain lattice paths $P’$ and $Q’$ representing $M\backslash i$ by “merging” the two squares on either side of such north steps. More precisely, we obtain $P’$ from $P$ by deleting the last east step at or before the $i$-th step, and $Q’$ from $Q$ by removing the first east step at or after the $i$-th step. See the figure for an illustrative example.

Proposition. $M[P,Q]\backslash i \cong M[P’,Q’]$.

Single-element deletions from a lattice path matroid are lattice path matroids.
Deleting the element 6 from $M[P,Q]$ is again a lattice path matroid. Its bases are the bases of $M[P,Q]$ that do not use the red north steps. $M[P,Q]\backslash 6 \cong M[P’,Q’]$.

We conclude that the class of lattice path matroids is closed under taking minors. Joe Bonin identified the excluded minors for the class of lattice path matroids: they comprise the rank-3 wheel and whirl, a rank-3 matroid on seven elements called $R_3$ and its dual, and five infinite families.

The class of lattice paths has many more interesting properties. For example, all of them are transversal matroids and their Tutte polynomials can be computed in polynomial time. I refer to the original papers by Bonin, De Mier, and Noy for this and more.