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
.
Let
M
be a matroid on
n
elements. Given a basis
B
⊆
{
1
,
…
,
n
}
of
M
, the indicator vector of
B
is
e
B
:=
∑
i
∈
B
e
i
,
where
e
i
is the standard
i
th unit vector in
R
n
. The matroid polytope
P
M
is the convex hull of the set
{
e
B
∣
B
is a basis of
M
}
⊆
R
n
.
Let
M
be the rank 2 matroid on 4 elements with bases
That is, all 2-element subsets of
{
1
,
2
,
3
,
4
}
except
{
3
,
4
}
. The corresponding indicator vectors of
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
=
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
{
1
,
1
,
0
,
0
}
, 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
{
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
Δ
n
r
.
A matroid polytope is contained in the hypersimplex
Δ
n
r
, where
r
is the rank of the associated matroid and
n
is the size of the ground set of the associated matroid. More precisely, the vertices of
P
M
are a subset of the vertices of
Δ
n
r
.
Every edge of a matroid polytope
P
M
is a parallel translate of
e
i
−
e
j
for some
i
,
j
∈
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
∖
i
∪
j
for some
i
,
j
∈
E
.
Matroid polytopes are members of the family of generalized permutohedra.
Let
r
:
2
E
→
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:
where
E
is the ground set of the matroid
M
and
β
(
M
)
is the signed beta invariant of
M
:
β
~
(
M
)
=
(
−
1
)
r
(
M
)
+
1
β
(
M
)
,
β
(
M
)
=
(
−
1
)
r
(
M
)
∑
X
⊆
E
(
−
1
)
|
X
|
r
(
X
)
.
The matroid independence polytope or independence matroid polytope is the convex hull of the set
{
e
I
∣
I
is an independent set of
M
}
⊆
R
n
.
The (basis) matroid polytope is a face of the independence matroid polytope. Given the rank
ψ
of a matroid
M
, the independence matroid polytope is equal to the polymatroid determined by
ψ
.
The flag matroid polytope is another polytope constructed from the bases of matroids. A flag
F
is a strictly increasing sequence
F
1
⊂
F
2
⊂
⋯
⊂
F
m
of finite sets. 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
)
≤
r
N
(
Y
)
−
r
N
(
X
)
for all
X
⊂
Y
⊆
E
.
Given pairwise concordant matroids
M
1
,
…
,
M
m
on the ground set
E
with ranks
r
1
<
⋯
<
r
m
, consider the collection of flags
(
B
1
,
…
,
B
m
)
where
B
i
is a basis of the matroid
M
i
and
B
1
⊂
⋯
⊂
B
m
. Such a collection of flags is a flag matroid
F
. The matroids
M
1
,
…
,
M
m
are called the constituents of
F
. For each flag
B
=
(
B
1
,
…
,
B
m
)
in a flag matroid
F
, let
v
B
be the sum of the indicator vectors of each basis in
B
v
B
=
v
B
1
+
⋯
+
v
B
m
.
Given a flag matroid
F
, the flag matroid polytope
P
F
is the convex hull of the set
{
v
B
∣
B
is a flag in
F
}
.
A flag matroid polytope can be written as a Minkowski sum of the (basis) matroid polytopes of the constituent matroids:
P
F
=
P
M
1
+
⋯
+
P
M
k
.
