Carathéodory, Helly and Radon Numbers for Sublattice Convexities

The Carathéodory, Helly, and Radon numbers are three main invariants in convexity theory. They relate, respectively, to minimal representations of points in a convex hull; to the size of minimal infeasible inequality systems; and to VC-dimensions and the existence of centerpoints (generalized medians). These invariants have been determined, exactly or approximately, for a number of different convexity structures. We consider convexity structures defined by the sublattices and by the convex sublattices of finite-dimensional Euclidian, integer and Boolean spaces. Such sublattices arise as feasible sets in submodular optimization (lattice programming) and in monotone comparative statics of optimization and fixed-point problems. We present new results on the exact Carathéodory numbers for these sublattice convexities. Our results imply, for example, that if a subset of a finite set can be obtained with unions and intersections from a given family of subsets of , then can be obtained with unions and intersections from a small subfamily of . Convex sublattice and integral L-natural convexities are induced by polyhedra defined by dual generalized network flow constraint systems. We reduce the problem of finding the Carathéodory number for the integral L-natural convexity to an extremal problem in the theory of permutations, namely, finding the maximum size of a minimal cover of all ordered pairs of elements from a finite set using permutations of that set; this extremal problem is solved in a companion paper co-authored with Eric Balandraud. We also find very close upper and lower bounds for the other Carathéodory numbers, and the exact Helly and Radon numbers of most of these convexities. We leave as open problems the determination of the Helly and Radon numbers of the integer convex sublattice convexity.