On Radon and fractional Helly theorems

Abstract: Radon theorem plays a basic role in many results of combinatorial convexity. It says that any set of d+2 points in R^d can be split into two parts so that their convex hulls intersect. It implies Helly theorem and as shown recently also its more robust version, so-called fractional Helly theorem. By standard techniques this consequently yields an existence of weak epsilon nets and a (p,q)-theorem.

We will show that we can obtain these results even without assuming convexity, replacing it with very weak topological conditions. More precisely, given an intersection-closed family F of subsets of R^d, we will measure the complexity of F by the supremum of the first d/2 Betti numbers over all elements of F. We show that bounded complexity of F guarantees versions of all the results mentioned above.

Based on joint work with Xavier Goaoc and Andreas Holmsen.

computational geometrydiscrete mathematicsdata structures and algorithmscombinatorics

Audience: researchers in the discipline

Discrete and Computational Geometry Seminar in Paris

Series comments: Language is English if anyone in the audience prefers it (otherwise French).

Links and passwords for the talks are on the seminar homepage: monge.univ-mlv.fr/~hubard/GAC/