Splits and k-Splits of the Hypersimplex
Benjamin Schröter
Technische Universität Berlin

January 20, 2017
Osaka, Japan
Algebraic and Geometric Combinatorics on Convex Polytopes

Matroids
A (d, n)-matroid assigns to each subset of S ⊂ [n] a rank rk(S) ∈ Z, s.t.
rk(∅) = 0andrk([n]) = drk(S) ≤ rk(S ∪ e) ≤ rk(S) + 1 for e ∈ [n]rk(S) + rk(S ∪ f ∪ g) ≤ rk(S ∪ f ) + rk(S ∪ g) for f , g ∈ [n]A d-set S ⊂ [n] is a basis if rk(S) = d.

MatroidsA (d, n)-matroid assigns to each subset of S ⊂ [n] a rank rk(S) ∈ Z, s.t.
rk(∅) = 0andrk([n]) = drk(S) ≤ rk(S ∪ e) ≤ rk(S) + 1 for e ∈ [n]rk(S) + rk(S ∪ f ∪ g) ≤ rk(S ∪ f ) + rk(S ∪ g) for f , g ∈ [n]A d-set S ⊂ [n] is a basis if rk(S) = d.

ExampleI The rank function of the uniform matroid Ud,n is rk(S) = min{# S, d}.

All d-sets are bases in this case.
I For a list of vectors v1 , . . . , vn the following defines a rank functionrk(S) = dim span{vi : i ∈ S} .
The corresponding matroid is called realizable.

Matroid Polytopes
The convex hull of the characteristic vectors of the bases of a matroid M isthe matroid polytope. For the uniform matroid this is the hypersimplex(∆(d, n) =x ∈ RnnX)

xi = d and xi ≥ 0.

i=1

An outer describtion for the matroid polytope of M isPM =x ∈ ∆(d, n)

Xxi ≤ rk(F ) for all subsets F of [n]i∈FA set F is a flacet if the corresponding inequality is facet defining.

ExampleThe matroid of the columns of1213!

1 0 1 10 1 1 1

has 5 bases and rk(34) = 1

23143424.

The Dressiann

We lift the vertices of ∆(d, n) with a height function π ∈ R d .
Liftings that decompose ∆(d, n) into matroid polytopes are called tropical
Plücker vectors or valuations on the uniform matroid. Tropical Plücker
vectors correspond to tropical linear spaces.

Example(v , π(v ))(v , 0)

The Dressiann

We lift the vertices of ∆(d, n) with a height function π ∈ R d .
Liftings that decompose ∆(d, n) into matroid polytopes are called tropical
Plücker vectors or valuations on the uniform matroid. Tropical Plücker
vectors correspond to tropical linear spaces.
The Dressian Dr(d, n) is the subfan of the secondary fan of tropical Plücker
vectors. This is the moduli space of all regular tropical linear spaces.

Example(v , π(v ))(v , 0)

The Dressian
The Dressian has been studied by various people.
(Fink, Herrman, Jensen, Joswig, Kapranov, Rincon, Speyer, Sturmfels ...)I Dr(2, n) is the space of phylogenetic trees.
I For d > 2 only Dr(3, 6), Dr(3, 7) and Dr(3, 8) are completely known.
I All the rays of the above examples correspond to tropicalizations oflinear spaces.
I A tropical point configuration gives rise to a matroid subdivision – thisis obtained from a tropicalization of a linear space. (Stiefel map)
I The dimension of Dr (3, n) is in Θ(n2 ), that implies that ‘most’ points

in the Dressian are not tropicalizations of linear spaces.

The DressianThe Dressian has been studied by various people.
(Fink, Herrman, Jensen, Joswig, Kapranov, Rincon, Speyer, Sturmfels ...)I Dr(2, n) is the space of phylogenetic trees.
I For d > 2 only Dr(3, 6), Dr(3, 7) and Dr(3, 8) are completely known.
I All the rays of the above examples correspond to tropicalizations oflinear spaces.
I A tropical point configuration gives rise to a matroid subdivision – thisis obtained from a tropicalization of a linear space. (Stiefel map)
I The dimension of Dr (3, n) is in Θ(n2 ), that implies that ‘most’ points

in the Dressian are not tropicalizations of linear spaces.

Questions
I What is the dimension of Dr(d, n)?
I Are all of the rays of Dr(d, n) tropicalizations of linear spaces?

Answers via corank vectors of split matroids
Theorem (Joswig, S. 2016)
The ’corank vector’ of a ’split matroid’ M is contained in the interior of asimplicial cone in Dr (d, n). Moreover,!

1 n− 1 ≤ dim Dr(d, n) ≤n d!

n−2−1 .
d −1

For fixed d the dimension of the Dressian is of order Θ(nd−1 ).

Theorem (Joswig, S. 2016)
Let M be a connected split (d, n)-matroid. The ’corank vector’ of the’series-free lift’ of M is a ray in the Dressian Dr(d + 1, n + 2). This raycorresponds to the tropicalization of a linear space if and only if M isrealizable.

Canonical Subdivisions and Corank Vectors
Given a matroid M, the corank-function ρ(M) is the height function that
lifts the vertex of ∆(d, n) corresponding to S to height d − rk(S).
Speyer 2005: The vector ρ(M) is a tropical Plücker vector.
The polytope PM occurs as a cell in the induced subdivision.
Feichtner, Sturmfels 2005: This cell is maximal if and only if M isconnected.

Lemma (Speyer 2005; Joswig, S. 2016)
The vector ρ(M) corresponds to a tropicalization of a linear space if andonly if M is realizable.

Splits
A split of ∆(d, n) is a subdivision with exactly two maximal faces. Two
split-hyperplanes are compatible if they do not intersect in the interior of∆(d, n).

Lemma (Joswig, S. 2016)
I The facets of PM are either supported by hypersimplex splits or arehypersimplex facets.
I Two flacets F and G are compatible if and only if#(F ∩ G) + d ≤ rk(F ) + rk(G) .

We call a matroid a split matroid if its flacets form a compatible system ofhypersimplex splits.

Split and Paving Matroids
A matroid is paving if its rank function satisfies
rk(S) = # S for all sets S with # S ≤ d − 1 .
It is conjectured that almost all matroids are paving.

Theorem (Joswig, S. 2016)
A connected (d, n)-matroid M is paving if and only if it is a split matroid
such that each split flacet has rank d − 1.
Remark: Split matroids are closed under dualization.
There is a excluded-minor characterization for the class of split matroids.

The percentage of paving matroids among the isomorphismclasses of all matroids of rank d on n elements
d\n4

5678

91011122345678
9
1011

57
50
100

46
31
40
100

43
24
22
33
100

38
21
17
14
29
100

36
21
34
121025
100

33
30
77
63
14
7
22
100

32
52
−
−
−
17
5
20
100

30
78
−
−−
−
194
18
100

29
91
−
−
−−
−
16
3
17

This computation has been done with polymake.
It is based on data from Matsumoto, Moriyama, Imai and Bremner.

The percentage of split matroids among the isomorphismclasses of all matroids of rank d on n elements
d\n4567891011122345678
910
11

100
100
100

100
100
100
100

100
89
100
100
100

100
75
75
100
100
100

100
60
60
60
100
100
100

100
52
82
82
52
100
100
100

100
61
−−−61
100
100
100

100
80
−−−−80
100
100
100

100
91
−−−−−91
100
100

This computation has been done with polymake.
It is based on data from Matsumoto, Moriyama, Imai and Bremner.

Dimension of the DressianTheorem (Joswig, S. 2016)
The corank vector ρ(M) of a split matroid M is contained in the interior ofa simplicial cone in Dr (d, n). Moreover,!

1 n− 1 ≤ dim Dr(d, n) ≤n d!

n−2−1 .
d −1

For fixed d the dimension of the Dressian is of order Θ(nd−1 ).

Dimension of the DressianTheorem (Joswig, S. 2016)
The corank vector ρ(M) of a split matroid M is contained in the interior ofa simplicial cone in Dr (d, n). Moreover,!

1 n− 1 ≤ dim Dr(d, n) ≤n d!

n−2−1 .
d −1For fixed d the dimension of the Dressian is of order Θ(nd−1 ).
upper bound: Speyer’s f -vector bound on the number of vertices of atropical linear space.
lower bound: Knuth’s construction for a stable set in the vertex-edge-graphof ∆(d, n) – a Johnson graph – gives a compatible set ofvertex splits.

Rays in the Secondary Fan

Idea: Embed the point configuration P and its subdivision into P × [−1, 1].
In our situation take ∆(d, n) × ∆(1, 2) ⊂ ∆(d + 1, n + 2).
The construction uses the choice of a maximal cell. The hourglass shape
reduces the dimension.

Rays of the Dressian
Let M be a connected split matroid and sf(M) the (d + 2, n + 2)-matroid,that is the series-extension at f of the free extension M +[n] f .

Example(2, 6)-matroid M with 3 split flacets. The corank subdivision of sf(M).

Rays of the Dressian
Let M be a connected split matroid and sf(M) the (d + 2, n + 2)-matroid,that is the series-extension at f of the free extension M +[n] f .

Example(2, 6)-matroid M with 3 split flacets. The corank subdivision of sf(M).
I PM × PU
1,2 is a facet of Psf(M) .
I All facets are connected with Psf(M)I The dual graph is 2-connected.
I All cycles in the dual graph havelength 3.

.

Rays of the Dressian
Let M be a connected split matroid and sf(M) the (d + 2, n + 2)-matroid,that is the series-extension at f of the free extension M +[n] f .

Theorem (Joswig, S. 2016)
The corank vector of the series-free lift sf(M) is a ray in the DressianDr(d + 1, n + 2). This ray corresponds to the tropicalization of a linear
space if and only if M is realizable.

Example(2, 6)-matroid M with 3 split flacets. The corank subdivision of sf(M).
I PM × PU
1,2 is a facet of Psf(M) .
I All facets are connected with Psf(M)I The dual graph is 2-connected.
I All cycles in the dual graph havelength 3.

.

Nested Matroids
A (d, n)-matroid N is called nested if its split flacets form a chain
F1 ( · · · ( Fk−1 . The matroid polytope of N is given byPN =x ∈ ∆(d, n)

Xxi ≤ rk(F` ), for all 1 ≤ ` ≤ k − 1i∈F`.

All flacets of N are incompatible if k > 2.

ExampleThe series-parallel lift sf k (U1,2 ) is a nested matroid.
This matroid has k − 1 split flacets.
The bounded part of the corresponding tropical linear space is a k-simplex.

k-Splits
A k-split is a subdivision of a point configuration into k maximal cells whichintersect in an inner face of codim. k−1. The dual of a k-split is ak-simplex.

Theorem (Herrmann 2009)
A k-split is a coarsest regular subdivision and induced by a polyhedral fanwith k rays and k maximal cells.

k-Splits
A k-split is a subdivision of a point configuration into k maximal cells whichintersect in an inner face of codim. k−1. The dual of a k-split is ak-simplex.

Theorem (Herrmann 2009)
A k-split is a coarsest regular subdivision and induced by a polyhedral fan
with k rays and k maximal cells.

ExampleSplits are the same as 2-splits.

k-Splits
A k-split is a subdivision of a point configuration into k maximal cells whichintersect in an inner face of codim. k−1. The dual of a k-split is ak-simplex.

Theorem (Herrmann 2009)
A k-split is a coarsest regular subdivision and induced by a polyhedral fanwith k rays and k maximal cells.

ExampleSplits are the same as 2-splits. Two examples of 3-splits:k-Splits of ∆(d, n) and ∆d−1 × ∆n−d−1
Let eI be a vertex of ∆(d, n), that is in the intersection of all maximal cellsof a k-split. Each such maximal cell intersects the vertex figure
F(eI ) =x ∈ ∆(d, n)Xi∈Ixi = d − 1full dimensional. The vertex figure is isomorphic to the product of simplices∆d−1 × ∆n−d−1 . Interior points of the induced subdivision are redundant.

Example∆(2, 4)∆1 × ∆1

Consequences: Classification of all k-splits in ∆(d, n)Theorem (S. 2017+ )Each k-split of the hypersimplex ∆(d, n) is a matroid subdivision.
The k maximal cells are connected nested matroids with k−1 split flacets orequivalently k+1 cyclic flats.
Moreover, this subdivision is realizable by a tropical point configuration, i.e.,
an image under the Stiefel map.

Example123434∆(2, 4)∆1 × ∆1

∅

1234
12∅

Next Step
Express other subdivisions as combinations of k-splits.

’+’’=’’–’