The Matroid Intersection Conjecture

This is a guest post by Johannes Carmesin.

About a month ago, on 6 October, when OpenAI made more than 700 mathematical manuscripts available in a single day, I was shocked. I am particularly impressed by the speed at which AI is getting better at mathematics. These manuscripts contain powerful results, including the resolution of Hadwiger’s conjecture. Yet I feel that something often overlooked is that we need more information than these manuscripts alone to assess AI capabilities.

OpenAI itself reported that the initial collection comprised 722 manuscripts, grouped into 372 families of results, arising from an evaluation in which its model was posed approximately 4,000 problems. The full list of attempted problems and their outcomes has not been made public.

One of the results, Problem #185, disproves the packing/covering conjecture formulated by Nathan Bowler and myself. Remarkably, Nash-Williams’ considerably older intersection conjecture, which is a special case, remains open. Early in my mathematical career, more than ten years ago, I worked intensively on this conjecture without being able to prove it. Beyond that personal interest, I think it is particularly timely to discuss it now because it offers an interesting case study of modern AI capabilities. Let me start from the beginning.

The Aharoni–Berger theorem

Menger’s theorem says that in a finite graph, the maximum number of vertex-disjoint paths between vertex sets $A$ and $B$ equals the minimum size of a vertex set separating them. This is an instance of linear-programming duality: one problem packs paths, while the dual covers all $A$–$B$ paths by vertices. Integrality gives actual paths and vertices as optimal solutions. Complementary slackness explains how they fit together: each chosen path meets the separator exactly once, and every separator vertex lies on a chosen path.

This gives the following more structural formulation of Menger’s theorem. Given vertex sets $A$ and $B$, there are pairwise vertex-disjoint $A$–$B$ paths and an $A$–$B$ separator consisting of exactly one vertex from each path; see the figure below.

The four blue $A$–$B$ paths are pairwise vertex-disjoint. The orange vertices form an $A$–$B$ separator containing exactly one vertex from each path.

The formulation makes sense for infinite graphs too, whereas equality of infinite cardinalities loses this information. Aharoni and Berger proved that these compatible witnesses always exist, settling the long-standing Erdõs–Menger conjecture. An example of a simple infinite graph where the Aharoni–Berger theorem is non-trivial is given in the figure below.

An uncountable matching obstruction. The left vertices are indexed by the infinite countable ordinals, and the right vertices by all countable ordinals; $\omega_1$ denotes the first uncountable ordinal. Each left vertex is joined to every smaller ordinal on the right, with one neighbourhood highlighted in blue. Every countable set of left vertices can be matched to distinct neighbours, but Fodor’s lemma rules out a matching covering the entire left side.

From graphs to matroids

Before passing to infinite matroids, let us look at another structural statement in the finite setting. For two matroids on a common ground set $E$, a packing consists of disjoint spanning sets, one for each matroid. A covering consists of independent sets, one in each matroid, whose union is $E$.

For two copies of the cycle matroid of a connected graph, packing asks for two edge-disjoint spanning trees; covering asks for two forests that together contain every edge. Packing becomes possible when there are enough edges, while covering becomes possible when there are few enough.

The finite packing/covering theorem combines these two possibilities. It partitions $E$ into a dense part $P$ and a sparse part $Q$: the matroids restricted to $P$ admit a packing, and the matroids obtained by contracting $P$ admit a covering of $Q$. Thus the dense part supports disjoint spanning sets, and the remaining elements can be covered by independent sets after contraction as shown below.

Packing and covering in two copies of the cycle matroid of the same graph. The blue edges form the dense part $P$. The disjoint blue sets $S_1$ and $S_2$ each contain a spanning tree of the blue core, giving the required packing. The orange edges form the sparse part $Q$. After contracting the blue core to a single vertex, the orange sets $I_1$ and $I_2$ are both forests, and together they cover $Q$.

