The Membership Problem in Jump Systems
László Lovász · Journal of Combinatorial Theory Series B · 1997
A jump system is a set of lattice points satisfying a certain exchange axiom. This notion was introduced by Bouchet and Cunningham [2], as a common generalization of (among others) the sets of bases of a matroid and degree sequences of subgraphs of a graph. We prove, under additional assumptions, a min-max formula for the distance of a lattice point from a jump system. The conditions are met in the examples above, and so our formula contains, as special cases, Tutte'sf-factor-theorem and Edmonds' matroid intersection theorem.