Back in 1966, Rado\u00a0[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.<\/p>\n
What we did know was graphs. In particular, infinite graphs\u00a0[5]. And these were luring us – towards matroids.<\/p>\n
It had all begun with a dream, many years earlier.\u00a0As an undergraduate studying with Halin, I had heard of the ends<\/span> of an infinite graph:\u00a0limit points at\u00a0infinity such as the three red dots in this graph:<\/p>\n 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\u00a0<\/span>is taken to be an equivalence class of rays<\/span>, 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.<\/p>\n 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\u2019 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\u2019 as incidence. What fun!<\/p>\n But when I tried this in earnest several years\u00a0later, with my student Daniela K\u00fchn, we soon got bogged down. It\u00a0turned out that infinite cycles such as the above did not always Then for the same reasons we had to iterate again,\u00a0iterate transfinitely\u00a0\u2013 and ultimately failed. The end of the\u00a0story\u00a0[4] was that topology, of all things, came to the rescue. And now matroids began to call. One of the finite graph theorems that wouldn\u2019t 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\u2019t 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?<\/p>\n The usual matroid axioms, together with<\/p>\n (I4) An infinite set is independent as soon as all\u00a0its finite subsets are independent<\/p>\n as known from vector spaces, do not cover such\u00a0matroids: a circuit, with all its proper subsets independent,\u00a0can obviously not be infinite. So we looked for new axioms:\u00a0axioms for infinite matroids that would default to the known\u00a0finite ones for finite structures, but which would also allow\u00a0for infinite circuits such as those topological ones.<\/p>\n It was fun trying\u00a0\u2013 slowly, experimenting as much as\u00a0thinking, and unaware that others had tried before us.\u00a0Eventually, we came up with five sets of infinite matroid\u00a0axioms\u00a0[2]\u00a0\u2013 in terms of independent sets, bases, circuits,\u00a0closure and rank\u00a0\u2013 that worked in the way I had hoped: they made\u00a0the edge sets of topological circles of a locally finite\u00a0infinite graph into the circuits of a matroid, and our\u00a0topological spanning trees into the bases of that matroid. (In\u00a0due course, even a base packing theorem emerged that implied our\u00a0topological tree packing theorem, as hoped for\u00a0[1]. But that was\u00a0much later.) Thus, for an infinite graph there were now two\u00a0different cycle matroids: one whose circuits were the finite\u00a0cycles, and another whose circuits were the edge sets of\u00a0topological circles, finite or infinite. And each of these had a\u00a0dual: the cocircuits of the first were all the bonds (finite or\u00a0infinite), those of the latter precisely the finite bonds [3].<\/p>\n In particular: it turned out, with hindsight, that\u00a0those `infinite cycles\u2019 which had given us such pain to find,\u00a0and which we were able to nail down only with the help of\u00a0topology, had a combinatorial description after all: as the\u00a0minimal non-empty sets of edges not meeting any finite bond in\u00a0just a single edge. It was thus the matroids lurking in the\u00a0background which\u00a0\u2013 once found\u00a0\u2013 provided that much-sought\u00a0combinatorial description of infinite cycles that would make\u00a0theorems about cycles in finite graphs generalize to infinite\u00a0graphs!<\/p>\n To top it all, it turned out that we had solved that\u00a0ancient problem of Rado’s. Or more precisely: that we discovered\u00a0that Higgs and Oxley had solved it long before us. But this is a\u00a0story for a later blog, in which we shall look at the infinite\u00a0axioms more explicitly and give more concrete examples of\u00a0infinite matroids.<\/p>\n To wind up this one, let me say a little about that\u00a0traditional axiom (I4): why it was a natural one to suggest at\u00a0the time matroids were invented, but also why it is\u00a0\u2013 from a\u00a0modern perspective\u00a0\u2013 a somewhat simple-minded one.<\/p>\n Axiom (I4) makes independence into a property of an\u00a0infinite combinatorial structure that depends only on its finite\u00a0substructures. Such properties can typically be verified by an\u00a0application of Zorn\u2019s Lemma, or by a so-called compactness\u00a0<\/span>argument: one that uses the compactness of an infinite product\u00a0of compact spaces, typically finite, as proved by Tychonoff in\u00a0the 1930s. Compactness was en vogue at the time and emerged in\u00a0various guises, and so it must have been natural then to specify\u00a0the infinite independent sets of a matroid as determined by the\u00a0finite ones as in\u00a0(I4).<\/p>\n But let\u2019s look at this problem again now, even put\u00a0in this way: given<\/span> the collection of\u00a0finite subsets of some given set that we wish to call\u00a0independent, which infinite subsets should we grant the same\u00a0status?<\/p>\n Axiom (I4) gives a straightforward answer: take them\u00a0all. All, that is, that have a chance of complying with that\u00a0other intended axiom, that subsets of independent sets shall be\u00a0independent. And Rado, one of the champions of compactness and\u00a0other equivalents of the axiom of choice, saw that this was too\u00a0crude: in order for infinite matroids to allow for duality as we\u00a0know it from finite ones, we have to choose as the infinite\u00a0independent sets a carefully balanced subclass of all those\u00a0allowed by\u00a0(I4). To find this subclass, and to describe it by\u00a0axioms both subtle and simple enough to yield an interesting\u00a0theory of infinite matroids with duality, was his 1966\u00a0challenge.<\/p>\n It now seems that we are finally there. With those\u00a0newly found axioms, infinite matroid theory can at last be\u00a0developed in line with its finite counterpart that has raced so\u00a0successfully ahead. The train is already gaining momentum,\u00a0inviting you to jump on\u00a0\u2013\u00a0but this, too, will be a story for\u00a0later posts.<\/p>\n [1] E. Aigner-Horev, J.-O. Fr\u00f6hlich and J. Carmesin,\u00a0Infinite matroid union,\u00a0arXiv:1111.0602<\/a>.<\/p>\n [2] H. Bruhn, R. Diestel, M. Kriesell, R. Pendavingh\u00a0and P. Wollan, Axioms\u00a0for infinite matroids<\/a>, Adv. Math 239 (2013), 18\u201346.<\/p>\n [3] H. Bruhn and R. Diestel, Infinite matroids in\u00a0graphs<\/a>, in the Infinite Graph Theory\u00a0<\/span>special volume of Discrete Math. 311 (2011), 1461\u20131471.<\/p>\n [4] R. Diestel, The\u00a0cycle space of an infinite graph<\/a>, Comb. Probab. Computing\u00a014 (2005), 59\u201379.<\/p>\n [5] R. Diestel, Locally\u00a0finite graphs with ends: a topological approach I\u2013II<\/a>I,\u00a0Discrete Math 311\u2013312 (2010\u201311).<\/p>\n [6] R. Rado, Abstract linear dependence, Colloq.\u00a0Math. 14 (1966), 257\u201364.<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading ![\"ThreeCycleRedDots\"](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2014\/10\/ThreeCycleRedDots.png\")
<\/a><\/p>\n
\nwork: we had to iterate to allow cycles like<\/p>\n<\/a><\/p>\n
\nEven for graphs with abstract ends, not necessarily planar,\u00a0there is a natural topology in which rays converge to `their\u2019\u00a0ends. And it was the edge sets of circles in this topology that\u00a0turned out to be the right notion of infinite cycle in locally\u00a0finite infinite graphs, in the sense of allowing us to\u00a0generalize those finite graph theorems. But these circles could\u00a0be wild: containing infinitely many double rays arranged like\u00a0the rationals, and continuum many ends!\u00a0The perimiter circle of the planar graph below is an example:<\/p>\n<\/a><\/p>\n