printable pdf
比利时vs摩洛哥足彩 ,
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

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