Author Archives: Zach Walsh

The foundation of a segment-cosegment exchange

Posted on by
Reply

1. Introduction

In this post I’ll present the following result from a recent paper of Matt Baker, Oliver Lorscheid, myself, and Tianyi Zhang.

Theorem 1. [BLWZ25] The foundation of a matroid is invariant under the operation of segment-cosegment exchange.

This will allow me to discuss three important topics that have not received much attention on this blog:

  • Pastures, which are algebraic objects that generalize fields, partial fields, and hyperfields. They were introduced by Baker and Lorscheid [BL21] and are special types of both tracts and ordered blue fields; see [BL21] for details.
  • The foundation of a matroid, which is a pasture canonically associated to the matroid that determines its rescaling classes of representations over any pasture. Foundations were introduced by Baker and Lorscheid in [BL21].
  • Segment-cosegment exchange, which is an operation that replaces a coindependent $U_{2,n}$-restriction (a segment) with a $U_{2,n}$-restriction of the dual (a cosegment). It was defined by Oxley, Semple, and Vertigan in [OSV00] and has $\Delta$-$Y$ exchange as a special case.

I’ll give some background on these three topics, and then discuss some consequences of Theorem 1. The interested reader can find more details about pastures and foundations in [BL25] and [BLZ25] or from recorded talks by Matt Baker and Oliver Lorscheid, more details about segment-cosegment exchange in Section 11.5 of [Oxl11], and more details about Theorem 1 in [BLWZ25].

2. Pastures

In matroid theory, we typically think of a representation of a matroid $M$ over a field $\mathbb F$ as a matrix over $\mathbb F$ whose column set is $E(M)$ and whose independent sets of columns are the independent sets of $M$. The following observation gives a slightly different perspective: we can represent $M$ with a function from $r$-tuples of $E(M)$ to $\mathbb F$ that satisfies three properties.

Observation 1. A rank-$r$ matroid $M$ on ground set $E$ is representable over a field $\mathbb F$ if and only if there is a function $\Delta \colon E^r \to \mathbb F$ so that:

  1. $\Delta(e_1, e_2, \dots, e_r) \ne 0$ if and only if $\{e_1, e_2, \dots, e_r\}$ is a basis of $M$.
  2. $\Delta(e_{\sigma(1)}, \dots, e_{\sigma(r)}) = \textrm{sign}(\sigma) \cdot \Delta(e_1, \dots, e_r)$ for every permutation $\sigma$ of $[r]$.
  3. $\Delta$ satisfies the 3-term Plücker relations: for all $J \in E^{r-2}$ and $(e_1, e_2, e_3, e_4) \in E^4$,
    $\Delta(Je_1e_2)\Delta(Je_3e_4) – \Delta(Je_1e_3)\Delta(Je_2e_4) + \Delta(Je_1e_4)\Delta(Je_2e_3) = 0$.

One direction is immediate: if a matrix $A$ with $r$ rows represents $M$ over $\mathbb F$, then we can choose $\Delta$ to be the function that maps $(e_1, \dots, e_r)$ to the determinant of the corresponding $r$-tuple of columns of $A$, and $\Delta$ will satisfy the three properties. The converse follows from facts about the Plücker embedding of the Grassmannian $\textrm{Gr}(r, \mathbb F^E)$, or it can be proved directly without much difficulty.

From Observation 1 we can note the following: to represent $M$ over $\mathbb F$, we only need to know the multiplicative structure of $\mathbb F$ and the triples from $\mathbb F$ that sum to zero. This means that if we replace addition with suitable axioms for the set of triples that “sum” to zero, we can obtain an abstraction of fields over which we can still represent matroids; this is one way to motivate the definition of a pasture. The underlying multiplicative object will be a monoid with zero, which is a multiplicatively written commutative monoid $P$ with an element $0$ that satisfies $0 \cdot a = 0$ for all $a \in P$; we write $1$ for the unit of $P$ and $P^{\times}$ for the group of invertible elements of $P$.

Definition 1. [BL21] A pasture is a monoid with zero $P$ so that $P^{\times} = P – \{0\}$, together with a set $N_P$ (the null set) of triples from $P$ so that:

  • (P1) If $(a,b,c) \in N_P$, then every permutation of $(a,b,c)$ is in $N_P$.
  • (P2) If $(a,b,c) \in N_P$ and $d \in P$, then $(ad, bd, cd) \in N_P$.
  • (P3) $(a, 0, 0) \in N_P$ if and only if $a = 0$.
  • (P4) There is a unique $\epsilon \in P – \{0\}$ so that $(1, \epsilon, 0) \in N_P$.

Pastures generalize fields, partial fields (see Stefan van Zwam’s blog post for a definition), and hyperfields (see Matt Baker’s blog post for a definition). I’ll next list some important examples of pastures.

  • If $\mathbb F$ is a field, then $\mathbb F$ is a pasture with $(x, y, z) \in N_{\mathbb F}$ if and only if $x + y + z = 0$. Here $\epsilon = -1$.
  • Let $\mathbb F_1^{\pm} = \{0, 1, -1\}$ with the expected multiplication and let $N_{\mathbb F_1^{\pm}}$ consist of all permutations of $(0,0,0)$ and $(1,-1,0)$. Then $\mathbb F_1^{\pm}$ with null set $N_{\mathbb F_1^{\pm}}$ is a pasture called the regular partial field. Here $\epsilon = -1$. 
  • Let $\mathbb S = \{0, 1, -1\}$ with the expected multiplication and let $N_{\mathbb S}$ consist of all permutations of $(0,0,0)$, $(1,-1,0)$, $(1,1,-1)$, and $(1,-1,-1)$ (this is $(0,0,0)$ and all triples containing a $1$ and a $-1$). Then $\mathbb S$ with null set $N_{\mathbb S}$ is a pasture called the sign hyperfield. Here $\epsilon = -1$.
  • Let $\mathbb T = \mathbb R _{\ge 0}$ with the expected multiplication, and $(a,b,c) \in N_{\mathbb T}$ if $\max\{a,b,c\}$ is attained at least twice. Then $\mathbb T$ with null set $N_{\mathbb T}$ is a pasture called the tropical hyperfield. Here $\epsilon = 1$ because $(1,1,0)$ is in the null set. 
  • Let $\mathbb K = \{0, 1\}$ with the expected multiplication and let $N_{\mathbb K}$ consist of all permutations of $(0,0,0)$, $(1,1,0)$, and $(1,1,1)$. Then $\mathbb K$ with null set $N_{\mathbb K}$ is a pasture called the Krasner hyperfield. Here $\epsilon = 1$.

