Matroid - Infinite Matroids

Infinite Matroids

The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. For a long time, one of the difficulties has been that there were many reasonable and useful definitions, none of which appeared to capture all the important aspects of finite matroid theory. For instance, it seemed to be hard to have bases, circuits, and duality together in one notion of infinite matroids.

The simplest definition of an infinite matroid is to require finite rank; that is, the rank of E is finite. This theory is similar to that of finite matroids except for the failure of duality due to the fact that the dual of an infinite matroid of finite rank does not have finite rank. Finite-rank matroids include any subsets of finite-dimensional vector spaces and of field extensions of finite transcendence degree.

The next simplest infinite generalization is finitary matroids. A matroid is finitary if it has the property that

Equivalently, every dependent set contains a finite dependent set. Examples are linear dependence of arbitrary subsets of infinite-dimensional vector spaces (but not infinite dependencies as in Hilbert and Banach spaces), and algebraic dependence in arbitrary subsets of field extensions of possibly infinite transcendence degree. Again, the class of finitary matroid is not self-dual, because the dual of a finitary matroid is not finitary. Finitary infinite matroids are studied in model theory, a branch of mathematical logic with strong ties to algebra.

In the late 1960s matroid theorists asked for a more general notion that shares the different aspects of finite matroids and generalizes their duality. Many notions of infinite matroids were defined in response to this challenge, but the question remained open. One of the approaches examined by D.A. Higgs became known as B-matroids and was studied by Higgs, Oxley and others in the 1960s and 1970s. According to a recent result by Bruhn, Diestel, Kriesell, Pendavingh and Wollan (2010), it solves the problem: Arriving at the same notion independently, they provided four different systems of axioms – in terms of independence, bases, circuits, closure and rank. The duality of B-matroids generalizes dualities that can be observed in infinite graphs.