Trouble with infinite oriented matroids

Posted on June 1, 2026 by Nathan Bowler

After many years, this series of posts on infinite matroids is finally coming to an end. We started with the basic definitions and axioms, and building on those we have seen how a great deal of matroid theory can be lifted to infinite matroids, from representability and graphic matroids through to excluded minor characterisations and matroid intersection. Today, however, we are going to look at an instructive case of ideas from finite matroid theory which do not generalise to infinite matroids.

This is an old project, which I have been thinking about on-and-off for years together with Winfried Hochstättler and Stefan Kaspar. Probably Stefan is the one who has put most into this project and who has kept it alive and interesting for so long. Thanks Stefan! It’s about trying and failing to sensibly define infinite oriented matroids.

Before we get to what goes wrong in the infinite world, however, we should take a moment to remind ourselves how finite oriented matroids are defined. Although there are lots of different cryptomorphic axiomatisations, for our purposes it will be enough to look at the axiomatisation in terms of signed circuits.

A signing $X$ of a set $\underline X$ is a partition of $\underline X$ into a pair of sets $(X^+, X^-)$. There are lots of examples of matroids that come with a natural signing of each of their circuits. For example, let $D$ be any directed graph, and let $M$ be the cycle matroid of its underlying undirected graph. Then any circuit of $M$ is a cycle, and we can naturally partition its edges according to which way they point around the cycle. More generally, if $M$ is any matroid represented over the reals, then any circuit of $M$ is necessarily linearly dependent, and the linear combination witnessing this is unique up to (nonzero) scaling. So we can partition the circuit into those elements with a positive and those with a negative coefficient.

Notice that in each case, when we took a signing $X$ we could equally have taken the opposite signing $-X$ with $(-X)^+ = X^-$ and $(-X)^- = X^+$. So it is normal to include both options, giving a collection of signed sets which is symmetric, in the sense of being closed under taking opposites. To capture these and many more general examples, we can define an oriented matroid to be a pair $(E, \mathcal{C})$ where $E$ is a (finite) set and $\mathcal{C}$ is a set of signed subsets of $E$ satisfying the following axioms:

(OC1) $\emptyset \notin \mathcal{C}$

(OC2) $\mathcal{C}$ is symmetric

(OC3) For any $X$ and $Y$ in $\mathcal{C}$ with $\underline X \subseteq \underline Y$ we have $X = \pm Y$

(OC4) For any $X$ and $Y$ in $\mathcal{C}$, any $e \in X^+ \cap Y^-$, there is some $Z \in \mathcal{C}$ with $Z^+ \subseteq (X^+ \cup Y^+) – e$ and $Z^- \subseteq (X^- \cup Y^-) – e$

It’s clear that the underlying sets of these signed circuits must then be the circuits of a matroid, and we call $\mathcal{C}$ an orientation of that matroid. There is no space here to go into the rich theory of finite oriented matroids, but a good introduction is [1]. All we will need is that, as for ordinary matroids, we can define minors and duality for oriented matroids.

To understand the duality, we need the notion of orthogonality. If $X$ and $Y$ are signed sets then we say they are orthogonal if they are disjoint or if there is both at least one element where they agree on the sign and also at least one element where they disagree on the sign. Then for any orientation of a matroid there is a unique orientation of its dual all of whose signed sets are orthogonal to the signed circuits of the original matroid. Having defined duality of oriented matroids in this way, we can go on to define minors, since contraction is dual to restriction and it is clear how restriction should be defined for oriented matroids.

How could we generalise these notions to infinite matroids? It’s clear how to define finitary oriented matroids: they should be pairs $(E, \mathcal{C})$ such that $E$ is a set and $\mathcal{C}$ is a set of finite signed subsets of $E$ satisfying (OC1)-(OC4). But how can we go beyond this? There are a few essential properties that any definition should satisfy:

Every infinite oriented matroid should satisfy at least the axioms (OC1)-(OC4), though there could be additional restrictions
Infinite oriented matroids should be closed under both minors and duality
Natural examples such as finitary oriented matroids and infinite regular matroids (defined earlier in this series) should be included.

