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

M

, the matroid polytope

PM

is the convex hull of the indicator vectors of the bases of

M

.

Definition

Let

M

be a matroid on

n

elements. Given a basis

B\subseteq\{1,...,n\}

of

M

, the indicator vector of

B

is

eB:=\sumiei,

where

ei

is the standard

i

th unit vector in

Rn

. The matroid polytope

PM

is the convex hull of the set

\{eB\midBisabasisofM\}\subseteqRn.

Examples

M

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

\{1,2,3,4\}

except

\{3,4\}

. The corresponding indicator vectors of

l{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

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

\{1,1,0,0\}

, therefore its convex hull is the square pyramid by definition.

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

PN

is the octahedron. Observe that the polytope

PM

from the previous example is contained in

PN

.

M

is the uniform matroid of rank

r

on

n

elements, then the matroid polytope

PM

is the hypersimplex
r
\Delta
n
.[1]

Properties

r
\Delta
n
, where

r

is the rank of the associated matroid and

n

is the size of the ground set of the associated matroid.[2] Moreover, the vertices of

PM

are a subset of the vertices of
r
\Delta
n
.

PM

is a parallel translate of

ei-ej

for some

i,j\inE

, the ground set of the associated matroid. In other words, the edges of

PM

correspond exactly to the pairs of bases

B,B'

that satisfy the basis exchange property:

B'=B\setminus{i\cupj}

for some

i,j\inE.

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

r:2EZ

be the rank function of a matroid

M

. The matroid polytope

PM

can be written uniquely as a signed Minkowski sum of simplices:[3]

PM=\sumA\subseteq\tilde{\beta}(M/A)\DeltaE-A

where

E

is the ground set of the matroid

M

and

\beta(M)

is the signed beta invariant of

M

:

\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

\psi

of a matroid

M

, the independence matroid polytope is equal to the polymatroid determined by

\psi

.

Flag matroid polytope

The flag matroid polytope is another polytope constructed from the bases of matroids. A flag

l{F}

is a strictly increasing sequence

F1\subsetF2\subset\subsetFm

of finite sets.[4] Let

ki

be the cardinality of the set

Fi

. Two matroids

M

and

N

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

M1,...,Mm

on the ground set

E

with ranks

r1<<rm

, consider the collection of flags

(B1,...,Bm)

where

Bi

is a basis of the matroid

Mi

and

B1\subset\subsetBm

. Such a collection of flags is a flag matroid

l{F}

. The matroids

M1,...,Mm

are called the constituents of

l{F}

.For each flag

B=(B1,...,Bm)

in a flag matroid

l{F}

, let

vB

be the sum of the indicator vectors of each basis in

B

vB=

v
B1
+ … +v
Bm

.

Given a flag matroid

l{F}

, the flag matroid polytope

Pl{F}

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]

Pl{F}=

P
M1

++

P
Mk

.

References

  1. . See in particular the remarks following Prop. 8.20 on p. 114.
  2. 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.
  3. Federico . Ardila . Carolina. Benedetti. Jeffrey. Doker . Matroid polytopes and their volumes . . 43 . 4 . 841–854 . 2010 . 0810.3947 . 10.1007/s00454-009-9232-9.
  4. Borovik . Alexandre V.. Gelfand . I.M. . White . Neil . Coxeter Matroids. Progress in Mathematics. 216 . 2013 . 10.1007/978-1-4612-2066-4 .