Pfaffian structures and critical problems in finite symplectic spaces

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 setS of non-zero vectors in a non-singular symplectic spaceV of dimension2m, find its symplectic critical exponent, that is, the minimum of the set {m?dim(U):U∩S=0}, whereU ranges over all the (totally) isotropic subspaces disjoint fromS. In particular, we derive a formula for the number of isotropic subspaces of a given dimension disjoint from the setS by Möbius inversion over the order ideal of isotropic flats in the lattice of flats of the matroid onS given by linear dependence. This formula implies that the symplectic critical exponent ofS depends only on its matroid and Pfaffian structure; however, it may depend on the dimension of the symplectic spaceV.     

The incidence structure of subspaces with well-scaled frames

In this paper, the incidence structure of classes of subspaces that generalize the regular (unimodular) subspaces of rational coordinate spaces is studied. Let F the a field and S - F β {0}. A subspace, V, of a coordinate space over F is S-regular if every elementary vector of V can be scaled by an element of F β {0} so that all of its non-zero entries are elements of S. A subspace that is {−1, +1 }-regular over the rational field is regular.Associated with a subspace, V, over an arbitrary (respectively, ordered) field is a matroid (oriented matroid) having as circuits (signed circuits) the set of supports (signed supports) of elementary vectors of V. Fundamental representation properties are established for the matroids that arise from certain classes of subspaces. Matroids that are (minor) minimally non-representable by various classes of subspaces are identified. A unique representability results is established for the oriented matroids of subspaces that are dyadic (i.e., {±2⁰, ±2¹, ±2², …}-regular) over the rationals. A self-dual characterization is established for the matroids of S-regular subspaces which generalizes Minty's characterization of regular spaces as digraphoids.     

Representations of matroids and free resolutions for multigraded modules

Let k be a field, let R=k[x₁,…,xm] be a polynomial ring with the standard Zm-grading (multigrading), let L be a Noetherian multigraded R-module, and let be a finite free multigraded presentation of L over R. Given a choice S of a multihomogeneous basis of E, we construct an explicit canonical finite free multigraded resolution T_•(Φ,S) of the R-module L. In the case of monomial ideals our construction recovers the Taylor resolution. A main ingredient of our work is a new linear algebra construction of independent interest, which produces from a representation ? over k of a matroid M a canonical finite complex of finite dimensional k-vector spaces T_•(?) that is a resolution of Ker?. We also show that the length of T_•(?) and the dimensions of its components are combinatorial invariants of the matroid M, and are independent of the representation map ?.     

Generalized ridge regression,least squares with stochastic prior information,and Bayesian estimators

The ridge estimator of the usual linear model is generalized by the introduction of an a priori vector r and an associated positive semidefinite matrix S. It is then shown that the generalized ridge estimator can be justified in two ways: (a) by the minimization of the residual sum of squares subject to a constraint on the length, in the metric S, of the vector of differences between r and the estimated linear model coefficients, (b) by incorporating prior knowledge, r playing the role of the vector of means and S proportional to the precision matrix. Both a Bayesian and an Aitken generalized least squares frameworks are used for the latter. The properties of the new estimator are derived and compared to the ordinary least squares estimator. The new method is illustrated with different assumptions on the form of the S matrix.     

Vector representable matroids of given rank with given automorphism group

A simple way of associating a matroid of prescribed rank with a graph is shown. The matroids so constructed are representable over any sufficiency large field. Their use is demonstrated by the following result: Given an integer k?3 and a function G associating a group with each subset of a set S, there is a matroid M(E), representable over any sufficiently large field, such that E ? S, and for any T ?/ S, the rank of M/Tis k, and the automorphine group of MT is isomorphic to G(T).     

An Adjacency Criterion for Coxeter Matroids

A Coxeter matroid is a generalization of matroid, ordinary matroid being the case corresponding to the family of Coxeter groups A _n , which are isomorphic to the symmetric groups. A basic result in the subject is a geometric characterization of Coxeter matroid in terms of the matroid polytope, a result first stated by Gelfand and Serganova. This paper concerns properties of the matroid polytope. In particular, a criterion is given for adjacency of vertices in the matroid polytope.     

