Author Archives: Zach Walsh

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.

 

 

Online Talk: James Oxley

Posted on by
Reply

YouTube recording: https://www.youtube.com/watch?v=fKgb4XxhQzk

Time: Wednesday, April 24 at 3pm ET
Zoom: https://gatech.zoom.us/j/8802082683

Speaker: James Oxley, Louisiana State University
Title: The legacy of Dominic Welsh

Abstract: Dominic Welsh wrote the first comprehensive text on matroids. He supervised 28 doctoral theses and wrote over 100 papers and five books. As impressive as these numbers are, they fail to truly capture the spirit of the man who inspired generations of students and imbued them with not only a love of mathematical beauty but with a deep and abiding affection for the man himself. Dominic died in November, 2023. The speaker will attempt to capture some of the key aspects of his legacy.