Matroids and Flag Matroids

The main idea in this chapter is to establish the intimate connection between matroids and the symmetric group Sym _n . This will be seen most clearly in the Maximality Property, which is really just a reformulation of the well-known characterization of matroids in terms of the Greedy Algorithm. It says, briefly, that for every linear ordering of the set of elements of the matroid, there is a unique maximal basis. But linear orderings of a finite set can be interpreted as its permutations. This brings the symmetric group into a pivotal role in matroid theory to an extent that has never been appreciated previously. Coxeter matroids are essentially just the generalization of matroids obtained when the group Sym _n is replaced by an arbitrary finite Coxeter group. Thus this first chapter will not only cast matroid theory in this new light, but also prepare the way for, and provide a prototype for, the more general Coxeter matroids.