Discrete convexity: Convexity for functions defined on discrete spaces (Q1613357)

The concept of discrete convexity for a real-valued function defined on a discrete space is an extension of the convexity definition of continuous functions. The equivalence of discrete convexity and the conventional definition of increasing (non-decreasing) first forward differences of functions of single variables is established. A further extension of the discrete convexity with submodularity yields the concept of strong discrete convexity. A strongly convex function is proved to have positive semidefinite matrix of second forward differences, and a partial converse of this result is provided.