<>
Definition
==========
- A **Gelfand-Tsetlin pattern** (or GT-pattern) is a triangular configuration of non-negative integers, $$\begin{array}{cccccccccccccc} x_{n1} & & x_{n2} & & \cdots & & x_{nn} \\ & \ddots & & \ddots & & & & & \\ & & x_{21} & & x_{22} \\ & & & x_{11} & \end{array}$$ with $x_{i+1,j} \geq x_{ij}$ and $x_{ij} \geq x_{i+1,j+1}$ whenever the indexing is defined.
<>
Additional information
======================
- The two defining conditions ensure every row to be an [integer partition](/IntegerPartitions) and that any two adjacent rows define a skew shape.
- The **shape** of a GT-pattern is the partition given by its top row. Its **weight** (or **type**) is the integer partition of the multiplicities of its entries. The following GT-pattern has shape $(5,4,3,1)$ and weight $(4,4,3,1,1)$:
$$\begin{matrix}5 & & 4 & & 3 & & 1 & & 0\\ & 5 & & 4 & & 3 & & 0 \\ & & 5 & & 3 & & 3 & \\ & & & 5 & & 3 \\ & & & & 4\\ \end{matrix}$$
- There is a natural bijection between GT-patterns with parameters $(l,s)$ and semi-standard Young tableaux with $s$ boxes and maximal entry at most $l$. The skew shape defined by row $j$ and $j+1$ (counting from the bottom) in a GT-pattern describes which cells in the corresponding tableau contain $j$.
Gelfand-Tsetlin polytopes
=========================
The inequalities above (with a fixed top row and fixed row sums) describe a polytope in $\mathbb{R}^{\frac{n(n+1)}{2}}$,
and each GT-pattern therefore naturally corresponds to a lattice point inside this polytope.
This type of polytope has integer vertices.
The usual definition of a *Gelfand-Tsetlin polytope* is to impose an additional restriction on the row sums.
Thus, the GT-polytope $P_{\lambda,w}$ is defined as all real Gelfand-Tsetlin patterns $(x_{ij})$ such that
$x_{ni}=\lambda_i$ and $\sum_i (x_{j,i}-x_{j-1,i}) = w_j$ where $x_{ij}=0$ whenever the indexing is outside the triangular array.
Then, the lattice points in $P_{\lambda,w}$ are in bijection with semi-standard Young tableaux of shape $\lambda$
and type $w$, and the lattice points are counted by the Kostka numbers $K_{\lambda w}$.
The vertices of these polytopes are for small examples integral
<>,
but there are families of GT-patterns where
the GT-polytope has arbitrary large *denominator*, see <>.
Hence, for each pair $(\lambda,w)$ the polytope can $P_{\lambda,w}$ either be
- Empty
- Integral
- Non-integral
All non-empty $P_{\lambda,w}$ contain at least one integral vertex, (this is a consequence of Knutson and Tao's proof of the Saturation conjecture). All polytopes $P_{\lambda,\lambda}$ consist of exactly one lattice point.
Since $K_{\lambda w}$ is invariant under permutation of the entries in $w$ (proved by Bender and Knuth),
most research has been focused on the case when $w$ is a partition.
However, $P_{\lambda,w}$ might be integral for some $w$ but non-integral for some permutation of w.
Tiles
-----
In <>,
the notion of *tiles* is introduced as an important statistic on GT-patterns.
The related statistic is linked to the dimension of faces of Gelfand-Tsetlin polytopes.
The *tiling* of a pattern is the finest partition of the entries in
the pattern, such that adjacent (NW,NE,SW,SE) entries that are equal belong to the same part. These parts are called *tiles*, and each entry in a pattern belong to exactly one tile.
A tile is *free* if it do not intersect any of the first and the last row.
For example,
$$\begin{matrix}5 & & 4 & & 2 & & 1 & & 0\\ & 5 & & 3 & & 2 & & 0 \\ & & 5 & & 3 & & 2 & \\ & & & 5 & & 2 \\ & & & & 4\\ \end{matrix}$$
has 7 tiles, and the tile consisting of the two 3:s is the only free tile.
"The machinery of tilings allows us easily to find non-integral vertices of GT-polytopes by looking for a tiling with a tiling matrix satisfying certain properties. [See Lemma 2.2 in source] Then the tilings can be "filled" in a systematic way with the entries of a GT pattern that is a non-integral vertex." <>
Applications
============
Schur polynomials
-----------------
The close connection between GT-patterns and Schur polynomials
is quite apparent. The Schur polynomial $s_\lambda(x_1,\dotsc,x_n)$ can be expressed
as a sum over lattice points in $GT(\lambda)$, the set of integral triangular GT-patterns with top row
equal to $\lambda$. We have that
$$s_\lambda(x_1,\dotsc,x_n) = \sum_{G \in GT(\lambda) } x^{w(G)}$$
where $w$ is the weight of the pattern $G$.
Hall--Littlewood polynomials
----------------------------
The identity for Schur functions can be
generalized to Hall--Littlewood polynomials,
via a weighted version of Brion's theorem.
See
<>
Let $\lambda$ be a partition. Then
$$P_\lambda(x;t) = \sum_{G \in GT(\lambda) } p_G(t) x^{w(G)}$$
where $p_G(t)$ is a certain statistic that depends on $G$.
This theorem can also be proved via other means, see
<>
Key polynomials
---------------
The *key polynomials* generalize the Schur polynomials.
In
<>,
a formula for key polynomials is proved,
where the sum runs over lattice points in a union of so called *reduced Kogan faces* of $GT(\lambda)$.
Schubert polynomials
--------------------
It was recently proved in [1903.08275](https://arxiv.org/abs/1903.08275) that *Schubert polynomials* can be expressed as
a sum over lattice points in a Minkowski-sum of GT-polytopes.
Alternatively, Schubert polynomials can also be expressed as a sum over reduced Kogan faces of a certain Gelfand-Tsetlin polytope, where each face contribute with a single monomial.
The reduced Kogan faces are in bijection with pipe dreams, which are used to describe Schubert polynomials.
Remarks
=======
It is possible to extend this definition to a parallelogram GT-pattern, in which case the GT-pattern corresponds to a skew semi-standard Young tableau.
For example, here is such a GT-pattern and the corresponding skew semi-standard Young tableau:
$$\begin{matrix}5 & & 4 & & 3 & & 1\\ & 4 & & 4 & & 3 & & 1\\ & & 4 & & 4 & & 2 & & 1\\ & & & 4 & & 3 & & 2 & & 1\\ & & & & 3 & & 2 & & 2 & & 0\\ & & & & & 2 & & 2 & & 0 & & 0 \\ \end{matrix} \qquad \begin{matrix} & & 1 & 2 & 5\\ & & 2 & 3\\1 & 1 & 4\\2\\ \end{matrix}.$$
The skew shape is $(5, 4, 3, 1)/(2, 2)$ and the weight is $(3, 3, 1, 1, 1)$.
Alternating sign matrices
-------------------------
There is also a correspondence between Gelfand Tsetlin patterns and [Alternating Sign Matrices](/AlternatingSignMatrices). In this case we use a special type of Gelfand Tsetlin pattern called a *monotone triangle*. Monotone triangles are Gelfand Tsetlin patterns with strict inequalities instead of weak, and the top row equals $1 2 \cdots n$.
Using the alternating sign matrix and its monotone triangle as above we have a map which gives the following Gelfand Tsetlin pattern:
\begin{align\*} 1 & &2 & &3 & &4 \\ &\; \; \; \; \; \; \;1 & &\; \; \; \; \; \; \;\;3 & &\; \; \; \; \; \; \;4 & \\ & & 1 & &3 & & \\ & & &\; \; \; \; \; \; \; \;2 & & & \end{align\*}
which has column partial sum matrix
$\begin{pmatrix}0 &1 &0 &0\\1 &0 &1 &0 \\1 &0 &1 &1 \\1 &1 &1 &1 \end{pmatrix}$
and maps to the alternating sign matrix
$\begin{pmatrix}0 &1 &0 &0 \\1 &-1 &1 &0 \\0 &0 &0 &1 \\0 &1 &0 &0 \end{pmatrix}$
Additional resources
====================
- See [here](http://www.educreations.com/lesson/view/gt-pattern-to-ssyt/21062001/?s=0ZDgsT&ref=appemail) an interesting video showing the bijection from a GT Pattern to a SSYT.
- See <> p. 313 for further references.
- [Gelfand-Tsetlin patterns](https://www.math.upenn.edu/~peal/polynomials/gtpatterns.htm) in [PerAlexandersson](/PerAlexandersson)'s catalog of symmetric functions.
References
==========
<>
Sage examples
=============
{{{#!sagecell
def GTPiter(l,s):
for la in Partitions(s, max_length=l):
top_row = la + [0]*(l-len(la))
for P in GelfandTsetlinPatterns(n=l, top_row=top_row):
yield P
def statistic(GT):
return sum(GT[0])
for l,s in [(2,2), (3,3)]:
for GT in GTPiter(l,s):
print GT,"=>",statistic(GT)
}}}
Technical information for database usage
========================================
- A GT-pattern is uniquely represented as a **list of lists** representing its rows from top to bottom.
- GT-patterns are parametrized by two parameters **length of the first row** and **sum of the first row**.
- The database contains all GT-pattern where the sum of the two parameters is at most 6.