Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra

Authors:
  • ABAndré Bouchet
    André Bouchet
  • WCWilliam H. Cunningham
    William H. Cunningham
Publisher website
Google Scholar
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.

This publication has 10 references indexed in Scilit: