Annals of Combinatorics 1 (1997) 105-106

Combinatorics and Nonparametric Mathematics

Joseph P.S. Kung

Department of Mathematics, University of North Texas, Denton, Texas 76203, USA

Received June 3, 1997

Abstract. Nonparametric statistics, toric varieties, matroids -- a more disparate trio of mathematical subjects can hardly be imagined, and yet, they share a basic idea. The idea is to replace a numerical or continuous quantity in an existing "classical" subject by a discrete combinatorial quality. In nonparametric statistics, one replaces the values of the sample points, which are usually real numbers, by, say, their ranks or signs. In the theory of toric varieties, the replacement is done through the action of the group of diagonal matrices. Under this action, two nonzero coefficients in a polynomial are in the same orbit and, hence, it only matters whether a coefficient is zero or nonzero.
        In matroid theory, one replaces the value of a determinant by the bit of information whether it is zero or nonzero. Retaining more information, such as the trinary piece, or trit of information whether the determinant is zero, positive or negative, one obtains oriented matroid theory. Pushing this further, by retaining a 2, 4, or 8-tuple of bits or trits, one obtains complex, quarternionic, and octonionic matroids or oriented matroids. The last two types of matroids have not been studied and one expects that the theory will be complicated. A satisfactory axiomatization for quarternionic matroid would require understanding identities between determinants over skew fields. Similarly, a theory of octonionic matroids would uncover the precise role played by associativity in linear algebra or, equivalently, Desargues' theorem in geometry.
        Several papers in this journal show nonparametrization in action. Four of these papers are about symplectic analogues of matroids. The paper by Serganova, Vince, and Zelevinsky [8] and the two papers of Borovik, Gelfand, Vince, and White [1,2] (one of which appeared in an earlier issue) study symplectic matroids in terms of a certain polytope similar to the independent-set polytope for matroids. The more general polytope, defined using Coxeter groups, was defined by Gelfand and Serganova [5] in 1987. The independent-set polytope, has wide applications in combinatorial optimization since its definition by Edmonds in 1970 [3]. Another paper [6], by the author, gives a direct (and somewhat different) definition of a symplectic matroid in terms of an exchange-augmentation axiom derived from a straightening identity for Pfaffians. This definition harks back to Whitney's definition of a matroid in 1935. The study of symplectic matroids may be viewed as part of an Erlanger Programm to study analogues of matroids for the classical linear groups first suggested by Gian-Carlo Rota in his Bowdoin lectures in 1971 [7]. Symplectic matroids also provide a natural context to study the synthetic or intrinsic geometry of symplectic spaces.
        Another way combinatorics can assume center stage in a subject is to replace a continuous object by simpler combinatorial structures. The classical example of this is the replacement of a topological space by a simplicial complex in algebraic topology. The definition of combinatorial differential manifolds, by Gelfand and MacPherson, is a more recent example. Many properties arrangements of hyperplanes reside in the matroid determined by its lattice of intersection. The paper by Michael Falk [4], is about connections between an arrangement and its matroid. More specifically, it studies the question whether the Orlik-Solomon algebra of a matroid determines that matroid and gives an account of what is known in the rank-3 case. The paper of Terhalle [9], studies the role played by a valuated matroid in "realizing" trees.
        These papers give an indication why many have considered combinatorics to be one of the central subjects of mathematics.


1.  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.

2.  A.V. Borovik, I.M. Gelfand, and N.L. White, Coxeter matroid polytopes, Ann. Combin. 1 (1997) 123–134.

3.  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.

4.  M. Falk, Arrangements and cohomology, Ann. Combin. 1 (1997) 135–158.

5.  I.M. Gelfand and V.V. Serganova, On a general definition of a matroid and a greedoid, Soviet Math. Dokl. 35 (1987) 6–10.

6.  J.P.S. Kung, Pfaffian structures and critical problems in finite symplectic spaces, Ann. Combin. 1 (1997) 159–172.

7.  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.

8.  V.V. Serganova, A. Vince, and A. Zelevinsky, A geometric characterization of Coxeter matroids, Ann. Combin. 1 (1997) 173–182.

9.  W.F. Terhalle, Coordinatizing R-trees in terms of Universal c-trees, Ann. Combin. 1 (1997) 183–196.

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