Solving the linear matroid parity problem as a sequence of matroid intersection problems

In this paper, we present an O(r ⁴ n) algorithm for the linear matroid parity problem. Our solution technique is to introduce a modest generalization, the non-simple parity problem, and identify an important subclass of non-simple parity problems called easy parity problems which can be solved as matroid intersection problems. We then show how to solve any linear matroid parity problem parametrically as a sequence of easy parity problems.In contrast to other algorithmic work on this problem, we focus on general structural properties of dual solutions rather than on local primal structures. In a companion paper, we develop these ideas into a duality theory for the parity problem.     

The basis monomial ring of a matroid

We define the basis monomial ring M_G of a matroid G and prove that it is Cohen-Macaulay for finite G. We then compute the Krull dimension of M_G, which is the rank over Q of the basis-point incidence matrix of G, and prove that dim B_G ≥ dim M_G under a certain hypothesis on coordinatizability of G, where B_G is the bracket ring of G.     

The solution to the partition reconstruction problem

Given a partition λ of n, a k-minor of λ is a partition of n−k whose Young diagram fits inside that of λ. We find an explicit function g(n) such that any partition of n can be reconstructed from its set of k-minors if and only if k?g(n). In particular, partitions of n?k²+2k are uniquely determined by their sets of k-minors. This result completely solves the partition reconstruction problem and also a special case of the character reconstruction problem for finite groups.     

Numerical solution to a stokes interface problem

A numerical algorithm is described for solving the generalized eigenvalue problem arising in the study of the spectrum of a preconditioned operator in the pressure equation derived from a Stokes interface problem. The algorithm is implemented for two finite element schemes. It is tested for a problem with an analytical solution and is applied to spectrum computations in the case of a piecewise constant viscosity. A large number of numerical experiments are analyzed, and recommendations are given for solving the Stokes interface problem in practice.     

The intersection of a matroid and a simplicial complex

A classical theorem of Edmonds provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a ``covering" parameter. We generalize this theorem, replacing one of the matroids by a general simplicial complex. One application is a solution of the case of a matroidal version of Ryser's conjecture. Another is an upper bound on the minimal number of sets belonging to the intersection of two matroids, needed to cover their common ground set. This, in turn, is used to derive a weakened version of a conjecture of Rota. Bounds are also found on the dual parameter--the maximal number of disjoint sets, all spanning in each of two given matroids. We study in detail the case in which the complex is the complex of independent sets of a graph, and prove generalizations of known results on ``independent systems of representatives" (which are the special case in which the matroid is a partition matroid). In particular, we define a notion of -matroidal colorability of a graph, and prove a fractional version of a conjecture, that every graph is -matroidally colorable.

The methods used are mostly topological.

     

On a matroid identity

The purpose of this note is to prove an identity for generalized Tutte-Grothendieck invariants, at least two special cases of which have already proved to be of considerable use. In addition, one of these special cases is used to strengthen results of Lindström on the critical exponent of a representable matroid and the chromatic number of a regular matroid.     

Complementary bases of a matroid

Let e₁, e′₁, e₂, e′₂, …, e_n, e′_n be the elements of matroid M. Suppose that {e₁, e₂, …;, e_n} is a base of M and that every circuit of M contains at least m + 1 elements. We prove that there exist at least 2^m bases, called complementary bases, of M with the property that only one of each complementary pair e_j, e′_j is contained in any base.We also prove an analogous result for the case where E is partitioned into E₁, E₂, …, E_n and the initial base contains |E_j| ? 1 elements from partition E_j.     

Lower-dimensional linear complementarity problem approaches to the solution of a bi-obstacle problem

A globally convergent Broyden-like method for solving a bi-obstacle problem is proposed based on its equivalent lower-dimensional linear complementarity problem. A suitable line search technique is introduced here. The global and superlinear convergence of the method is verified under appropriate assumptions.     

Exact solution to a parametric linear programming problem

In this paper, we present a cubically convergent method for finding the largest eigenvalue of a nonnegative irreducible tensor. A cubically convergent method is used to solve an equivalent system of nonlinear equations which is transformed by the tensor eigenvalue problem. Due to particular structure of tensor, Chebyshev’s direction is added to the method with a few extra computation. Two rules are designed such that the descendant property of the search directions is ensured. The global convergence is proved by using the line search technique. Numerical results indicate that the proposed method is competitive and efficient on some test problems.     

An analytical solution to a matrix Riemann-Hilbert problem

The matrix Riemann-Hilbert problem relevant to the BGK model in the kinetic theory of gases is solved analytically.

---

Zusammenfassung Das Matrix-Riemann-Hilbert Problem, das in der kinetischen Theorie der Gase für das BGK-Modell auftritt, wird analytisch gelöst.