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.

Representable Matroid Lifts

Posted on by
Reply

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

Posted on by
2

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

The cycle double cover theorem

Posted on by
Reply

This is a guest post by Johannes Carmesin.

You have probably all heard that OpenAI announced a fully automated proof of the cycle double cover conjecture, which was conjectured independently by Tutte, Itai and Rodeh, Szekeres, and Seymour about fifty years ago.

First, to answer the most immediate question: yes, the proof is correct.

Here, I would like to do two things:

  1. explain the statement of the theorem; and
  2. give an overview of how the proof has been verified.

Statement of the theorem

The theorem has a particularly appealing topological formulation: every bridgeless multigraph can be embedded in a pseudosurface in such a way that every face is a disc. In particular, every edge occurs exactly twice among the boundary walks of the faces. Here, a pseudosurface is a topological space obtained from a closed surface (possibly disconnected) by identifying finitely many points.

The use of pseudosurfaces is very natural in this context: embeddings of different blocks can be glued together at their common cut-vertices. An example that pseudosurfaces are genuinely necessary is given below.

The bowtie graph, consisting of two triangles glued together at a single vertex. It has a unique cycle double cover. It contains each triangle twice. The corresponding embedding has four disc faces and lies naturally in two spheres identified at the common vertex. This shows that pseudosurfaces are genuinely necessary in the topological formulation of the problem.
The bowtie graph, consisting of two triangles glued together at a single vertex.
It has a unique cycle double cover. It contains each triangle twice.
The corresponding embedding has four disc faces and lies naturally in two spheres identified at the common vertex. This shows that pseudosurfaces are genuinely necessary in the topological formulation of the problem.

The algebraic counterpart of this topological statement is the following equivalent formulation: every bridgeless multigraph $G$ has a cycle double cover. That is, there exists a family $\{C_i\mid i\in I\}$ of cycles of $G$ such that every edge belongs to exactly two of the cycles $C_i$.

To see the connection, suppose first that such a cycle double cover is given. For every cycle $C_i$, take a disc and glue its boundary to the corresponding cycle in the graph. Since every edge occurs in exactly two cycles of the family, every edge is incident with two such discs. The resulting space is a pseudosurface in which the original graph is embedded and the added discs are precisely its faces.

For a simple example showing that pseudosurfaces are genuinely necessary in the above topological formulation of the cycle double cover conjecture, see the figure below.

Conversely, given such an embedding in a pseudosurface, the family $\{C_i\mid i\in I\}$ consists of the boundary walks $C_i$ of the faces of the embedding, which are cycles. Taken over all faces, these cycles form a cycle double cover, because every edge occurs exactly twice among the boundary walks of the faces.

The assumption that the graph is bridgeless is necessary. Indeed, a bridge is a cocircuit-singleton and thus cannot belong to any cycle and therefore cannot be covered even once by a cycle, let alone exactly twice.

About the proof

The proof by OpenAI establishes the second, algebraic formulation. In a nutshell, it begins with a nowhere-zero $\mathbb{F}_2^3$-flow $f$ on $G$; that is, an assignment of a nonzero vector in $\mathbb{F}_2^3$ to each edge such that, at every vertex, the values on the incident edges sum to zero. The existence of this flow follows from Seymour’s nowhere-zero six flow theorem (see also the recent short proof by DeVos and Nurse).

Roughly speaking, this flow is not quite a cycle double cover. The paper studies how one locally needs to modify the flow at each vertex so that it becomes a cycle double cover, and then there is a compatibility condition that needs to hold between adjacent vertices.

The compatibility conditions between the local modifications, and the equations for the local modifications give rise to a system of linear equations over $\mathbb{F}_2$, with one vector variable in $\mathbb{F}_2^3$ for each vertex and one scalar variable in $\mathbb{F}_2$ for each edge. OpenAI then uses duality to prove that this system always has a solution. The entire proof occupies only two pages.

Sang-il Oum gave an excellent talk on the proof and provides a much more detailed explanation. Jim Geelen (link) and Sang-il Oum (link) independently wrote short notes giving the complete proof in a different presentation, which I both find particularly pleasant to read and the latter additionally contains open questions.

Finally, the proof has already been formalised independently several times in Lean 4. Krystal Guo produced one formalisation of the core argument (personal communication), while Vaibhav Bajpai, Utku Okur, and I produced another, and one by OpenAI (see also this discussion in the AI-authored projects channel of the Lean Zulip community).