Quantitative \((p, q)\) theorems in combinatorial geometry (Q2012541)

Let \(\mathcal{C}_d\) be the family of convex sets in \(\mathbb{R}^d\). To present the main result of the paper, we need to introduce a few concepts concerning a function\(f: \mathcal{C}_d \rightarrow \mathbb{R}^+ \cup \{\infty\}\). Such a function \(f\) admits a Helly theorem if given \(0 < \epsilon < 1\) there is an integer \(H(f, d, \epsilon)\) such that the following property holds. For any finite family \(\mathcal{F}\subset \mathcal{C}_d\) and \(\lambda > 0\), if every subfamily \(\mathcal{F}^\prime\) of cardinality at most \(H(f, d, \epsilon)\) satisfies \(f\big(\bigcap \mathcal{F}^\prime\big) \geq \lambda\), then \(f\big(\bigcap \mathcal{F}\big) \geq (1 - \epsilon)\lambda\). It's said that \(f\) admits an approximation by inscribed polytopes if for every \(0 < \epsilon < 1\) there is a constant \(C(f, d, \epsilon)\) such for every \(0 \leq \lambda < \infty\) and every \(K \in \mathcal{C}_d\) with \(f(K) \geq \lambda\), there is a polytope \(P \in \mathbb{R}^d\) such that: (i) \(P \subset K\); (ii) \(P\) has at most \(C(f , d, \epsilon)\) vertices; (iii) \(f(P) \geq (1 - \epsilon)\lambda\). Finally, we say that \(f\) admits a fractional Helly theorem if, given \(0 < \epsilon < 1\) there is an integer \(F = F(f, d, \epsilon)\) such that the following holds. For any \(0 < \alpha \leq 1\) there is a \(\beta = \beta (\alpha, f, d, \epsilon) > 0\) such that given any finite family \(\mathcal{F} \subset \mathcal{C}_d\), if there are at least \(\alpha\binom{|\mathcal{F}|}{F}\) subfamilies \(\mathcal{A} \subset \mathcal{F}\) of cardinality \(F\) that satisfy \(f(\bigcap \mathcal{A}\big) \geq 1\), then there is a subfamily \(\mathcal{F}^\prime \subset\mathcal{F}\) of cardinality at least \(\beta |\mathcal{F}|\) such that \(f(\bigcap \mathcal{F}^\prime\big) \geq 1 - \epsilon\). The authors obtain the following \; Theorem. Let \(f: \mathcal{C}_d \rightarrow \mathbb{R}^+ \cup \{\infty\}\) be a monotone function that admits a Helly theorem, approximations by inscribed polytopes, and a fractional Helly theorem, and let \(\epsilon > 0\). Then, given \(p \geq q \geq F(f, d, \frac{\epsilon}{2})\), there is a constant \(c = c(f, p, q, d, \epsilon)\) such that the following holds. For any finite family \(\mathcal{F} \subset \mathcal{C}_d\), if out of every \(p\) elements of \(\mathcal{F}\) there is a \(q\)-tuple \(\mathcal{A}\) such that \(f(\bigcap \mathcal{A}) \geq 1\) then there is a family \(\mathcal{T}\) of at most \(c\) convex sets \(K_1, K_2, \dots, K_c\) such that \(f(K_i) \geq 1 - \epsilon\) for each \(i\) and every set in \(\mathcal{F}\) contains at least one set in \(\mathcal{T}\). The previous theorem is then applied to functions such as the volume, surface area or number of points of a discrete set.