The integer decomposition property andGelfand–Tsetlin polytopes
Per Alexandersson
Royal institute of Technology, Stockholm

Osaka, August 1, 2018

Per Alexandersson

GT-polytopes

Motivation
Gelfand–Tsetlin polytopes appear in various areas:
Closely related to type An root systems.
I Lattice points ↔ semi-standard Young tableaux.
I Special faces ↔ formula for Schubert polynomials
I Lattice points in some special faces ↔ Demazure
characters
I Contain several other families of polytopes.
IRich interplay with other combinatorial objects.

Per Alexandersson

GT-polytopes

Skew Gelfand-Tsetlin patterns
A Gelfand-Tsetlin pattern, or GT-patterns for short, is atriangular or parallelogram arrangement of non-negativenumbers,
x1mx2m..

···
..

.

xnm···..

.

x12x22···x11x21.
xn2···
···

···

xn1

whereabc

andcaPer Alexanderssonb⇔GT-polytopesa ≥ c ≥ b.

A bijection
54251

3

123

13

13

13

←→

1 1 1 5 52 2 3 63 4
46←→

· · 1 3· 1 2· 42023023434233

1133

11221110
1Per Alexandersson0GT-polytopes

Gelfand-Tsetlin polytopes

Consider all GT-patterns with m rows, with top and bottom
row given by λ and µ. The inequalities defines a convex
polytope, Pλ/µ .

Per Alexandersson

GT-polytopes

Gelfand-Tsetlin polytopes

Consider all GT-patterns with m rows, with top and bottom
row given by λ and µ. The inequalities defines a convex
polytope, Pλ/µ .
The integer points in Pλ/µ corresponds to Young tableauxwith shape λ/µ and entries ≤ (m − 1).

Per Alexandersson

GT-polytopes

Marked order polytopes
The GT-polytopes are a special case of marked orderpolytopes.
7x14x5x2

3x4x6

1x32

1Figure : Hasse diagam of a marked poset. The inequalities weget are 1 ≤ x4 ≤ x2 ≤ x1 ≤ 7, x2 ≤ 4, 1 ≤ x6 ≤ 3 ≤ x5 ≤ 4,x6 ≤ x4 and 2 ≤ x3 ≤ x1 .
Per Alexandersson

GT-polytopes

Integrally closed polytopes

A convex polytope P is said to have the integer
decomposition property (IDP) if for every positive integer k
and integer point p ∈ kP, there are integer points pj ∈ Psuch thatp = p1 + p2 + · · · + pk .

Per Alexandersson

GT-polytopes

Integrally closed polytopes

A convex polytope P is said to have the integer
decomposition property (IDP) if for every positive integer kand integer point p ∈ kP, there are integer points pj ∈ Psuch thatp = p1 + p2 + · · · + pk .

Per Alexandersson

GT-polytopes

Unimodular triangulations

All marked order polytopes have a unimodular triangulation.
Such a triangulation decomposes the polytope into
unimodular simplices, that have volume 1.

Per Alexandersson

GT-polytopes

Unimodular triangulations

All marked order polytopes have a unimodular triangulation.
Such a triangulation decomposes the polytope into
unimodular simplices, that have volume 1.
Hence, GT-polytopes are IDP.

Per Alexandersson

GT-polytopes

IDP and concatenation
Let  denote the elementwise addition of GT-patterns.

1 1 1 1 1 5
1 1 1 3 3 3
1 2 2 2 2 2 4 4 52 4 5=
1 1
1 1
1 5
1 3
1313

1 2 4
2 2 42 2 5245

Per Alexandersson

GT-polytopes

IDPGeneralizing:(Pλ1 , Pλ2 , . . . , Pλk )is IDP — see Akiyoshi’s talk.

Per Alexandersson

GT-polytopes

IDP
Generalizing:(Pλ1 , Pλ2 , . . . , Pλk )is IDP — see Akiyoshi’s talk.
However,?
?
?

3? = 1 4
2

has no solution, so (P3 , P2/1 ) is not IDP.

Per Alexandersson

GT-polytopes

IDP
Generalizing:(Pλ1 , Pλ2 , . . . , Pλk )is IDP — see Akiyoshi’s talk.
However,?
?
?

3? = 1 4
2