Many other interesting examples of pastures can be found in the appendix of [BLZ25].

3. Matroids over pastures

By taking Observation 1 and encoding the 3-term Plücker relations with null triples, one can represent matroids over pastures. 

Definition 2. [BB19] Given a pasture $P$ and a rank-$r$ matroid $M$ on ground set $E$, a $P$-representation of $M$ is a function $\Delta \colon E^r \to P$ so that:

  1. $\Delta(e_1, e_2, \dots, e_r) \ne 0$ if and only if $\{e_1, e_2, \dots, e_r\}$ is a basis of $M$.
  2. $\Delta(e_{\sigma(1)}, \dots, e_{\sigma(r)}) = \textrm{sign}(\sigma) \cdot \Delta(e_1, \dots, e_r)$ for every permutation $\sigma$ of $[r]$.
  3. For all $J \in E^{r-2}$ and all $(e_1, e_2, e_3, e_4) \in E^4$,
    $\Big(\Delta(Je_1e_2)\Delta(Je_3e_4), \epsilon\Delta(Je_1e_3)\Delta(Je_2e_4), \Delta(Je_1e_4)\Delta(Je_2e_3)\Big) \in N_P$.

(Note that $\textrm{sign}(\sigma) \in \{1,\epsilon\}$.) The function $\Delta$ is a Grassmann-Plücker function for $M$.

Matroid representations over pastures have the following attractive properties:

  • A matroid is $\mathbb F_1^{\pm}$-representable if and only if it is regular.
  • $\mathbb S$-representations of $M$ are orientations of $M$. In this case the Grassmann-Plücker function is called a chirotope.
  • $\mathbb T$-representations of $M$ are valuations of $M$.
  • Every matroid is representable over $\mathbb K$, via the Grassmann-Plücker function that maps each independent $r$-tuple to $1$ and each dependent $r$-tuple to $0$. Clearly the first two properties hold, and the third follows from basis exchange properties. 

There is a natural notion of equivalence for Grassmann-Plücker functions. Let $\Delta_1$ and $\Delta_2$ be Grassmann-Plücker functions for a matroid $M$ on ground set $E$ to a pasture $P$. We say that $\Delta_1$ and $\Delta_2$ are rescaling equivalent if there is a function $c \colon E \to P – \{0\}$ and a constant $d \in P – \{0\}$ so that $\Delta_2(e_1, \dots, e_r) = d \cdot c(e_1) \cdots c(e_r) \Delta_1(e_1, \dots, e_r)$ for all $(e_1, \dots, e_r) \in E^r$. When $P$ is a field, rescaling equivalence classes are projective equivalence classes of matrix representations, and when $P = \mathbb S$, rescaling equivalence classes are reorientation classes of chirotopes.

4. The foundation of a matroid

The foundation of a matroid $M$ is a pasture canonically associated with $M$. The definition relies on the notion of a morphism between pastures $P_1$ and $P_2$, which is a function $f \colon P_1 \to P_2$ that is a homomorphism of the underlying monoids with zero (so $f(0) = 0$, $f(1) = 1$, and $f$ respects multiplication) so that $(f(a), f(b), f(c)) \in N_{P_2}$ whenever $(a, b, c) \in N_{P_1}$. For example, $\mathbb F_1^{\pm}$ has a morphism to every pasture (map $0$ to $0$, $1$ to $1$, and $-1$ to $\epsilon$), and every pasture has a morphism to $\mathbb K$ (map $0$ to $0$ and everything else to $1$).

Pastures and the morphisms between them form a category, and much of the theory of matroids over pastures relies on using tools from category theory to study the category of pastures; this is the perspective that leads to the notion of the foundation of a matroid.

Theorem 2. [BL25] For every matroid $M$ there is a pasture $F(M)$ so that for every pasture $P$, morphisms from $F(M)$ to $P$ are in one-to-one correspondence with rescaling classes of $P$-representations of $M$, functorially in $P$.

The pasture $F(M)$ is the foundation of $M$. Here “functorially in $P$” means that for every morphism of pastures $P_1 \to P_2$ there is a commutative diagram, shown in Figure 1. (For those well-versed in category theory, $F(M)$ represents the functor taking a pasture $P$ to the set of rescaling classes of $P$-representations of $M$.) 

Figure 1: For every morphism of pastures $P_1 \to P_2$, the diagram commutes. Here $\textrm{Hom}(F(M), P_i)$ is the set of morphisms from $F(M)$ to $P_i$, and $\mathcal X_M^R(P_i)$ is the set of rescaling classes of $P_i$-representations of $M$.

There is overwhelming evidence that foundations are natural:

  • Every regular matroid has foundation $\mathbb F_1^{\pm}$.
  • Every projective geometry with rank at least $3$ over a finite field $\mathbb F_q$ has foundation $\mathbb F_q$.
  • $M$ and $M^*$ have isomorphic foundations.
  • If $N = M/X\backslash Y$, then there is a morphism from $F(N)$ to $F(M)$.
  • The multiplicative group of $F(M)$ is the inner Tutte group of $M$ as defined by Dress and Wenzel [DW89].
  • If $F(M)$ is a partial field, it is isomorphic to the universal partial field of $M$ as defined by Pendavingh and van Zwam [PvZ10].

