The Abstract

	Annals of Combinatorics 1 (1997) 159-172 Pfaffian Structures and Critical Problems in Finite Symplectic Spaces Joseph P.S. Kung Department of Mathematics, University of North Texas, Denton, Texas 76203, USA kung@unt.edu Received March 18, 1997 AMS Subject Classification: 05B35; 05B25, 05C70, 05C35, 05E15, 15A15 Abstract. Just as matroids abstract the algebraic properties of determinants in a vector space, Pfaffian structures abstract the algebraic properties of Pfaffians or skew-symmetric determinants in a symplectic space (that is, a vector space with an alternating bilinear form). This is done using an exchange-augmentation axiom which is a combinatorial version of a Laplace expansion or straightening identity for Pfaffians. Using Pfaffian structures, we study a symplectic analogue of the classical critical problem: given a set S of non-zero vectors in a non-singular symplectic space V of dimension 2m, find its symplectic critical exponent, that is, the minimum of the set {m - dim(U): U∩S= Ø}, where U ranges over all the (totally) isotropic subspaces disjoint from S. In particular, we derive a formula for the number of isotropic subspaces of a given dimension disjoint from the set S by Möbius inversion over the order ideal of isotropic flats in the lattice of flats of the matroid on S given by linear dependence. This formula implies that the symplectic critical exponent of S depends only on its matroid and Pfaffian structure; however, it may depend on the dimension of the symplectic space V. Keywords: Matroids, Pfaffians, symplectic space, basis exchange axioms, critical problem, isotropic subspace, Möbius inversion References 1. H.H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, Preliminary edition, M.I.T. Press, Cambridge, 1970. 2. L.E. Dickson, Linear Groups, Teubner, Leipzig, 1901, Reprinted Dover, New York 1958. 3. J. Edmonds and D.R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Stand. 69B (1965) 147–153. 4. J.P.S. Kung, An Erlanger program for combinatorial geometries, Ph. D. Thesis, M.I.T., Cambridge, 1978. 5. J.P.S. Kung, Bimatroids and invariants, Adv. Math. 30 (1978) 238–249. 6. J.P.S. Kung, Strong maps, In: Theory of Matroids, N.L. White, Ed., Cambridge University Press, Cambridge, 1986, pp. 224–253. 7. J.P.S. Kung, Critical problems, In: Matroid Theory, J.E. Bonin, J.G. Oxley and B. Servatius, Eds., Amer. Math. Soc., Providence, RI, 1996, pp. 1–127. 8. L. Lovàsz and M.D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986. 9. J.G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992. 10. R. Rado, Note on independence functions, Proc. London Math. Soc. (3) 7 (1957) 300–320. 11. G.-C. Rota, Combinatorial Theory and Invariant Theory, Notes taken by L. Guibas from the National Science Foundation Seminar in Combinatorial Theory, Bowdoin College, Maine, 1971, unpublished typescript. 12. W.T. Tutte, The factorisation of linear graphs, J. London Math. Soc. 22 (1947) 107–111. 13. D.J.A.~Welsh, Matroid Theory, Academic Press, London and New York, 1976. 14. G. Whittle, On the critical exponent of transversal matroids, J. Combin. Theory Ser. B 37 (1984) 94–95. Get the LaTex \| DVI \| PS file of this abstract. back

Annals of Combinatorics 1 (1997) 159-172

Pfaffian Structures and Critical Problems in Finite Symplectic Spaces

Joseph P.S. Kung

Department of Mathematics, University of North Texas, Denton, Texas 76203, USA
kung@unt.edu

Received March 18, 1997

AMS Subject Classification: 05B35; 05B25, 05C70, 05C35, 05E15, 15A15

Abstract. Just as matroids abstract the algebraic properties of determinants in a vector space, Pfaffian structures abstract the algebraic properties of Pfaffians or skew-symmetric determinants in a symplectic space (that is, a vector space with an alternating bilinear form). This is done using an exchange-augmentation axiom which is a combinatorial version of a Laplace expansion or straightening identity for Pfaffians. Using Pfaffian structures, we study a symplectic analogue of the classical critical problem: given a set S of non-zero vectors in a non-singular symplectic space V of dimension 2m, find its symplectic critical exponent, that is, the minimum of the set {m - dim(U): U∩S= Ø}, where U ranges over all the (totally) isotropic subspaces disjoint from S. In particular, we derive a formula for the number of isotropic subspaces of a given dimension disjoint from the set S by Möbius inversion over the order ideal of isotropic flats in the lattice of flats of the matroid on S given by linear dependence. This formula implies that the symplectic critical exponent of S depends only on its matroid and Pfaffian structure; however, it may depend on the dimension of the symplectic space V.

Keywords: Matroids, Pfaffians, symplectic space, basis exchange axioms, critical problem, isotropic subspace, Möbius inversion

References

1. H.H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, Preliminary edition, M.I.T. Press, Cambridge, 1970.

2. L.E. Dickson, Linear Groups, Teubner, Leipzig, 1901, Reprinted Dover, New York 1958.

3. J. Edmonds and D.R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Stand. 69B (1965) 147–153.

4. J.P.S. Kung, An Erlanger program for combinatorial geometries, Ph. D. Thesis, M.I.T., Cambridge, 1978.

5. J.P.S. Kung, Bimatroids and invariants, Adv. Math. 30 (1978) 238–249.

6. J.P.S. Kung, Strong maps, In: Theory of Matroids, N.L. White, Ed., Cambridge University Press, Cambridge, 1986, pp. 224–253.

7. J.P.S. Kung, Critical problems, In: Matroid Theory, J.E. Bonin, J.G. Oxley and B. Servatius, Eds., Amer. Math. Soc., Providence, RI, 1996, pp. 1–127.

8. L. Lovàsz and M.D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986.

9. J.G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.

10. R. Rado, Note on independence functions, Proc. London Math. Soc. (3) 7 (1957) 300–320.

11. G.-C. Rota, Combinatorial Theory and Invariant Theory, Notes taken by L. Guibas from the National Science Foundation Seminar in Combinatorial Theory, Bowdoin College, Maine, 1971, unpublished typescript.

12. W.T. Tutte, The factorisation of linear graphs, J. London Math. Soc. 22 (1947) 107–111.

13. D.J.A.~Welsh, Matroid Theory, Academic Press, London and New York, 1976.

14. G. Whittle, On the critical exponent of transversal matroids, J. Combin. Theory Ser. B 37 (1984) 94–95.

Get the LaTex | DVI | PS file of this abstract.

back