Author: josephineyu

Open problem session 2

~ josephineyu ~ Leave a comment

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.

Open problems session 1

~ josephineyu ~ Leave a comment

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?