Also, foundations of small matroids can be computed in Macaulay2, so foundations are practically useful in matroid research as well as interesting.

5. Segment-cosegment exchange

In [BLWZ25], we study how matroid foundations behave with respect to several fundamental matroid operations  including 2-sum, parallel connection, and generalized parallel connection, but in this post I will just focus on one: segment-cosegment exchange. I’ll motivate this operation via graph theory. If a graph $G$ has a triangle $T$, the graph obtained from $G$ by adding a vertex $v$ adjacent to each vertex of $T$ and then deleting the edges of $T$ is called the $\Delta$-$Y$ exchange of $G$ along $T$; see Figure 2 for an example. This operation was originally motivated by the study of electrical networks, but also preserves many natural topological properties of graphs, such as linkless embeddability.

Figure 2: (a) shows a graph $G$ with a triangle $T = \{x_1, x_2, x_3\}$, and (b) shows the $\Delta$-$Y$ exchange of $G$ along $T$.

In [AO91], Akkari and Oxley generalized $\Delta$-$Y$ exchange to matroids using a gluing operation called generalized parallel connection.

Definition 3. [Bry75] Let $M_1$ and $M_2$ be matroids with ground sets $E_1$ and $E_2$ respectively. If $E_1 \cap E_2 = T$ with $M_1|T = M_2|T$ and $T$ is a modular flat in $M_1$, then the generalized parallel connection $P_T(M_1, M_2)$ is the matroid on $E_1 \cup E_2$ such that $F$ is a flat of $P_T(M_1, M_2)$ if and only if $F \cap E_i$ is a flat of $M_i$ for $i = 1,2$. (A flat $T$ is modular if $(T, F’)$ satisfies the submodular rank inequality with equality for every flat $F’$.)

For example, if $T = \varnothing$, then $P_T(M_1, M_2) = M_1 \oplus M_2$, and if $T$ is a point $e$, then $P_T(M_1, M_2)$ is the parallel connection of $M_1$ and $M_2$ with respect to $e$. See Figure 3 for an example of a generalized parallel connection of $F_7^-$ with $M(K_4)$ across a triangle.

Given a matroid $M$ with a triangle $T$, Akkari and Oxley [AO91] defined the $\Delta$-$Y$ exchange of $M$ along $T$ as $P_T(M(K_4), M) \backslash T$. This is well-defined because $T$ is a modular flat of $M(K_4)$, and it directly generalizes $\Delta$-$Y$ exchange for graphs because adding a vertex adjacent to each vertex of $T$ forms $K_4$.

Figure 3: A geometric representation and an $\mathbb R$-representation of the generalized parallel connection of the non-Fano plane and $M(K_4)$ along the common restriction $\{x_1, x_2, x_3\}$, which is a modular flat of $M(K_4)$.

If $T$ is a coindependent triangle of $M$, the $\Delta$-$Y$ exchange of $M$ along $T$ replaces $T$ with a triangle in the dual (a triad). Oxley, Semple, and Vertigan showed in [OSV00] that with a suitable generalization of $M(K_4)$, one can replace a coindependent $U_{2,n}$-restriction with a $U_{2,n}$-restriction in the dual. For $n \ge 3$, let $Y = \{y_1, y_2, \dots, y_n\}$ be a basis of $PG(n – 1, \mathbb R)$ ($n$-dimensional projective space over $\mathbb R$), and let $L$ be a line freely placed relative to $Y$ (so $L$ is disjoint from the span of any $n – 2$ elements of $Y$). By modularity of subspaces of a vector space, for all $i \in [n]$ the hyperplane spanned by $Y – \{y_i\}$ intersects $L$ in a unique element $x_i$. Let $X = \{x_1, x_2, \dots, x_n\}$, and let $\Theta_n$ be the matroid on $X \cup Y$; see Figure 4 for examples. The matroid $\Theta_n$ has the following nice properties:

  • $\Theta_3 \cong M(K_4)$.
  • $X$ is a modular flat of $\Theta_n$.
  • $\Theta_n^*|Y \cong U_{2,n}$.
  • $\Theta_n$ is representable over every field $\mathbb F$ with order at least $n$. If $t_1,t_2,\dots, t_n$ are distinct elements in $\mathbb F$, then the matrix $[D | I_n]$ with entry $D_{ij} = t_i – t_j$ represents $\Theta_n$, with $X$ spanned by $\{[1,1,\dots, 1]^T, [t_1, t_2, \dots, t_n]^T\}$. Figure 4 shows a representation of $\Theta_4$ over $\mathbb R$ with $t_i = i$ for all $i \in [4]$.
Figure 4: (a) shows a geometric representation of $\Theta_3$ (which is isomorphic to $M(K_4)$), and (b) shows an $\mathbb R$-representation of $\Theta_4$.

Since $X$ is a modular flat of $\Theta_n$, one can form the generalized parallel connection along $X$ with any matroid that has a $U_{2,n}$-restriction.

Definition 4. [OSV00] Let $M$ be a matroid with a coindependent set $X$ so that $M|X \cong U_{2,n}$ with $n \ge 3$. The segment-cosegment exchange of $M$ along $X$ is the matroid $P_X(\Theta_n, M) \backslash X$.

Since $X$ is coindependent, one can show that $Y$ is a $U_{2,n}$-restriction of $(P_X(\Theta_n, M) \backslash X)^*$. There is also a dual operation: if $M^*|X \cong U_{2,n}$ and $X$ is independent in $M$, we can take the segment-cosegment exchange of $M^*$ along $X$, and then take the dual; this is called the cosegment-segment exchange of $M$ along $X$. This operation is in fact inverse to segment-cosegment exchange; see [Proposition 11.5.11, Oxl11] for details. 

