The University of Michigan Combinatorics Seminar
Fall 2003
October 17, 4:10-5:00, 3866 East Hall

The fractional Helly number for convex lattice sets

Imre Bárány

Renyi Institute (Budapest) and University College (London)


A convex lattice set is an intersection of a convex subset of Rd with the integer lattice Zd. I will explain that the Helly number of d-dimensional convex lattice sets is 2d. However, the fractional Helly number is only d+1:

For every d and every a in (0,1], there exists b>0 such that if F1,... ,Fn are convex lattice sets in Zd such that the intersection of Fi, i in I, is not empty for at least a(n choose (d+1)) of the index sets I of size d+1 contained in {1,2, ... ,n}, then there exists a (lattice) point common to at least bn of the Fi.
This implies a (p,d+1)-theorem for every p greater than or equal to d+1; that is, if FF is a finite family of convex lattice sets in Zd such that among every p sets of FF, some d+1 intersect, then FF has a transversal of size bounded by a function of d and p. This is joint work with J.Matousek.