Lectures on Jump Systems

Geelen, Jim (1996) Lectures on Jump Systems.
Technical Report , 20 p.


A jump system is a nonempty set of integral vectors that satisfy a certain exchange axiom. This notion was introduced by Bouchet and Cunningham, and popularized by recent results of Lovász. A degree system of a graph G is the set of degree sequences of all subgraphs of G. Degree systems are the primary example of jump systems. Other examples come from matroids and from two generalizations of matroids (polymatroids and delta-matroids). Discussion of these special cases will be kept to a minimum, and will only be used to motivate certain results. The main result is a min-max formula of Lovász for the distance of an integral point from a jump system. This formula generalizes two of the more important min-max theorems in combinatorial optimization; namely, Tutte's f-factor-theorem, and Edmonds' matroid intersection theorem. Other points of interest are the existence of a greedy algorithm for optimizing linear functions, and a characterization of the convex hulls of jump systems. Even apart from the possibility of obtaining very general theorems, jump systems are appealing due to their simple definition and elegant structure.

Download: [img] Postscript
Download (233kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-246
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/246