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

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

↑ 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.0 2.1 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.0 3.1 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.0 4.1 Borovik, Alexandre V.; Gelfand, I.M.; White, Neil (2013). "Coxeter Matroids". Progress in Mathematics 216. doi:10.1007/978-1-4612-2066-4.