has no solution, so (P3 , P2/1 ) is not IDP.

SAD!
Per Alexandersson

GT-polytopes

Part II
Integrality and non-integrality. Motivated by research byKing, Tollu, Toumazet and later de Loera and McAllister.

Per Alexandersson

GT-polytopes

Gelfand-Tsetlin polytopes II
Let Pλ/µ,w be the Gelfand-Tsetlin polytope defined by thesame inequalities and equalities before, with the addition
that the sum of the entries in row j resp. row j + 1 in thepattern differ by exactly wj .

Per Alexandersson

GT-polytopes

Gelfand-Tsetlin polytopes II
Let Pλ/µ,w be the Gelfand-Tsetlin polytope defined by thesame inequalities and equalities before, with the addition
that the sum of the entries in row j resp. row j + 1 in thepattern differ by exactly wj .
43423311331221 31 2411

←→110
102

Here, w = (2, 2, 1, 1) and w is the type of the tableau; wj
counts the number of boxes with content j.
Per Alexandersson

GT-polytopes

Connection with structure constants
The number of integer points in Pλ/µ,w is equal to thenumber of Young tableaux with shape λ/µ and type w.

Per Alexandersson

GT-polytopes

Connection with structure constants
The number of integer points in Pλ/µ,w is equal to thenumber of Young tableaux with shape λ/µ and type w.
These numbers, denoted Kλ/µ,w , are the skew Kostka
numbers.
Kλ/µ,w xw

Xsλ/µ (x) =w weak integer composition=

XKλ/µ,w mw (x)w partition

Per Alexandersson

GT-polytopes

Connection with structure constants
The number of integer points in Pλ/µ,w is equal to thenumber of Young tableaux with shape λ/µ and type w.
These numbers, denoted Kλ/µ,w , are the skew Kostka
numbers.
Kλ/µ,w xw

Xsλ/µ (x) =w weak integer composition=XKλ/µ,w mw (x)w partition

The Kλ/µ,w are special cases of Littlewood–Richardsoncoefficients.

Per Alexandersson

GT-polytopes

Properties of Pλ/µ,w
The GT-polytopes Pλ/µ,w have strange properties.

12Berenstein, Kirillov, 1988 and Rassart, 2004
King, Tollu, Toumazet and de Loera, McAllister, 2004
Per Alexandersson

GT-polytopes

Properties of Pλ/µ,w
The GT-polytopes Pλ/µ,w have strange properties.
All Pλ/µ,w have polynomial Ehrhart function. 1I Some Pλ/µ,w are non-integral. 2I

12Berenstein, Kirillov, 1988 and Rassart, 2004
King, Tollu, Toumazet and de Loera, McAllister, 2004
Per Alexandersson

GT-polytopes

Properties of Pλ/µ,w
The GT-polytopes Pλ/µ,w have strange properties.
All Pλ/µ,w have polynomial Ehrhart function. 1I Some Pλ/µ,w are non-integral. 2ILet w be a permutation of the entries in w. ThenI Pλ/µ,w might be integral while Pλ/µ,w is non-integral.
I The number of integer points in Pλ/µ,w and Pλ/µ,w isalways the same.

12Berenstein, Kirillov, 1988 and Rassart, 2004
King, Tollu, Toumazet and de Loera, McAllister, 2004
Per Alexandersson

GT-polytopes

Some propertiesDetermining if Pλ/µ,w is non-empty is hard, there is no easyalgorithm for this. However, all non-empty Pλ/µ,w contains
at least one integer vertex. 33This is a consequence of the proof of the saturation conjecture byA. Knutson and T. Tau.
Per Alexandersson

GT-polytopes

Some properties

Determining if Pλ/µ,w is non-empty is hard, there is no easyalgorithm for this. However, all non-empty Pλ/µ,w contains
at least one integer vertex. 3
The case |µ| = 0 (non-skew case) is easy, there is a simplecondition on λ and w which is necessary and sufficient.

3This is a consequence of the proof of the saturation conjecture byA. Knutson and T. Tau.
Per Alexandersson

GT-polytopes

Methods
The main resource is Jesús A. De Loera and Tyrrell B.
McAllister, Vertices of Gelfand-Tsetlin Polytopes, Discrete &Computational Geometry 32 (2004), no. 4, 459–470.