This theorem is equivalent to Edmonds’ intersection theorem, with one matroid dualised when passing between the formulations. The structural form of Edmonds’ intersection theorem says that two matroids $M$ and $N$ on $E$ have a common independent set $I$ with a partition satisfying

$I=I_M\mathbin{\dot\cup}I_N,
\qquad
\operatorname{cl}_M(I_M)\cup\operatorname{cl}_N(I_N)=E.$

Every element of $E$ is spanned by the $M$-part in $M$ or by the $N$-part in $N$. For finite matroids, this supplies a certificate that $I$ has maximum possible size. As with Menger’s theorem, the structural statement explains why the optimum has been reached.
 
Now we pass to infinite matroids. It is highly desirable to obtain a fully algebraic proof of the Aharoni–Berger theorem. Nash-Williams had proposed a conjecture for finitary matroids (see this paper by Aharoni and Ziv) which would imply this theorem. The statement of this conjecture is the above statement of Edmonds’ intersection theorem, with the assumption that $M$ and $N$ are finite matroids replaced by the assumption that they are finitary matroids. Here a matroid is finitary if all its circuits are finite, although its ground set may be infinite. Since finite-cycle matroids of graphs are examples of finitary matroids, the standard deduction of Menger’s theorem from matroid intersection extends to infinite matroids, showing that Nash-Williams’ conjecture implies the Aharoni–Berger theorem.
 
This post can be understood without any particular knowledge of infinite matroids. However, if you would like to learn more about them, Nathan Bowler’s series on infinite matroids is an excellent introduction.
 
Nathan and I worked on another problem of Nash-Williams concerning the existence of packings in infinite matroids. During our investigation, we discovered the packing/covering statement given above. Interestingly, before our work it did not seem to be part of the literature even for finite matroids. But as classical rank-based approaches to packings are much less powerful for infinite matroids, we were, in a sense, forced to discover it. This is a very attractive aspect of studying infinite graphs and matroids: standard induction arguments often cannot simply be replaced by transfinite induction. Instead, to extend a theorem from the finite to the infinite setting, one is forced to discover a more structural version of it. Menger’s theorem and the packing/covering theorem are excellent examples of this phenomenon.
 
Nathan and I conjectured that the above packing/covering statement holds not only for finite matroids but for all infinite matroids. We proved that this statement is equivalent to the assertion that every pair of matroids on a common ground set satisfies Edmonds’ intersection statement in the above form, and thus implies Nash-Williams’ conjecture. Here I should note that, for applications in infinite topological graph theory, it would be enough to prove this conjecture for a subclass of all matroids called tame matroids. Of course, we made the conjecture in full generality, as this was the next open problem to consider.

What is Problem #185?

OpenAI found a counterexample on a countable ground set to the packing/covering conjecture formulated by Nathan and myself. Yet the tame case of the conjecture remains open, including Nash-Williams’ conjecture.

Even the correct infinite analogue of a uniform matroid requires care. In the finite case, all subsets of a fixed size are bases. This description cannot simply be transferred to infinite cardinalities: an infinite set and a proper superset can have the same size, whereas one basis cannot be a proper subset of another. The appropriate definition is structural: a matroid is uniform if every subset of its ground set is independent or spanning. We are interested in such matroids of infinite rank and corank, so that every basis and its complement are infinite.

The existence of such a matroid is itself non-trivial. Nathan Bowler and Stefan Geschke constructed examples that are equal to their duals on the same labelled ground set, assuming Martin’s Axiom. An important contribution of OpenAI’s work is to construct such a matroid $U$ in ZFC, resolving the existence question without this additional assumption.

A finite uniform matroid is determined, up to isomorphism, by the size of its ground set and the size of a basis. For infinite rank and corank, these cardinalities no longer determine the matroid. Indeed, rather surprisingly, infinite uniform matroids offer, intuitively speaking, more freedom in their construction than any other matroids known to date. These matroids were therefore the most promising ingredients for a counterexample. Two copies of a self-dual uniform matroid nevertheless admit both a packing and a covering: simply take a basis and its complement.

