Carathéodory, Helly, and Radon Numbers for Sublattice and Related Convexities

Maurice Queyranne () and Fabio Tardella ()
Additional contact information
Maurice Queyranne: Sauder School of Business, University of British Columbia, Vancouver, B.C., Canada V6T 1Z2; CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Fabio Tardella: Department of Methods and Models for Economics, Territory and Finance, Sapienza University of Rome, Rome, 00161, Italy

Mathematics of Operations Research, 2017, vol. 42, issue 2, 495-516

Abstract: The Carathéodory, Helly, and Radon numbers are three main invariants in convexity theory. 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 in submodular optimization (lattice programming) and in monotone comparative statics of optimization and fixed point problems. We also consider integral L-natural convexities, induced by dual network flow constraint systems. We determine the exact Carathéodory, Helly, and Radon numbers of most of these convexities, and very close upper and lower bounds for the other Carathéodory numbers. Our results imply, for example, that if a set can be obtained with unions and intersections from a given family of subsets of a finite set then it can be obtained with unions and intersections from a small subfamily. We also show that finding the Carathéodory number of integral L-natural convexities reduces to an extremal problem in the theory of permutations, solved in a companion paper. We leave as open problems the determination of the Helly and Radon numbers of the integer convex sublattice convexity.

Keywords: convexity; lattice theory; combinatorics; abstract convexity; discrete convexity; Carathéodory number; Helly number; Radon number (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0815 (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:inm:ormoor:v:42:y:2017:i:2:p:495-516

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().