## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, May 02, 2013, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Uli Wagner (Institute of Science and Technology Austria)

## Helly vs. Betti

Helly's theorem, a basic result in convex geometry, asserts the following: If F={C1,...,Cn} is a finite family of convex sets in Rd whose intersection is empty then there exists a "certificate of bounded size" for this, namely a subfamily G of F of d+1 sets whose intersection is already empty.

This result has led to a whole line of research that investigates Helly-type theorems. In general, the Helly number of a finite family F of sets is defined as the smallest integer h=h(F) such that if the intersection of all sets in F is empty, then there is already some subfamily of at most h sets whose intersection is empty. The aim in this line of business is to find conditions on F that guarantee that the Helly number is bounded (independently of n, the size of the family).

One important class of Helly-type theorems investigates topological conditions on the sets in F and their intersections. One way of measuring the topological complexity of a subset of Rd is in terms of its Betti numbers bk, which, roughly speaking, measure the number of k-dimensional "holes" in the set.

Here, we present the following Helly-type result that, qualitatively, unifies and generalizes a number of Helly-type theorems due to Amenta, Matousek, Kalai and Meshulam, and others.

Theorem. Suppose that F is a finite family of arbitrary sets in Rd such that the intersection of any subfamily of F has the first d/2 Betti numbers b0,...,bd/2-1 bounded by some number B. Then the Helly number of F is bounded by some number h=h(d,B) that depends only on d and on B.

Joint work with X. Goaoc, P. Paták, Z. Safernová, and M. Tancer

Information for students and suggested topics for student talks