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 .
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
The matroid independence polytope or independence matroid polytope is the convex hull of the set
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 .
The flag matroid polytope is another polytope constructed from the bases of matroids. A flag is a strictly increasing sequence
of finite sets.[4] Let be the cardinality of the set . Two matroids and are said to be concordant if their rank functions satisfy
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
A flag matroid polytope can be written as a Minkowski sum of the (basis) matroid polytopes of the constituent matroids:[4]