Matroid polytope

• 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,~\sum _{e\in E}{\textbf {x}}(e)=r\right\}}$

The matroid independence polytope or independence matroid polytope is the convex hull of the set

${\displaystyle \{\,\mathbf {e} _{I}\mid I{\text{ is an independent set of }}M\,\}\subseteq \mathbb {R} ^{n}.}$

The (basis) matroid polytope is a face of the independence matroid polytope. Given the rank ${\displaystyle \psi }$ of a matroid ${\displaystyle M}$, the independence matroid polytope is equal to the polymatroid determined by ${\displaystyle \psi }$.

The flag matroid polytope is another polytope constructed from the bases of matroids. A flag ${\displaystyle {\mathcal {F}}}$ is a strictly increasing sequence

${\displaystyle F^{1}\subset F^{2}\subset \cdots \subset F^{m}\,}$

of finite sets.^[4] Let ${\displaystyle k_{i}}$ be the cardinality of the set ${\displaystyle F_{i}}$. Two matroids ${\displaystyle M}$ and ${\displaystyle N}$ are said to be concordant if their rank functions satisfy

${\displaystyle r_{M}(Y)-r_{M}(X)\leq r_{N}(Y)-r_{N}(X){\text{ for all }}X\subset Y\subseteq E.\,}$

Given pairwise concordant matroids ${\displaystyle M_{1},\dots ,M_{m}}$ on the ground set ${\displaystyle E}$ with ranks ${\displaystyle r_{1}<\cdots <r_{m}}$, consider the collection of flags ${\displaystyle (B_{1},\dots ,B_{m})}$ where ${\displaystyle B_{i}}$ is a basis of the matroid ${\displaystyle M_{i}}$ and ${\displaystyle B_{1}\subset \cdots \subset B_{m}}$. Such a collection of flags is a flag matroid ${\displaystyle {\mathcal {F}}}$. The matroids ${\displaystyle M_{1},\dots ,M_{m}}$ are called the constituents of ${\displaystyle {\mathcal {F}}}$. For each flag ${\displaystyle B=(B_{1},\dots ,B_{m})}$ in a flag matroid ${\displaystyle {\mathcal {F}}}$, let ${\displaystyle v_{B}}$ be the sum of the indicator vectors of each basis in ${\displaystyle B}$

${\displaystyle v_{B}=v_{B_{1}}+\cdots +v_{B_{m}}.\,}$

Given a flag matroid ${\displaystyle {\mathcal {F}}}$, the flag matroid polytope ${\displaystyle P_{\mathcal {F}}}$ is the convex hull of the set

${\displaystyle \{v_{B}\mid B{\text{ is a flag in }}{\mathcal {F}}\}.}$

A flag matroid polytope can be written as a Minkowski sum of the (basis) matroid polytopes of the constituent matroids:^[4]

${\displaystyle P_{\mathcal {F}}=P_{M_{1}}+\cdots +P_{M_{k}}.\,}$