A Helly-type theorem for unions of convex sets (Q1361809): Difference between revisions

In this paper, it is shown that for every \(d,k\geq 1\), there exist numbers \(q(d,k)\) and \(h(d,k)\) such that any family \({\mathcal K}\) of subsets of \(\mathbb{R}^d\) for which the intersection of \(q\) or fewer elements of \({\mathcal K}\) is a union of at most \(k\) convex sets, has Helly number at most \(h\). (This result was proved, in a different way, by Alon and Kalai, in 1995.) A related ``topological Helly-type theorem'' is also proved. There is an interesting section on related results, in which connections to linear programming and to other topics in convexity theory are summarized. In the proof of the geometric theorem, the author first introduces a property, with a combinatorial flavor, that is satisfied by unions of at most \(k\) convex sets in \(\mathbb{R}^d\). It is then shown, using order-of-magnitude arguments, that if \({\mathcal K}\) is a family of sets in \(\mathbb{R}^d\), such that the intersection of any finite subfamily has this new property, it has a Helly number that is less than a certain bound. This bound can, in principle, be computed on the basis of the results in the paper, but is quite large and (according to the author) perhaps not the best possible.