Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Imre Barany

University College London and Mathematical Institute of the Hungarian Academy of Sciences

The fractional Helly number for convex lattice sets

Abstract:

A set of the form $C\\cap\\bf{Z}^d$, where $C\\subseteq R^d$ is convex and $Z^d$ denotes the integer lattice, is called a {\\it convex lattice set}. I will explain that the Helly number of $d$-dimensional convex lattice sets is $2^d$. However, the {\\it fractional Helly number\\/} is only $d+1$: For every $d$ and every $\\alpha\\in (0,1]$ there exists $\\beta>0$ such that whenever $F_1,\\ldots,F_n$ are convex lattice sets in $\\bf{Z}^d$ such that $\\bigcap _{i\\in I} F_i\\neq\\emptyset$ for at least $\\alpha{n\\choose d+1}$ index sets $I\\subseteq\\{1,2,\\ldots,n\\}$ of size $d+1$, then there exists a (lattice) point common to at least $\\beta n$ of the $F_i$. This implies a $(p,d+1)$-theorem for every $p\\geq d+1$; that is, if $H$ is a finite family of convex lattice sets in $\\bf{Z}^d$ such that among every $p$ sets of $H$, some $d+1$ intersect, then $H$ has a transversal of size bounded by a function of $d$ and $p$. This is joint work with J. Matousek.

Host: Van Vu

October 28, 2003

3:00 PM

AP&M 7321

****************************