A Fractional Helly Theorem for BoxesAlgebra & Discrete Mathematics
|Prof. Deborah Oliveros, CINNMA-UNAM
|Mon, Apr 7 2014, 12:10PM
Helly’s theorem is perhaps one of the most widely used theorems in discrete geometry, and states that if every d+1 tuple of a finite family of convex sets in the euclidean space intersect, then all the sets of the family intersect. If not necessarily all, but a fraction of the (d+1)-tuples of the sets intersect, then the Fractional Helly Theorem states that a fraction of the sets must have a point in common. In this talk we will discuss an interesting behavior of fractional Helly’s theorem for the family of n-dimensional Boxes, (with edges parallel to the coordinate axes) an its relation with extremal graph theory.