The operation of segment-cosegment exchange behaves well with respect to representability properties and excluded minors. For example, in their paper introducing the operation, Oxley, Semple, and Vertigan use it to show that for every prime power $q$, the class of matroids representable over the finite field of order $q$ has at least $2^{q – 4}$ excluded minors. For more examples, keep reading!

6. The foundation of a segment-cosegment exchange

We have finally arrived at Theorem 1, which I’ll restate below.

Theorem 3. [BLWZ25] Let $M$ be a matroid and let $X \subseteq E(M)$ be a coindependent set such that $M|X \cong U_{2,n}$ for some $n \ge 3$. Then the foundation of the segment-cosegment exchange of $M$ along $X$ is isomorphic to $F(M)$.

By duality, cosegment-segment exchange also preserves foundations. Since the foundation of a matroid determines its rescaling classes of representations over any pasture, Theorem 3 essentially says that segment-cosegment exchange preserves all representability properties for matroids over pastures. This has a number of interesting consequences:

  • When $M$ is representable over a partial field $P$, Theorem 3 shows that there is a bijection between rescaling equivalence classes of $P$-representations of $M$ and rescaling classes of $P$-representations of the segment-cosegment exchange of $M$ along $X$; this was proved by Oxley, Semple, and Vertigan [OSV00].
  • When $M$ is representable over a partial field, Theorem 3 implies that $M$ and the segment-cosegment exchange of $M$ along $X$ have the same universal partial field; this resolves a conjecture of van Zwam [vZ09].
  • Theorem 3 implies that $M$ is orientable if and only if the segment-cosegment exchange of $M$ along $X$ is orientable, which was seemingly not previously known in either direction.
  • A matroid is rigid if it has only one valuation, up to rescaling. Theorem 3 implies that $M$ is rigid if and only if the segment-cosegment exchange along $X$ is rigid.

For every pasture $P$, the class of matroids representable over $P$ is minor-closed, and with a bit more work, Theorem 3 also has the following consequence for the excluded minors for $P$-representable matroids, which was proved in the special case that $P$ is a partial field by Oxley, Semple, and Vertigan [OSV00].

Theorem 4. [BLWZ25] Let $P$ be a pasture, and let $M$ be an excluded minor for representability over $P$. Then every segment-cosegment exchange of $M$ is also an excluded minor for representability over $P$.

So, Theorem 3 adds to the overwhelming evidence that the foundation of a matroid is a natural and useful invariant, and I hope this will be enough for the interested reader to start working with foundations!

Statement on AI Usage

Chat GPT-6.1 Sol produced the figures and helped with proofreading. The author takes full responsibility for the content.

References

[AO91] S. Akkari, J. Oxley. Some extremal connectivity results for matroids. J. Combin. Theory Ser. B, 52(2):301-320, 1991.

[BB19] M. Baker, N. Bowler. Matroids over partial hyperstructures. Adv. Math., 343:821-863, 2019.

[BL21] M. Baker, O. Lorscheid. The moduli space of matroids. Adv. Math., 390:Paper No. 107883, 118, 2021.

[BL25] M. Baker, O. Lorscheid. Foundations of matroids, Part 1: Matroids without large uniform minors. Mem. Amer. Math. Soc., 305(1536):v+84, 2025.

[BLZ25] M. Baker, O. Lorscheid, T. Zhang. Foundations of matroids, Part 2: Further theory, examples, and computational methods. Comb. Theory, 5(1):Paper No. 1, 77, 2025.

[BLWZ25] M. Baker, O. Lorscheid, Z. Walsh, T. Zhang. The foundation of generalized parallel connections, 2-sums, and segment-cosegment exchanges of matroids. Comb. Theory, 5(4):Paper No. 12, 38, 2025.

[Bry75] T. Brylawski. Modular constructions for combinatorial geometries. Trans. Amer. Math. Soc., 203:1-44, 1975.

[DW89] A. W. M. Dress, W. Wenzel. Geometric algebra for combinatorial geometries. Adv. Math., 77(1):1-36, 1989.

[Oxl11] J. Oxley. Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011.

[OSV00] J. Oxley, C. Semple, D. Vertigan. Generalized $\Delta-Y$ exchange and $k$-regular matroids. J. Combin. Theory Ser. B, 79(1):1-65, 2000.

[PvZ10] R. Pendavingh, S. van Zwam. Confinement of matroid representations to subsets of partial fields. J. Combin. Theory Ser. B, 100(6):510-545, 2010.

[vZ09] S. van Zwam. Partial fields in matroid theory. PhD thesis, Eindhoven, 2009.

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.

Matroid Basis Density

Posted on by
Reply

What is the maximum number of bases of an n-element, rank-r matroid? This question is not interesting: the answer the answer is $\binom{n}{r}$, and equality holds only for the uniform matroid $U_{r,n}.$ However, if we exclude a fixed uniform matroid as a minor, this problem becomes much more interesting.

Problem 1: What is the maximum number of bases of an n-element, rank-r matroid with no $U_{s,t}$-minor? Call this number $\text{ex}_{\mathsf M}(n, r, U_{s,t})$.

To avoid issues with the parity of n and small sporadic examples, I will focus on the following relaxation of Problem 1, which asks for the asymptotically maximum basis density for rank-r matroids with no $U_{s,t}$-minor.

Problem 2: What is $\lim_{n \to\infty}\frac{\text{ex}_{\mathsf M}(n, r, U_{s,t})}{\binom{n}{r}}$? Call this number $\pi_{\mathsf M}(r, U_{s,t})$.