Matroid Matching Via Mixed Skew-Symmetric Matrices

Tutte associates a V by V skew-symmetric matrix T, having indeterminate entries, with a graph G=(V,E). This matrix, called the Tutte matrix, has rank exactly twice the size of a maximum cardinality matching of G. Thus, to find the size of a maximum matching it suffices to compute the rank of T. We consider the more general problem of computing the rank of T + K where K is a real V by V skew-symmetric matrix. This modest generalization of the matching problem contains the linear matroid matching problem and, more generally, the linear delta-matroid parity problem. We present a tight upper bound on the rank of T + K by decomposing T + K into a sum of matrices whose ranks are easy to compute.Part of this research was done while the authors visited the Fields Institute in Toronto, Canada. The research was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

Polytopal and nonpolytopal spheres an algorithmic approach

The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework for a new computational approach to the Steinitz problem [13]. We describe an algorithm which, for a given combinatorial (d − 2)-sphereS withn vertices, determines the setC _d,n(S) of rankd oriented matroids withn points and face latticeS. SinceS is polytopal if and only if there is a realizableM εC _d,n(S), this method together with the coordinatizability test for oriented matroids in [10] yields a decision procedure for the polytopality of a large class of spheres. As main new result we prove that there exist 431 combinatorial types of neighborly 5-polytopes with 10 vertices by establishing coordinates for 98 “doubted polytopes” in the classification of Altshuler [1]. We show that for alln ≧k + 5 ≧8 there exist simplicialk-spheres withn vertices which are non-polytopal due to the simple fact that they fail to be matroid spheres. On the other hand, we show that the 3-sphereM ₉₆₃ ⁹ with 9 vertices in [2] is the smallest non-polytopal matroid sphere, and non-polytopal matroidk-spheres withn vertices exist for alln ≧k + 6 ≧ 9.     

Mod 2 cohomology of combinatorial Grassmannians

Matroid bundles, introduced by MacPherson, are combinatorial analogues of real vector bundles. This paper sets up the foundations of matroid bundles. It defines a natural transformation from isomorphism classes of real vector bundles to isomorphism classes of matroid bundles. It then gives a transformation from matroid bundles to spherical quasifibrations, by showing that the geometric realization of a matroid bundle is a spherical quasifibration. The poset of oriented matroids of a fixed rank classifies matroid bundles, and the above transformations give a splitting from topology to combinatorics back to topology. A consequence is that the mod 2 cohomology of the poset of rank k oriented matroids (this poset classifies matroid bundles) contains the free polynomial ring on the first k Stiefel-Whitney classes.     

Infinite graphs and bicircular matroids

B-matroids are a class of pre-independence spaces which retain many important properties of independence spaces. Higgs has shown that an infinite generalization of the cycle matroid of a finite graph which admits two-way infinite paths as circuits need not be a B-matroid. In this note it is shown that a similar generalization of the finite bicircular matroid is a ways a B-matroid.     

Amalgams of free inverse semigroups

We study inverse semigroup amalgams of the formS * _U T whereS andT are free inverse semigroups andU is an arbitrary finitely generated inverse subsemigroup ofS andT. We make use of recent work of Bennett to show that the word problem is decidable for any such amalgam. This is in contrast to the general situation for semigroup amalgams, where recent work of Birget, Margolis and Meakin shows that the word problem for a semigroup amalgamS * _U T is in general undecidable, even ifS andT have decidable word problem,U is a free semigroup, and the membership problem forU inS andT is decidable. We also obtain a number of results concerning the structure of such amalgams. We obtain conditions for theD-classes of such an amalgam to be finite and we show that the amalgam is combinatorial in such a case. For example every one-relator amalgam of this type has finiteD-classes and is combinatorial. We also obtain information concerning when such an amalgam isE-unitary: for example every one relator amalgam of the formInv<A ∪B :u =v > whereA andB are disjoint andu (resp.v) is a cyclically reduced word overA ∪A ⁻¹ (resp.B ∪B ⁻¹) isE-unitary. Research of all authors supported by a grant from the Italian CNR. The first and third authors’ research was partially supported by MURST. The second author’s research was also partially supported by NSF and the Center for Communication and Information Science of the University of Nebraska at Lincoln.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

