Delta matroid polytopes always have dyadic volume triangulations
Regular dyadic triangulations of delta-matroid polytopes
Discrete Mathematics
Summary
Some shapes, called polytopes, can be broken down into simpler pieces called simplices. For certain shapes related to math structures known as matroids, these pieces can all have the smallest possible volume. But for related shapes called delta-matroid polytopes, this isn’t always true. The authors found that while the simplest kind of these shapes may not break down so simply, all delta-matroid polytopes can be subdivided into pieces whose volumes are powers of two, giving a neat structured way to break them apart.
What this means in practice
- •For combinatorial optimization teams: Use structured triangulations of delta-matroid polytopes to design algorithms that handle type B combinatorial objects more efficiently.
- •For computational geometry developers: Implement triangulation methods that guarantee dyadic volume simplices for integral type B generalized permutohedra, improving numerical stability and integrality properties.
A theory result. No direct application yet.
Authors
Mathieu Vallée
Abstract
Backman and Liu proved that every integral generalized permutohedron of type $A$, and in particular every matroid base polytope, admits a regular unimodular triangulation. The analogous statement fails in type $B$: the delta-matroid simplex \[\operatorname*{conv}\{\mathbf{0},\ e_1+e_2,\ e_1+e_3,\ e_2+e_3\}\] has normalized volume $2$ and no lattice points other than its vertices, so it has no unimodular triangulation. We show moreover that, up to the natural symmetries of the $0/1$ cube and deletion of constant coordinates, it is the unique non-unimodular delta-matroid polytope that is a simplex. We prove instead that every delta-matroid polytope admits a regular dyadic triangulation, meaning a lattice triangulation whose maximal simplices have normalized volumes that are powers of two. More generally, every integral type $B$ generalized permutohedron admits such a triangulation. The main lattice-theoretic ingredient is that the type $B$ root configuration forms a totally dyadic system, a $2$-local analogue of total unimodularity. As a consequence, these polytopes satisfy a dyadic version of the integer decomposition property. In each dimension the corresponding exponent can be chosen uniformly, even though ordinary integer decomposition can fail for delta-matroid polytopes.