Matroid polytope

Let ${\displaystyle M}$ be a matroid on ${\displaystyle n}$ elements. Given a basis ${\displaystyle B\subseteq \{1,\dots ,n\}}$ of ${\displaystyle M}$, the indicator vector of ${\displaystyle B}$ is

${\displaystyle \mathbf {e} _{B}:=\sum _{i\in B}\mathbf {e} _{i},}$

where ${\displaystyle \mathbf {e} _{i}}$ is the standard ${\displaystyle i}$th unit vector in ${\displaystyle \mathbb {R} ^{n}}$. The matroid polytope ${\displaystyle P_{M}}$ is the convex hull of the set

${\displaystyle \{\mathbf {e} _{B}\mid B{\text{ is a basis of }}M\}\subseteq \mathbb {R} ^{n}.}$

Square pyramid

Octahedron

• Let ${\displaystyle M}$ be the rank 2 matroid on 4 elements with bases

${\displaystyle {\mathcal {B}}(M)=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}.}$

That is, all 2-element subsets of ${\displaystyle \{1,2,3,4\}}$ except ${\displaystyle \{3,4\}}$. The corresponding indicator vectors of ${\displaystyle {\mathcal {B}}(M)}$ are

${\displaystyle \{\{1,1,0,0\},\{1,0,1,0\},\{1,0,0,1\},\{0,1,1,0\},\{0,1,0,1\}\}.}$

The matroid polytope of ${\displaystyle M}$ is

${\displaystyle P_{M}={\text{conv}}\{\{1,1,0,0\},\{1,0,1,0\},\{1,0,0,1\},\{0,1,1,0\},\{0,1,0,1\}\}.}$

These points form four equilateral triangles at point ${\displaystyle \{1,1,0,0\}}$, therefore its convex hull is the square pyramid by definition.

• Let ${\displaystyle N}$ be the rank 2 matroid on 4 elements with bases that are all 2-element subsets of ${\displaystyle \{1,2,3,4\}}$. The corresponding matroid polytope ${\displaystyle P_{N}}$ is the octahedron. Observe that the polytope ${\displaystyle P_{M}}$ from the previous example is contained in ${\displaystyle P_{N}}$.
• If ${\displaystyle M}$ is the uniform matroid of rank ${\displaystyle r}$ on ${\displaystyle n}$ elements, then the matroid polytope ${\displaystyle P_{M}}$ is the hypersimplex ${\displaystyle \Delta _{n}^{r}}$.[1]

• A matroid polytope is contained in the hypersimplex ${\displaystyle \Delta _{n}^{r}}$, where ${\displaystyle r}$ is the rank of the associated matroid and ${\displaystyle n}$ is the size of the ground set of the associated matroid.[2] Moreover, the vertices of ${\displaystyle P_{M}}$ are a subset of the vertices of ${\displaystyle \Delta _{n}^{r}}$.
• Every edge of a matroid polytope ${\displaystyle P_{M}}$ is a parallel translate of ${\displaystyle e_{i}-e_{j}}$ for some ${\displaystyle i,j\in E}$, the ground set of the associated matroid. In other words, the edges of ${\displaystyle P_{M}}$ correspond exactly to the pairs of bases ${\displaystyle B,B'}$ that satisfy the basis exchange property: ${\displaystyle B'=B\setminus {i\cup j}}$ for some ${\displaystyle i,j\in E.}$[2] Because of this property, every edge length is the square root of two. More generally, the families of sets for which the convex hull of indicator vectors has edge lengths one or the square root of two are exactly the delta-matroids.
• Matroid polytopes are members of the family of generalized permutohedra.[3]
• Let ${\displaystyle r:2^{E}\rightarrow \mathbb {Z} }$ be the rank function of a matroid ${\displaystyle M}$. The matroid polytope ${\displaystyle P_{M}}$ can be written uniquely as a signed Minkowski sum of simplices:[3]

${\displaystyle P_{M}=\sum _{A\subseteq E}{\tilde {\beta }}(M/A)\Delta _{E-A}}$

where ${\displaystyle E}$ is the ground set of the matroid ${\displaystyle M}$ and ${\displaystyle \beta (M)}$ is the signed beta invariant of ${\displaystyle M}$:

${\displaystyle {\tilde {\beta }}(M)=(-1)^{r(M)+1}\beta (M),}$

${\displaystyle \beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X).}$

${\displaystyle P_{M}:=\left\{{\textbf {x}}\in \mathbb {R} _{+}^{E}~|~\sum _{e\in U}{\textbf {x}}(e)\leq r(U),\forall U\subseteq E\right\}}$