比利时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
****************************