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

DOI10.1016/J.JCTA.2005.01.011MaRDI QIDQ2575801zbMATH OpenOpenAlexFDO

Authors Vladimir I. Danilov, Alexander V. Karzanov, G. A. Koshevoy

Publication date 6 December 2005

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

discrete concave function triangular grid Young tableau

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10) Polytopes and polyhedra (52B99)

Abstract: 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 the shape and content of a semi-standard skew Young tableau are obtained.

Review text

The authors study discrete strip-concave functions with fixed boundary conditions from a polyhedral perspective. They provide explicit inequalities for the cone of such functions, and they prove integrality and integral feasibility results for associated polytopes. Discrete strip-concave functions generalize Gelfand--Tsetlin patterns [\textit{I.~M. Gelfand} and \textit{M.~L. Tsetlin}, Dokl.~Akad.~Nauk SSSR, n. Ser. 71, 825--828 (1950; Zbl 0037.15301)] to arrays that are not necessarily triangular. They may be defined as follows. Fix \(n \in {\mathbb N} \), and let \((a_{i})_{i=1}^{n}, (b_{i})_{i=1}^{n}\) be sequences of integers such that \(a_{i} \leq b_{i}, 1 \leq i \leq n\), and \[ a_{0} = 0, \quad 0 \leq a_{1} - a_{0} \leq \dotsb \leq a_{n} - a_{n-1} \leq 1, \quad 1 \geq b_{1} - b_{0} \geq \dotsb \geq b_{n} - b_{n-1} \geq 0. \] Denote by \(V\) the index set \(\{(i,j) \in \mathbb Z^{2} : 0 \leq i \leq n, a_{i} \leq j \leq b_{i}\}\). An array on such an index set is said to have convex configuration. The main cases of interest are those in which \(a_{1} = \dotsb = a_{n} = 0\) and either (1) \(b_{i} = i\), (2) \(b_{i} = i + m\), or (3) \(b_{i} = m\). These are called the triangular, trapezoidal, and parallelogram-wise configurations, respectively. A strip-concave array is an array \(X = (x_{ij})_{(i,j) \in V}\) such that \[ x_{ij} - x_{i,j-1} \geq x_{i-1,j} - x_{i-1,j-1} \qquad \text{and} \qquad x_{i-1,j} - x_{i-1, j-1} \geq x_{i,j+1} - x_{ij} \] whenever the terms are defined. In particular, the Gelfand-Tsetlin patterns are strip-concave arrays with triangular configurations. A discrete strip-concave function is the associated function \(x : V \to \mathbb R\) such that \(x(i,j) = x_{ij}\). The polyhedral cone in \(\mathbb R^{V}\) of discrete strip-concave functions (normalized so that \(x_{00} = 0\)) is denoted by \({\mathcal SC}_{V}\). The boundary of a strip-concave array is encoded by four vectors \(\lambda^{X}, \overline{\lambda}^{X}, \mu^{X}, \nu^{X}\) defined by \[ \begin{alignedat}{2} \lambda^{X}_{j} & = x_{nj} - x_{n,j-1}, & \quad \overline{\lambda}^{X}_{j} & = x_{0j} - x_{0,j-1}, \\ \mu^{X}_{i} & = x_{ia_{i}} - x_{i-1, a_{i-1}}, & \quad \nu^{X}_{i} & = x_{ib_{i}} - x_{i-1, b_{i-1}}. \end{alignedat} \] Thus, we may define polyhedra of discrete strip-concave functions in which some or all of the boundary is fixed: \[ \begin{aligned} {\mathcal SC}(\lambda\backslash\overline{\lambda}, \mu, \nu) & = \{ X \in {\mathcal SC}_{V} : (\lambda^{X}, \overline{\lambda}^{X}, \mu^{X}, \nu^{X}) = (\lambda,\overline{\lambda}, \mu, \nu) \}, \\ {\mathcal SC}(\lambda\backslash\overline{\lambda}, \mu) & = \{ X \in {\mathcal SC}_{V} : (\lambda^{X}, \overline{\lambda}^{X}, \mu^{X}) = (\lambda,\overline{\lambda}, \mu) \}. \end{aligned} \] The main results of this paper are the following. (1) The authors provide a complete list of facet-defining inequalities bounding the cone of discrete strip-concave functions with trapezoidal or parallelo\-gram-wise configurations. Such strip-concave functions with \(\mu^{X} = 0^{n}\) are in bijective correspondence with skew semi-standard Young tableaux. Consequently, this result characterizes the shape and content vectors of such tableaux. (2) The polytopes \({\mathcal SC}(\lambda \backslash \overline{\lambda}, \mu, \nu)\) satisfy a ``saturation condition [cf.~\textit{A.~Knutson} and \textit{T.~Tao}, J.~Am.~Math.~Soc.~12, No.~4, 1055--1090 (1999; Zbl 0944.05097)] in the parallelogram-wise and trapezoidal cases: if such a polytope is nonempty, then it contains an integral lattice point. {(3)} Given any convex configuration, the polytope \({\mathcal SC}(\lambda \backslash \overline{\lambda}, \mu)\) is integral---\textit{i.e.}, all of its vertices have only integral entries. (If one fixes in addition \(\nu^{X}\), then the polytope need no longer be integral [\textit{J.~A.~De Loera} and \textit{T.~B.~McAllister}, Discrete Comput.~Geom.~32, No.~4, 459--470 (2004; Zbl 1057.05077)].) The authors prove these results by exploiting the notion of admissible flows on digraphs whose nodes are the entries of \(X\) and whose edges connect diagonally adjacent nodes.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Discrete strip-concave functions, Gelfand--Tsetlin patterns, and related polyhedra

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