Bases in Infinite Matroids

We consider bases in matroids of infinite rank, and prove: (a) the existence of a perfect matching in the 'transition graph' of any two bases. This is an extension of the existence of a non-zero generalized diagonal in the transition matrix between bases in finite dimensional linear spaces, and settles a conjecture of the second author [8]. (b) A Cantor-Bernstein theorem for matroids. (c) The existence of a winning strategy for the 'good guy' in an exchange game between bases in infinite matroids. 1. Preliminaries A matroid is a pair Jt = (S,«/), where J is a non-empty family of subsets of S satisfying: (a) /e |/| then /u {x}eJ for some xeJ\I, and (c) if all finite subsets of/belong to , / then IEJ (that is, M is offinite character). When S is infinite such structures are also called independence spaces [12]. By (c) and Zorn's lemma, J has elements which are maximal with respect to containment, and these are called bases for M. The subsets of S which belong to . / are called independent and those which do not belong to J are said to be dependent. A minimal dependent set is called a circuit. The following is well known (see, for example, [12]). LEMMA 1.1. If B is a basis and x^B then there exists a unique subset D of B such that D U {x} is a circuit. For B, x, D as in the lemma we write D = sB(x) (the s stands for ' support'—think of the case of linear spaces). We extend this definition by writing sB(x) = {x} for x e B. For a subset T of S we let sp (T) = T U {x e S: IU {*} i J for some independent subset / of T). If sp(r) = S we say that T is spanning (for Ji). The following lemma, which will be basic in our arguments, follows easily from axioms (a), (b) and (c). LEMMA 1.2. Ifle J, X is a finite subset ofI,Y^S and \ Y\ < \X\ then (I\X) U Y is not spanning. It is not too difficult to prove the lemma also for X infinite, which yields as a corollary that all bases have the same cardinality. Since this version of the lemma will not be used, we leave its proof to the interested reader. Received 2 May 1989. 1991 Mathematics Subject Classification 05B35. Research supported by the CNRS and the PRC Math-Info. J. London Math. Soc. (2) 44 (1991) 385-392