Matroid polytope explained
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
, the matroid polytope
is the
convex hull of the
indicator vectors of the bases of
.
Definition
Let
be a
matroid on
elements. Given a basis
of
, the
indicator vector of
is
where
is the standard
th unit vector in
. The
matroid polytope
is the
convex hull of the set
\{eB\midBisabasisofM\}\subseteqRn.
Examples
be the rank 2 matroid on 4 elements with bases
l{B}(M)=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}.
That is, all 2-element subsets of
except
. The corresponding indicator vectors of
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
is
PM=conv\{\{1,1,0,0\},\{1,0,1,0\},\{1,0,0,1\},\{0,1,1,0\},\{0,1,0,1\}\}.
These points form four equilateral triangles at point
, therefore its convex hull is the
square pyramid by definition.
be the rank 2 matroid on 4 elements with bases that are
all 2-element subsets of
. The corresponding matroid polytope
is the
octahedron. Observe that the polytope
from the previous example is contained in
.
is the
uniform matroid of rank
on
elements, then the matroid polytope
is the
hypersimplex
.
[1] Properties
, where
is the rank of the associated matroid and
is the size of the ground set of the associated matroid.
[2] Moreover, the vertices of
are a subset of the vertices of
.
- Every edge of a matroid polytope
is a parallel translate of
for some
, the ground set of the associated matroid. In other words, the edges of
correspond exactly to the pairs of bases
that satisfy the basis exchange property:
for some
[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.
be the rank function of a matroid
. The matroid polytope
can be written uniquely as a signed
Minkowski sum of
simplices:
[3] PM=\sumA\subseteq\tilde{\beta}(M/A)\DeltaE-A
where
is the ground set of the matroid
and
is the signed beta invariant of
:
\tilde{\beta}(M)=(-1)r(M)+1\beta(M),
\beta(M)=(-1)r(M)\sumX\subseteq(-1)|X|r(X).
PM:=
| E~|~\sum |
\left\{bf{x}\inR | |
| e\inU |
bf{x}(e)\leqr(U),\forallU\subseteqE\right\}
Related polytopes
Independence matroid polytope
The matroid independence polytope or independence matroid polytope is the convex hull of the set
\{eI\midIisanindependentsetofM\}\subseteqRn.
The (basis) matroid polytope is a face of the independence matroid polytope. Given the rank
of a matroid
, the independence matroid polytope is equal to the
polymatroid determined by
.
Flag matroid polytope
The flag matroid polytope is another polytope constructed from the bases of matroids. A flag
is a strictly increasing sequence
F1\subsetF2\subset … \subsetFm
of finite sets.[4] Let
be the cardinality of the set
. Two matroids
and
are said to be
concordant if their rank functions satisfy
rM(Y)-rM(X)\leqrN(Y)-rN(X)forallX\subsetY\subseteqE.
Given pairwise concordant matroids
on the ground set
with ranks
, consider the collection of flags
where
is a basis of the matroid
and
. Such a collection of flags is a
flag matroid
. The matroids
are called the
constituents of
.For each flag
in a flag matroid
, let
be the sum of the indicator vectors of each basis in
Given a flag matroid
, the
flag matroid polytope
is the convex hull of the set
\{vB\midBisaflaginl{F}\}.
A flag matroid polytope can be written as a Minkowski sum of the (basis) matroid polytopes of the constituent matroids:
[4]
References
- . See in particular the remarks following Prop. 8.20 on p. 114.
- Gelfand . I.M.. Goresky . R.M. . MacPherson . R.D. . Serganova . V.V.. Vera Serganova . 1987. Combinatorial geometries, convex polyhedra, and Schubert cells. Advances in Mathematics. 63. 3. 301 - 316. 10.1016/0001-8708(87)90059-4 . free.
- Federico . Ardila . Carolina. Benedetti. Jeffrey. Doker . Matroid polytopes and their volumes . . 43 . 4 . 841–854 . 2010 . 0810.3947 . 10.1007/s00454-009-9232-9.
- Borovik . Alexandre V.. Gelfand . I.M. . White . Neil . Coxeter Matroids. Progress in Mathematics. 216 . 2013 . 10.1007/978-1-4612-2066-4 .