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

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.