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.

Although this post is part of the ongoing series on infinite matroids, it begins with an old result about graphs. Suppose that you have a graph $G$, and you want to know whether you can partition it into an edge-disjoint union of cycles. If $G$ is finite then there is a straightforward necessary and sufficient condition for this; every vertex of $G$ should have even degree. Necessity is obvious, and to see sufficiency note that as long as $G$ has any edges it cannot be a tree so it must contain some cycle; after deleting the edges of that cycle, every vertex still has even degree and so we can keep doing the same again until we have exhausted all the edges of the graph. 

What if $G$ is infinite? In that case it is no longer sufficient that all degrees are even. Indeed, consider the two-way infinite ray; every vertex has degree 2, but there isn’t even a single cycle. So we need a stronger condition. Rather than considering individual vertices, we should consider cuts. Since any cycle meets any cut in an even number of edges, if $G$ is an edge-disjoint union of cycles then every cut of $G$ must be a disjoint union of finite sets of even size, so must itself be even or infinite. In 1960, Nash-Williams showed that this condition is sufficient [3].

Theorem 1: Let $G$ be any graph. Then $G$ is an edge-disjoint union of cycles if and only if $G$ has no finite cuts of odd size.

In this post we will examine various generalisations of this result, as well as some of the basic ideas used to prove them, and we will finish up by looking at some intriguing open problems which remain. However, we will not look at Nash-Williams’ original proof, since that was long and technical, and over the years more efficient proofs have emerged (see for example [4],[5]).

Roughly speaking, the modern proofs work in the following way. We want to prove the result by induction on the cardinality of $G$. As the base case, we suppose that $G$ is countable. In this case, we can use an argument like the one above to recursively pick a sequence of edge-disjoint cycles $C_1, C_2,\ldots$ covering all edges of $G$.

For the induction step, we want to break $G$ up into strictly smaller edge-disjoint subgraphs of smaller cardinality, which we will use to cover larger and larger chunks of $G$. We will make sure that each of these subgraphs $H$ has the following properties:

1. Any finite cut of $H$ is also a cut of $G$
2. Any finite cut of $G – E(H)$ is also a cut of $G$

The first of these properties is obviously useful, since it ensures in particular that $H$ has no finite odd cuts, so that we can apply the induction hypothesis to it. It is also easy to extend any infinite subgraph $X$ of $G$ to a subgraph $H$ of the same cardinality satisfying (1), by repeatedly taking each finite cut of $X$ which isn’t a cut of $G$ and either adding all edges of the corresponding cut of $G$ (if that cut is finite) or infinitely many edges of the corresponding cut of $G$ (if that cut is infinite). So by closing under this operation we can easily extend any subgraph of $G$ to one satisfying (1).

The second property is used in a recursive construction of our partition of $G$ into subgraphs, to ensure that after we have taken $H$ as a partition class we still have no odd-sized cuts in the remainder and so we can continue finding more partition classes in the same way. Rather surprisingly, there is another operation, akin to that in the previous paragraph but more technical, such that by closing under that operation we can turn any subgraph of $G$ into another of the same cardinality satisfying (2). Even more surprisingly, the exact details of that operation need not be specified for the proof. 

Why not? There is a very useful trick, often applicable in such situations, called the Elementary Submodel Method. It allows us to define a kind of universal closure operation, which when applied to a subgraph closes it under almost anything we might have wanted. That seems miraculous. How could it possibly work? The idea is to make use of a result from logic called the Löwenheim-Skolem Theorem, which states that if we have some theory expressed using first-order logic, some model $M$ of that theory and some infinite subset $X$ of $M$ then we can find a submodel $N$ of $M$ including $X$ and of the same cardinality as $X$, such that any first order statement which holds (in $N$) for some elements of $N$ still holds for those same elements in $M$. $N$ is then called an elementary submodel of $M$. 

A first idea about how to apply this might be to take $M$ to be the graph $G$, considered as a model of the theory of graphs, and define $H$ to be the subgraph corresponding to $N$. Then for any construction we can express in the language of graphs, $H$ will be closed as a subgraph of $G$ under that construction. This is already fairly powerful, but unfortunately the operations under which we want to close subgraphs are often too complicated to be expressible using first-order logic in the language of graphs. So we need a more powerful idea.

What we do instead is to take $M$ to be the whole set-theoretic mathematical universe (considered as a model of the axioms of set theory). Given an infinite subgraph $X$ of $G$ we can now find an elementary submodel $N$ of $M$ including $X$ and containing $G$. If we define $H$ to be the intersection of $N$ with $G$ then it will really be closed under any operation we might think of. Any readers who are logicians might now be worried about whether it is really ok to step outside the set-theoretic universe and treat that whole universe as a mathematical object in this way. Would it then be contained in itself? This is a valid worry, but it can be circumvented by instead taking $M$ to be a large enough fragment of the set-theoretic universe, rather than the whole thing. 

For those reading about the Elementary Submodel Method for the first time, I understand that it can be a little mind-blowing the first time you see it. I remember that it took me a while to wrap my head around it. For the purposes of this post, all you need to remember is that it gives you a kind of universal closure operation, which (with a little more work) lets us push through the proof outlined above.

However, if at some point in life you find yourself working with some recursive construction where you would like to close some infinite graphs (or indeed matroids) under some very technical operations, and perhaps it isn’t easy to see exactly what those operations should be, do consider whether the Elementary Submodel Method might be a helpful tool for you. A good introduction can be found in [4].

