Tuesday, June 18
10:00 AM-12:00 PM
Room 303
MS5
Delta-Matroids and Jump Systems
Delta-matroids are a fairly new generalization of matroids; the first papers appeared within the last ten years. They share many of the attractive properties of matroids---greedy algorithm, polyhedral description, nice constructions. Among other things, delta-matroids permit generalization of some of the central problems of matroid theory, such as representability and partitioning. Jump systems are sets of lattice points satisfying a single axiom, and delta-matroids turn out to be exactly those that are contained in the unit cube. The first paper on jump systems appeared in 1995. The convex hulls of jump systems form a nice class of "bisubmodular" polyhedra. However, unlike their special case, the integral polymatroids of Edmonds, they are not determined by these polyhedra. Recent results of Lovasz suggest that jump systems provide a valuable setting for several of the fundamental results of combinatorial optimization. The minisymposium speakers will provide a survey of recent results on delta-matroids and jump systems.
Organizer: William H. Cunningham
University of Waterloo, Canada
- 10:00 Delta-Matroids and Jump Systems
- Andre Bouchet, Universit‚ du Maine, France
- 10:30 Representable Delta-Matroids
- James F. Geelen, CWI, The Netherlands
- 11:00 The Membership Problem in Jump Systems
- Laszlo Lovasz, Yale University
- 11:30 Gaps in Jump Systems
- Andras Sebo, Universit‚ J. Fourier, France
MEM, 3/21/96