Submodular Functions, Matroids, and Certain Polyhedra.

The viewpoint of the subject of matroids, and related areas of lattice theory, has always been, in one way or another, abstraction of algebraic dependence or, equivalently, abstraction of the incidence relations in geometric representations of algebra. Often one of the main derived facts is that all bases have the same cardinality. (See Van der Waerden, Section 33.) From the viewpoint of mathematical programming, the equal cardinality of all bases has special meaning — namely, that every basis is an optimum-cardinality basis. We are thus prompted to study this simple property in the context of linear programming. It turns out to be useful to regard “pure matroid theory”, which is only incidentally related to the aspects of algebra which it abstracts, as the study of certain classes of convex polyhedra. (1) A matroid M = (E,F) can be defined as a finite set E and a nonempty family F of so-called independent subsets of E such that (a) Every subset of an independent set is independent, and (b) For every A ⊆ E, every maximal independent subset of A, i.e., every basis of A, has the same cardinality, called the rank, r(A), of A (with respect to M). (This definition is not standard. It is prompted by the present interest). (2) Let RE denote the space of real-valued vectors x = [xj], j ∈ E. Let R+E = {x: 0 ≤ x ∈ RE}. (3) A polymatroid P in the space RE is a compact non-empty subset of R+E such that (a) 0 ≤ x0 ≤ x1 ∈ P = ⇒ x0 ∈ P. (b) For every a ∈ R+E, every maximal x ∈ P such that x ≤ a, i.e., every basis x of a, has the same sum j∈E xj, called the rank, r(a), of a (with respect to P).