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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s