A topological colorful Helly theorem

Date

August 19, 2003

Speaker

Gil Kalai

Affiliation

Hebrew University

Overview

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 Rn 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 and discuss related issues.

Gil Kalai, joint work with Roy Meshulam

Speakers

Gil Kalai

Gil Kalai is Professor of Mathematics at the Hebrew University of Jerusalem, He was the recipient of the Pólya Prize in 1992, the Erdos Prize of the Israel Mathematical Society in 1993, and the Fulkerson Prize in 1994. He is known for finding variants of the simplex algorithm that can be proven to run in subexponential time, for showing that every monotone property of graphs has a sharp phase transition and for solving Borsuk’s conjecture on the number of pieces needed to partition convex sets into subsets of smaller diameter and for other fundamental work in combinatorics and convexity.