A homotopy theorem for matroids. I
W. T. Tutte · Transactions of the American Mathematical Society · 1958
By a matroid on a finite set M we understand a class M of non-null subsets of 717 which satisfies the following axioms.Axiom I. TVa member of M contains another as a proper subset.Axiom II.If (X, Y)<EM, a<EXC\Y and b<EX-(XC\Y), then there exists Z<EM such that b<EZcz(XKJY) -{a}.Such systems were introduced by Hassler Whitney [l].As an example let L he any class of subsets of 717 forming a group under mod 2 addition, and let M be the class of all minimal non-null members of L. Then it is easily verified that L satisfies Axiom II and that each non-null member of L is a sum of non-null members of M. It follows that Msatisfies both axioms and is thus a matroid.Such a matroid we call binary.In particular M may be the set of edges of a finite graph G and L may be the class of 1-cycles mod 2 of G. Then it is found that the members of M are those sets of edges of G which define circuits.In this case we call M the circuit-matroid of G. Given a matroid M let 0 be the class of all unions of members of M. Then each element of Q is a subset of 717.We partition 0 into disjoint classes 0_i, Qo, Qi, Qi, • • • according to the following rules.(i) The null subset 0 of 717, considered as an empty union, is the only member of 0_i.(ii) When Qr has been determined for -ISrSkwe define Qk+i as the class of all minimal members of k Pk= 0 -U Qr. r=-lThat is Qk+i consists of all members of Pk which have no other members of Pk as a subset.The members of 0 are the flats of M. Those belonging to Qd are the flats of dimension d, or d-flats.At the end of §2 of this paper we interpret the dimensions of the flats of a circuit-matroid in terms of graph theory.We shall see that the flats of a matroid M on a set M have some properties resembling those of the elements of a projective geometry.Because of this analogy we refer to the 0-flats, 1-flats and 2-flats of M as its points, lines and planes respectively.The points are simply the members of the class M.We have to recognize one distinction which has no analogue in projective