Integer concave cocirculations and honeycombs

Abstract

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^{\prime }$ satisfying $h^{\prime }(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.

arXiv comment20 pages, 12 figures, submitted to IPCO2004