Discrete convexity

V. I. Danilov ; G. A. Koshevoy

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems. Part XI, Tome 312 (2004), pp. 86-93

Résumé

In the paper we explain what sets and functions on the lattice $\mathbb Z^n$ could be called convex. The basis of our theory is the following three main postulates of the classic convex analysis: concave functions are stable under summation, they are also stable under convolution, and the superdifferential of a concave function is nonempty at each point of the domain. Interesting classes of discrete concave functions (and even dual) arise if we require either the existence of superdifferentials and stability under convolution or the existence of superdifferentials and stability under summation. The corresponding classes of convex sets are obtained as the affinity domains of such discretely concave functions. The first type classes are stable under summation and the second type classes are stable under intersection. In both type classes the separation theorem holds true. Unimodular sets play an important role in the classification of such classes. The so-called polymatroidal discretely concave functions, the most widespread among applications, are related to the unimodular system $\mathbb A_n:=\{\pm e_i,e_i-e_j\}$. Such functions naturally appear in mathematical economics, play an important role for solution the Horn problem, for describing submodule invariants over rings with discrete valuation, in Gelfand–Tzetlin patterns and so on.