Nathan and I already regarded direct sums of such matroids as a promising strategy in 2013. We explored the idea briefly, but gave up: we thought that making it work, if it could be made to work at all, would take us years.

OpenAI assembles countably many copies of its specially constructed uniform matroid into two direct sums on the same ground set. The copies are disjoint within each matroid, but the two decompositions overlap. The construction exploits the freedom in choosing the uniform matroid, using set-theoretic machinery to enforce additional properties that make this pair a counterexample. The difficult task is to enforce those properties while still satisfying all infinite-matroid axioms. OpenAI also supplies a Lean formalisation.

Joó versus the machine

In 2021, in a major advance, Attila Joó proved Nash-Williams’ conjecture for finitary matroids on a countable ground set. See the figure below for an overview of the different classes and the remaining open cases of the intersection and packing/covering conjectures.

Matroid classes, with examples. Finitary matroids have only finite circuits; in a tame matroid, every circuit meets every cocircuit in a finite set. Wild matroids fail the latter condition. Countability refers to the ground set, not to the set of ends of a graph. Intersection holds for finite pairs and for countable finitary pairs (Joó); the uncountable finitary case remains open. Packing/covering holds for finitary pairs on arbitrary ground sets (Bowler–Carmesin). For both conjectures, the general tame case remains open even on a countable ground set, and the unrestricted case fails already on a countable ground set. The examples illustrate the classes; $U$ is the building block of the counterexample.


Given that Nash-Williams’ conjecture is older, better known and mentioned in OpenAI’s manuscript, I suspect the model attempted it too but could not solve it. But that is a guess.

OpenAI’s result is exciting pioneering work and raises far more questions than it answers, which is often an indicator of interesting mathematics. I am therefore a little disappointed that it did not formulate the conjecture for tame matroids, which is the obvious next step. Indeed, if true, this conjecture would imply an extension of the Aharoni–Berger theorem to a large class of topological spaces.

Infinite uniform matroids can, under suitable set-theoretic assumptions, have bases of different cardinalities, which is a very non-combinatorial artefact. From a combinatorial perspective, OpenAI’s counterexample may be interpreted as excluding these non-combinatorial constructions from the natural class of matroids for which Edmonds’ intersection principle holds. This may give some hope that, if packing/covering holds for much wider classes of matroids than those for which it is currently known, a proof might, like that of the Aharoni–Berger theorem, be combinatorial in nature. Aharoni’s 1987 proof of the countable Erdõs–Menger conjecture was followed, nearly two decades later, by Aharoni and Berger’s proof for arbitrary graphs. I see Joó’s theorem as an analogous milestone for Nash-Williams’ conjecture, giving grounds to hope for a similar development: that the club-set techniques used in the Aharoni–Berger theorem can be extended to infinite matroids by combining them with Joó’s ideas.

Hence I regard Joó’s theorem as the most substantial result in the area today.

In infinite matroid intersection, AI currently leads in constructing counterexamples, but a human holds the strongest theorem.

Studying AI capabilities more broadly

To assess AI capabilities, we need to know how often a system solves a specified set of problems under specified conditions. OpenAI’s counts do not answer that question.

There is evidence beyond Problem #185 that current AI systems are stronger at finding counterexamples than at proving theorems. Indeed, in the summer, Vaibhav Bajpai, Nathan Bowler, Utku Okur and I released Ten Challenges in Combinatorics: a selection of ten significant problems in combinatorics, formalised in Lean and hence ready to be tackled by AI. Since then, three of these ten challenges have been resolved – all by counterexamples! Of course, more investigations are needed to underscore the claim that current AI systems are more successful at refuting conjectures than at proving them.

