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?**



Looking for a canonical (matroid polytope) subdivision of the hypersimplex
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](http://arxiv.org/abs/1112.1278), 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}$.)


