ON MAXIMAL S-FREE SETS AND THE HELLY NUMBER FOR THE FAMILY OF S-CONVEX SETS

We study two combinatorial parameters, which we denote by f(S) and h(S), associated with an arbitrary set S subset of R-d, where d is an element of N. In the nondegenerate situation, 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 parameter h(S) is the Helly number of the family of all sets that can be given as the intersection of S with a convex subset of R-d. We obtain the inequality f(S) <= h(S) for an arbitrary S, and the equality f(S) = h(S) for every discrete S. Furthermore, motivated by research in integer and mixed-integer optimization, we show that 2(d) is the sharp upper bound on f(S) in the case S = (Z(d) x R-n) boolean AND C, where n >= 0 and C subset of Rd+n is convex. The presented material generalizes and unifies results of various authors, including the result h(Z(d)) = 2(d) of Doignon, the related result f(Z(d)) = 2(d) of Lovasz, and the inequality f(Z(d) boolean AND C) = 2(d), which has recently been proved for every convex set C subset of R-d by Moran and Dey.