Here are some papers related to topics discussed at our summer school.

Robert Crowell and Ngoc Tran: Tropical geometry and mechanism design

Michael Joswig: The Cayley trick for tropical hypersurfaces with a view toward Ricardian economics

Skip to content
# Tropical Mathematics and Economics

## notes and problems from the HCM summer school May 9-13, 2016

# Papers from the summer school

# Day 5 lectures

# Open problem session 2

## Vicki Powers

## Elizabeth Baldwin

## Gleb Koshevoy

## Yoshinori Shiozawa

# Day 5 slides

# Open problems session 1

**Gleb Koshevoy**

### Good Exercise:

### Question:

## John Weymark

# Day 4 slides

# Day 3 slides

# Day 2 slides and exercises

# Day 1 slides and exercises

# Hausdorff Summer School on Tropical Geometry and Economics

Here are some papers related to topics discussed at our summer school.

Robert Crowell and Ngoc Tran: Tropical geometry and mechanism design

Michael Joswig: The Cayley trick for tropical hypersurfaces with a view toward Ricardian economics

Diane Maclagan: Tropical ideals and valuated matroids. **Related paper**

Elizabeth Baldwin: Tropical Intersections and Equilibrium. Slides: **3-bezout**

Power indices in voting theory**: Slide**.

It was shown in the second talk that every tropical hypersurface of strong substitute type (facet normals in directions) can be decomposed as a signed sum of tropical hyperplanes (represented by “dots”) and an algorithm was given. According to this algorithm, the dots are placed only at the vertices of the tropical hypersurface. We can label maximal cells in dual subdivision by the number of dots (with signs) placed at the dual vertex.

**Problem: **Find a simple rule for computing the number of dots for each maximal cell in the subdivision.

For two polytopes and in , we can define their *Minkowski sum *as and their *Minkowski subtraction* as . If , then we say that the Minkowski substraction is *valid.*

It was shown by Danilov and Koshevoy that an integral polytope can be obtained from standard simplices (including lower dimensional ones) using these two operations if and only if it is of the form $$ where and are real valued functions on subsets of . This family contains generalized polymatroids, which are obtained by Minkowski sums and valid subtractions.

**Question 1: **What is the “polytope algebra” of subdivisions of polytopes? in particular, of strong substitute type (or type )? For in case, is it generated by “integrally shifted” standard simplices?

For an -convex function , the “affinity areas” (on which is affine) are -convex sets. These are generalized polymatroids. The collections of all affinity areas gives a regular subdivision of the domain of into generalized polymatroids. A generalized polymatroid that cannot be (regularly?) subdivided into smaller generalized polymatroids is called *indecomposable *or *primitive*.

**Question 2:** How many indecomposable generalized polymatroids are there of dimension ?

It can be shown that each indecomposable polymatroid is contained in a unit cube, so it is sufficient to consider only the matroid polytopes.

For , there are two: the standard triangle and its negative.

For , there are eight: two tetrahedra and six pyramids.

**Question 3**: Is it true that chambers of the hyperplane arrangement with normals in the maximal laminar family are indecomposable polymatroids?

A “wild conjecture” is that every indecomposable polymatroid arises this way, but Benjamin Schroeter calimed to have counterexamples.

**Remark**: Positroids are an important subfamily to look at.

See the slides for more problems.

Fix positive integers and , and consider matrices over or . A matrix is called *generic *if it induces a triangulation of the product of simplices .

**Question 1:** How many different types of generic matrices are there? In other words, if we remove the non-generic matrices from or , how many connected components are there in the complement? Equivalently, how many regular subdivisions of are there?

Note: This paper by Paco Santos contains some results on this exact problem.

For generic , the maximal cells in the subdivision of induced by can be labeled by spanning trees. Two spanning trees are compatible (can appear in the same triangulation) if and only if there are no directed cycles when we take the union of their edges with opposite orientations.

**Question 2**: Given a set of compatible spanning trees, do the spanning trees appear together in the same (regular) triangulation?

This paper by Oh and Yoo gives precise conditions for the collection of spanning trees that encode a triangulation. There are many non-regular triangulations of products of simplices (see the same paper by Santos above), so even if the trees appear together, we cannot expect to have a matrix that gives this.

This paper by Danilov, Karzanov, and Koshevoy may be relevant. It is about triangulations of flow polytopes, and products of simplices are special cases.

**Diane Maclagan**: Valuated matroids and tropical algebra**Elizabeth Baldwin**: Tropical Intersections, and applying the Tropical Bezout-Bernstein Theorem in Economics.**Slides**.

For any set of vectors in , let be the family of *integral* polytopes whose facet normals are in directions and let be the family of *integral* polytopes whose edge directions are in directions (H for Hoffman or Hyperplanes, and Ed for Edmond or Edges).

Let , which are edge directions of the simplex with vertices . It is a maximal unimodular system. It is easy to see that (also called *convex polytopes* or *alcoved polytopes*) is closed under intersection. The family (also called *convex polytopes *or *generalized polymatroids *or *generalized permutohedra*) is not closed under intersection (e.g. take two pyramid in an octahedron, which is the matroid polytope of that do not share a square face).

But has the property that the intersection of any two (but not three!) polytopes in the the family is an integral polytope. We will call this property (*).

**Problem **(proven by Isedora Heller): Suppose is a maximal cardinality unimodular system with property (*). Is after a change of lattice basis?

**Remark**: Let be a graph and the matrix whose columns are for all edges in the graph. We can then construct a *graphical matrix* and cographical matrix of . Seymour’s decomposition theorem says that every unimodular system is obtained from graphical matrices, cographical matrices, and an exceptional system via two operation , which is putting the matrices (whose columns are the vectors) in a block diagonal form, and is like with an extra row containing a one and the rest zero.

Let be a finite collection of some linear subspaces of . We say that is *unimodular *if for any subcollection , the group is torsion-free.

**Conjecture: **Suppose is a unimodular set of vectors such that the lines spanned by vectors in form a *maximal* unimodular system of subspaces, i.e. we cannot add any other subspaces to the collection while keeping the unimodularity property. Then for some after a change of lattice basis.

Intersect the boundary of the sets ‘s (see the slides) with the set of valuations, which can be assumed to be convex. Call this intersection

**Question**: Write $late S$ as the intersection of a tropical hyperplane with the set of valuations. Find conditions under which this is possible. How do you find the tropical hyperplane?

**Michael Joswig**: Tropical Linear Programming. (Slides continue from day 1)**Elizabeth Baldwin**. The Extended Product-Mix Auction.**Slides**.

**Michael Joswig**. Tropical Hypersurfaces.**Slides for all three lectures**.**Code**.**Elizabeth Baldwin**. Tropical Hypersurfaces in Economics and the Unimodularity Theorem.**Slides**.**Kazuo Murota**. Discrete Convex Analysis I: concepts of discrete convex functions.**Slides. Problems.**

In this website we collect course materials for the summer school: lectures, exercises, open problems and discussions.