Just this week, we released LPBench, a larger set of slightly more than 100 problems formalised in Lean, to study broader AI capabilities. We are grateful to Anthropic for providing us with the means to test its best currently publicly available models on these problems. They performed strongly in generating Lean proofs for results in the literature, making them reliable tools for formalising human proofs. The second important piece of news for human mathematicians is that, despite some effort, they were unable to resolve any of the 32 open problems in the benchmark.

The foundation of a segment-cosegment exchange

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.

Representable Matroid Lifts

In this blog post, I’m going to discuss a part of a paper I wrote with Zach Walsh a few years back called “Matroid lifts and representability.” We’ll start by motivating the idea of a matroid lift.

Let $A \in \mathbb{F}^{r_1 \times n}$ and $B \in \mathbb{F}^{r_2 \times n}$ be matrices such that $A$ is a row-submatrix of $B$. Let $E$ denote the column set of $B$, which also naturally indexes the column set of $A$. Let $M_A$ and $M_B$ denote the matroids on ground set $E$ defined by linear independence in $A$ and $B$, respectively. Since $A$ is a row-submatrix of $B$, there is a special relationship between $M_A$ and $M_B$. In particular, every flat of $M_A$ is a flat of $M_B$. This motivates the following definition: given two matroids $M_1$ and $M_2$ on a common ground set $E$, one says that $M_2$ is a lift of $M_1$ if every flat of $M_1$ is a flat of $M_2$.

An Example

Recall that $U_{r,n}$ denotes the uniform matroid of rank $r$ on $n$ elements. One can check that $U_{2,3}$ is a lift of $U_{1,3}$. One can check this by noting that the flats of $U_{1,3}$ are the empty set, the full ground set, and each singleton set and that each of these are also flats of $U_{2,3}$. Alternatively, one can consider the following $\mathbb{Q}$-matrix

$\begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{pmatrix}$

and note that the matroid of the top row is $U_{1,3}$ and the matroid of the whole matrix is $U_{2,3}$. One interesting thing to note is that even though $U_{1,3}$ and $U_{2,3}$ are both $\mathbb{F}_2$-representable, there is no $2\times 3$ $\mathbb{F}_2$ matrix $B$ that represents $U_{2,3}$, whose top row represents $U_{1,3}$.

Notational Remark

For any matroid $Q$, I will use the notation $r_Q$ and ${\rm cl}_Q$ to denote the rank function and closure operator in $Q$.

Elementary lifts

If $M_2$ is a lift of $M_1$, then the rank of $M_2$ is greater than or equal to that of $M_1$. When $M_2$ is a lift of $M_1$ whose rank is exactly one greater than that of $M_1$, one says that $M_2$ is an elementary lift of $M_1$. I will now describe a classical theorem of Brylawski, the dual version of which was previously stated by Crapo, that gives an elegant combinatorial characterization of all elementary lifts of a matroid $M$.

Let $M$ be a matroid on ground set $E$. A linear class of $M$ is a collection $\mathcal{L}$ of circuits of $M$ such that if $C_1,C_2 \in \mathcal{L}$ satisfy

$|C_1 \cup C_2| – r_M(C_1 \cup C_2) = 2$

then if $C_3$ is a circuit of $M$ contained in $C_1 \cup C_2$, then $C_3 \in \mathcal{L}$. For each such linear class, one can define a function $r_\mathcal{L}: 2^{E} \rightarrow \mathbb{N}$ as follows

$r_\mathcal{L}(X) = \begin{cases}r_M(X) & \textnormal{if each circuit of } M|X \textnormal{ is in } \mathcal{L} \\ r_M(X) + 1 & {\rm otherwise}.\end{cases}$

For each linear class $\mathcal{L}$ of $M$, $r_\mathcal{L}$ is the rank function of a matroid $L$ such that $L$ is an elementary lift of $M$. What is even more interesting is that for every elementary lift $L$ of $M$, there exists a linear class $\mathcal{L}$ of circuits of $M$ such that the rank function of $L$ is $r_{\mathcal{L}}$.

