Structural theorems for submodular functions,polymatroids and polymatroid intersections

This paper presents a lattice-theoretic decomposition method for submodular functions. This decomposition is derived from a lattice, called a skeleton, which has the property that the specified submodular function is reduced to be modular on it.Several types of skeletons arise from the various kinds of minimization problems of submodular functions. The minimization problem associated with the well-known min-max eqaulity of the polymatroid intersection problem affords a skeleton, which is shown to provide a direct-sum decomposition of the maximum common independent vectors, i.e. the solutions of the intersection problem. Furthermore, a parametrized polymatroid intersection problem is considered and the construction of its solution, called a universal pair, is described. This paper consists of the main results of the author's unpublished works 27], 35].