Canonical decompositions of symmetric submodular systems

Let E be a finite set, R be the set of real numbers and f: 2^E→R be a symmetric submodular function. The pair (E,f) is called a symmetric submodular system. We examine the structures of symmetric submodular systems and provide a decomposition theory of symmetric submodular systems. The theory is a generalization of the decomposition theory of 2-connected graphs developed by Tutte and can be applied to any (symmetric) submodular systems.     

A unique exchange property for bases

We define the concept of unique exchange on a sequence (X₁,…, X_m) of bases of a matroid M as an exchange of x ? X_i for y ? X_j such that y is the unique element of X_j which may be exchanged for x so that (X_i ? {x}) ∪ {y} and (X_j ? {y}) ∪ {x} are both bases. Two sequences X and Y are compatible if they are on the same multiset. Let UE(1) [UE(2)] denote the class of matroids such that every pair of compatible basis sequences X and Y are related by a sequence of unique exchanges [unique exchanges and permutations in the order of the bases]. We similarly define UE(3) by allowing unique subset exchanges. Then UE(1),UE(2), and UE(3) are hereditary classes (closed under minors) and are self-dual (closed under orthogonality). UE(1) equals the class of series-parallel networks, and UE(2) and UE(3) are contained in the class of binary matroids. We conjecture that UE(2) contains the class of unimodular matroids, and prove a related partial result for graphic matroids. We also study related classes of matroids satisfying transitive exchange, in order to gain information about excluded minors of UE(2) and UE(3). A number of unsolved problems are mentioned.     

Principal structure of submodular systems and hitchcock-type independent flows

This paper discusses the principal structure of submodular systems due to S. Fujishige. It is shown that the principal structure is the coarsest decomposition that is finer than any decomposition induced by the principal partition with respect to a minimal nonnegative superbase. The concept of Hitchcock-type independent flow is introduced so that previously known results on the principal structures for bipartite matchings, layered mixed matrices and independent matchings can be understood as applications of the present result.     

Principal structure of submodular systems and Hitchcock-type independent flows

A recent paper of mine [1] contains an error, which is not critical to the main result but still may confuse the readers. I would like to apologize this sincerely and show how to flix it.     

A property of root systems

One of the auxiliary results of a work of K. Suzuki is improved.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 75, pp. 151–153, 1978.     

Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions

We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart of the Karush-Kuhn-Tucker condition for convex programs. This work is supported by the Alexander von Humboldt fellowship (1982/83), West Germany.     

A totally geodesic property of Hopf vector fields

We prove that the Hopf vector field is unique among geodesic unit vector fields on spheres such that the submanifold generated by the field is totally geodesic in the unit tangent bundle with Sasaki metric. As an application, we give a new proof of stability (instability) of the Hopf vector field with respect to volume variation using standard approach from the theory of submanifolds and find exact boundaries for the sectional curvature of the Hopf vector field.     

On the Borel property for solutions to systems of complex vector fields

In this work we study the Borel property for smooth solutions to systems of complex vector fields associated to locally integrable structures. Inspired by the recent article [6], in which the Borel property was studied for generic submanifolds of the complex space, we prove similar results in this more general set up. In particular we obtain, for the case of corank one structures, a necessary and sufficient condition for the validity of the Borel property.     

A topological property of integrable systems

If we are given real-valued smooth functions on which are in involution, then, under some mild hypotheses, the subset of where these functions are linearly independent is not simply connected.

     

A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

On modules for which the finite exchange property implies the countable exchange property

It has been a long standing open problem whether the finite exchange property implies the full exchange property for an arbitrary module. The main results of this paper are Theorem 1.1: For modules whose idempotent endomorphisms are central, the finite exchange property implies the countable exchange property, and Theorem 2.11: Over a ring with ace on essential right ideals, the finite exchange property implies the full exchange property for every quasi-continuous module. The latter can be viewed as a partial affirmative answer to an open problem of Mohamed and Muller [8].     

A stability property of the unit vector basis ofl p

Let {e _n} be the unit vector basis ofl _p, l<p<∞, and letx _n=a_ne_n?b_nen+1. Necessary and sufficient conditions are given for the operatorT:l _p → span {x _n} defined byTe _i=x_i to be invertible.     

Decomposition of submodular functions

A decomposition theory for submodular functions is described. Any such function is shown to have a unique decomposition consisting of indecomposable functions and certain highly decomposable functions, and the latter are completely characterized. Applications include decompositions of hypergraphs based on edge and vertex connectivity, the decomposition of matroids based on three-connectivity, the Gomory—Hu decomposition of flow networks, and Fujishige’s decomposition of symmetric submodular functions. Efficient decomposition algorithms are also discussed.     

A polynomial cycle canceling algorithm for submodular flows

Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems, Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems. Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999