Convex hull of indicator vectors of bases
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 formula_1, the matroid polytope formula_2 is the convex hull of the indicator vectors of the bases of formula_1.
Definition.
Let formula_1 be a matroid on formula_5 elements. Given a basis formula_6 of formula_1, the indicator vector of formula_8 is
formula_9
where formula_10 is the standard formula_11th unit vector in formula_12. The matroid polytope formula_2 is the convex hull of the set
formula_14
 formula_16
That is, all 2-element subsets of formula_17 except formula_18. The corresponding indicator vectors of formula_19 are
 formula_20
The matroid polytope of formula_21 is
 formula_22
These points form four equilateral triangles at point formula_23, therefore its convex hull is the square pyramid by definition.
 formula_49
where formula_50 is the ground set of the matroid formula_21 and formula_52 is the signed beta invariant of formula_21:
 formula_54
 formula_55
formula_56
Related polytopes.
Independence matroid polytope.
The matroid independence polytope or independence matroid polytope is the convex hull of the set
formula_57
The (basis) matroid polytope is a face of the independence matroid polytope. Given the rank formula_58 of a matroid formula_21, the independence matroid polytope is equal to the polymatroid determined by formula_58.
Flag matroid polytope.
The flag matroid polytope is another polytope constructed from the bases of matroids. A flag formula_61 is a strictly increasing sequence
formula_62
of finite sets. Let formula_63 be the cardinality of the set formula_64. Two matroids formula_21 and formula_66 are said to be concordant if their rank functions satisfy
 formula_67
Given pairwise concordant matroids formula_68 on the ground set formula_50 with ranks formula_70, consider the collection of flags formula_71 where formula_72 is a basis of the matroid formula_73 and formula_74. Such a collection of flags is a flag matroid formula_75. The matroids formula_68 are called the constituents of formula_75.
For each flag formula_78 in a flag matroid formula_75, let formula_80 be the sum of the indicator vectors of each basis in formula_81
 formula_82
Given a flag matroid formula_75, the flag matroid polytope formula_84 is the convex hull of the set
formula_85
A flag matroid polytope can be written as a Minkowski sum of the (basis) matroid polytopes of the constituent matroids:
 formula_86