In this post I will discuss recent joint work with Jorn van der Pol and Michael Wigal [vdPWW25+] on these problems, with an emphasis on the following two points. First, Problems 1 and 2 are the specializations of the Turán number and Turán density of the daisy hypergraph $\mathcal D_r(s, t)$ to the class of matroid basis hypergraphs. Second, Problems 1 and 2 lead to many interesting related open problems of varying levels of difficulty. I hope that the interested reader will solve some of these open problems!

The Turán Density of a Daisy

I’ll begin with the original motivation for Problem 1: it is the Turán number of the daisy hypergraph $\mathcal D_r(s,t)$ within the class of matroid basis hypergraphs. I will briefly explain what this means, and why it is interesting. For all integers r,s,t with $r,t \ge s \ge 1$, an (r, s, t)-daisy, denoted $\mathcal D_r(s,t)$, is an r-uniform hypergraph with vertex set $S \cup T$ and edge set $\{S \cup X \mid X \in T^{(s)}\}$, where S is an (r – s)-element set, T is a t-element set disjoint from S, and $T^{(s)}$ is the set of all s-element subsets of T. The set S is the stem and the sets in $T^{(s)}$ are the petals. Note that $\mathcal D_r(s,t)$ has $\binom{t}{s}$ edges, that $\mathcal D_s(s, t)$ is simply the t-vertex, s-uniform hypergraph $K^{(s)}_t$, and that $\mathcal D_r(s,t)$ is a subgraph of both $\mathcal D_r(s , t+1)$ and $\mathcal D_r(s+1, t+1)$. See Figure 1 for some examples of daisies.

Figure 1: Examples of daisies.

Daisies were first defined explicitly by Bollabás, Leader, and Malvenuto, who showed that a well-known problem about the hypercube graph [Conjecture 8, BLM11] is equivalent to a natural conjecture about the Turán densities of daisies. The Turán number of an r-uniform hypergraph H, denoted $\text{ex}(n, r, H)$, is the maximum number of edges of an n-vertex, r-uniform hypergraph without H as a subgraph, and the Turán density of H is $\pi(r, H) = \lim_{n \to\infty}\frac{\textrm{ex}(n, r, H)}{\binom{n}{r}}$. These parameters are very well-studied; see Keevash’s survey [K11]. Bollobás, Leader, and Malvenuto conjectured that $\lim_{r \to \infty} \pi(\mathcal D_r(s,t)) = 0$ for all integers s and t with $t \ge s \ge 1$ [Conjecture 4, BLM11], which is a natural conjecture because as r grows, the daisy $\mathcal D_r(s,t)$ becomes sparser and sparser and therefore should be harder to avoid as a subgraph. However, this conjecture was recently disproved by Ellis, Ivan, and Leader for all $t \ge s \ge 2$ [Theorem 5, EIL24].

Theorem 1 [EIL24]: If q is a prime power, then $$\lim_{r \to \infty} \pi(\mathcal D_r(2, q + 2)) \ge \prod_{i=1}^{\infty} (1 – q^{-i}).$$

This is where matroids come into play: the hypergraphs used to find this lower bound are basis hypergraphs of $\mathbb F_q$-representable matroids, meaning that the vertex set is the ground set of the matroid and the edge set is the basis set of the matroid. In [vdPWW25+] we explored the construction used to prove Theorem 1 and found a connection between daisies and matroids: the basis hypergraph of a rank-r matroid M has a $\mathcal D_r(s,t)$-subgraph if and only if M has a $U_{s,t}$-minor [Corollary 2.3, vdPWW25+]. So $\textrm{ex}_{\mathsf M}(n, r, U_{s,t})$ is the maximum number of edges of an n-element, rank-r matroid basis hypergraph without $\mathcal D_r(s,t)$ as a subgraph. Therefore, $\textrm{ex}_{\mathsf M}(n, r, U_{s,t}) \le \textrm{ex}(n, r, \mathcal D_r(s,t))$ and $\pi_{\mathsf M}(r, U_{s,t}) \le \pi(r, \mathcal D_r(s,t))$, so Problems 1 and 2 give an approach for finding new lower bounds for $\lim_{r \to \infty} \pi(\mathcal D_r(s,t))$, which in turn would likely lead to new insights into the hypercube graph.

Results

The basis density parameter $\pi_{\mathsf M}(r, U_{s,t})$ is known in only a few nontrivial cases. In light of Theorem 1, the case $(s, t) = (2, q + 2)$ for a prime power q is particularly interesting.

Theorem 2 [vdPWW25+]: If $r \ge 2$ and $q$ is a prime power, then $$\pi_{\mathsf M}(r, U_{2,q + 2}) = r! \cdot \left(\frac{q – 1}{q^r – 1}\right)^r \cdot b(r,q),$$ where $b(r,q)$ is the number of bases of the rank-r projective geometry over the finite field of order q. In particular, $\lim_{r \to \infty} \pi_{\mathsf M}(r, U_{2,q+2}) = \prod_{i=1}^{\infty} (1 – q^{-i})$.

This was proved for q = 2 by Alon [A24] but was unknown in all other cases. Interestingly, Theorem 2 shows that one cannot use matroid basis hypergraphs to improve the lower bound of Theorem 1. The key to the proof is a theorem of Kung [K93] that upper bounds the number of points of a rank-r matroid with no $U_{2,q + 2}$-minor.

The only other known instances of Problem 2 are for the smallest nontrivial values of s and t.

Theorem 3 [vdPWW25+]: If $r \ge 3$, then $\pi_{\mathsf M}(r, U_{3,4}) = \frac{r! \cdot 2^{\lfloor r/2 \rfloor}}{r^r}$.

The proof is straightforward and relies on the fact that every matroid with no $U_{3,4}$-minor is a direct sum of matroids with rank at most two. The instance $(s,t) = (3,5)$ is more difficult, and we were only able to solve the case $r = 3$.

