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

Registration | Hotel Information | Dormitory Information | Transportation | Speaker Index


MEM, 3/21/96