Higher-rank lifts

I became aware of Zach’s existence when his paper “A new matroid lift construction and an application to group-labeled graphs” hit the arXiv. It gave a method for constructing non-elementary lifts of matroids in a way that generalized Brylawski’s construction. At the time, I was on the prowl for matroid theory tools that could be useful in rigidity theory, and matroid lifts had recently played a key role in a groundbreaking paper of Clinch, Jackson, and Tanigawa called “Abstract 3-Rigidity and Bivariate C12-Splines II: Combinatorial Characterization.” So I was very intrigued by Zach’s construction, which is given in the following theorem. 

Theorem (Walsh): Let $M$ be a matroid on ground set $E$ with circuit set $\mathcal{C}$. Let $N$ be a matroid on ground set $\mathcal{C}$ such that if $|C_1 \cup C_2| – r_M(C_1 \cup C_2) = 2$, then each $C \in \mathcal{C}$ such that $C \subset C_1 \cup C_2$ satisfies $C \in {\rm cl}_N(\{C_1 \cup C_2\})$. Then the function $\rho_N: 2^E \rightarrow \mathbb{N}$ defined as follows is the rank function of a lift of $M$ of rank $r_M(E) + r_N(\mathcal{C})$

$\rho_N(X) = r_M(X) + r_N(\{C : C \textnormal{ is a circuit of } M|X\}).$

Zach’s construction generalizes Brylawski’s construction in the sense that when $r_N(\mathcal{C}) = 1$, the rank-zero flat of $N$ is a linear class $\mathcal{L}$ of circuits of $M$, and that $r_\mathcal{L} = \rho_N$. Zach had hoped that this construction would completely generalize Brylawski’s result in that every lift of a matroid $M$ would have rank function of the form $\rho_N$ for some matroid $N$ on the circuit set of $M$. As we will see, this is not the case. However, it does hold for matroid lifts that arise from taking the matroid of a matrix, and a row-submatrix. This gives us a way to test that a given lift is “representable” as a lift, and can even be turned into a test for matroid representability.

Theorem (B-Walsh): Let $A \in \mathbb{F}^{r_1 \times n}$ and $B \in \mathbb{F}^{r_2 \times n}$ such that $A$ is a row-submatrix of $B$. Let $M_A,M_B$ respectively denote the column matroids of $A$ and $B$ and let $\mathcal{C}$ denote the set of circuits of $A$. Then there exists a matroid $N$ on ground set $\mathcal{C}$ such that $\rho_N$ is the rank function of $M_B$.

Here is a sketch of the proof. Since $A$ is a row-submatrix of $B$ we may without loss of generality assume that $B$ has the following form for some matrix $C$

$B = \binom{A}{C}$.

For each circuit $C$ of $M_A$ let $x_C$ be a fixed element of $\mathbb{F}^n$ such that $Ax = 0$. Then $Bx_C$ can be written in the following form for some $x_C’ \in \mathbb{F}^{r_2-r_1}$

$Bx_C = \binom{0}{x_C’}$.

This enables us to define a matroid $N$ on the circuit set $\mathcal{C}$ of $A$ by asserting that $\{C_1,\dots,C_k\}$ is independent in $N$ if and only if the set of vectors $\{x_{C_1}’,\dots,x_{C_k}’\}$ is linearly independent in $\mathbb{F}^{r_2-r_1}$. Then, the rank function of $M_B$ is $\rho_N$.

Non-representable higher rank lifts

The proof of the above theorem heavily depends on access to a linear representation of the higher rank matroid, that has a row-submatrix representing the lower rank matroid. This dependence on a representation cannot be avoided, at least not in full generality. In particular, we can obtain a counterexample from the Vámos matroid.

