Isotone functions, dual cones, and networks

AbstractIf the collection of all real-valued functions defined on a finite partially ordered set S of n elements is identified in the natural way with Rn, it is obvious that the subset of functions that are isotone or order preserving with respect to the given partial order constitutes a closed, convex, polyhedral cone K in Rn. The dual cone K* of K is the set of all linear functionals that are nonpositive of K. This article identifies the important geometric properties of K, and characterizes a nonredundant set of defining equations and inequalities for K* in terms of a special class of partitions of S into upper and lower sets. These defining constraints immediately imply a set of extreme rays spanning K and K*. One of the characterizations of K* involves feasibility conditions on flows in a network. These conditions are also used as a tool in analysis