Discrete convexity and unimodularity. I

2003/04/21 by V. I. Danilov, В. И. Данилов, Danilov, V. I. +3 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #math.CO

paper · pdf · doi:10.48550/arxiv.math/0304291

26 pages, Latex

arxiv created 2003/04/21 · openalex publication_date 2003/04/21 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we develop a theory of convexity for a free Abelian group M (the lattice of integer points), which we call theory of discrete convexity. We characterize those subsets X of the group M that could be call "convex". One property seems indisputable: X should coincide with the set of all integer points of its convex hull co(X) (in the ambient vector space V). However, this is a first approximation to a proper discrete convexity, because such non-intersecting sets need not be separated by a hyperplane. This issue is closely related to the question when the intersection of two integer polyhedra is an integer polyhedron. We show that unimodular systems (or more generally, pure systems) are in one-to-one correspondence with the classes of discrete convexity. For example, the well-known class of g-polymatroids corresponds to the class of discrete convexity associated to the unimodular system A_n:=± e_i, e_i-ej in Zⁿ.

Cited by

• Dynamics of multidimensional Simple Clock Auctions
• Integrating Aggregated Electric Vehicle Flexibilities in Unit Commitment Models using Submodular Optimization
• Oda's conjecture for reflexive polytopes: some special cases

Related

• More on discrete convexity
• On Arnold's Problem on the Classifications of Convex Lattice Polytopes
• Discrete Midpoint Convexity
• Groups of convex bodies
• Inclusion and Intersection Relations Between Fundamental Classes of Discrete Convex Functions