On delaunay oriented matroids for convex distance functions

For any finite point setS inE ^d, an oriented matroid DOM (S) can be defined in terms of howS is partitioned by Euclidean hyperspheres. This oriented matroid is related to the Delaunay triangulation ofS and is realizable, because of thelifting property of Delaunay triangulations. We prove that the same construction of aDelaunay oriented matroid can be performed with respect to any smooth, strictly convex distance function in the planeE ² (Theorem 3.5). For these distances, the existence of a Delaunay oriented matroid cannot follow from a lifting property, because Delaunay triangulations might be nonregular (Theorem 4.2(i). This is related to the fact that the Delaunay oriented matroid can be nonrealizable (Theorem 4.2(ii). This research was partially supported by the Spanish Grant DGICyT PB 92/0498-C02 and the David and Lucile Packard Foundation.     

Matroid Polytopes and their Volumes

We express the matroid polytope P _M of a matroid M as a signed Minkowski sum of simplices, and obtain a formula for the volume of P _M . This gives a combinatorial expression for the degree of an arbitrary torus orbit closure in the Grassmannian Gr _k,n . We then derive analogous results for the independent set polytope and the underlying flag matroid polytope of M. Our proofs are based on a natural extension of Postnikov’s theory of generalized permutohedra.     

An analysis of approximations for maximizing submodular set functions—I

LetN be a finite set andz be a real-valued function defined on the set of subsets ofN that satisfies z(S)+z(T)z(ST)+z(ST) for allS, T inN. Such a function is called submodular. We consider the problem max_SN{a(S):|S|K,z(S) submodular}.Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanK colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem.We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S) is nondecreasing andz(0) = 0, we show that a greedy heuristic always produces a solution whose value is at least 1 –[(K – 1)/K] ^K times the optimal value. This bound can be achieved for eachK and has a limiting value of (e – 1)/e, where e is the base of the natural logarithm.On leave of absence from Cornell University and supported, in part, by NSF Grant ENG 75-00568.Supported, in part, by NSF Grant ENG 76-20274.     

Symmetrizers of matrices

A symmetrizer of a given pair of matrices, A and B, is defined as a matrix X for which the product AXB is symmetric. Right and left symmetrizers of a given matrix A are defined accordingly. The main results of the paper are general representations of all three types of symmetrizers. The problem considered arose in connection with certain questions pertaining to admissible linear estimation in a Gauss-Markoff model.     

On exchange axioms for valuated matroids and valuated delta-matroids

Two further equivalent axioms are given for valuations of a matroid. Let M = (V,B) be a matroid on a finite setV with the family of basesB. For :BR the following three conditions are equivalent: A similar result is obtained for valuations of a delta-matroid.This work was done while the author was at Forschungsinstitut für Diskrete Mathematik, Universität Bonn.     

Finite groups with <Emphasis Type="Italic">S</Emphasis>-supplemented <Emphasis Type="Italic">p</Emphasis>-subgroups

Consider a finite group G. A subgroup is called S-quasinormal whenever it permutes with all Sylow subgroups of G. Denote by B _sG the largest S-quasinormal subgroup of G lying in B. A subgroup B is called S-supplemented in G whenever there is a subgroup T with G = BT and B∩T ≤ B _sG . A subgroup L of G is called a quaternionic subgroup whenever G has a section A/B isomorphic to the order 8 quaternion group such that L ≤ A and L ∩ B = 1. This article is devoted to proving the following theorem.     

Backward Perturbation Analysis for the Matrix Equation A~TXA+B~TYB=D

Consider the linear matrix equation A~TXA + B~TYB = D,where A,B are n X n real matrices and D symmetric positive semi-definite matrix.In this paper,the normwise backward perturbation bounds for the solution of the equation are derived by applying the Brouwer fixed-point theorem and the singular value decomposition as well as the property of Kronecker product.The results are illustrated by two simple numerical examples.