Unfortunately, there is no way to satisfy all of these requirements simultaneously. To understand why, we need to closely examine a particularly simple class of finitary orientable matroids. Suppose that we have any set $E$ of nonzero vectors in $\mathbb{R}^3$, such that no three of them lie in a common plane through the origin. Then the corresponding vector matroid $M(E)$ is simply the uniform matroid of rank 3 on $E$. Since this matroid is real representable, we can orient it in the way discussed earlier. This gives us a finitary oriented matroid.

What about its dual $M^*(E)$? That should be an orientation of the uniform matroid on $E$ of corank 3, whose circuits are all the sets of the form $E \setminus \{a,b\}$ with $a$ and $b$ distinct elements of $E$. To see how such a set should be oriented, consider the plane $H(a,b)$ through $a$, $b$ and the origin. We should partition the elements of $E \setminus \{a,b\}$ according to which side of this hyperplane they lie on. It isn’t hard to check that this signed set is orthogonal to every signed circuit, since no linear combination of points on the same side of the plane with all coefficients positive (or all negative) can ever evaluate to zero. So this must be the signing of $E \setminus \{a,b\}$ in the dual matroid.

Finally, let’s consider what the axiom (OC4) applied to $M^*(E)$ says about the set $E$. Suppose that we have two signed circuits $X$ and $Y$ of $M^*(E)$, orienting $E \setminus \{a,b\}$ and $E \setminus \{c,d\}$ respectively, and let $e$ be any element of $X^+ \cap Y^-$. Thus $e$ is different from $a$, $b$, $c$ and $d$. The signed circuit $Z$ given by (OC4) cannot contain $e$, so it must be a signing of $E \setminus \{e,f\}$ for some $f$. Furthermore, the region of $\mathbb{R}^3$ on the positive side of both $H(a,b)$ and $H(c,d)$ but on the negative side of $H(e,f)$ cannot meet $E$. If $E$ is finite then we have some wiggle room and we can always find a suitable choice of $f$ achieving this. But at the other end of the spectrum, if $E$ is dense in $\mathbb{R}^3$, this is a very strong condition. It forces $H(e,f)$ to contain the intersection of $H(a,b)$ and $H(c,d)$.

Putting all of this together, let’s fix a countable dense set $E$ of nonzero vectors in $\mathbb{R}^3$ such that no three of them lie on a common plane through the origin and there are no six of them $a,b,c,d,e,f$ such that $H(a,b)$, $H(c,d)$ and $H(e,f)$ all meet in a common line. It is straightforward to recursively build such a set. Then the dual to the natural orientation of $M(E)$ doesn’t satisfy (OC4). So there is no notion of infinite oriented matroid satisfying all three of the conditions above.

Where does this leave us? If we want to define infinite oriented matroids then we face a trilemma: we must give up on one of the three conditions.

Firstly, we could give up on the familiar circuit axioms. This is the approach taken by Wenzel in [2], as part of a larger project of defining infinite matroids over arbitrary fuzzy rings. Although it gives a very general and flexible definition in that context, in the particular case of oriented matroids we would lose many of the familiar properties and most of the theory of finite oriented matroids would have no analogue in this very general context.

Secondly, we could give up on duality but hope to preserve minors. From a matroid theoretic point of view, this would be a radical step, and it is hard to find an appropriate place to draw the line which is more useful than simply taking the union of the classes of finitary and regular matroids that we wanted to include. As an example of what can go wrong with this approach, those who remember the circuit axioms for infinite matroids might be tempted to work with signings of the circuits of infinite matroids satisfying (OC1)-(OC3) together with the following strengthened version of (OC4):

(OC4′) Suppose that $X \in \mathcal{C}$, $I \subseteq \underline X$ and $(Y_e)_{e \in I}$ is a family of elements of $\mathcal{C}$ such that $\underline Y_e \cap I = \{e\}$ and if $e$ is in $X^+$ then it is in $Y_e^-$ and if it is in $X^-$ then it is in $Y_e^+$. Then for every $f \in X^+ \setminus \bigcup_{e \in I} Y_e^-$ there is some $Z \in \mathcal{C}$ such that $f \in Z^+ \subseteq (X^+ \cup \bigcup_{e \in I} Y_e^+) \setminus I$ and $Z^- \subseteq (X^- \cup \bigcup_{e \in I} Y_e^-) \setminus I$

Unfortunately the class of such oriented matroids is not even closed under minors. Returning to our earlier counterexample, we can recursively extend our earlier set $E$ to a larger countable set $E’$ such that for any five distinct elements $a,b,c,d$ and $e$ of $E’$ there is a further element $f$ such that $H(a,b)$, $H(c,d)$ and $H(e,f)$ do intersect in a common line. So $M^*(E’)$ does satisfy (OC4), and it can even be shown to satisfy (OC4′). But its contraction minor $M^*(E)$ does not.

The final alternative is to give up on including all finitary oriented matroids. We could still hope to include all regular infinite matroids, since that class is already closed under duality and minors. The most promising option here involves the Farkas condition, which states that every element of $E$ must be contained in a positive circuit $X$ (one with $X^+ = \underline X$) or a positive cocircuit. Imposing this condition on the matroid and all its minors already forces (OC4′). However, this is a very restrictive definition, and for example it remains open whether it even includes all regular infinite matroids.

All of these issues and many more are explored in far more depth in our preprint [3]. Even though we didn’t find a satisfying definition of infinite oriented matroids, we ran into a number of subtle and interesting problems along the way, and the exploration was well worth the effort.

—

**References**

[1] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler, *Oriented Matroids*, Encyclopedia of Mathematics and its Applications, vol. 46, 2nd ed., Cambridge University Press, 1999.

[2] W. Wenzel, *Dual Pairs of Matroids with Coefficients in Finitary Fuzzy Rings of Arbitrary Rank*, Mathematica Pannonica **27/NS1** (2021), no. 1, 48-61.

[3] N. Bowler, W. Hochstättler, and S. Kaspar, *On the Possibilities of Defining Infinite Oriented Matroids*, preprint (2026), arXiv:2603.15843.

Representability over infinite fields

Posted on May 11, 2026 by Rutger Campbell

While a there have been remarkable techniques and discoveries for representability over finite fields (see [GGW14; W05] for a selection), not much has been said about representability over infinite fields — except perhaps how badly our existing techniques fail. This blogpost will cover some of these failures and some hopeful conjectures (or future pathologies).

We use $\mathcal{M}(\mathbb{F})$ to denote the matroids representable over a field $\mathbb{F}$.

Excluded minors

For finite fields, we of course have the following result announced by Geelen, Gerards, and Whittle:

Theorem (Geelen, Gerards, Whittle [GGW14]): For each finite field $\mathbb{F}$, there are finitely many excluded minors for $\mathcal{M}(\mathbb{F})$.

This has many useful consequences. For each finite field $\mathbb{F}$, there is a constant time certificate when a matroid is not $\mathbb{F}$-representable and there is a finite second-order logical sentence for $\mathbb{F}$-representability using a predicate for independence.

In contrast, Mayhew, Newman, and Whittle showed that [MNW09]:

Theorem (Mayhew, Newman, Whittle [MNW09]): For each infinite field $\mathbb{F}$, each element of $\mathcal{M}(\mathbb{F})$ is a minor of an excluded minor for $\mathcal{M}(\mathbb{F})$.

In essence, the set of excluded minors for $\mathcal{M}(\mathbb{F})$ is as wild as $\mathcal{M}(\mathbb{F})$ itself. When the set of excluded minors for a class $\mathcal{C}$ contain $\mathcal{C}$ in its downwards-closure like this, we say that $\mathcal{C}$ is swamped. Another way in which the set of excluded minors for a class can be seen as “worse” then the class itself is when they dominate in quantity on a given number of elements. Taking $e_n$ to be the number of non-isomorphic excluded minors for $\mathcal{C}$ on at most $n$ elements and $c_n$ to be the number of non-isomorphic members of $\mathcal{C}$ on at most $n$ elements, we say that $\mathcal{C}$ is fractal when $\lim_{n\to\infty}\frac{e_n}{c_n}=\infty$. Mayhew, Newman, and Whittle show that for any integer $k\geq 3$, the class $\mathcal{C}$ of sparse paving matroids with at most $k$ circuit-hyperplanes is fractal [MNW2]. However, they leave the following open:

Problem: For each infinite field $\mathbb{F}$, is the class $\mathcal{M}(\mathbb{F})$ is fractal?

One of the most significant recent results in matroid representability theory is due to Nelson:

Theorem (Nelson [N18]): For $n\geq 12$, there are at most $2^{n^3/4}$ representable matroids on ground set $[n]$.

Combining this with Knuth’s [K74] lower bound ($2^{2^n/\text{poly}(n)}$) on the number of matroids on $[n]$, it gives us that asymptotically almost all matroids are non-representable. Along with this result, Nelson also gave one of the most significant conjectures in matroid representation theory:

Conjecture: Taking $d(n)=(\lfloor\frac{n}{2}\rfloor-1)(\lceil\frac{n}{2}\rceil-1)$, we have the following:

Asymptotically almost all representable matroids on $[n]$ have rank in $\{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil\}$ and has exactly $d(n)-1$ nonbases.
Asymptotically almost all matroids on $[n]$ with rank in $\{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil\}$ and exactly $d(n)-1$ nonbases are representable.

The value $d(n)-1$, is the maximum number of non-bases that can exist without enforcing a non-trivial algebraic relation and by only having points placed “generically”.
The problem presented above is also interesting under the assumption that Nelson’s conjecture holds.

Natural Classes

Representability over any field is closed under minors and direct sums. However, a significant difference between finite and infinite fields is that with infinite fields we can place points in “general position”; matroid representability over an infinite field is closed under principal extension (i.e. freely placing an element into a flat). In general, we we say a class is natural, when it contains $U_{1,1}$ and is closed under the following: isomorphism, minors, direct sums, and principal extensions. It is the freedom of principal extension that seems to make natural classes wild. Besides, $\mathcal{M}(\mathbb{F})$ for $\mathbb{F}$ infinite, other natural classes include algebraic matroids over a given field, orientable matroids, and arbitrary intersections of natural classes. Also of particular note, is the class of Gammoids (matroids given by a linkage function in a directed graph), the smallest natural class. It is known that all of the above classes are swamped.

Problem: Are all proper natural classes swamped?

Problem: Are all proper natural classes fractal? Or are Gammoids swamped but not fractal?

Problem: Are asymptotically almost all representable matroids gammoids?

Efficient Discription

In fact it is open whether or not we have compact, efficient description of matroids representable over an infinite field:

Problem: For each representable matroid $M=(E,r)$, is there an algorithm $\mathcal{A}_M$ that computes $r(X)$ in time polynomial in $|E|$?

For example, it would be sufficient to show that each representable matroid $M=(E,r)$ is representable by a matrix whose entries are algebraic with minimal polynomials whose degrees and coefficients are bounded by a polynomial in $|E|$. However, the best known bound on the degree is $2^{2^{2|E|^2}}$ given by Bell, Funk, Kim, and Mayhew [BFKW20]. By Knuth’s [K74] lower bound ($2^{2^n/\text{poly}(n)}$) on the number of matroids, we cannot have a such an algorithms $\mathcal{A}_M$ for all (representable and non-representable) matroids, while Nelson’s [N18] upper bound $2^{n^3/4}$ leaves it open for representable matroids. Also note that with a positive resolution to Nelson’s conjecture, we would be able to resolve this problem for almost all representable matroids by simply using the size, rank, and nonbases to construct $\mathcal{A}_M.

I thank Geoff Whittle and Jim Geelen for helpful discussion on this post and Jorn van der Pol for a correction.

References

[BFKW20] J. Bell, D. Funk, B. D. Kim, D. Mayhew, Effective Versions of Two Theorems of RADO, Quarterly J. Math. 71 (2020), 599–618.
[GGW14] J. Geelen, B. Gerards, G. Whittle, Solving Rota’s conjecture, Notices Amer. Math. Soc. 61 (2014), 736–743.
[K74] D. Knuth, The asymptotic number of geometries, J. Combin. Theory. Ser. A 16 (1974), 398–400.
[MNW09] D. Mayhew, M. Newman, G. Whittle, On excluded minors for real representability, J. Combin. Theory Ser. B 99 (2009), 685–689.
[MNW21] D. Mayhew, M. Newman, G. Whittle, Fractal classes of matroids, Adv. in Appl. Math. 126 (2021), 101995.
[N18] P. Nelson, Almost all matroids are nonrepresentable, Bull. London Math. Soc. 50 (2018), 245-248.
[W05] G. Whittle, Recent work in matroid representation theory, Discrete Math. 302 (2005), 285–296.

