Bounded VC-dimension implies a fractional Helly theorem
type: Item
instance of: scholarly article
title: Bounded VC-dimension implies a fractional Helly theorem
zbMATH Open document ID: 1059.52012
published in: Discrete \& Computational Geometry
publication date: 2004-09-22T00:00:00Z
review text: The classical theorem of Helly states that if \(C\) is a finite family of convex sets in \(R^d\), such that any \(d+1\) or fewer of the sets of \(C\) have a non-empty intersection then the intersection of all sets of \( C\) is non-empty. In this paper it is proved that every set system of bounded VC-dimension has fractional Helly property. To be more concrete, if the dual shatter function of a set system \(F\) is bounded by \(o(m^k)\), then \(F\) has fractional Helly number \(k\). This further implies a \((p,k)\)-theorem: for every \(F\) as above and every \(p \geq k\), there exists \(T\) such that if \(G \subseteq F\) is a finite subfamily where among every \(p\) sets, some \(k\) intersect, then \(G\) has a transversal of size \(T\). Examples, where the assumptions about bounded dual shatter functions applies, include families of sets in \(R^d\) definable by a bounded number of polynomial inequalities of bounded degree. In this case the fractional Helly number \(d+1\) is obtained.
reviewed by: S. Nickel
Mathematics Subject Classification ID: 52A35
zbMATH DE Number: 2101564
zbMATH Keywords: fractional Helly property
zbMATH Keywords: transversal
author: Jiří Matoušek
MaRDI profile type: Publication
full work available at URL: s00454-003-2859-z
OpenAlex ID: W2007940480
DOI: 10.1007/S00454-003-2859-Z
description: scientific article; zbMATH DE number 2101564