## Abstract

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, 2^{d}) 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}.

Original language | English (US) |
---|---|

Pages (from-to) | 79-101 |

Number of pages | 23 |

Journal | Advances in Applied Mathematics |

Volume | 29 |

Issue number | 1 |

DOIs | |

State | Published - Jul 1 2002 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Applied Mathematics