Deformation cones for polytopes
Federico Castillo
Kansas University

July 30, 2018Federico Castillo (Kansas University)

Deformation cones

July 30, 20181 / 27

Polytopes

Definition
A polytope is the convex hull of finite points.

Federico Castillo (Kansas University)

Deformation cones

July 30, 20182 / 27

Polytopes

Definition
A polytope is the convex hull of finite points.
.

Federico Castillo (Kansas University)

Deformation cones

July 30, 20182 / 27

Alternative definition
Minkowski-Weyl Theorem
Every polytope P is the bounded intersection of finitely many halfspaces. Moreprecisely, there exist a1 , · · · , an ∈ Rd \{0} and b1 , · · · , bn ∈ R such thatP = x ∈ Rd : at1 x ≤ b1 , · · · , atn x ≤ bn .

Federico Castillo (Kansas University)

Deformation cones

July 30, 20183 / 27

Alternative definition
Minkowski-Weyl Theorem
Every polytope P is the bounded intersection of finitely many halfspaces. Moreprecisely, there exist a1 , · · · , an ∈ Rd \{0} and b1 , · · · , bn ∈ R such thatP = x ∈ Rd : at1 x ≤ b1 , · · · , atn x ≤ bn .
Example: Crosspolytope.
(♦d = conv(±e1 , · · · , ±ed ) =

d

x∈R :

d
X

)
±xi ≤ 1 .

i=1Federico Castillo (Kansas University)

Deformation cones

July 30, 20183 / 27

Interesting example: Permutohedronσ(1), · · · , σ(d) : σ a permutattion ,)d +1 X|I | + 1dx ∈ R : x1 + · · · + xd =
,
xi ≤
.
2
2

