Orthogonal Matroids
Andrew Vince
and Neil White
DOI: 10.1023/A:1011212331779
Abstract
The notion of matroid has been generalized to Coxeter matroid by Gelfand and Serganova. To each pair (W, P) consisting of a finite irreducible Coxeter group W and parabolic subgroup P is associated a collection of objects called Coxeter matroids. The (ordinary) matroids are the special case where W is the symmetric group (the A n case) and P is a maximal parabolic subgroup.This generalization of matroid introduces interesting combinatorial structures corresponding to each of the finite Coxeter groups. Borovik, Gelfand and White began an investigation of the B n case, called symplectic matroids. This paper initiates the study of the D n case, called orthogonal matroids. The main result (Theorem 2) gives three characterizations of orthogonal matroid: algebraic, geometric, and combinatorial. This result relies on a combinatorial description of the Bruhat order on D n (Theorem 1). The representation of orthogonal matroids by way of totally isotropic subspaces of a classical orthogonal space (Theorem 5) justifies the terminology orthogonal matroid.
Pages: 295–315
Keywords: orthogonal matroid; Coxeter matroid; Coxeter group; Bruhat order
Full Text: PDF
References
1. A.V. Borovik, I.M. Gelfand, A. Vince, and N. White, “The lattice of flats and its underlying flag matroid polytope,” Annals of Combinatorics 1 (1998), 17-26.
2. A.V. Borovik, I.M. Gelfand, and N. White, “Symplectic matroids,” J. Alg. Combin. 8 (1998), 235-252.
3. A.V. Borovik, I.M. Gelfand, and N. White, Coxeter Matroids, Birkhauser, Boston, to appear.
4. 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.
5. A.V. Borovik and A. Vince, “An adjacency criterion for Coxeter matroids.” J. Alg. Combin. 9 (1999), 271-280.
6. A. Bouchet, “Greedy algorithm and symmetric matroids,” Math. Programming 38 (1987), 147-159.
7. V.V. Deodhar, “Some characterizations of Coxeter groups,” Enseignments Math. 32 (1986), 111-120.
8. I.M. Gelfand, M. Goresky, R.D. MacPherson, and V.V. Serganova, “Combinatorial Geometries, convex poly- hedra, and Schubert cells,” Adv. Math. 63 (1987), 301-316.
9. I.M. Gelfand and V.V. Serganova, “On a general definition of a matroid and a greedoid,” Soviet Math. Dokl. 35 (1987), 6-10.
10. I.M. Gelfand and V.V. Serganova, “Combinatorial geometries and torus strata on homogeneous compact manifolds,” Russian Math. Surveys 42 (1987), 133-168; I.M. Gelfand, in Collected Papers, Vol. III, Springer- Verlag, New York, 1989, pp. 926-958.
11. H. Hiller, Geometry of Coxeter Groups, Pitman, Boston, 1982.
12. V.V. Serganova, A. Vince, and A.V. Zelevinski, “A geometric characterization of Coxeter matroids,” Annals of Combinatorics 1 (1998), 173-181.
13. A. Vince, “The greedy algorithm and Coxeter matroids,” J. of Alg. Combin., 11 (2000), 155-178.
14. N. White (Ed.), Theory of Matroids, Cambridge University Press, Cambridge, 1986.
2. A.V. Borovik, I.M. Gelfand, and N. White, “Symplectic matroids,” J. Alg. Combin. 8 (1998), 235-252.
3. A.V. Borovik, I.M. Gelfand, and N. White, Coxeter Matroids, Birkhauser, Boston, to appear.
4. 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.
5. A.V. Borovik and A. Vince, “An adjacency criterion for Coxeter matroids.” J. Alg. Combin. 9 (1999), 271-280.
6. A. Bouchet, “Greedy algorithm and symmetric matroids,” Math. Programming 38 (1987), 147-159.
7. V.V. Deodhar, “Some characterizations of Coxeter groups,” Enseignments Math. 32 (1986), 111-120.
8. I.M. Gelfand, M. Goresky, R.D. MacPherson, and V.V. Serganova, “Combinatorial Geometries, convex poly- hedra, and Schubert cells,” Adv. Math. 63 (1987), 301-316.
9. I.M. Gelfand and V.V. Serganova, “On a general definition of a matroid and a greedoid,” Soviet Math. Dokl. 35 (1987), 6-10.
10. I.M. Gelfand and V.V. Serganova, “Combinatorial geometries and torus strata on homogeneous compact manifolds,” Russian Math. Surveys 42 (1987), 133-168; I.M. Gelfand, in Collected Papers, Vol. III, Springer- Verlag, New York, 1989, pp. 926-958.
11. H. Hiller, Geometry of Coxeter Groups, Pitman, Boston, 1982.
12. V.V. Serganova, A. Vince, and A.V. Zelevinski, “A geometric characterization of Coxeter matroids,” Annals of Combinatorics 1 (1998), 173-181.
13. A. Vince, “The greedy algorithm and Coxeter matroids,” J. of Alg. Combin., 11 (2000), 155-178.
14. N. White (Ed.), Theory of Matroids, Cambridge University Press, Cambridge, 1986.