Symplectic Matroids
Alexandre V. Borovik
, Israel Gelfand
and Neil White
Department of Mathematics, Rutgers University, New Brunswick NJ 08903
DOI: 10.1023/A:1008610715466
Abstract
A symplectic matroid is a collection B of k-element subsets of J = {1, 2, ..., n, 1*, 2*, ...; n*}, each of which contains not both of i and i* for every i 
n, and which has the additional property that for any linear ordering 
of J such that i j implies j* i* and i j* implies j i* for all i, j n, B has a member which dominates element-wise every other member of B. Symplectic matroids are a special case of Coxeter matroids, namely the case where the Coxeter group is the hyperoctahedral group, the group of symmetries of the n-cube. In this paper we develop the basic properties of symplectic matroids in a largely self-contained and elementary fashion. Many of these results are analogous to results for ordinary matroids (which are Coxeter matroids for the symmetric group), yet most are not generalizable to arbitrary Coxeter matroids. For example, representable symplectic matroids arise from totally isotropic subspaces of a symplectic space very similarly to the way in which representable ordinary matroids arise from a subspace of a vector space. We also examine Lagrangian matroids, which are the special case of symplectic matroids where k = n, and which are equivalent to Bouchet”s symmetric matroids or 2-matroids.
n, and which has the additional property that for any linear ordering of J such that i j implies j* i* and i j* implies j i* for all i, j n, B has a member which dominates element-wise every other member of B. Symplectic matroids are a special case of Coxeter matroids, namely the case where the Coxeter group is the hyperoctahedral group, the group of symmetries of the n-cube. In this paper we develop the basic properties of symplectic matroids in a largely self-contained and elementary fashion. Many of these results are analogous to results for ordinary matroids (which are Coxeter matroids for the symmetric group), yet most are not generalizable to arbitrary Coxeter matroids. For example, representable symplectic matroids arise from totally isotropic subspaces of a symplectic space very similarly to the way in which representable ordinary matroids arise from a subspace of a vector space. We also examine Lagrangian matroids, which are the special case of symplectic matroids where k = n, and which are equivalent to Bouchet”s symmetric matroids or 2-matroids.Pages: 235–252
Keywords: symplectic matroid; Coxeter matroid; totally isotropic subspace; symmetric matroid; 2-matroid
Full Text: PDF
References
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, I.M. Gelfand, and N. White, “On exchange properties for Coxeter matroids and oriented matroids,” J. Discrete Math. (to appear).
3. A.V. Borovik, I.M. Gelfand, and N. White, Coxeter Matroids, Birkhauser, in preparation.
4. A.V. Borovik, I.M. Gelfand, and N. White, Flag Matroids, to appear.
5. 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, pp. 13-34, 1995.
6. A. Bouchet, “Greedy algorithm and symmetric matroids,” Mathematical Programming 38 (1987), 147-159.
7. A. Bouchet, “Representability of -matroids,” Proc. 6th Hungarian Colloquium of Combinatorics, Colloquia Mathematica Societas Janos Bolyai, pp. 167-182, 1987.
8. A. Bouchet, “Matchings and -matroids,” Discrete Applied Mathematics 24 (1989), 55-62.
9. A. Bouchet, “Multimatroids I. Coverings by independent sets,” SIAM J. Discrete Math. (to appear). P1: JSN/PCY P2: JSN Journal of Algebraic Combinatorics KL629-02-Borovik August 21, 1998 17:17 252 BOROVIK, GELFAND AND WHITE
10. A. Bouchet, A. Dress, and T. Havel, “ -matroids and metroids,” Advances in Math. 91 (1992), 136-142.
11. T. Brylawski, “Constructions,” in Theory of Matroids, N. White (Ed.), Cambridge University Press, 1986.
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, Springer- Verlag, New York, Vol. III, pp. 926-958, 1989.
14. J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge University Press, 1990.
15. W. Wenzel, “Geometric algebra of -matroids and related combinatorial geometries,” Habilitationsschrift, Bielefeld, 1991.
16. A.V. Zelevinski and V.V. Serganova, “Combinatorial optimisation on Weyl groups, greedy algorithms and generalised matroids,” Acad. Sci. USSR, Scientific Council for complex problem “Cybernetics”, 1989, 24 pp. (in Russian).
2. A.V. Borovik, I.M. Gelfand, and N. White, “On exchange properties for Coxeter matroids and oriented matroids,” J. Discrete Math. (to appear).
3. A.V. Borovik, I.M. Gelfand, and N. White, Coxeter Matroids, Birkhauser, in preparation.
4. A.V. Borovik, I.M. Gelfand, and N. White, Flag Matroids, to appear.
5. 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, pp. 13-34, 1995.
6. A. Bouchet, “Greedy algorithm and symmetric matroids,” Mathematical Programming 38 (1987), 147-159.
7. A. Bouchet, “Representability of -matroids,” Proc. 6th Hungarian Colloquium of Combinatorics, Colloquia Mathematica Societas Janos Bolyai, pp. 167-182, 1987.
8. A. Bouchet, “Matchings and -matroids,” Discrete Applied Mathematics 24 (1989), 55-62.
9. A. Bouchet, “Multimatroids I. Coverings by independent sets,” SIAM J. Discrete Math. (to appear). P1: JSN/PCY P2: JSN Journal of Algebraic Combinatorics KL629-02-Borovik August 21, 1998 17:17 252 BOROVIK, GELFAND AND WHITE
10. A. Bouchet, A. Dress, and T. Havel, “ -matroids and metroids,” Advances in Math. 91 (1992), 136-142.
11. T. Brylawski, “Constructions,” in Theory of Matroids, N. White (Ed.), Cambridge University Press, 1986.
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, Springer- Verlag, New York, Vol. III, pp. 926-958, 1989.
14. J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge University Press, 1990.
15. W. Wenzel, “Geometric algebra of -matroids and related combinatorial geometries,” Habilitationsschrift, Bielefeld, 1991.
16. A.V. Zelevinski and V.V. Serganova, “Combinatorial optimisation on Weyl groups, greedy algorithms and generalised matroids,” Acad. Sci. USSR, Scientific Council for complex problem “Cybernetics”, 1989, 24 pp. (in Russian).