Integer concave cocirculations and honeycombs

Details Integer concave cocirculations and honeycombs Integer concave cocirculations and honeycombs

2004-01-23

arxiv.org/abs/math/0401313v1

Lecture Notes in Computer Sci., 3064, 2004, 368-387

Mathematics

Combinatorics

20 pages, 12 figures, submitted to IPCO2004

Scientific paper

A convex triangular grid is represented by a planar digraph $G$ embedded in the plane so that (a) each bounded face is surrounded by three edges and forms an equilateral triangle, and (b) the union $\Rscr$ of bounded faces is a convex polygon. A real-valued function $h$ on the edges of $G$ is called a concave cocirculation if $h(e)=g(v)-g(u)$ for each edge $e=(u,v)$, where $g$ is a concave function on $\Rscr$ which is affinely linear within each bounded face of $G$. Knutson and Tao [J. Amer. Math. Soc. 12 (4) (1999) 1055--1090] proved an integrality theorem for so-called honeycombs, which is equivalent to the assertion that an integer-valued function on the boundary edges of $G$ is extendable to an integer concave cocirculation if it is extendable to a concave cocirculation at all. In this paper we show a sharper property: for any concave cocirculation $h$ in $G$, there exists an integer concave cocirculation $h'$ satisfying $h'(e)=h(e)$ for each boundary edge $e$ with $h(e)$ integer and for each edge $e$ contained in a bounded face where $h$ takes integer values on all edges. On the other hand, we explain that for a 3-side grid $G$ of size $n$, the polytope of concave cocirculations with fixed integer values on two sides of $G$ can have a vertex $h$ whose entries are integers on the third side but $h(e)$ has denominator $\Omega(n)$ for some interior edge $e$. Also some algorithmic aspects and related results on honeycombs are discussed.

Affiliated with

Also associated with

No associations

Rating

Integer concave cocirculations and honeycombs 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 Integer concave cocirculations and honeycombs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integer concave cocirculations and honeycombs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7960