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] More precisely, the vertices of $P_{M}$ are a subset of the vertices of $\Delta _{n}^{r}$ .
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 matroid independence polytope or 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.
1 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.
1 2 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.
1 2 Borovik, Alexandre V.; Gelfand, I.M.; White, Neil (2013). "Coxeter Matroids". Progress in Mathematics. 216. doi:10.1007/978-1-4612-2066-4.

This article is issued from Wikipedia - version of the 10/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.