TY - JOUR

T1 - Transversal numbers for hypergraphs arising in geometry

AU - Alon, Noga

AU - Kalai, Gil

AU - Matoušek, Jiří

AU - Meshulam, Roy

N1 - Funding Information:
* Corresponding author. E-mail address: meshulam@math.technion.ac.il (R. Meshulam). 1 Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. 2 Supported by Charles University grants No. 158/99 and 159/99. Part of the research was done during visits to The Hebrew University of Jerusalem and to ETH Zürich and supported by these institutions. 3 Supported by the Israel Science Foundation and by NSF grant No. CCR-9987845.

PY - 2002/7

Y1 - 2002/7

N2 - The (p, q) theorem of Alon and Kleitman asserts that if F is a family of convex sets in ℝd satisfying the (p, q) condition for some p ≥ q ≥ d + 1 (i.e. among any p sets of F, some q have a common point) then the transversal number of F is bounded by a function of d, p, and q. By similar methods, we prove a (p, q) theorem for abstract set systems F. The key assumption is a fractional Helly property for the system F∩ of all intersections of sets in F. We also obtain a topological (p, d + 1) theorem (where we assume that F is a good cover in ℝd or, more generally, that the nerve of F is d-Leray), as well as a (p, 2d) theorem for convex lattice sets in ℤd. We provide examples illustrating that some of the assumptions cannot be weakened, and an example showing that no (p, q) theorem, even in a weak sense, holds for stabbing of convex sets by lines in ℝ3.

AB - The (p, q) theorem of Alon and Kleitman asserts that if F is a family of convex sets in ℝd satisfying the (p, q) condition for some p ≥ q ≥ d + 1 (i.e. among any p sets of F, some q have a common point) then the transversal number of F is bounded by a function of d, p, and q. By similar methods, we prove a (p, q) theorem for abstract set systems F. The key assumption is a fractional Helly property for the system F∩ of all intersections of sets in F. We also obtain a topological (p, d + 1) theorem (where we assume that F is a good cover in ℝd or, more generally, that the nerve of F is d-Leray), as well as a (p, 2d) theorem for convex lattice sets in ℤd. We provide examples illustrating that some of the assumptions cannot be weakened, and an example showing that no (p, q) theorem, even in a weak sense, holds for stabbing of convex sets by lines in ℝ3.

UR - http://www.scopus.com/inward/record.url?scp=0036657523&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036657523&partnerID=8YFLogxK

U2 - 10.1016/S0196-8858(02)00003-9

DO - 10.1016/S0196-8858(02)00003-9

M3 - Article

AN - SCOPUS:0036657523

VL - 29

SP - 79

EP - 101

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

IS - 1

ER -