Loading...
Please wait, while we are loading the content...
Similar Documents
A fractional Helly theorem for convex lattice sets
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bárány, Imre Matousek, Jirí |
| Copyright Year | 2003 |
| Abstract | A set of the form C boolean AND Z(d), where C subset of or equal to R-d is convex and Z(d) denotes the integer lattice, is called a convex lattice set. It is known that the Helly number of d-dimensional convex lattice sets is 2(d). We prove that the fractional Helly number is only d + 1: For every d and every alpha is an element of (0, 1] there exists beta>0 such that whenever F-1,...,F-n are convex lattice sets in Z(d) such that boolean AND(iis an element ofI) F-i not equal 0 for at least alpha((n)(d+1)) index sets I subset of or equal to {1,2,...,n} of size d + 1, then there exists a (lattice) point common to at least betan of the F-i. This implies a (p, d + 1)-theorem for every p greater than or equal to d + 1; that is, if F is a finite family of convex lattice sets in Zd such that among every p sets of F, some d + 1 intersect, then F has a transversal of size bounded by a function of d and p. (C) 2003 Elsevier Science (USA). All rights reserved. |
| Starting Page | 227 |
| Ending Page | 235 |
| Page Count | 9 |
| File Format | PDF HTM / HTML |
| DOI | 10.1016/S0001-8708(02)00037-3 |
| Alternate Webpage(s) | http://www.ms.mff.cuni.cz/acad/kam/matousek/fhd.ps.gz |
| Alternate Webpage(s) | https://users.renyi.hu/~barany/cikkek/91.pdf |
| Alternate Webpage(s) | http://www.renyi.hu/~barany/cikkek/91.pdf |
| Alternate Webpage(s) | https://doi.org/10.1016/S0001-8708%2802%2900037-3 |
| Volume Number | 174 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
