# Papers from the summer school

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

Robert Crowell and Ngoc Tran: Tropical geometry and mechanism design

# Day 5 lectures

Diane Maclagan: Tropical ideals and valuated matroids. Related paper

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

# Open problem session 2

## Vicki Powers

Power indices in voting theory:  Slide.

## Elizabeth Baldwin

It was shown in the second talk that every tropical hypersurface of strong substitute type (facet normals in $A_n^\#$ 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.

## Gleb Koshevoy

For two polytopes $P$ and $Q$ in $\mathbb{R}^n$, we can define their Minkowski sum as $P \oplus Q := \{p + q : p \in P, q \in Q\}$ and their Minkowski subtraction as $P \ominus Q = \max\{C : B \oplus C \subseteq A\}$.  If $(P \ominus Q) \oplus Q = P$, then we say that the Minkowski substraction $P \ominus Q$ 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 $$\{ x : a(S) \leq \sum_{i\in S} \leq b(S) \text{ for all } S \subset \{1,\dots,n\}\}$$ where $a$ and $b$ are real valued functions on subsets of $\{1,\dots,n\}$.  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 $A_n$)?  For in $A_n$ case, is it generated by “integrally shifted” standard simplices?

For an $M^\#$-convex function $f$, the “affinity areas” (on which $f$ is affine) are $M^\#$-convex sets.  These are generalized polymatroids.  The collections of all affinity areas gives a regular subdivision of the domain of $f$ 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 $n$?

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 $n=2$, there are two: the standard triangle and its negative.

For $n=3$, 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.

## Yoshinori Shiozawa

See the slides for more problems.

Fix positive integers $M$ and $N$, and consider $M \times N$ matrices $A$ over $\mathbb{R}$ or $\mathbb{R}^+$.  A matrix $A$ is called generic if it induces a triangulation of the product of simplices $\Delta_{M-1} \times \Delta_{N-1}$.

Question 1: How many different types of generic matrices are there? In other words, if we remove the non-generic matrices from $\mathbb{R}^{M\times N}$ or ${\mathbb{R}^+}^{M\times N}$, how many connected components are there in the complement?  Equivalently, how many regular subdivisions of $\Delta_{M-1} \times \Delta_{N-1}$ are there?

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

For generic $A$, the maximal cells in the subdivision of $\Delta_{M-1} \times \Delta_{N-1}$ induced by $A$ 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 $A$ 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.

# Day 5 slides

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

# Open problems session 1

## Gleb Koshevoy

### Good Exercise:

For any set of vectors $A$ in $\mathbb{Z}^n$, let $H(A)$ be the family of integral polytopes whose facet normals are in $A$ directions and let $Ed(A)$ be the family of integral polytopes whose edge directions are in $A$ directions  (H for Hoffman or Hyperplanes, and Ed for Edmond or Edges).

Let $A_n=\{e_i - e_j : i \neq j \text{ in } \{1,\dots,n\}\} \cup \{\pm e_i : i \in \{1,\dots,n\}\}$, which are edge directions of the simplex with vertices $0,e_1,\dots,e_n$.  It is a maximal unimodular system.  It is easy to see that $H(A_n)$ (also called $L^\#$ convex polytopes or alcoved polytopes) is closed under intersection.  The family $Ed(A_n)$ (also called $M^\#$ 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 $U_{4,2}$ that do not share a square face).

But $Ed(A_n)$ 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 $A$ is a maximal cardinality unimodular system with property (*).  Is $A = A_n$ after a change of lattice basis?

Remark: Let $G$ be a graph and $A$ the matrix whose columns are $e_i - e_j$ for all edges $(i,j)$ in the graph.  We can then construct a graphical matrix $[I | A]$and cographical matrix $[I | A^T]$ of $G$Seymour’s decomposition theorem says that every unimodular system is obtained from graphical matrices, cographical matrices, and an exceptional system $R_{10}$ via two operation $\oplus$, which is putting the matrices (whose columns are the vectors) in a block diagonal form, and $\oplus'$ is like $\oplus'$ with an extra row containing a one and the rest zero.

### Question:

Let $\mathcal{L}$ be a finite collection of some linear subspaces of $\mathbb{Q}^n$.  We say that $\mathcal{L}$ is unimodular if for any subcollection $\{L_1,\dots,L_r\} \subset \mathcal{L}$, the group $\mathbb{Z}^n / (\mathbb{Z}^n \cap L_1+\cdots L_r)$ is torsion-free.

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

## John Weymark

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

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?

# Day 4 slides

• Yoshinori Shiozawa: Some New Topics in International Trade Theory. Slides.
• Kazuo Murota: Discrete Convex Analysis III: Algorithms for discrete convex functions. Slides. Slides.

# Day 3 slides

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

# Day 2 slides and exercises

• Kazuo Murota. Discrete Convex Analysis II: Properties of discrete convex functions.  Slides. Problems (same as Day 1).
• Michael Joswig. Tropical convexity. (Slides continue from day 1)
• John Weymark. A geometric approach to dominant strategy implementation. Slides.

# Day 1 slides and exercises

• 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.

# Hausdorff Summer School on Tropical Geometry and Economics

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