The fractional Helly number for separable convexity spaces

Abstract

A convex lattice set in ${\mathbb{Z}}^d$ is the intersection of a convex set in ${\mathbb{R}}^d$ with the integer lattice ${\mathbb{Z}}^d$. A classical theorem of Doignon states that the Helly number of $d$-dimensional convex lattice sets equals $2^d$, exponentially larger than the Helly number $d+1$ of ordinary convex sets in ${\mathbb{R}}^d$. By contrast, a remarkable theorem of Bárány and Matousek states that the fractional Helly number of convex lattice sets drops back down to $d+1$, matching the classical fractional Helly theorem of Katchalski and Liu. In this paper we generalize the Bárány--Matousek theorem to abstract convexity spaces (in the sense of van de Vel) that satisfy a suitable separation axiom. Our main result implies the following: if a separable convexity space has Radon number at most $r$, then its fractional Helly number is at most $2^r$. This bound is nearly tight, as illustrated by the case of box convexity in ${\mathbb{R}}^d$, whose Radon number is $\hat{I}˜(\log d)$ and fractional Helly number equals $d+1$.

12 pages