On Maximal S-free Convex Sets

Let S be a subset of integer points that satisfy the property that $conv(S) \cap Z^n = S$. Then a convex set K is called an S-free convex set if $int(K) \cap S = \emptyset$. A maximal S-free convex set is an S-free convex set that is not properly contained in any S-free convex set. We show that maximal S-free convex sets are polyhedra. This result generalizes a result of Basu et al. (2010) for the case where S is the set of integer points in a rational polyhedron and a result of Lovasz (1989) and Basu et al. (2009) for the case where $S$ is the set of integer points in some affine subspace of $R^n$.

Article

Download

View PDF