Infinite matroids

Guest post by Reinhard Diestel.

This is the first of what might become an irregular series of posts on infinite matroids, written on the invitation of Irene Pivotto for the Union. This first piece tells the story of how finite matroids and infinite graphs conspired to get us to think about how to axiomatize infinite matroids. How we ended up solving an old problem we had not even known about – and how it came to be that infinite matroid theory is suddenly exploding. It is meant to be light reading, with some deeper hints to ponder. Future posts, to be written by Nathan Bowler, are likely to be more mathematical and less anecdotal, as they follow up the various open ends of the emerging theory.

Back in 1966, Rado [6] asked whether there was a way to axiomatize matroids in such a way that infinite matroids, too, would have duals. A big challenge, given what was known. But we knew none of this.

What we did know was graphs. In particular, infinite graphs [5]. And these were luring us – towards matroids.

It had all begun with a dream, many years earlier. As an undergraduate studying with Halin, I had heard of the ends of an infinite graph: limit points at infinity such as the three red dots in this graph:

ThreeCycleRedDots

There is a combinatorial definition of ends that divorces the notion of convergence appealed to in this example from the topology of the plane: an end is taken to be an equivalence class of rays, that is, 1-way infinite paths, where two rays are considered as equivalent if no finite set of vertices separates them. As is easy to check, the graph above has three such classes each of which corresponds to one of the red dots, in that its rays converge to that dot in the plane.

Now here was my dream, inspired by this picture. There are a number of theorems about cycles in finite graphs that do not readily generalize to infinite graphs; Hamilton cycles are an obvious example. Might `infinite cycles’ such as the perimeter circle of the above graph come to the rescue and give us infinite analogues of finite cycle theorems? In our example, the perimeter circle would be an infinite Hamilton cycle. And the formal definition of an infinite cycle would be: a cyclic sequence of alternately double rays and ends, with `is an element of’ as incidence. What fun!

But when I tried this in earnest several years later, with my student Daniela Kühn, we soon got bogged down. It turned out that infinite cycles such as the above did not always
work: we had to iterate to allow cycles like

iterated

Then for the same reasons we had to iterate again, iterate transfinitely – and ultimately failed. The end of the story [4] was that topology, of all things, came to the rescue.
Even for graphs with abstract ends, not necessarily planar, there is a natural topology in which rays converge to `their’ ends. And it was the edge sets of circles in this topology that turned out to be the right notion of infinite cycle in locally finite infinite graphs, in the sense of allowing us to generalize those finite graph theorems. But these circles could be wild: containing infinitely many double rays arranged like the rationals, and continuum many ends! The perimiter circle of the planar graph below is an example:

WildCircle

And now matroids began to call. One of the finite graph theorems that wouldn’t generalize to infinite graphs naively was the tree packing theorem of Nash-Williams and Tutte. But we were able to prove an infinite tree packing theorem for the naturally adapted topological notion of tree: a set of edges that connects all the vertices but whose topological closure does not contain a circle. Shouldn’t there be a notion of infinite matroid hiding behind this, one in which these topological trees would be the bases, and edge sets of topological circles the circuits?

The usual matroid axioms, together with

(I4) An infinite set is independent as soon as all its finite subsets are independent

as known from vector spaces, do not cover such matroids: a circuit, with all its proper subsets independent, can obviously not be infinite. So we looked for new axioms: axioms for infinite matroids that would default to the known finite ones for finite structures, but which would also allow for infinite circuits such as those topological ones.

It was fun trying – slowly, experimenting as much as thinking, and unaware that others had tried before us. Eventually, we came up with five sets of infinite matroid axioms [2] – in terms of independent sets, bases, circuits, closure and rank – that worked in the way I had hoped: they made the edge sets of topological circles of a locally finite infinite graph into the circuits of a matroid, and our topological spanning trees into the bases of that matroid. (In due course, even a base packing theorem emerged that implied our topological tree packing theorem, as hoped for [1]. But that was much later.) Thus, for an infinite graph there were now two different cycle matroids: one whose circuits were the finite cycles, and another whose circuits were the edge sets of topological circles, finite or infinite. And each of these had a dual: the cocircuits of the first were all the bonds (finite or infinite), those of the latter precisely the finite bonds [3].

In particular: it turned out, with hindsight, that those `infinite cycles’ which had given us such pain to find, and which we were able to nail down only with the help of topology, had a combinatorial description after all: as the minimal non-empty sets of edges not meeting any finite bond in just a single edge. It was thus the matroids lurking in the background which – once found – provided that much-sought combinatorial description of infinite cycles that would make theorems about cycles in finite graphs generalize to infinite graphs!

To top it all, it turned out that we had solved that ancient problem of Rado’s. Or more precisely: that we discovered that Higgs and Oxley had solved it long before us. But this is a story for a later blog, in which we shall look at the infinite axioms more explicitly and give more concrete examples of infinite matroids.

To wind up this one, let me say a little about that traditional axiom (I4): why it was a natural one to suggest at the time matroids were invented, but also why it is – from a modern perspective – a somewhat simple-minded one.

Axiom (I4) makes independence into a property of an infinite combinatorial structure that depends only on its finite substructures. Such properties can typically be verified by an application of Zorn’s Lemma, or by a so-called compactness argument: one that uses the compactness of an infinite product of compact spaces, typically finite, as proved by Tychonoff in the 1930s. Compactness was en vogue at the time and emerged in various guises, and so it must have been natural then to specify the infinite independent sets of a matroid as determined by the finite ones as in (I4).

But let’s look at this problem again now, even put in this way: given the collection of finite subsets of some given set that we wish to call independent, which infinite subsets should we grant the same status?

Axiom (I4) gives a straightforward answer: take them all. All, that is, that have a chance of complying with that other intended axiom, that subsets of independent sets shall be independent. And Rado, one of the champions of compactness and other equivalents of the axiom of choice, saw that this was too crude: in order for infinite matroids to allow for duality as we know it from finite ones, we have to choose as the infinite independent sets a carefully balanced subclass of all those allowed by (I4). To find this subclass, and to describe it by axioms both subtle and simple enough to yield an interesting theory of infinite matroids with duality, was his 1966 challenge.

It now seems that we are finally there. With those newly found axioms, infinite matroid theory can at last be developed in line with its finite counterpart that has raced so successfully ahead. The train is already gaining momentum, inviting you to jump on – but this, too, will be a story for later posts.

[1] E. Aigner-Horev, J.-O. Fröhlich and J. Carmesin, Infinite matroid union, arXiv:1111.0602.

[2] H. Bruhn, R. Diestel, M. Kriesell, R. Pendavingh and P. Wollan, Axioms for infinite matroids, Adv. Math 239 (2013), 18–46.

[3] H. Bruhn and R. Diestel, Infinite matroids in graphs, in the Infinite Graph Theory special volume of Discrete Math. 311 (2011), 1461–1471.

[4] R. Diestel, The cycle space of an infinite graph, Comb. Probab. Computing 14 (2005), 59–79.

[5] R. Diestel, Locally finite graphs with ends: a topological approach I–III, Discrete Math 311–312 (2010–11).

[6] R. Rado, Abstract linear dependence, Colloq. Math. 14 (1966), 257–64.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.