What we want to focus on for now is how the same method allows us to extend Nash-Williams’ results to infinite matroids. The obvious question to ask is when we can express the ground set of a matroid as a disjoint union of circuits. In the discussion above, we relied on the fact that every cycle in a graph meets every cut in an even number of edges. The corresponding property in the language of matroids would be that every circuit-cocircuit intersection is even, or to put it another way, that the matroids we are working with are binary. And indeed we do get a corresponding result for infinite binary matroids, with a very similar proof:

Theorem 2: Let $M$ be a finitary binary matroid such that no finite cocircuit of $M$ has odd size. Then the ground set of $M$ is a disjoint union of circuits.

Note that this theorem is only for finitary matroids, which means that all circuits are finite, not for infinite matroids in general. We will return to this point later. However, it turns out that the theorem above can be generalised slightly beyond binary matroids. It turns out that what we need to do is to make precise exactly what it is that is used about circuits in binary matroids for the base case of an argument of the kind outlined above. 

Remember that the base case was that in which $M$ is countable. Our plan there was to recursively define a sequence of disjoint circuits $C_1, C_2, \ldots$ covering the ground set. To define $C_n$, we need that even after we have deleted the circuits $C_1, \ldots, C_{n-1}$ there is still at least one more circuit to choose as $C_n$. To ensure that we ultimately cover the whole ground set, we also need that we can choose this new circuit to contain our favourite edge $e$ of $M$. We can formalise all of this as follows:

Definition: A matroid $M$ is finite matching extendable if for any finite list $C_1, \ldots C_{n-1}$ of disjoint circuits of $M$ and any edge $e$ of $M$ not in any $C_i$ there is some circuit $C_n$ of $M$ containing $e$ and disjoint from all the other $C_i$.

So what we are using to prove the base case in our argument for finitary binary matroids is the fact that they are finite matching extendable. Komjáth, Milner and Polat showed [2] that this property also suffices for the general case.

Theorem 3: Let $M$ be any finitary matroid which is finite matching extendable. Then the ground set of $M$ is a disjoint union of circuits.

Once again, Komjáth, Milner and Polat’s proof was tricky and technical. However, using the Elementary Submodel Method, Attila Joó and I were able to give a much shorter alternative proof. 

Instead of generalising Theorem 1 to matroids, a natural question to ask is what happens for directed graphs. More precisely, a natural question to ask in this context is which directed graphs can be expressed as a disjoint union of directed cycles. After a little thought, it is clear that the following statement is the analog of Theorem 1 for directed graphs:

Theorem 4: Let $D$ be any directed graph such that every for every cut $K$ of $D$ the sets of edges crossing $K$ in each direction have the same cardinality. Then $D$ is a disjoint union of directed cycles. 

The history of this statement is a little peculiar. After proving Theorem 1 in 1960, Nash-Williams claimed that his methods could also be extended to give Theorem 4. However, he did not explain how to do so, and over the decades nobody else was able to reconstruct such a proof. Finally, in 2017 Thomassen gave Theorem 4 as a conjecture in [5], and a few years later this conjecture was finally proved by Attila Joó [1] using the Elementary Submodel Method.

Since we could generalise Theorem 1 to matroids, it is natural to ask whether we can also generalise Theorem 4 to matroids. And indeed we can, namely to regular matroids. To understand the statement, we need to understand what the analog of a directed cycle in a regular matroid might be. A quick way to express the concept we need is by using an alternative characterisation of regular matroids due to White [6].

Definition: A signing of a matroid $M$ consists of a choice, for each circuit $C$ of $M$, of a function $f_C \colon C \to \{-1, 1\}$ and a choice, for each cocircuit $D$ of $M$, of a function $g_D \colon D \to \{-1, 1\}$, such that for any circuit $C$ and cocircuit $D$ we have $$\sum_{e \in C \cap D} f_C(e)g_D(e) = 0\,.$$ A signed matroid is a matroid together with a signing of that matroid.

Fact: A matroid $M$ is regular if and only if it has a signing.

For example we can find a signing of the matroid associated to any graph $G$ by directing the edges of $G$ arbitrarily, defining each $f_C$ to be 1 on the edges directed in one sense around $C$ and -1 for the edges directed in the opposite sense, and defining each $g_D$ to be 1 on the edges crosssing $D$ in one direction and -1 on the edges crossing $D$ in the opposite direction. The desired equation holds since each cycle crosses each cut the same number of times in each direction.

In this context, it is clear what the analog of a directed cycle should be. We say that a circuit $C$ (or cocircuit $D$) of a signed matroid is directed if $f_C$ (or $g_D$) is constant. Attila and I were able to extend Theorem 4 to regular matroids as follows:

Theorem 5: Let $M$ be a finitary signed matroid such that for any cocircuit $D$ of $M$ the sets $g_D^{-1}(-1)$ and $g_D^{-1}(1)$ have the same cardinality. Then the ground set of $M$ is a disjoint union of directed circuits. 

All of the matroidal statements we have considered here were for finitary matroids. The reason for this, however, is not that they are known to be false for infinitary matroids. Indeed, there are no known counterexamples even for general infinite matroids. I would be very interested in any ideas for how to prove or refute the corresponding statements for arbitrary infinite matroids.

However there is an even more basic statement from which the countable case of Theorem 5 quickly follows, which is also open for general infinite matroids. It is an analog of the Farkas Lemma for signed matroids. It would probably be needed for any proof of Theorem 5 for general infinite matroids. So I would be extremely interested in any ideas on how to approach this problem.

Conjecture: Let $M$ be a (possibly infinite) signed matroid and $e$ an edge of $M$. Then $e$ is either contained in a directed circuit or a directed cocircuit. 

References: