Annals of Combinatorics 1 (1997) 173-181
A Geometric Characterization of Coxeter Matroids
V.V. Serganova, A. Vince, and A. Zelevinsky
Department of Mathematics, University of California, Berkeley, CA 94720, USA
Department of Mathematics, University of Florida, Gainesville, FL 32611, USA
Department of Mathematics, Northeastern University, Boston, MA 02115, USA
Received February 11, 1997
AMS Subject Classification: 05E99, 05B35, 20F55
Abstract.Coxeter matroids, introduced by Gelfand and Serganova, are combinatorial structures associated with any finite Coxeter group and its parabolic subgroup; they include ordinary matroids as a special case. A basic result in the subject is a geometric characterization of Coxeter matroids, first stated by Gelfand and Serganova. This paper presents a self-contained, simple proof of a more general version of this geometric characterization.
Keywords: matroid, Coxeter group, Coxeter matroid, Bruhat order
1. A.V. Borovik and I.M. Gelfand, $WP$-matroids and thin Schubert cells on Tits systems, Adv. Math. 103 (1994) 162–179.
2. A.V. Borovik and I.M. Gelfand, Matroids on chamber systems, Publ. LaCIM 14 (1993) 25–62.
3. A.V. Borovik, I.M. Gelfand, A. Vince, and N. White, The lattice of flats and its underlying flag matroid polytope, Ann. Combin. 1 (1997) 17–26.
4. A.V. Borovik, I.M. Gelfand, and N. White, On exchange properties for Coxeter matroids and oriented matroids, preprint.
5. A.V. Borovik, I.M. Gelfand, and N. White, Symplectic matroids, preprint.
6. A.V. Borovik and K.S. Roberts, Coxeter groups and matroids, In: Groups of Lie Type and Geometries, W.M. Kantor and L. Di Martino, Eds., Cambridge University Press, Cambridge, 1995, pp. 13–34.
7. A.V. Borovik and A. Vince, An adjacency criterion for Coxeter matroids, submitted.
8. N. Bourbaki, Groupes et Algèbres de Lie. Ch. IV-VI, Hermann, Paris, 1968.
9. V.V. Deodhar, Some characterizations of Coxeter groups, Enseignments Math. 32 (1986) 111–120.
10. D. Gale, Optimal assignments in an ordered set: an application of matroid theory, J. Combin. Theory 4 (1968) 1073–1082.
11. I.M. Gelfand, M. Goresky, R.D. MacPherson, and V.V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. Math. 63 (1987) 301–316.
12. I.M. Gelfand and V.V. Serganova, On a general definition of a matroid and a greedoid, Soviet Math. Dokl. 35 (1987) 6–10.
13. I.M. Gelfand and V.V. Serganova, Combinatorial geometries and torus strata on homogeneous compact manifolds, Russian Math. Surveys 42 (1987) 133–168, see also: I.M. Gelfand, Collected Papers, Vol. III, Springer-Verlag, New York, 1989, pp. 926–958.
14. H. Hiller, Geometry of Coxeter Groups, Pitman, Boston, 1982.
15. V. Serganova and A. Zelevinsky, Combinatorial optimization on Weyl groups, greedy algorithms and generalized matroids, preprint, Scientific Council in Cybernetics, USSR Academy of Sciences, 1989.
16. N. White, Ed., Theory of Matroids, Cambridge University Press, Cambridge, 1986.