Radon numbers and the fractional Helly theorem

2019/03/04 by Holmsen, Andreas F., Lee, Dong-Gyu
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1903.01068

Abstract

A basic measure of the combinatorial complexity of a convexity space is its Radon number. In this paper we show a fractional Helly theorem for convexity spaces with a bounded Radon number, answering a question of Kalai. As a consequence we also get a weak epsilon-net theorem for convexity spaces with a bounded Radon number. This answers a question of Bukh and extends a recent result of Moran and Yehudayoff.

Related

• Helly type problems in convexity spaces
• The fractional Helly number for separable convexity spaces
• Radon numbers grow linearly
• A fractional Helly theorem for set systems with slowly growing homological shatter function
• Helly-type theorems for separated d-intervals