Maximal \(S\)-free convex sets and the Helly number (Q2835843)

Let \(S\) be a given subset of \(\mathbb{R}^d\). A family \(\{C_1, \dots, C_m\}\) of convex subsets of \(\mathbb{R}^d\) is a critical family for \(S\) (of size \(m\)) if \(\bigcap_{j=1}^m C_j \cap S = \emptyset\) and \(\bigcap_{j\neq i} C_j \cap S \neq \emptyset\) for each index \(i\). The Helly number of \(S\) is \(h(S) = \sup\{m : m \text{ is the size of a critical family for } S\}\). The facet number \(f(S)\) is the largest possible number of facets of a \(d\)-dimensional polyhedron \(L\) such that the interior of \(L\) is disjoint with \(S\) and \(L\) is inclusion-maximal with respect to this property. The authors prove first that \(h(S) \leq (d + 1)f(S)\), when \(S\) is a closed subset of \(\mathbb{R}^d\). This bound is tight: if \(S\) is a \(d\)-dimensional closed convex set, then \(f(S) = 1\) while \(h(S) = d + 1\). Then, when \(S = S_1 \times \mathbb{R}^q\) and \(S_1\) is discrete, the authors show that \(h(S) = h(S_1)(q+1)\). Finally, the inequality \(h(S_1\times S_2) \geq h(S_1) h(S_2)\) is established in the case when the sets \(S_1, S_2\) are both discrete.