Annals of Combinatorics 1 (1997) 123-134
Coxeter Matroid Polytopes
Alexandre V. Borovik, Israel M. Gelfand, and Neil White
Department of Mathematics, UMIST, P.O. Box 88, Manchester
M60 1QD, UK
Department of Mathematics, Rutgers University, New Brunswick,
NJ 08903, USA
Department of Mathematics, University of Florida, Gainesville,
FL 32611, USA
Recieved February 7, 1997
AMS Subject Classification: 05B35, 05E15, 20F55, 52B40
Abstract. If Δ is a polytope in real affine space, each edge of Δ determines a reflection in the perpendicular bisector of the edge. The exchange group W(Δ) is the group generated by these reflections, and Δ is a (Coxeter) matroid polytope if this group is finite. This simple concept of matroid polytope turns out to be an equivalent way to define Coxeter matroids. The Gelfand-Serganova Theorem and the structure of the exchange group both give us information about the matroid polytope. We then specialize this information to the case of ordinary matroids; the matroid polytope by our definition in this case turns out to be a facet of the classical matroid polytope familiar to matroid theorists.
Keywords: matroid polytope, Coxeter matroid, exchange group
1. C. Berge, Principles of Combinatorics, Academic Press, New York, 1971.
2. A. Björner, B. Korte, and L. Lovàsz, Homotopy properties of greedoids, Adv. Appl. Math. 6 (1985) 447–494.
3. A.V. Borovik and I.M. Gelfand, $WP$-matroids and thin Schubert cells on Tits systems, Adv. Math. 103 (1994) 162–179.
4. A.V. Borovik, I.M. Gelfand, and N.L. White, Coxeter Matroids, Birkhäuser, Boston, in preparation.
5. A.V. Borovik, I.M. Gelfand, and N.L. White, Exchange properties of Coxeter matroids and oriented matroids, Discrete Math., to appear.
6. A.V. Borovik, I.M. Gelfand, and N.L. White, Symplectic matroids, J. Algebraic Combin., to appear.
7. A.V. Borovik, I.M. Gelfand, and N.L. White, Flag matroids, in preparation.
8. A.V. Borovik, I.M. Gelfand, A. Vince, and N.L. White, The lattice of flats and its underlying flag matroid polytope, Ann. Combin. 1 (1997) 17–26.
9. 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.
10. A.V. Borovik and A. Vince, An adjacency criterion for Coxeter matroids, J. Algebraic Combin., submitted.
11. A. Bouchet, Greedy algorithm and symmetric matroids, Math. Programming 38 (1987) 147–159.
12. B.J. Carman, Matroids and Their Polytopes, M. Sc. Dissertation, UMIST, Manchester, 1995.
13. J. Edmonds, Submodular functions, matroids, and certain polyhedra, In: Combinatorial Structures and Their Applications, R. Guy et al., Eds., Gordon and Breach, New York, 1970, pp. 69–87.
14. 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.
15. I.M. Gelfand and V.V. Serganova, On a general definition of a matroid and a greedoid, Soviet Math. Dokl. 35 (1987) 6–10.
16. 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.
17. J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge University Press, Cambridge, 1976.
18. S.B. Maurer, Matroid basis graphs. I, J. Combin. Theory Ser. B 14 (1973) 216–240.
19. J.G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.
20. V.V. Serganova, A. Vince, and A. Zelevinsky, A geometric characterization of Coxeter matroids, Ann. Combin. 1 (1997) 173–181.
21. D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.
22. W. Wenzel, Geometric algebra of Δ-matroids and related combinatorial geometries, Habilitationschrift, Bielefeld, 1991.
23. N.L. White, Ed., Theory of Matroids, Cambridge University Press, Cambridge, 1986.
24. H. Whitney, On the abstract properties of linear dependence, Amer. J. Math. 57 (1935) 509–533.
25. A.V. Zelevinsky and V.V. Serganova, Combinatorial optimization on Weyl groups, greedy algorithms and generalized matroids, Acad. Sci. USSR, Scientific Council on the Complex Problem ``Cybernetics'', Moscow, 1989, 24 pp., preprint (in Russian).