Bounded VC-dimension implies a fractional Helly theorem

DOI10.1007/s00454-003-2859-zzbMath1059.52012OpenAlexW2007940480MaRDI QIDQ1880214

Ji{ří} Matoušek

Publication date: 22 September 2004

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-003-2859-z

zbMATH Keywords

transversalfractional Helly property

Mathematics Subject Classification ID

Helly-type theorems and geometric transversal theory (52A35)

Related Items (max. 100)

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Helly-type theorems for the diameter ⋮ Improved bounds on the Hadwiger-Debrunner numbers ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Combinatorial properties of nonarchimedean convex sets ⋮ From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Mini-workshop: Topological and differential expansions of o-minimal structures. Abstracts from the mini-workshop held November 27 -- December 3, 2022 ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ Fractional Helly theorem for Cartesian products of convex sets ⋮ Approximate subgroups with bounded VC-dimension ⋮ A definable \((p,q)\)-theorem for NIP theories ⋮ Helly’s theorem: New variations and applications ⋮ Definably amenable NIP groups ⋮ DEFINABLE AND INVARIANT TYPES IN ENRICHMENTS OF NIP THEORIES ⋮ DP-MINIMALITY: INVARIANT TYPES AND DP-RANK ⋮ Quantitative \((p, q)\) theorems in combinatorial geometry ⋮ Two refinements of the bound of Sauer, Perles and Shelah, and of Vapnik and Chervonenkis ⋮ Radon numbers and the fractional Helly theorem ⋮ From a $(p,2)$-Theorem to a Tight $(p,q)$-Theorem ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ VC-dimension and Erdős-Pósa property ⋮ Covering nearly surface-embedded graphs with a fixed number of balls ⋮ A note on smaller fractional Helly numbers ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ On the transversal number and VC-dimension of families of positive homothets of a convex body ⋮ Externally definable sets and dependent pairs II ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs ⋮ Some Themes Around First Order Theories Without the Independence Property ⋮ Helly-type problems

This page was built for publication: Bounded VC-dimension implies a fractional Helly theorem