Given any matroid $M$ on ground set $E$ and an independent subset $I \subset E$, $M\setminus I$ is always a lift of $M / I$ and the difference in ranks is $|I|$ and all lifts can be obtained in this way. Let $V_8$ be the matroid with ground set $\{1,2,\dots,8\}$ of rank $4$, such that every subset of size four or smaller is independent, with the exceptions of the following four-element subsets

$1234,3456,5678,1278,3478.$

This is known as the Vámos matroid, which is known to not be representable over any field. Then $V_8 \setminus \{7,8\}$ is a lift of $V_8 / \{7,8\}$, and as Zach and I show in our paper, there is no matroid $N$ of rank $2$ on the circuit set of $V_8 / \{7,8\}$ such that the rank function of $V_8 \setminus \{7,8\}$ is $\rho_N$. We generalize this construction to construct a two-parameter infinite antichain (in the minor partial order) of sparse paving matroids that are not representable over any field, that satisfy Ingleton’s inequality.

Concluding remarks

As with many papers I’ve written, the bulk of the time I spent “writing” this paper was spent chasing something I wound up being unable to prove. In particular, I was hoping to generalize the theorem about representable lifts of matroids being obtainable via Zach’s construction to the family of algebraic matroids. Alas, not only was I unable to prove that, I’m not so sure if it’s true anymore. But I really don’t have any reason to make a conjecture either way.

Direct sum of q-matroids

One of the most straightforward operations you can do when you want to make a new matroid out of old ones, is taking the direct sum. The direct sum of the matroids $M_1=(E_1,r_1)$ and $M_2=(E_2,r_2)$ is the matroid $M$ on ground set $E=E_1\sqcup E_2$ with for all $A\subseteq E$,
\[ r(A)=r_1(A\cap E_1)+r_2(A\cap E_2). \]Alternatively, its independent sets are the unions of an independent set in $M_1$ and an independent set in $M_2$. The third equivalent way to define the direct sum is by saying that $M=M_1\oplus M_2$ is precisely the matroid such that $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$.

In this post, we will discuss the q-analogue of this concept. The q-analogues of matroids, called q-matroids, have been introduced here. Instead of considering a matroid on a finite ground set, where every subset has a rank that satisfies certain axioms, we take a q-matroid on a finite dimensional vector space where every subspace has a rank, again satisfying certain axioms. A good intuition is to think about matroids as a bicolouring of the Boolean lattice, and q-matroids as a bicolouring of the subspace lattice.

If we take the direct sum of two q-matroids $M_1=(E_1,r_1)$ and $M_2=(E_2,r_2)$, it makes sense for $M=M_1\oplus M_2$ to have as a ground space the direct sum of vector spaces $E_1\oplus E_2$. It is also reasonable to ask that $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$. But then it gets difficult. Where for sets, we can write any subset $A\subseteq E_1\sqcup E_2$ as $(A\cap E_1)\sqcup(A\cap E_2)$, such a thing is not true for vector spaces. Suppose for example $E_1=\langle100\rangle$ and $E_2=\langle010,001\rangle$ (over my favourite finite field $\mathbb{F}_2$) such that $E_1\oplus E_2$ is a 3-dimensional space. Then the space $A=\langle111\rangle$ does not intersect $E_1$ nor $E_2$. What is its rank going to be?

One could hope that maybe the rank axioms of q-matroids take care of this. Look for example at the direct sum of $U_{1,1}$ and $U_{1,2}$ over $\mathbb{F}_2$.

We see that the interval between $0$ and $\langle100\rangle$ and the interval between $\langle010,001\rangle$ and $E$ are coloured as $U_{1,1}$, showing $M|_{E_1}=M/E_2=M_1$. On the other hand, the interval between $0$ and $\langle010,001\rangle$ and the interval between $\langle100\rangle$ and $E$ are coloured as $U_{1,2}$, showing that $M|_{E_2}=M/E_1=M_2$. There is now only one way to colour the rest of the lattice:

