View PDF HTML (experimental)

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 $\Theta(\log d)$ and fractional Helly number equals $d+1$.

Submission history

From: Andreas Holmsen [view email]
[v1] Mon, 2 Dec 2024 12:34:43 UTC (14 KB)
[v2] Fri, 6 Dec 2024 15:40:45 UTC (13 KB)
[v3] Tue, 18 Feb 2025 09:41:51 UTC (13 KB)
[v4] Sun, 19 Jul 2026 01:53:27 UTC (16 KB)