A topological colorful Helly theorem

Gil Kalai

Yale and Hebrew University

April 16,
refreshments at 3:45pm


Let F be a finite family of convex sets in n-dimensional Euclidean space. Helly's theorem asserts that if every n+1 members of the family has a point in common then there is a point in common to all members of the family.

Lovasz proved the following extension of Helly theorem:

Colorful Helly Theorem. Consider n+1 families of convex sets in R^n and suppose that for every choice of n+1 sets, one from each family there is a point in common to all these sets. Then one of the families is intersecting.

This innocent looking extension is quite deeper than Helly's original theorem and the associated Caratheodory-type theorem of Barany has many applications in discrete geometry.

Helly himself realized that in his theorem convex sets can be replaced by topological cells if you impose the requirement that all non-empty intersections of these sets are again topological cells. (Since the intersection of convex sets is also convex this requirement is automatically satisfied in the original geometric version.) Helly's topological version of his theorem follows from the later "nerve theorems" of Leray and others.

In the lecture I will present a topological version for Lovasz' colorful Helly theorem present a matroidal generalization and discuss related issues.

Speaker's Contact Info: kalai(at-sign)cs.yale.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on April 13, 2004 at 11:20 AM. Copyright © 1998-99, Sara C. Billey. All rights reserved.