Unimodular matrix representations for pseudo-orientable ribbon graphs

Posted on April 27, 2026 by Guest Contributor

This is a guest post by Donggyu Kim, who recently posted about the cycles of ribbon graphs. In this post, Donggyu introduces a generalisation of orientable ribbon graphs, pseudo-orientable ribbon graphs, based on recent work with Changxin Ding [2].

In my previous post, we saw that orientable ribbon graphs admit principally unimodular matrix representations. More precisely, for any orientable ribbon graph $\mathbb{G}$ and quasi-tree $X$, there exists a principally unimodular matrix $\mathbf{A}$ such that

$$\det(\mathbf{A}[Q \triangle X]) =\begin{cases}1 & \text{if $Q$ is a quasi-tree},\\0 & \text{otherwise},\end{cases}\qquad\qquad\tag{$*$}$$

where $Q\triangle X:= (Q\setminus X) \cup (X\setminus Q)$ denotes the symmetric difference of $Q$ and $X$, and $\mathbf{A}[Q \triangle X]$ is the principal submatrix of $\mathbf{A}$ indexed by $Q \triangle X$.

As noted in the previous post, the construction of such a matrix $\mathbf{A}$ relies heavily on the orientability of $\mathbb{G}$, and indeed it is not hard to find non-orientable ribbon graphs that do not admit such PU matrix representations.

Today, I will introduce a new class of ribbon graphs, called pseudo-orientable, which generalizes orientable ribbon graphs and admits PU matrix representations satisfying (*). For simplicity, we will restrict our attention to bouquets, that is, ribbon graphs with a single vertex. However, the results extend easily to general ribbon graphs by making use of the partial duality introduced by Chmutov [1]. We will also identify bouquets with signed chord diagrams; see Figure 1.

A bouquet (left) with three edges, where the edge $1$ is twisted/non-orientable (red) and the edges $2$ and $3$ are untwisted/orientable (blue). The corresponding signed chord diagram (right) is obtained by drawing chords on the boundary of the vertex and assigning signs (in this figure, the colors red and blue) to the chords according to the orientability of the corresponding edges.

Pseudo-orientability

Let’s begin by defining pseudo-orientable bouquets.

Definition. A bouquet $\mathbb{G}$ is pseudo-orientable if the boundary of the vertex admits two closed segments $S_1$ and $S_2$ such that

$S_1 \cap S_2$ is the set of two distinct points,
for each orientable edge, both of its ends lie in the interior of the same segment, either $S_1$ or $S_2$, and
for each non-orientable edge, one end lies in the interior of $S_1$ and the other end lies in the interior of $S_2$.

See Figure 2 (left) for an example of a pseudo-orientable bouquet.

The adjustment $\widehat{\mathbb{G}}$ of $\mathbb{G}$ at $(S_1,S_2)$ is the orientable bouquet obtained in the following way:

Cut the bouquet along $S_2$ and then reglue it with a half-twist. Note that all edges are orientable in the new bouquet.
Add a new orientable edge, denoted by $\widehat{e}$, connecting the two points in $S_1\cap S_2$.

Figure 2 (right) illustrates the resulting orientable bouquet $\widehat{\mathbb{G}}$.

The left figure is a pseudo-orientable bouquet $\mathbb{G}$, whose orientable edges are colored blue and non-orientable edges are colored red. A pair $(S_1,S_2)$ is indicated by dotted arrows. The right figure is the adjustment $\widehat{\mathbb{G}}$ of $\mathbb{G}$ at $(S_1,S_2)$, obtained by flipping the bottom segment $S_2$. The three blue-red dashed lines indicate orientable edges that were non-orientable in $\mathbb{G}$. The new edge $\widehat{e}$ is depicted as the blue dashed line. All edges in $\widehat{\mathbb{G}}$ are orientable.

Every orientable bouquet is pseudo-orientable, because we can get a pair $(S_1,S_2)$ by letting $S_1$ be a small boundary segment containing no ends of edges, and $S_2$ be the remaining boundary segment.