Theorem 4 [vdPWW25+]: $\pi_{\mathsf M}(3, U_{3,5}) = 3/4$.

However, this is notable because Turán [T41] conjectured that $\pi(3, K_5^{(3)}) = 3/4$, so Theorem 3 shows that this conjecture holds within the class of matroid basis hypergraphs, via the connection described in the previous section. The proof of Theorem 4 is structural, and relies on the fact that every rank-3 matroid with no $U_{3,5}$-restriction either has no $U_{2,5}$-minor or can be covered by two lines [Lemma 6.4, vdPWW25+].

Open Problems

In light of Theorems 2, 3, and 4, there are several instances of Problem 2 that may not be difficult to solve.

  1. Find $\pi_{\mathsf M}(r, U_{2,t+2})$ when t is not a prime power.
  2. Find $\pi_{\mathsf M}(r, U_{q,q+2})$ when q is a prime power.
  3. Find $\pi_{\mathsf M}(r, U_{s,s+1})$ for $s \ge 4$.
  4. Find $\pi_{\mathsf M}(3, U_{3,t})$ for $t \ge 6$.

A solution to (1) would surely use a theorem of Geelen and Nelson about the number of points of a rank-r matroid with no $U_{2,t+2}$-minor [GN15], so when r is sufficiently large I expect that $\pi_{\mathsf M}(r, U_{2,t+2}) = \pi_{\mathsf M}(r, U_{2,q+2})$ where q is the largest prime power at most t. For (2), I expect that $\pi_{\mathsf M}(r, U_{q,q+2}) = \pi_{\mathsf M}(r, U_{2,q+2})$. Problem (3) is interesting because $\pi_{\mathsf M}(r, U_{s,s+1})$ is the asymptotic maximum basis density for rank-r matroids with circumference at most s. It seems likely that the densest such matroids are direct sums of uniform matroids with rank at most s – 1. Finally, for (4) it seems like the answer should be given by the freest rank-3 matroids that can be covered by $(t-1)/2$ lines when t is odd, or by $(t – 2)/2$ lines and one point when t is even.

I’ll close by discussing some interesting problems related to Problems 1 and 2, beginning with the following generalization of Problem 1.

Problem 3: Let $\mathcal M$ and $\mathcal F$ be sets of matroids. What is the maximum number of bases of an n-element, rank-r matroid in $\mathcal M$ with no minor in $\mathcal F$? 

This problem has many interesting special cases. For example, when $\mathcal M$ is the class of graphic matroids and $\mathcal F$ is empty, Problem 3 is asking for the maximum number of spanning trees among all n-edge, (r+1)-vertex graphs, which has been solved for many choices of n and r by Kelmans [K96]. It would be interesting to obtain the binary analogue of Kelmans’ results.

Problem 4: Find the maximum number of bases of an n-element, rank-r binary matroid.

This is just Problem 1 for $(s,t) = (2,4)$, and is most interesting when $n < 2^r – 1$. When $n = 2^r – 2^{r – c}$ for some $c \ge 1$ it seems likely that the number of bases will be maximized by the rank-r Bose-Burton geometry on n elements, but it is unclear what the answer should be for other values of n.

In the case that $\mathcal M$ is the class of rank-3 affine matroids over $\mathbb R$ and $\mathcal F$ is empty, Problem 3 has a more geometric flavor.

Problem 5: Among all sets of n points in $\mathbb R^2$ with no t in general position, what is the maximum number of non-collinear triples?

Theorems 3 and 4 can be used to solve this problem when t = 4 or 5, but this problem is open for all t at least six. Of course, one can also replace $\mathbb R^2$ with $\mathbb F^s$ for any field $\mathbb F$ and integer $s \ge 2$, and seek to maximize the the number of s-sets in general position. However, Problem 5 as stated is in some sense dual to a still-open problem of Erdős [E88]: among all sets of n points in $\mathbb R^2$ with no four on a line, what is the maximum cardinality of a subset in general position, in the worst case? 

Clearly Problem 3 has a wide variety of specializations, so I hope that every matroid theorist can find (and solve!) some instance that suits their interests.

References

[A24] N. Alon. Erasure list-decodable codes and Turán hypercube problems. Finite Fields and Their Applications, 100:102513, 2024.

[BLM11] B. Bollabás, I. Leader, C. Malvenuto. Daisies and other Turán problems. Combin. Probab. Comput,, 20(5):743—747, 2011.

[EIL24] D. Ellis, M.-R. Ivan, I. Leader. Turán densities for daisies and hypercubes. Bull. London Math. Soc., 56(12):3838—3853, 2024.

[E88] P. Erdős. Some old and new problems in combinatorial geometry. In Applications of discrete mathematics (Clemson, SC, 1986), pages 32—37, 1988.

[GN15] J. Geelen, P. Nelson. The number of points in a matroid with no n-point line as a minor. J. Combin. Theory Ser. B, 100(6):625—630, 2010.

[K11] P. Keevash. Hypergraph Turán problems. In Surveys in combinatorics, volume 392 of London Math. Soc. Lecture Note Ser., pages 83—139. Cambridge Univ. Press, Cambridge, 2011.

[K96] A. Kelmans. On graphs with the maximum number of spanning trees. Random Struct. Algorithms, 9:177—192, 1996.

[K93] J. P. S. Kung. Extremal matroid theory. In Graph structure theory (Seattle, WA, 1991), volume 147 of Comtemp. Math., pages 21—61. Amer. Math. Soc., Providence, RI, 1993.

[T41] P. Turán. On an extremal problem in graph theory. Mat. Fiz. Lapok, 48:436—452, 1941.

Delta-Modular Matroids

Posted on by
Reply

