Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
The membership problem in jump systems

László Lovasz


A jump system is a set of lattice points satisfying a certain exchange axiom. This notion was introduced by Bonchet and Cunningham, as a common generalization (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's f-factor-theorem and Edmonds matroid intersection theorem


Publication typeInproceedings
> Publications > The membership problem in jump systems