Concave cocirculations in a triangular grid Original Research Article

Let G be a planar digraph embedded in the plane such that each bounded face contains three edges and forms an equilateral triangle, and let the union image of these faces be a convex polygon. We consider the polyhedral cone image formed by the real-valued functions σ on the set of boundary edges of G with the following property: there exists a concave function c on image which is affinely linear within each bounded face and satisfies c(v) − c(u) = σ(e) for each boundary edge e = (u, v). Knutson, Tao and Woodward obtained a result on honeycombs which implies that if the polygon image is a triangle, then the cone image is described by linear inequalities of Horn’s type with respect to so-called puzzles, along with obvious linear constraints. The purpose of this paper is to give an alternative proof of that result, working in terms of discrete concave functions, rather than honeycombs. Our proof is based on a linear programming approach and a nonstandard flow model. Moreover, the result is extended to an arbitrary convex polygon image as above.