The goal of this post is to entice readers to work with an interesting class of matroids that has important connections with the theory of integer programming. These matroids are called Delta-modular, and they are a natural generalization of regular matroids. After giving some background information, I will state and discuss some fundamental properties of Delta-modular matroids, and then state and discuss some important open problems concerning these matroids. 

Introduction

A fundamental problem in integer programming is to solve the following Integer Linear Program (ILP): find $\textrm{max}\{c^Tx \mid Ax \le b \textrm{ and } x \in \mathbb Z^n\}$ where $A \in \mathbb Z^{m \times n}$, $b \in \mathbb Z^m$, and $c \in \mathbb Z^n$. This problem is $\mathcal N\mathcal P$-hard, but we can hope for better efficiency if the matrix $A$ has special structure. Given a positive integer $\Delta$, an integer matrix $A$ is $\Delta$-modular if the absolute value of every $\textrm{rank}(A) \times \textrm{rank}(A)$ submatrix of $A$ is at most $\Delta$. A classic result of Hoffman and Kruskal [HK56] implies that ILPs over 1-modular (or unimodular) matrices can be solved in strongly polynomial time. After about 60 years with little progress, a breakthrough result of Artmann, Weismantel, and Zenklusen showed that ILPs over 2-modular (or bimodular) matrices can be solved in strongly polynomial time [AWZ17]. Determining the complexity for solving ILPs over $\Delta$-modular matrices with $\Delta \ge 3$ is a major open problem in the theory integer programming.

The proof of Artmann, Weismantel, and Zenklusen heavily relies on structural properties of 2-modular matrices. This is where matroids come in! For each positive integer $\Delta$ we say that a matroid is $\Delta$-modular if it has a representation over $\mathbb Q$ as a $\Delta$-modular matrix, and we write $\mathcal M_{\Delta}$ for the class of $\Delta$-modular matroids. The hope is that studying $\mathcal M_{\Delta}$ via techniques from structural matroid theory will uncover new properties of $\Delta$-modular matrices that are relevant for integer programming. However, $\mathcal M_{\Delta}$ is also a very natural class of matroids, because $\mathcal M_1$ is precisely the class of regular matroids!

Properties

Even though $\mathcal M_{1}$ is fundamental in integer programming and matroid theory, little is known about $\Delta$-modular matroids when $\Delta \ge 2$. Below is a list of five properties that will likely be important for future work with these matroids.

Property 1: For all $\Delta \ge 1$, the class $\mathcal M_{\Delta}$ is closed under minors and duality.

Closure under minors was proved in [Proposition 8.6.1, GNW22] and closure under duality was proved by D’Adderio and Moci [Theorem 2.2, DM13] using arithmetic matroids, although a more direct proof due to Marcel Celaya can be found in [Theorem 4.2, OW22]. Of course, Property 1 is crucial for using techniques from structural matroid theory to study $\mathcal M_{\Delta}$.

Property 2: For all $\Delta \ge 1$, every matroid in $\mathcal M_{\Delta}$ is representable over every field with characteristic greater than $\Delta$.

This follows from the fact that if $A$ is a $\Delta$-modular matrix and $p$ is a prime greater than $\Delta$, then the set of all $\textrm{rank}(A)\times \textrm{rank}(A)$ submatrices of $A$ with non-zero determinant does not change if we perform all calculations modulo $p$. In particular, every matroid in $\mathcal M_2$ is dyadic, and every matroid in $\mathcal M_3$ is $\textrm{GF}(5)$-representable. Also, since there is a prime in the interval $(\Delta, 2\Delta]$ by Chebyshev’s Theorem, Property 2 implies that the uniform matroid $U_{2, 2\Delta + 2}$ is not in $\mathcal M_{\Delta}$. Again, Property 2 is crucial because it allows for the potential use of tools from the study of matroids representable over partial fields.

Property 3: When $\Delta \ge 2$, the class $\mathcal M_{\Delta}$ is not closed under direct sums.

This is where $\mathcal M_{\Delta}$ differs from matroid classes defined by representability over a partial field, which are always closed under direct sums. Intuitively, Property 3 is true because a block-diagonal matrix for which each block is $\Delta$-modular may not be $\Delta$-modular itself. As a particular example of Property 3, the uniform matroid $U_{2,4}$ is in $\mathcal M_2$, but $U_{2,4} \oplus U_{2,4}$ is not in $\mathcal M_2$ [Proposition 4.4, OW22].  

Property 4: If $r$ is sufficiently large as a function of $\Delta$, then every simple rank-$r$ matroid in $\mathcal M_{\Delta}$ has at most $\binom{r+1}{2} + 80\Delta^7 \cdot r$ elements [Theorem 1.3, PSWX24].

The problem of finding upper bounds on the number of columns of a rank-$r$ $\Delta$-modular matrix has received a lot of recent attention, because this also provides bounds for important parameters associated with ILPs over $\Delta$-modular matrices; see [LPSX23] for details. The bound in Property 4 was proved with techniques from matroid theory, and is currently the best known bound for fixed $\Delta$.

Property 5: $\mathcal M_{\Delta}$ contains no spikes with rank greater than $2\Delta$ [Proposition 2.1, PSWX24].

