Carathéodory, Helly and Radon Numbers for Sublattice Convexities

M. Queyranne () and F. Tardella ()
Additional contact information
M. Queyranne: Université catholique de Louvain, CORE, Belgium
F. Tardella: Dipartimento MEMOTEF, Sapienza University of Rome

No 2015010, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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.

Date: 2015-04-02
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2015.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2015010

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().