Discrete strip-concave functions, Gelfand-Tsetlin patterns, and related polyhedra

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:112

Article

Danilov, VI ; Karzanov, AV ; Koshevoy, GA

关键词: triangular grid;    Gelfand-Tsetlin pattern;    discrete concave function;    Young tableau;   

DOI  :  10.1016/j.jcta.2005.01.011

来源: Elsevier

【 摘 要 】

Discrete strip-concave functions considered in this paper are, in fact, equivalent to an extension of Gelfand-Tsetlin patterns to the case when the pattern has a not necessarily triangular but convex configuration. They arise by releasing one of the three types of rhombus inequalities for discrete concave functions (or hives) on a convex part of a triangular grid. The paper is devoted to a combinatorial study of certain polyhedra related to such functions or patterns, and results on faces, integer points and volumes of these polyhedra are presented. Also some relationships and applications are discussed. In particular, we characterize, in terms of valid inequalities, the polyhedral cone formed by the boundary values of discrete strip-concave functions on a grid having trapezoidal configuration. As a consequence of this result, necessary and sufficient conditions on a pair of vectors to be shape and content of a semi-standard skew Young tableau are obtained. (c) 2005 Elsevier Inc. All rights reserved.

【 授权许可】

Free