# Looking for a canonical (matroid polytope) subdivision of the hypersimplex

A matroid polytope is the convex hull of the indicator vectors of the bases of a matroid, and a matroid polytope subdivision (MPS) is a polyhedral subdivision of a matroid polytope whose cells are also matroid polytopes. I recently heard there is a “canonical” (non-trivial) MPS of the matroid polytope of the uniform matroid of rank $k$ on $n$ elements (a.k.a. the $n$-th hypersimplex of $k$-th order = convex hull of all indicator vectors of $k$-element subsets of $\{1,...,n\}$ in $\mathbb{R}^n)$ intro matroid polytopes of Schubert matroids (a.k.a. generalized Catalan matroids, shifted matroids).

Does anyone have a reference for this statement?

• Lattice path matroids aren't Schubert matroids; they're intersections of Schubert with opposite Schubert matroids. – Allen Knutson Apr 22 '14 at 14:42
• You're right, I modified accordingly. – Camilo Sarmiento Apr 22 '14 at 15:19

The uniform matroid itself is a Schubert matroid, so the trivial subdivision where we don't subdivide at all meets this criterion.

There is no way we can use all the Schubert matroids. Let $M$ be the Schubert matroid whose bases are all $k$-element subsets of $\{ 1,2, \ldots, n \}$ except for $\{ 1,2,3,\ldots, k \}$. If we remove the polytope of $M$ from $\Delta(k,n)$, what remains is a matroid polytope which has no nontrivial matroid subdivision. Namely, it corresponds to the matroid (call it $N$) where the elements $\{ k+1, k+2, \ldots, n \}$ are all parallel to each other, and the total rank is $k$. So, if we use $M$ in our matroidal subdivision, then all that is left over is $N$.

I'm not sure how to define "canonical" in this setting, but none of the common matroid subdivisions use only Schubert matroids. What is the source of this claim?

Based on your comments below, I am pretty sure I know what you are looking for. I think you want a certain subdivision of $\Delta(k,n)$ with $\binom{n-2}{k-1}$ facets. I illustrate with an example for $(k,n) = (4,9)$: One of the $\binom{7}{3}$ facets of the subdivision will be the matroid represented by the columns of any matrix of the form $$\begin{pmatrix} 1 & 0 & 0 & 0 & \ast & \ast & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & \ast & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & \ast & \ast & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & \ast & \ast & \ast \\ \end{pmatrix}.$$ To describe all the $\binom{7}{3}$ facets, let the path of $\ast$'s range over all possible paths from the upper left to the lower right of the $4 \times 5$ rectangle.

Let $G$ be a subset of $\{ 1, \ldots, k \} \times \{ k+1, \ldots, n \}$. Let $(e_1, e_2, \ldots, e_k)$ be the vertices of the simplex $\Delta^{k-1}$ and let $(f_{k+1}, \ldots, f_n)$ be the vertices of $\Delta^{n-k-1}$. Set $$P(G) = \mathrm{Hull} \{ (e_i, f_j) : (i,j) \in G \} \subseteq \Delta^{k-1} \times \Delta^{n-k-1}.$$ Every polyhedral subdivision of $\Delta^{k-1} \times \Delta^{n-k-1}$ is a division into pieces of the kind $P(G)$. You get simplices if and only if $G$, considered as a bipartite graph on $\{ 1, \ldots, k \} \cup \{ k+1, \ldots, n \}$, is a tree. The "staircase subdivision" of $\Delta^{k-1} \times \Delta^{n-k-1}$ corresponds to the set of $\binom{n-2}{k-1}$ paths through a $k \times (n-k)$ grid. So the above example is $G = \{ (1,5), (1,6), (2,6), (3,6), (3,7), (4,7), (4,8), (4,9) \}$.

Now, given $G$, we can also define a matroid $M(G)$ by building a $(0, 1, \ast)$ matrix as above. (This construction is called the "principal transversal matroid".) If we have a collection $G_i$ so that $(P(G_i))$ form a polyhedral subdivision of $\Delta^{k-1} \times \Delta^{n-k-1}$, then the matroid polytopes of the $M(G_i)$ are a subdivision of $\Delta(k,n)$. We discuss this construction in Section 2 of Dressians, tropical Grassmannians and their rays, although not as clearly as I wish we had.

I can say a ton more about this, but I don't want to go on forever. Let me just point out where the staircase confusion presumably came from: Schubert matroids look like $$\begin{pmatrix} 1 & 0 & 0 & 0 & \ast & \ast & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & \ast & \ast & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & \ast & \ast & \ast & 0 & 0 \\ 0 & 0 & 0 & 1 & \ast & \ast & \ast & \ast & \ast \\ \end{pmatrix}.$$ So they also are described by paths through a rectangle, but not in the same way. (And there are $\binom{n}{k}$ of them, not $\binom{n-2}{k-1}$.)

• (I forgot to exclude the trivial subdivision...) The source was a colleague of mine, who also mentioned that such MPS was analogous to the stratification of the Grassmanian of $k$-planes in $\mathbb{R}^n$. He didn't remember where he saw that statement, hence I came to MO. – Camilo Sarmiento Apr 22 '14 at 14:41
• Matroids loosely correspond to closed T-invariant subvarieties of the Grassmannian, unlike the Bruhat cells, which are only locally closed. I really don't see a possible analogy here. – Allen Knutson Apr 22 '14 at 14:44
• I see. My background is in combinatorics, and I arrived at that question because I wanted to know about the MPSs of the (k,n)-hypersimplex that give a staircase triangulation of the cartesian product of a (k-1)-simplex with a (n-k-1)-simplex when looking at a vertex figure. When I spoke "staircase" and "hypersimplex", my colleague somehow came up with "Schubert matroid", which now I learn doesn't make much sense... – Camilo Sarmiento Apr 22 '14 at 20:31
• @CamiloSarmiento Now I think I know what you are looking for, see my edit. I can talk about matroid subdivisions basically forever; if you have some specific questions about this, let me know and I can say much more. – David E Speyer Apr 23 '14 at 12:50
• @DavidSpeyer Precisely! :) . So it is a mere coincidence that both the cells of the MPS you described, and the Schubert matroids, can be "indexed" by staircases (although on different grids)? – Camilo Sarmiento Apr 23 '14 at 13:48