Concave cocirculations in a triangular grid

Details Concave cocirculations in a triangular grid Concave cocirculations in a triangular grid

2003-04-21

arxiv.org/abs/math/0304289v1

Linear Algebra and its Applications, 400C, 2005, 67-89

Mathematics

Combinatorics

21 pages

Scientific paper

Let $G=(V(G),E(G))$ be a planar digraph embedded in the plane in which all inner faces are equilateral triangles (with three edges in each), and let the union $\Rscr$ of these faces forms a convex polygon. The question is: given a function $\sigma$ on the boundary edges of $G$, does there exist a concave function $f$ on $\Rscr$ which is affinely linear within each bounded face and satisfies $f(v)-f(u)=\sigma(e)$ for each boundary edge $e=(u,v)$? The functions $\sigma$ admitting such an $f$ form a polyhedral cone $C$, and when the region $\Rscr$ is a triangle, $C$ turns out to be exactly the cone of boundary data of honeycombs. Studing honeycombs in connection with a problem on spectra of triples of zero-sum Hermitian matrices, Knutson, Tao, and Woodward \cite{KTW} showed that $C$ is described by linear inequalities of Horn's type with respect to so-called {\em 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 finctions, rather than honeycombs, and using only linear programming and combinatorial tools. Moreover, we extend the result to an arbitrary convex polygon $\Rscr$.

Affiliated with

Also associated with

No associations

Rating

Concave cocirculations in a triangular grid does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Concave cocirculations in a triangular grid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concave cocirculations in a triangular grid will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218078