This was a key fact used in the proof of Property 4, and also differs from the typical situation for matroids over partial fields. Since spikes are notoriously `wild’, this is good news!

Open Problems

Since the study of $\Delta$-modular matroids is so new, there are many open problems.

Problem 1: Let $\mathcal M_{\Delta}^t$ be the class of matroids with a representation as a totally $\Delta$-modular matrix. Is $\mathcal M_{\Delta}^t = \mathcal M_{\Delta}$?

An integer matrix $A$ is totally $\Delta$-modular if the determinant of every square submatrix has absolute value at most $\Delta$. When $\Delta \le 2$, every $\Delta$-modular matrix is projectively equivalent to a totally $\Delta$-modular matrix, so Problem 1 has an affirmative answer when $\Delta \le 2$. However, when $\Delta \ge 3$ it is unclear whether every $\Delta$-modular matrix is projectively equivalent to a totally $\Delta$-modular matrix, so new ideas may be needed.

Problem 2: Find an absolute constant $C$ so that if $r$ is sufficiently large, then every simple rank-$r$ matroid in $\mathcal M_{\Delta}$ has at most $\binom{r+1}{2} + C\Delta\cdot r$ elements.

This is a natural next step from the bound in Property 4. There is a lower bound of $\binom{r+1}{2} + (\Delta – 1)(r – 1)$ that holds for all $\Delta \ge 1$ (see [Proposition 1, LPSX23]), so the bound in Problem 2 would be tight up to the constant $C$. While this lower bound is the correct answer for $\Delta = 1$ [Hel57] and $\Delta = 2$ [OW22, LPSX23], a recent construction of Averkov and Schymura [Theorem 1.3, AS22] does better for $\Delta \in \{4, 8, 16\}$, so there is no obvious choice for $C$ that is tight for all $\Delta$. 

Problem 3: Find a class $\mathcal N$ of matroids so that ILPs with $\Delta$-modular constraint matrix $A$ with $M(A) \in \mathcal N$ can be solved in polynomial time.

This is in the spirit of a recent result showing that ILPs over $\Delta$-modular matrices for which each row has at most two nonzero entries can be solved in strongly polynomial time [FJWY22]. Perhaps the most interesting choice for $\mathcal N$ would be the class of projections of graphic matroids, because the matroids in $\mathcal M_{\Delta}$ providing the best known lower bound in Problem 2 are projections of graphic matroids.

Problem 4: Find the list of excluded minors for $\mathcal M_{2}$.

Since $\mathcal{ M}_{\Delta}$ is minor-closed and every matroid in $\mathcal M_{\Delta}$ is representable over finite fields by Property 2, Rota’s Conjecture says that $\mathcal M_{\Delta}$ has a finite list of excluded minors. Tutte showed that $\mathcal M_{1}$ has only three excluded minors: $U_{2,4}$, the Fano plane $F_7$, and its dual $F_7^*$ [Tut58]. It should be feasible (but difficult) to use existing techniques to find the list of excluded minors when $\Delta = 2$; there is a more detailed discussion in [OW22]. 

Problem 5: Find a decomposition theorem for $\mathcal M_{2}$.

Seymour’s celebrated decomposition theorem says that every internally $4$-connected matroid in $\mathcal M_1$ is graphic, cographic, or a specific $10$-element matroid $R_{10}$ [Sey80]. Do matroids in $\mathcal M_2$ satisfy a similar property? If a decomposition can be found efficiently for $\mathcal M_2$, it would have several interesting consequences. For example, it would likely give a new proof that ILPs over 2-modular matrices can be solved in polynomial time. It would also likely give a polynomial-time algorithm for determining if a given matrix is 2-modular; this recognition problem is open for $\Delta$-modular matrices when $\Delta \ge 2$. While Problem 5 is certain to be difficult, it would likely be worthwhile to use the approach of [MNvZ11] and [CMN15] to systematically study what such a decomposition would look like. Of course, this problem is also highly interesting for $\mathcal M_{\Delta}$ with $\Delta \ge 3$.

References

[AWZ17] S. Artmann, R. Weismantel, R. Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1206-1919, 2017.

[AS22] G. Averkov, M. Schymura. On the maximal number of columns of a Delta-modular matrix. In K. Aardal and Laura L. Sanità, editors, Integer Programming and Combinatorial Optimization, pages 29-42, Cham, 2022. Springer International Publishing.

[CMN15] C. Chun, D. Mayhew, M. Newman. Obstacles to decomposition theorems for sixth-root-of-unity matroids. Ann. Combin., 19:79-93, 2015.

[DM13] M. D’Adderio, L. Moci. Arithmetic matroids, the Tutte polynomial, and toric arrangements. Adv. in Math., 232:335-367, 2013.

[FJWY22] S. Fiorini, G. Joret, S. Weltge, Y. Yuditsky. Integer programs with bounded subdeterminants and two nonzeros per row. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 13-24, 2022.

[GNW22] J. Geelen, P. Nelson, Z. Walsh. Excluding a line from complex-representable matroids. To appear in Mem. Amer. Math. Soc.

[Hel57] I. Heller. On linear systems with integral valued solutions. Pac. J. Math., 7(3):1351-1364, 1957.

[HK56] A. Hoffman, J. Kruskal. Integral boundary points of convex polyhedra. Linear Inequalities and Related Systems, 24:223-246, 1956.

[LPSX23] J. Lee, J. Paat, I. Stallknecht, L. Xu. Polynomial upper bounds on the number of differing columns of Delta-modular integer programs. Math. Oper. Res., 48(4):1811-2382, 2023.

[MWvZ11] D. Mayhew, G. Whittle, S. H. M. van Zwam. An obstacle to a decomposition theorem for near-regular matroids. SIAM J. Disc. Math., 25(1):271-279, 2011.

[OW22] J. Oxley, Z. Walsh. 2-Modular matrices. SIAM J. Disc. Math., 36:1231-1248, 2022.

[PSWX24] J. Paat, I. Stallknecht, Z. Walsh, L. Xu. On the column number and forbidden submatrices for Delta-modular matrices. SIAM J. Disc. Math., 38:1-18, 2024.

[Sey80] P. D. Seymour. Decomposition of regular matroids. J. Combin. Theory Ser. B, 28:305-359, 1980.

[Tut58] W. T. Tutte. A homotopy theorem for matroids, I, II. Trans. Amer. Math. Soc., 88, 144-174, 1958.