We also remark that the class of pseudo-orientable ribbon graphs is closed under taking ribbon graph minors.

PU matrix representations for pseudo-orientable bouquets

The Matrix–Quasi-tree Theorem for pseudo-orientable bouquets is as follows.

Theorem. Let $\mathbb{G}$ be a pseudo-orientable bouquet. Then there is an $E(\mathbb{G})$-by-$E(\mathbb{G})$ matrix $\mathbf{M}$ such that

$$\det(\mathbf{M}[Q])=\begin{cases}1 & \text{if $Q$ is a quasi-tree},\\0 & \text{otherwise}.\end{cases}$$

In particular, $\det(\mathbf{I} + \mathbf{M})$ is the number of quasi-trees of $\mathbb{G}$.

Remarkably, the matrix $\mathbf{M}$ is neither skew-symmetric nor symmetric in general, but can be expressed as the sum of a skew-symmetric matrix and a rank-one symmetric matrix. The theorem follows from two parallel stories on ribbon graphs and matrices, with delta-matroids underlying both.

For a subset $S$ of $[n]:=\{1,2,\ldots,n\}$, let

$$\widehat{S} :=\begin{cases}S & \text{if $|S|$ is even},\\S\cup\{n+1\} & \text{if $|S|$ is odd}.\end{cases}$$

Ribbon graphs. Let $\mathbb{G}$ be a pseudo-orientable bouquet, and let $\widehat{\mathbb{G}}$ be an adjustment of $\mathbb{G}$. We set $E(\mathbb{G}) = [n]$ and $\widehat{e} = n+1$. Then the following equivalence holds:

$$\text{$Q$ is a quasi-tree of $\mathbb{G}$} \iff \text{$\widehat{Q}$ is a quasi-tree of $\widehat{\mathbb{G}}$}.\tag{1}$$

Matrices. Let $\mathbf{A}$ be an $(n+1)$-by-$(n+1)$ PU skew-symmetric matrix representing $\widehat{\mathbb{G}}$. We can write it as

$$\mathbf{A} =\begin{pmatrix}\mathbf{A}’ & \mathbf{v}\\-\mathbf{v}^T & 0\end{pmatrix},$$

and let $\mathbf{M} := \mathbf{A}’ + \mathbf{v}\mathbf{v}^T$.

Then we have

$$\det(\mathbf{M}[Q])=\det(\mathbf{A}[\widehat{Q}])\tag{2}$$

for each $Q\subseteq [n]$.

By the property (*) of the matrix $\mathbf{A}$ representing $\widehat{\mathbb{G}}$ (with $X=\emptyset$) together with (1) and (2), we deduce the theorem.

Delta-matroids. Delta-matroids are already lurking in the two pictures above. Recall that a ribbon graph gives rise to a delta-matroid via its quasi-trees, and a (skew-)symmetric matrix gives rise to a delta-matroid via the index sets of nonsingular principal submatrices. Moreover, the delta-matroid associated with an orientable ribbon graph is even. What, then, can we say about the delta-matroid associated with a pseudo-orientable ribbon graph?

A delta-matroid $D$ is strong if it satisfies the simultaneous basis exchange property: for any bases $B,B’$ and $x\in B\triangle B’$, there is $y\in B\triangle B’$ such that $B\triangle\{x,y\}$ and $B’\triangle\{x,y\}$ are bases.

Every matroid, even delta-matroid, and ribbon-graphic delta-matroid is strong, but not every delta-matroid is. For example, the delta-matroid $([3],\{\emptyset,\{1\},\{2\},\{3\},\{1,2,3\}\})$ is not strong.

Murota [4] gave a concise relationship between strong and even delta-matroids, attributing it to Geelen:

Proposition. Let $D = ([n],\mathcal{B})$ be a set system. Then $D$ is a strong delta-matroid if and only if $\widehat{D} := ([n+1],\widehat{\mathcal{B}})$ is an even delta-matroid, where $\widehat{\mathcal{B}} := \{ \widehat{B} : B\in\mathcal{B} \}$.

Finally, pseudo-orientable ribbon graphs are precisely those ribbon graphs $\mathbb{G}$, up to ribbon graph $2$-isomorphism [3], for which $\widehat{D(\mathbb{G})}$ is ribbon-graphic — this characterization captures our original motivation for the study [2].