Per Alexandersson

GT-polytopes

Methods
The main resource is Jesús A. De Loera and Tyrrell B.
McAllister, Vertices of Gelfand-Tsetlin Polytopes, Discrete &Computational Geometry 32 (2004), no. 4, 459–470.
66 11 5 9 3 5 2 3 00
2 9 2
2 5 2400
2 92
3 12 0 024100

666540Per Alexandersson

GT-polytopes

444342211

10
10
00
000

Methods
6

6 11 5 9 3 5 2 3 00
2 9 2
2 5 202 9 4
2 1 0
3 2 0 0
24



0 0
1
1
10 0


1
0


0

10
1
1000
1
0
0
0

0

0
0
1
0
0

0

0

0
0
0
10

0
0
0
1
0

Per Alexandersson

666454443420
1

0

0


00

GT-polytopes

21
10
1
0000

10
1

0001
1000000
00


1
2


1
00

Methods
6

6 11 5 9 3 5 2 3 00
2 9 2
2 5 202 9 4
2 1 0
3 2 0 0
24



0 0
1
1
10 0

1

0


0

10
1
1
000
1
00
0

0

00
1
0
0

0

0

00
0
10

0
0
0
1
0

6664

5444
3420
1
00002110
10000101000110000000001
2

1
0

Theorem: The dimension of ker TG is equal to the dimensionof the minimal (dimensional) face of the GT-polytope
containing G.
Per Alexandersson

GT-polytopes

Main results
Theorem (A. 2014)
All integral Pλ/µ,1 are compressed.
This implies the existence of a unimodular triangulation andIDP.
Note that the polytope Pλ/µ,1 is always non-empty and that
integer points in this polytope correspond to standard Youngtableaux of shape λ/µ.

Per Alexandersson

GT-polytopes

Integrality of Pλ/µ,1Theorem (A. 2014)
The only shapes λ/µ for which Pλ/µ,1 is integral are
∗

···

..
.

..
.

···
or a disjoint union of rows of boxes.

Per Alexandersson

GT-polytopes∗

Proof idea
Find subdiagram patterns that admit a non-integralvertex.
I Prove that all skew diagrams that avoid these patterns
must be of the form above.
I

..
.
..
.

(four or more boxes)..
.
Per Alexandersson

GT-polytopes

Refinement results

Proposition (A. 2014)
Suppose w0 <ref w and let P = Pλ/µ,w and P 0 = Pλ/µ,w0 .
Then01. |P 0 ∩ Zd | is greater or equal to |P ∩ Zd |. (Easy)
2. If P 0 is integral, then P is integral. (GT-proof)
3. If P 0 is integrally closed, then so is P. (Tableau-proof)

Per Alexandersson

GT-polytopes

Example
Non-skew case λ = 431, and w in the boxes.

2222

422

332

431

3221

4211

3311

22211

32111

41111

221111 311111
211111111111111
Note: only partitions w are shown here.
Per Alexandersson

GT-polytopes

Part III
Related questions and big counterexamples.
Ehrhart polynomial: p(k) = |kP ∩ Zd |.
Leading coefficient = volume of the polytope.

Per Alexandersson

GT-polytopes

Open problem

Conjecture (King, Tollu Toumazet, 2004)
All coefficient in the Ehrhart polynomial obtained from
Pλ/µ,w are non-negative.

Per Alexandersson

GT-polytopes

Open problem

Conjecture (King, Tollu Toumazet, 2004)
All coefficient in the Ehrhart polynomial obtained from
Pλ/µ,w are non-negative.
This conjecture contains the problem about positivity of
Ehrhart polynomial of the Birkhoff polytope.

Per Alexandersson

GT-polytopes

Maybe the conjecture is false?
There are order polytopes with negative Ehrhart coefficients:
1x1x2...

x`−1x`z0This order polytope has Ehrhart polynomial given byP`p(k) = k+1
j=1 j . For ` = 20, there are negative coefficients.

Per Alexandersson

GT-polytopes

Negative coefficients
Consequence: There are Ehrhart polynomials of faces ofPλ/µ with negative coefficients:x1
10x2x3zx4x5

Per Alexandersson

GT-polytopes

The endThank you for yourtime

Per Alexandersson

GT-polytopes