Unfortunately, this construction becomes not unique already in dimension 4. If we try to make the direct sum $U_{1,2}\oplus U_{1,2}$, semimodularity of the rank function gives that all 1-dimensional spaces have rank 1 and all 3-dimensional spaces have rank 2. Any 2-dimensional space intersecting $E_1$ or $E_2$ is a basis. But there are 2-dimensional spaces that intersect neither $E_1$ nor $E_2$ (over $\mathbb{F}_2$, there are three of them) and those can be either a basis or a circuit. Any choice will produce another q-matroid.

The solution to this problem is to write the direct sum in a very convoluted way that is not helpful for matroids over sets, but that does have a nice q-analogue. This is the following. As mentioned, let $E=E_1\oplus E_2$. Make a matroid $M_1’$ by adding loops to $M_1$ until its groud space is $E$: $M_1’$ is the q-matroid on $E$ such that $M_1’|_{E_1}=M_1$ and $M_1’|_{E_2}$ consists of only loops. Similarly, let $M_2’$ be the q-matroid on $E$ such that $M_2’|_{E_2}=M_2$ and $M_2’|_{E_1}$ consists of only loops. Now the direct sum $M_1\oplus M_2$ is defined as the matroid union $M_1’\vee M_2’$.

It turns out that adding loops is, inductively, possible in the q-analogue. Also matroid union (as an honour to the name of this blog, surely!) has a well-defined q-analogue: this operation is defined for matroids on the same ground set, and can thus be generalised to q-matroids with the same ground space without the troubles that come with the direct sum of vector spaces. The rank function of the direct sum of two q-matroids is \[ r_{M_1\oplus M_2}(A)=\min_{X\subseteq A}\{r_{M_1′}(X)+r_{M_2′}(X)+\dim A-\dim X\}. \]

An equivalent way to phrase this definition of the direct sum of q-matroids, is by requiring the direct sum to to be the “most independent” q-matroid satisfying $M|_{E_1}=M/E_2=M_1$ and $M|_{E_2}=M/E_1=M_2$. This can be made precise in category theory language.

It is unclear what the independent spaces of the direct sum of two q-matroids are. The vector space sum of an independent space in $M_1$ and an independent space in $M_2$ is independent in the direct sum. But there are many more independent spaces. Many other properties of the direct sum of matroids fail to have a nice q-analogue. What does work in the q-analogue, is that the cyclic flats of the direct sum are exactly the sums of the cyclic flats of $M_1$ and $M_2$.

You might have guessed that if $M_1$ and $M_2$ are q-matroids represented by matrices $G_1$ and $G_2$ (I’m going to use this notion without a formal definition), then their direct sum is not necessarily represented by the matrix \[ \left[ \begin{array}{cc} G_1 & 0 \\ 0 & G_2 \end{array} \right]. \] Interestingly, the question about representability can be translated to the language of linear sets in finite geometry, making it possible to use several results in finite geometry for q-matroids.

References

[AJNZ26] Gianira Alfarano, Relinde Jurrius, Alessandro Neri and Ferdinando Zullo. Representability of the direct sum of uniform q-matroids. Combinatorial Theory, 6 (2026).

[CJ24] Michela Ceria and Relinde Jurrius. The direct sum of q-matroids. Journal of Algebraic Combinatorics, 59, pp. 291-330 (2024).

[GLJ23] Heide Gluesing-Luerssen and Benjamin Jany. Coproducts in categories of q-matroids. European Journal of Combinatorics 112, 103733 (2023).

[GLJ24] Heide Gluesing-Luerssen and Benjamin Jany. Decomposition of q-matroids using cyclic flats. SIAM Journal on Discrete Mathematics 38, pp 2940–2970 (2024).

[GLJ25] Heide Gluesing-Luerssen and Benjamin Jany. Representability of the direct sum of q-matroids. Journal of Algebraic Combinatorics 61, 51 (2025).