Acknowledgements

I thank Changxin Ding and Jorn van der Pol for helpful comments.

References

[1] Sergei Chmutov. Generalized duality for graphs on surfaces and the signed Bollobas–Riordan polynomial. J. Combin. Theory Ser. B 99(3):617–638, 2009. doi:10.1016/j.jctb.2008.09.007
[2] Changxin Ding and Donggyu Kim. Pseudo-orientable ribbon graphs: Matrix–Quasi-tree theorem and log-concavity, 2026. arXiv preprint.
[3] Iain Moffatt and Jeaseong Oh. A 2-isomorphism theorem for delta-matroids. Adv. in Appl. Math. 126, Paper No. 102133, 2021. doi:10.1016/j.aam.2020.102133
[4] Kazuo Murota. A note on M-convex functions on jump-systems. Discrete Appl. Math. 289:492–502, 2021. doi:10.1016/j.dam.2020.09.019

Packing versus covering binary matroid minors

Posted on April 6, 2026 by Rose McCarty

Many different areas of combinatorics and optimization are interested in objects that admit a rough duality between packing and covering. A classic example is that every bipartite graph either has a matching of size $k$, or has a set of at most $k-1$ vertices which “hit” every edge (i.e. a vertex cover of size $k$; this is Kőnig’s theorem).

Another example where only a rough duality is possible was proven by Erdős and Pósa. They showed that every graph either has $k$ cycles that are pairwise vertex-disjoint, or has a set of $\mathcal{O}(k \log{k})$ many vertices which hit every cycle (i.e. a set of vertices whose deletion yields a forest). Note that this is not an exclusive “or”; some graphs have both. But any graph with a hitting set of size $r$ has at most $r$ pairwise vertex-disjoint cycles.

In general, for any problem which is suitable to study within this framework, the maximum size of a packing should be at most the minimum size of a covering (or at least roughly so). This is typically the easy direction (I would love to hear in the comments about any natural examples where it is not the easy direction!). If the other direction is also (roughly) satisfied, then the set of objects is said to have the Erdős-Pósa property, meaning that if there is no packing of size $k$, then there is a covering of size at most $f(k)$, for some function $f$.

Binary Matroids

For binary matroids there is a somewhat different notion of covering. It is convenient to think of a graph with a “small vertex cover” as being “close to” a graph whose largest packing has size zero. So instead of deleting a small set of vertices, we add a low-rank matrix. Formally, consider a binary matroid $M$ which is represented by the columns of an $n \times m$ binary matrix $A$. A rank-$k$ perturbation of $M$ is then any matroid $M’$ which can be represented by the columns of $A+B$, where $B$ is an $n \times m$ binary matrix of rank at most $k$. We perform addition over the binary field.

Campbell, Gollin, Hatzel, Kwon, Oum, Wiederrecht, and I proved the following theorem. Given a graph $H$, we write $M(H)$ for its cycle matroid.

Theorem
For any planar graph $H$, there is a function $f_H$ so that for every integer $k$, every binary matroid either has the cycle matroid of $k$ vertex-disjoint copies of $H$ as a minor, or has a rank-$f_H(k)$ perturbation which does not have $M(H)$ as a minor.

This really is an Erdős-Pósa property in the sense that it gives a rough min-max theorem for packing $M(H)$ minors. When $H$ is a cycle and the matroid is graphic, one should roughly think of the theorem as saying the following. Note that this is a conjecture; it does NOT just follow from our theorem. This is because, informally, our perturbations are allowed to leave the graphic world, and the ones below are not.

Conjecture
There exists a function $f$ so that for any integer $k$, every multigraph either 1) has a minor with $k$ different blocks, each of which is a cycle, or 2) can be turned into a forest by performing the following operations at most $f(k)$ times:

identify two vertices $u$ and $v$ into a single vertex. This operation does not change the number of edges. So for instance if $u$ and $v$ were adjacent originally, there will be a loop at the new vertex after identification.
split a vertex $v$ into two vertices $v_1$ and $v_2$. This operation is the opposite of identification.

Thank you to Mathieu Rundström for correcting the previous wrong version of the conjecture!

The Matroid Union

A blog for and by the matroid community