Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra

Abstract

This paper relates an axiomatic generalization of matroids, called a jump system, to polyhedra arising from bisubmodular functions. Unlike the case for usual submodularity, the points of interest are not all the integral points in the relevant polyhedron but form a subset of them. However, it is shown that the convex hull of the set of points of a jump system is a bisubmodular polyhedron, and that the integral points of an integral bisubmodular polyhedron determine a (special) jump system. The authors prove addition and composition theorems for jump systems, which have several applications for delta-matroids and matroids.