×

Partial intersection theorem and flows in abstract networks. (English) Zbl 0916.05017

Author’s abstract: The aim of this paper is to introduce a general framework for various results regarding constructions of matroids and (generalized) polymatroids—for instance, the basic operations on (generalized) polymatroids and constructions of transversal matroids, gammoids, and their generalization. All of them are covered by the following theorem: If \(\mathbb{P}_1\) and \(\mathbb{P}_2\) are generalized polymatroids in \({\mathfrak R}^n \oplus {\mathfrak R}^m\), respectively, and \(\mathbb{P}_1'\) is the set of the vectors from \(\mathbb{P}_1\) whose projections to \({\mathfrak R}^m\) are in \(\mathbb{P}_2\), then the projection of \(\mathbb{P}_1'\) to \({\mathfrak R}^n\) is a generalized polymatroid. An equivalent statement is obtained using a flow model that has many common features with the concept of group-valued flows.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
90B10 Deterministic network models in operations research
Full Text: DOI