Radon numbers and the fractional Helly theorem (Q2022784)

A convexity space is a pair \((X, \mathcal{C})\), where \(X\) is a non-empty set and \(\mathcal{C}\) is a family of subsets of \(X\) satisfying the following conditions: (i) \(\emptyset, X \in \mathcal{C}\); (ii) if \(\mathcal{D} \subset \mathcal{C}\) is non-empty, then \(\bigcap_{C \in \mathcal{D}} C \in \mathcal{C}\); (iii) if \(\mathcal{D} \subset \mathcal{C}\) is non-empty and totally ordered by inclusion, then \(\bigcup_{C \in \mathcal{D}} C \in \mathcal{C}\). The members of \(\mathcal{C }\) are called convex sets. Given a subset \(Y \subset X\), the convex hull of \(Y\), denoted by \(\operatorname{conv}(Y )\), is the intersection of all convex sets containing \(Y\). The Radon number of \(X\) is the smallest integer \(r_2\) (if it exists) such that any subset \(P \subset X\) with \(|r_2| \geq 2\) can be partitioned into two parts \(P_1\) and \(P_2\) such that \(\operatorname{conv}(P_1 )\cap \operatorname{conv}(P_2 )\neq \emptyset\). The following fractional Helly theorem for convexity spaces with bounded Radon number is the main result of the paper. For every \(r \geq 3\) and \(\alpha \in (0, 1)\) there exists an \(m = m(r)\) and a \(\beta = \beta(\alpha, r)\) with the following property: Let \(F\) be a finite family of \(n \geq m\) convex sets in a convexity space with Radon number at most \(r\). If at least \(\alpha \binom nm\) of the \(m\)-tuples of \(F\) have non-empty intersection, then there are at least \(\beta n\) members of \(F\) whose intersection is non-empty. As a consequence, a weak \(\varepsilon\)-net theorem for convexity spaces with bounded Radon number is obtained.