matroid polytope

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

:$\backslash mathbf\; e\_B\; :=\; \backslash sum\_\{i\; \backslash in\; B\}\; \backslash mathbf\; e\_i,$

where $\backslash mathbf\; e\_i$ is the standard $i$th unit vector in $\backslash mathbb\{R\}^n$. The matroid polytope $P\_M$ is the convex hull of the set

:$\backslash \{\backslash mathbf\; e\_B\; \backslash mid\; B\; \backslash text\{\; is\; a\; basis\; of\; \}\; M\backslash \}\; \backslash subseteq\; \backslash mathbb\{R\}^n.$

Image:Square pyramid.png

Image:Octahedron.svg

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

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

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

:: $\backslash \{\backslash \{1,1,0,0\backslash \},\; \backslash \{1,0,1,0\backslash \},\; \backslash \{1,0,0,1\backslash \},\; \backslash \{0,1,1,0\backslash \},\; \backslash \{0,1,0,1\backslash \}\backslash \}.$

:The matroid polytope of $M$ is

: $P\_M\; =\; \backslash text\{conv\}\backslash \{\backslash \{1,1,0,0\backslash \},\; \backslash \{1,0,1,0\backslash \},\; \backslash \{1,0,0,1\backslash \},\; \backslash \{0,1,1,0\backslash \},\; \backslash \{0,1,0,1\backslash \}\backslash \}.$

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

• Let $N$ be the rank 2 matroid on 4 elements with bases that are all 2-element subsets of $\backslash \{1,2,3,4\backslash \}$. 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 $\backslash Delta\_n^r$.{{citation

| last = Grötschel | first = Martin | authorlink = Martin Grötschel

| contribution = Cardinality homogeneous set systems, cycles in matroids, and associated polytopes

| mr = 2077557

| pages = 99–120

| publisher = SIAM, Philadelphia, PA

| series = MPS/SIAM Ser. Optim.

| title = The Sharpest Cut: The Impact of Manfred Padberg and His Work

| year = 2004}}. See in particular the remarks following Prop. 8.20 on [https://books.google.com/books?id=iXJxerJLyTEC&oi=fnd&pg=PA114 p. 114].

• A matroid polytope is contained in the hypersimplex $\backslash 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.{{cite journal|last1=Gelfand |first1=I.M.|last2=Goresky |first2=R.M. |last3=MacPherson |first3=R.D. |last4=Serganova |first4=V.V.|author4-link= Vera Serganova |year=1987|title=Combinatorial geometries, convex polyhedra, and Schubert cells|journal=Advances in Mathematics|volume=63|issue=3|pages=301–316|doi=10.1016/0001-8708(87)90059-4 |doi-access=free}} Moreover, the vertices of $P\_M$ are a subset of the vertices of $\backslash Delta\_n^r$.
• Every edge of a matroid polytope $P\_M$ is a parallel translate of $e\_i-e\_j$ for some $i,j\backslash 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\text{'}$ that satisfy the basis exchange property: $B\text{'}\; =\; B\backslash setminus\{i\backslash cup\; j\}$ for some $i,j\backslash in\; E.$ 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.{{cite journal |first1=Federico |last1=Ardila |first2=Carolina|last2=Benedetti|first3=Jeffrey|last3=Doker |title=Matroid polytopes and their volumes |journal=Discrete & Computational Geometry |volume=43 |issue=4 |pages=841–854 |year=2010 |arxiv=0810.3947 |doi=10.1007/s00454-009-9232-9}}
• Let $r:2^E\; \backslash rightarrow\; \backslash 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:

:: $P\_M\; =\; \backslash sum\_\{A\backslash subseteq\; E\}\; \backslash tilde\{\backslash beta\}(M/A)\; \backslash Delta\_\{E-A\}$

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

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

:: $\backslash beta(M)\; =\; (-1)^\{r(M)\}\; \backslash sum\_\{X\backslash subseteq\; E\}\; (-1)^$

X

r(X).

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

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

:$\backslash \{\backslash ,\; \backslash mathbf\; e\_I\; \backslash mid\; I\; \backslash text\{\; is\; an\; independent\; set\; of\; \}\; M\; \backslash ,\backslash \}\; \backslash subseteq\; \backslash mathbb\; R^n.$

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

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

:$F^1\; \backslash subset\; F^2\backslash subset\; \backslash cdots\; \backslash subset\; F^m\; \backslash ,$

of finite sets.{{cite journal|last1=Borovik |first1=Alexandre V.|last2= Gelfand |first2=I.M. |last3=White |first3=Neil |title=Coxeter Matroids|journal=Progress in Mathematics|volume=216 |year=2013 |doi=10.1007/978-1-4612-2066-4 |isbn=978-1-4612-7400-1 }} 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)\; \backslash leq\; r\_N(Y)\; -\; r\_N(X)\; \backslash text\{\; for\; all\; \}\; X\backslash subset\; Y\; \backslash subseteq\; E.\; \backslash ,$

Given pairwise concordant matroids $M\_1,\backslash dots,M\_m$ on the ground set $E$ with ranks flag matroid $\backslash mathcal\{F\}$. The matroids $M\_1,\backslash dots,M\_m$ are called the constituents of $\backslash mathcal\{F\}$.

For each flag $B=(B\_1,\backslash dots,B\_m)$ in a flag matroid $\backslash mathcal\{F\}$, let $v\_B$ be the sum of the indicator vectors of each basis in $B$

: $v\_B\; =\; v\_\{B\_1\}+\backslash cdots+v\_\{B\_m\}.\; \backslash ,$

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

:$\backslash \{v\_B\; \backslash mid\; B\backslash text\{\; is\; a\; flag\; in\; \}\backslash mathcal\{F\}\backslash \}.$

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

: $P\_\backslash mathcal\{F\}\; =\; P\_\{M\_1\}\; +\; \backslash cdots\; +\; P\_\{M\_k\}.\; \backslash ,$

Polytope

Category:Polytopes