Πd−1 = conv
(
=



i∈I

This polytope has d! vertices and 2d − 2 facets. Notice that its dimension is d − 1.
(132)

(213)

(231)

(321)

(123)

(312)

Figure: The 2-permutohedron.
Federico Castillo (Kansas University)

Deformation cones

July 30, 2018

4 / 27

2-permutohedron

x1
x1
x1
x1

+ x2
x2

+ x3
+ x3
+ x3

+ x2
x2
x3

Federico Castillo (Kansas University)

Deformation cones

=
≤
≤
≤
≤
≤
≤

6
5
5
5
3
3
3
July 30, 2018

5 / 27

FacesFor any c ∈ Rd (which we will think of as a linear functional) define P c as thepoints in P the farthest in direction c.

Federico Castillo (Kansas University)

Deformation cones

July 30, 2018

6 / 27

FacesFor any c ∈ Rd (which we will think of as a linear functional) define P c as thepoints in P the farthest in direction c.Subsets of P of the above form are called
faces of P.

Federico Castillo (Kansas University)

Deformation cones

July 30, 2018

6 / 27

FacesFor any c ∈ Rd (which we will think of as a linear functional) define P c as thepoints in P the farthest in direction c.Subsets of P of the above form are called
faces of P.

Figure: Two different faces.

Federico Castillo (Kansas University)

Deformation cones

July 30, 2018

6 / 27

FacesFor any c ∈ Rd (which we will think of as a linear functional) define P c as thepoints in P the farthest in direction c.Subsets of P of the above form are called
faces of P.

Figure: Two different faces.

A facet is a face of codimension 1.

Fact:
Each vertex is the intersection of the facets containing it.
Federico Castillo (Kansas University)

Deformation cones

July 30, 2018

6 / 27

Deformations

Definition.
We say Q is a deformation of P if we can obtain Q by moving the facets of P
without overrunning vertices. That is, if a set of facets intersect in a vertex of P,
the same set must intersect in a vertex of Q.

Federico Castillo (Kansas University)

Deformation cones

July 30, 20187 / 27

Deformations

Definition.
We say Q is a deformation of P if we can obtain Q by moving the facets of P
without overrunning vertices. That is, if a set of facets intersect in a vertex of P,
the same set must intersect in a vertex of Q.
The main object of study is, given P, the set of all such Q.

Federico Castillo (Kansas University)

Deformation cones

July 30, 20187 / 27

Example(−1,2)

P F2

(4,2)


F1

F4

(−1,−1) F3(−1,2)(−3,0)(1,−1)

Q1(4.5,2)(2.5,0)

−1
 0

 0
1

(−1,2)

Q2




0
1


 2 
1 
 x

≤
 1 .
−1  y−12(2,2)(−1,−1)(−1,2)

Federico Castillo (Kansas University)b2 = (1, 2, 1, 0)

Deformation cones(2,2)(−1,−1)(−2,−2)b1 = (3, 2, 0, 2.5)Q3(−1,−2)b3 = (1, 2, 2, 0)

July 30, 20188 / 27

Example continued

What are all possible vectors b that give me a deformation?

Federico Castillo (Kansas University)

Deformation cones

July 30, 2018

9 / 27

Example continued

What are all possible vectors b that give me a deformation?

Answer for the previous example.
The set of all such vectors is given by the following two conditions
0 ≤ b2 + b3 ,b3 ≤ b1 + b4 .

A (non pointed) cone in R4 .

Federico Castillo (Kansas University)

Deformation cones

July 30, 2018

9 / 27

Example continued

What are all possible vectors b that give me a deformation?

Answer for the previous example.
The set of all such vectors is given by the following two conditions
0 ≤ b2 + b3 ,b3 ≤ b1 + b4 .

A (non pointed) cone in R4 .
This is what we are looking for.

Federico Castillo (Kansas University)

Deformation cones

July 30, 2018

9 / 27

Sure, but why? Part I

1. Parameter spaces.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201810 / 27

Sure, but why? Part I

1. Parameter spaces.
When solving a problem (math or otherwise) it is always helpful to consider all
possibilities simultaneously.
Don’t fight in the North or
the South. Fight every battle
everywhere, always, in yourmind. Everyone is yourenemy, everyone is yourfriend. Every possible seriesof events is happening all at
once. Live that way andnothing will surprise you.
Everything that happens will
be something that you’ve seen
before. (Game of Thrones,
Season 7, Episode 3)

Federico Castillo (Kansas University)

Deformation cones

July 30, 201810 / 27

Potentially useful for:

Are the following properties true over the whole cone?

Federico Castillo (Kansas University)

Deformation cones

July 30, 201811 / 27

Potentially useful for:

Are the following properties true over the whole cone?
1

Normality.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201811 / 27

Potentially useful for:

Are the following properties true over the whole cone?
1

Normality.

2

Ehrhart Positivity.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201811 / 27

Potentially useful for:

Are the following properties true over the whole cone?
1

Normality.

2

Ehrhart Positivity.

3

Unimodality of δ-vector.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201811 / 27

Potentially useful for:

Are the following properties true over the whole cone?
1

Normality.

2

Ehrhart Positivity.

3

Unimodality of δ-vector.

4

Quadratic generation of toric ideal.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201811 / 27

Sure, but why? Part II

2. Polytope Algebra.
Theorem (Shepard)
Q is a deformation of P iff exist λ, R such that Q + R = λP. Another name isweakly Minkowski summand.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201812 / 27

Sure, but why? Part II

2. Polytope Algebra.
Theorem (Shepard)
Q is a deformation of P iff exist λ, R such that Q + R = λP. Another name isweakly Minkowski summand.
These polytopes span the polytope algebra Π(P) developed by McMullen for a
combinatorial proof of g -theorem.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201812 / 27

Sure, but why? Part II

2. Polytope Algebra.
Theorem (Shepard)
Q is a deformation of P iff exist λ, R such that Q + R = λP. Another name isweakly Minkowski summand.
These polytopes span the polytope algebra Π(P) developed by McMullen for a
combinatorial proof of g -theorem.

Alternative parametrization.
In McMullen’s theory deformations are parametrized by the edge lengths,(balanced 1-weights).

Federico Castillo (Kansas University)

Deformation cones

July 30, 201812 / 27

Sure, but why? Part III

3. Nef cones.
The deformation cone modulo its lineality space is equal to the Nef cone of theassociated toric variety.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201813 / 27

Sure, but why? Part III

3. Nef cones.
The deformation cone modulo its lineality space is equal to the Nef cone of theassociated toric variety. In the Minimal Model Program it is very important toknow Nef cone, or more precisely, the NE cone (which is dual to Nef). In
particular it is crucial to know the rays (corresponding to extremal curves) of NE.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201813 / 27

Sure, but why? Part III

3. Nef cones.
The deformation cone modulo its lineality space is equal to the Nef cone of theassociated toric variety. In the Minimal Model Program it is very important toknow Nef cone, or more precisely, the NE cone (which is dual to Nef). In
particular it is crucial to know the rays (corresponding to extremal curves) of NE.

MMP
In birrational geometry knowledge of the facets of the Nef cone is important.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201813 / 27

Sure, but why? Part IV

4. Nice answers.
In the examples we are going to present, the resulting cones are interesting on theirown. They all have the property that although we are considering exponentiallymany parameters, the inequalities have very small support (usually 4 or 5 terms).

Federico Castillo (Kansas University)

Deformation cones

July 30, 201814 / 27

Classical example: Permutohedron
Let’s review the definition of permutohedron:Πd−1 = conv σ(1), · · · , σ(d) : σ a permutattion ,
(



)
d +1 X|I | + 1d= x ∈ R : x1 + · · · + xd =
,
xi ≤
.
2
2
i∈I

Federico Castillo (Kansas University)

Deformation cones

July 30, 201815 / 27

Classical example: Permutohedron
Let’s review the definition of permutohedron:Πd−1 = conv σ(1), · · · , σ(d) : σ a permutattion ,
(



)
d +1 X|I | + 1d= x ∈ R : x1 + · · · + xd =
,
xi ≤
.
2
2
i∈I

The takeaway from here is that the inequality description looks likeX
{x : heI , xi =xi ≤ f (I )∀I ⊂ [d]}.
i∈I

Remark/Question
To move facets mean to give a function on all subsets. Which functions give a
deformation?

Federico Castillo (Kansas University)

Deformation cones

July 30, 201815 / 27

Submodular Theorem.
Theorem (Edmonds, Fujishige,
Morton-Pachter-Shiu-Sturmfels-Wienand, C.-Liu)
A function f : 2[d] −→ R gives a deformation of Πd−1 if and only if it issubmodular. This means thatf (I ) + f (J) ≥ f (I ∩ J) + f (I ∪ J).
for any two subsets.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201816 / 27

Submodular Theorem.
Theorem (Edmonds, Fujishige,
Morton-Pachter-Shiu-Sturmfels-Wienand, C.-Liu)
A function f : 2[d] −→ R gives a deformation of Πd−1 if and only if it issubmodular. This means thatf (I ) + f (J) ≥ f (I ∩ J) + f (I ∪ J).
for any two subsets.
Submodular functions are very important on their own. An important
problem is to minimize/maximize the function itself.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201816 / 27

Submodular Theorem.
Theorem (Edmonds, Fujishige,
Morton-Pachter-Shiu-Sturmfels-Wienand, C.-Liu)
A function f : 2[d] −→ R gives a deformation of Πd−1 if and only if it issubmodular. This means thatf (I ) + f (J) ≥ f (I ∩ J) + f (I ∪ J).
for any two subsets.
Submodular functions are very important on their own. An important
problem is to minimize/maximize the function itself.
Even though we have roughly 2d parameters, the inequalities involves just 4
terms.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201816 / 27

Submodular Theorem.
Theorem (Edmonds, Fujishige,
Morton-Pachter-Shiu-Sturmfels-Wienand, C.-Liu)
A function f : 2[d] −→ R gives a deformation of Πd−1 if and only if it issubmodular. This means thatf (I ) + f (J) ≥ f (I ∩ J) + f (I ∪ J).
for any two subsets.
Submodular functions are very important on their own. An important
problem is to minimize/maximize the function itself.
Even though we have roughly 2d parameters, the inequalities involves just 4
terms.
Not all of them are necessary. The essential ones (facet-defining) are of theform f (I ∪ {a}) + f (I ∪ {b}) ≥ f (I ) + f (I ∩ {a, b}), where a, b ∈/ I.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201816 / 27

Submodular Theorem.
Theorem (Edmonds, Fujishige,
Morton-Pachter-Shiu-Sturmfels-Wienand, C.-Liu)
A function f : 2[d] −→ R gives a deformation of Πd−1 if and only if it issubmodular. This means thatf (I ) + f (J) ≥ f (I ∩ J) + f (I ∪ J).
for any two subsets.
Submodular functions are very important on their own. An important
problem is to minimize/maximize the function itself.
Even though we have roughly 2d parameters, the inequalities involves just 4
terms.
Not all of them are necessary. The essential ones (facet-defining) are of theform f (I ∪ {a}) + f (I ∪ {b}) ≥ f (I ) + f (I ∩ {a, b}), where a, b ∈/ I.
Matroid polytopes, and more general, polymatroids are deformations of
permutohedra.
Federico Castillo (Kansas University)

Deformation cones

July 30, 201816 / 27

Submodular cone
After quotienting by the lineality space, the deformation cone of Π2 is the 4-dimcone over the following picture:

Federico Castillo (Kansas University)

Deformation cones

July 30, 201817 / 27

Submodular cone
After quotienting by the lineality space, the deformation cone of Π2 is the 4-dimcone over the following picture:

We know the facets. The rays are unknown and quite an interesting problem.
Loopless Matroid polytopes are extremal, but there are extremal rays not comingfrom matroids.
Federico Castillo (Kansas University)

Deformation cones

July 30, 201817 / 27

Extending to Coxeter Arrangements

One important aspect of the permutohedron is that it has lots of symmetry.
Computation of the Deformation cone is certainly simpler when there is symmetry
involved. In a precise way the symmetry present in Πd−1 can be defined andclassified.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201818 / 27

Extending to Coxeter Arrangements

One important aspect of the permutohedron is that it has lots of symmetry.
Computation of the Deformation cone is certainly simpler when there is symmetry
involved. In a precise way the symmetry present in Πd−1 can be defined andclassified.
{Braid fan} −→{Coxeter arrangement}{Symmetric group Sd } −→{Weyl group W }{Permutohedron Πd−1 } −→{W -permutohedron (sum of all positive root

{facets indexed by subsets} −→Federico Castillo (Kansas University){facets indexed by weights}

Deformation cones

July 30, 201818 / 27

Extending to Coxeter Arrangements

One important aspect of the permutohedron is that it has lots of symmetry.
Computation of the Deformation cone is certainly simpler when there is symmetry
involved. In a precise way the symmetry present in Πd−1 can be defined andclassified.
{Braid fan} −→{Coxeter arrangement}{Symmetric group Sd } −→{Weyl group W }{Permutohedron Πd−1 } −→{W -permutohedron (sum of all positive root

{facets indexed by subsets} −→{facets indexed by weights}

This particular generalization comes up in the study of Coxeter Matroids.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201818 / 27

W -submodular
By using carefully the same methods as in the permutohedron, we get that a that:

Theorem (Ardila-C.-Postnikov)
The submodular cone is given byX  hαi , αj i 
f (wj ) ≤ f (wi ) + f (si wi ),−2hαi , αi i
j6=iand all other inequalities obtained by applying W to the equation. Here wk ’s are
the fundamental weights, si is the reflection that fixes all fundamental weights
except wi .

Federico Castillo (Kansas University)

Deformation cones

July 30, 201819 / 27

W -submodular
By using carefully the same methods as in the permutohedron, we get that a that:

Theorem (Ardila-C.-Postnikov)
The submodular cone is given byX  hαi , αj i 
f (wj ) ≤ f (wi ) + f (si wi ),−2hαi , αi i
j6=iand all other inequalities obtained by applying W to the equation. Here wk ’s are
the fundamental weights, si is the reflection that fixes all fundamental weights
except wi .
Remarks:
In type A this recovers submodular theorem.
Most coefficients are zero. The only nonzero are the neighbours in the
Dynkin diagram.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201819 / 27

Another generalization
In recent work with Liu, we defined a nested permutohedron. Informally, we
replace each vertex of the permutohedron by a smaller dimension permutohedron.

Figure: Π3 and Π23 (4, 1)Federico Castillo (Kansas University)

Deformation cones

July 30, 201820 / 27

The actual definition
RemarkWe actually define the new polytope through is normal fan. The braid fanclassifies points according to the relative order of the entries. The nested braid fanclassifies points according to the relative order of the entries and the relative orderof the first differences.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201821 / 27

The actual definition
RemarkWe actually define the new polytope through is normal fan. The braid fanclassifies points according to the relative order of the entries. The nested braid fanclassifies points according to the relative order of the entries and the relative orderof the first differences.

RemarkLater we found out that this is the barycentric subdivision of Braid fan.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201821 / 27

The actual definition
RemarkWe actually define the new polytope through is normal fan. The braid fanclassifies points according to the relative order of the entries. The nested braid fanclassifies points according to the relative order of the entries and the relative orderof the first differences.

RemarkLater we found out that this is the barycentric subdivision of Braid fan.

RemarkThe ’doubly’ nested braid fan is not the next barycentric subdivision.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201821 / 27

The actual definition
RemarkWe actually define the new polytope through is normal fan. The braid fanclassifies points according to the relative order of the entries. The nested braid fanclassifies points according to the relative order of the entries and the relative orderof the first differences.

RemarkLater we found out that this is the barycentric subdivision of Braid fan.

RemarkThe ’doubly’ nested braid fan is not the next barycentric subdivision.

One key point
Facets are indexed by ordered set partitions, a combinatorial object.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201821 / 27

Posets
In the permutohedron case, facets where indexed by sets.

RemarkIn this case, facets form a poset. In general there is no natural poset structure on
the set of facets.
..
.
{12357}{1357}
{157}

{135}
{15}
.. {1}.

Figure: Diamond giving the inequality f ({135}) + f ({157}) ≥ f ({1357}) + f ({15})Federico Castillo (Kansas University)

Deformation cones

July 30, 201822 / 27

Deformation for nested permutohedron
In this case, facets are indexed by ordered partitions and they also form a poset.
The deformation cone have two types of inequalities.
T4 = 53142

T3 = 531j42

T2 = 531j4j2

T30 = 53j142

T20 = 53j1j42

T1 = 53j1j4j2

T0 = 3j5j1j4j2

T00 = 5j3j1j4j2

1

For each diamond, same “submodular” pattern.

2

For elements in the bottom, we have something called theFederico Castillo (Kansas University)

Deformation cones

condition.

July 30, 201823 / 27

Examples of inequalities
T4 = 53142

T3 = 531j42

T2 = 531j4j2

T30 = 53j142

T20 = 53j1j42

T1 = 53j1j4j2

T0 = 3j5j1j4j2

T00 = 5j3j1j4j2

We have inequalities
f (531|4|2) + f (53|1|42) ≥ f (531|42) + f (53|1|4|2) Diamondf (3|5|4|2) + f (5|3|1|42) + f (53142) ≥ 2f (53|1|42) + f (53|142)

Federico Castillo (Kansas University)

Deformation cones

Ren

July 30, 201824 / 27

Examples of inequalities

One more to see the general

pattern:f (1|9|2|8|3|6|7|4|5) + f (1|9|8|2|3|6|7|4|5) + f (192836745) ≥2f (1|9|28|3|6|7|4) + f (19|28|36745)

Theorem(C.-Liu)
The collection of all diamonds andnested permutohedron.

Federico Castillo (Kansas University)

inequalities give the deformation cone of the

Deformation cones

July 30, 201825 / 27

SUMMARY

There is a concept of deformation of a polytope.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201826 / 27

SUMMARY

There is a concept of deformation of a polytope. The set of all deformations of agiven one is a polyhedral cone.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201826 / 27

SUMMARY

There is a concept of deformation of a polytope. The set of all deformations of agiven one is a polyhedral cone. It is not easy to compute (specially given a nonsimple polytope).

Federico Castillo (Kansas University)

Deformation cones

July 30, 201826 / 27

SUMMARY

There is a concept of deformation of a polytope. The set of all deformations of agiven one is a polyhedral cone. It is not easy to compute (specially given a nonsimple polytope). We can do it in particular cases.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201826 / 27

SUMMARY

There is a concept of deformation of a polytope. The set of all deformations of agiven one is a polyhedral cone. It is not easy to compute (specially given a nonsimple polytope). We can do it in particular cases.

Potential uses:
Are the following properties true over the whole cone?
1

Normality.

2

Ehrhart Positivity.

3

Unimodality of δ-vector.
Quadratic generation of toric ideal.

4

Federico Castillo (Kansas University)

Deformation cones

July 30, 201826 / 27

The End.

Federico Castillo (Kansas University)

Deformation cones

July 30, 201827 / 27