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 basesThat 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 . 
