Matroid polytope

In mathematics, a matroid polytope, also called a matroid basis polytope or basis matroid polytope to distinguish it from other polytopes derived from a matroid, is a polytope constructed via the bases of a matroid. Given a matroid $M$, the matroid polytope $P_M$ is the convex hull of the indicator vectors of the bases of $M$.

Definition

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

$\mathbf e_B := \sum_{i \in B} \mathbf e_i,$

where $\mathbf e_i$ is the standard $i$th unit vector in $\mathbb{R}^n$. The matroid polytope $P_M$ is the convex hull of the set

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

Examples

Square pyramid

Octahedron

• Let $M$ be the rank 2 matroid on 4 elements with bases

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

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

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

The matroid polytope of $M$ is

$P_M = \text{conv}\{\{1,1,0,0\}, \{1,0,1,0\}, \{1,0,0,1\}, \{0,1,1,0\}, \{0,1,0,1\}\},$

which is the square pyramid.

• Let $N$ be the rank 2 matroid on 4 elements with bases that are all 2-element subsets of $\{1,2,3,4\}$. The corresponding matroid polytope $P_N$ is the octahedron. Observe that the polytope $P_M$ from the previous example is contained in $P_N$.

• If $M$ is the uniform matroid of rank $r$ on $n$ elements, then the matroid polytope $P_M$ is the hypersimplex $\Delta_n^r$.^[1]

Properties

• A matroid polytope is contained in the hypersimplex $\Delta_n^r$, where $r$ is the rank of the associated matroid and $n$ is the size of the ground set of the associated matroid.^[2]

• Every edge of a matroid polytope $P_M$ is a parallel translate of $e_i-e_j$ for some $i,j\in E$, the ground set of the associated matroid. In other words, the edges of $P_M$ correspond exactly to the pairs of bases $B, B'$ that satisfy the basis exchange property: $B' = B\setminus{i\cup j}$ for some $i,j\in E.$^[2]

• Matroid polytopes are members of the family of generalized permutohedra.^[3]

• Let $r:2^E \rightarrow \mathbb{Z}$ be the rank function of a matroid $M$. The matroid polytope $P_M$ can be written uniquely as a signed Minkowski sum of simplices:^[3]

$P_M = \sum_{A\subseteq E} \tilde{\beta}(M/A) \Delta_{E-A}$

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

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

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

Related polytopes

Independence matroid polytope

The independence matroid polytope is the convex hull of the set

$\{\, \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 $\psi$ of a matroid $M$, the independence matroid polytope is equal to the polymatroid determined by $\psi$.

Flag matroid polytope

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

$F^1 \subset F^2\subset \cdots \subset F^m \,$

of finite sets.^[4] Let $k_i$ be the cardinality of the set $F_i$. Two matroids $M$ and $N$ are said to be concordant if their rank functions satisfy

$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 $M_1,\dots,M_m$ on the ground set $E$ with ranks $r_1<\cdots <r_m$, consider the collection of flags $(B_1,\dots, B_m)$ where $B_i$ is a basis of the matroid $M_i$ and $B_1 \subset \cdots\subset B_m$. Such a collection of flags is a flag matroid $\mathcal{F}$. The matroids $M_1,\dots,M_m$ are called the constituents of $\mathcal{F}$. For each flag $B=(B_1,\dots,B_m)$ in a flag matroid $\mathcal{F}$, let $v_B$ be the sum of the indicator vectors of each basis in $B$

$v_B = v_{B_1}+\cdots+v_{B_m}. \,$

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

$\{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]

$P_\mathcal{F} = P_{M_1} + \cdots + P_{M_k}. \,$

References

1. Grötschel, Martin (2004), "Cardinality homogeneous set systems, cycles in matroids, and associated polytopes", The Sharpest Cut: The Impact of Manfred Padberg and His Work, MPS/SIAM Ser. Optim., SIAM, Philadelphia, PA, pp. 99–120, MR 2077557. See in particular the remarks following Prop. 8.20 on p. 114.
2. Gelfand, I.M.; Goresky, R.M.; MacPherson, R.D.; Serganova, V.V. (1987). "Combinatorial geometries, convex polyhedra, and Schubert cells". Advances in Mathematics 63 (3): 301–316. doi:10.1016/0001-8708(87)90059-4.
3. Ardila, Federico; Benedetti, Carolina; Doker, Jeffrey (2010). "Matroid polytopes and their volumes". Discrete and Computational Geometry 43 (4): 841–854. arXiv:0810.3947. doi:10.1007/s00454-009-9232-9.
4. Borovik, Alexandre V.; Gelfand, I.M.; White, Neil (2013). "Coxeter Matroids". Progress in Mathematics 216. doi:10.1007/978-1-4612-2066-4.