Concave cocirculations in a triangular grid

DOI10.1016/J.LAA.2004.11.003MaRDI QIDQ1779253zbMATH OpenOpenAlexFDO

Authors Alexander V. Karzanov

Publication date 1 June 2005

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0304289

zbMATH Keywords

FlowPlanar graphDiscrete convex functionCocirculationTriangular lattice

Mathematics Subject Classification ID

Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20)

Abstract: 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$.

Recommendations

• Integer Programming and Combinatorial Optimization
• Discrete strip-concave functions, Gelfand--Tsetlin patterns, and related polyhedra
• Discrete concavity and the half-plane property
• The honeycomb model of 𝐺𝐿_{𝑛}(ℂ) tensor products II: Puzzles determine facets of the Littlewood-Richardson cone
• scientific article; zbMATH DE number 2174371

Cites work

• scientific article; zbMATH DE number 2174371 (Why is no real title available?)
• Eigenvalues of sums of Hermitian matrices
• Eigenvalues, invariant factors, highest weights, and Schubert calculus
• Integer Programming and Combinatorial Optimization
• Nilpotent operators and discretely concave functions
• The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjecture
• The honeycomb model of 𝐺𝐿_{𝑛}(ℂ) tensor products II: Puzzles determine facets of the Littlewood-Richardson cone

Cited in

(3)

• Integer Programming and Combinatorial Optimization
• Recent developments in discrete convex analysis
• Discrete strip-concave functions, Gelfand--Tsetlin patterns, and related polyhedra

This page was built for publication: Concave cocirculations in a triangular grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1779253)