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.
|