Source-linked AI summary
Regular dyadic triangulations of delta-matroid polytopes
Mathieu Vallée
TL;DR
Unimodular triangulations do not extend from type A to all type B examples: a delta-matroid simplex has volume 2 and no other lattice points. The paper replaces unimodularity with dyadic triangulations, proving them for delta-matroid polytopes and, more generally, integral type B generalized permutohedra. It also proves a dimension-uniform dyadic decomposition property, although ordinary integer decomposition can fail for delta-matroid polytopes.
Problem
The type A unimodular-triangulation result fails for a delta-matroid simplex in type B, which has normalized volume 2 and no lattice points beyond its vertices.
Source: Introduction · p. 1Method
The paper uses a totally dyadic type B root configuration and a deletion–contraction induction to construct regular dyadic triangulations.
Source: Introduction · p. 1Results
Every delta-matroid polytope and every integral type B generalized permutohedron admits a regular dyadic triangulation.
Source: Introduction · p. 2Takeaways & Limitations
For each dimension, a uniform exponent gives a dyadic decomposition property for integral type B generalized permutohedra, even though ordinary integer decomposition can fail for delta-matroid polytopes.
Source: Introduction · p. 2A simplex in a triangulation of a delta-matroid polytope need not itself be a delta-matroid polytope, so the simplex classification does not limit triangulation simplices to volumes 1 and 2.
Source: §2 · p. 4
Abstract
from arXiv · showhide
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.
Introduction
A volume-2 delta-matroid simplex shows that unimodular triangulations fail in type B, but every delta-matroid polytope—and every integral type B generalized permutohedron—has a regular dyadic triangulation. The paper also establishes a dimension-uniform dyadic decomposition property.
Introduction
- The simplex conv{0, e1 + e2, e1 + e3, e2 + e3} has normalized volume 2 and no lattice points beyond its vertices, so it has no unimodular triangulation.Up to cube symmetries and deletion of constant coordinates, it is the unique non-unimodular delta-matroid simplex.Source: Introduction · p. 1, Figure 1 · p. 2
- The type B root directions form a totally dyadic system: every subconfiguration generates the saturated lattice of its span over Z[1/2].This is presented as the 2-local replacement for total unimodularity.Source: Introduction · p. 1
- Every delta-matroid polytope admits a regular dyadic triangulation, and every integral type B generalized permutohedron does as well.The type B result also applies in type C with the same Z^n lattice convention, and in particular to integral type D generalized permutohedra.Source: Introduction · p. 2
- Integer-coordinate dicing decomposes an integral type B generalized permutohedron into translates of delta-matroid polytopes, whose triangulations are globalized by regular dicing.Source: Introduction · p. 2
- Ordinary integer decomposition can fail for delta-matroid polytopes, while dyadic triangulations still yield dimension-uniform saturation.Source: Introduction · p. 2
- For each dimension n, a uniform exponent m_n gives a dyadic decomposition for every integral type B_n generalized permutohedron and every dilation.For x in kP ∩ Z^n, the theorem expresses 2^m_n x as a sum of 2^m_n k lattice points of P.Source: Introduction · p. 2
1. Preliminaries
The preliminaries set the lattice and polytope conventions, characterize delta-matroids through symmetric exchange and type B edge directions, and classify their simplex polytopes by normalized volume.
1.1. Notation.
- For a d-dimensional lattice polytope, normalized volume is d! times Euclidean volume relative to its direction-space lattice.The paper takes lattice notions and normalized volume with respect to Z^n.Source: §1.1 · p. 2
1.2. Delta-matroids and their polytopes
- A delta-matroid is a nonempty set system satisfying symmetric exchange, and its 0/1 characteristic polytope has type B root directions as edges.Even delta-matroids correspond to type D edge directions, so results for delta-matroids include the type D case.Source: §1.2 · p. 3
- Deletion and contraction preserve the delta-matroid property when nonempty, and every nonempty face of a delta-matroid polytope is again a delta-matroid polytope.Source: §1.2 · p. 3
- A delta-matroid simplex has normalized volume 1 or 2; volume 2 occurs only for the stated simplex, up to coordinate symmetries and deletion of constant coordinates.Every other delta-matroid simplex is unimodular.Source: §1.2 · p. 3
2. Thus
The simplex classification isolates the unique non-unimodular delta-matroid simplex, while the subsequent tools locate face directions in a symmetric resonance arrangement and control regular refinements by small perturbations.
2. Thus
- Among the classified cases, only the triangle of two-element sets has normalized volume 2; the other cases have normalized volume 1.The triangle yields the simplex of Figure 1, and coordinate permutations, reflections, and deletion or insertion of constant coordinates preserve normalized volume.Source: §2 · pp. 3–4
1.3. The symmetric resonance arrangement.
- Every face direction space of a delta-matroid polytope is a flat of the symmetric resonance arrangement.The facet normals are signed-subset vectors, so the active facet equations defining a face give an intersection of arrangement hyperplanes.Source: §1.3 · p. 5
1.4. Regular subdivisions.
- For bounded families of perturbing weights, one sufficiently small positive perturbation parameter uniformly refines the original regular subdivision.On each original cell, the refinement is induced by the restricted perturbing weight.Source: §1.4 · p. 5
2. Dyadic systems, simplices and triangulations
These sections develop dyadic lattice tools for triangulations: type B roots provide a totally dyadic system, and dyadicness is preserved under faces and suitable joins. Dyadic complementarity supplies the lattice condition connecting the component direction spaces.
2.1. Dyadic numbers and totally dyadic systems.
- The type B root configuration B+ is a totally dyadic system: every subset dyadically generates the saturated lattice of its span.The paper's minor argument establishes this property for the type B root directions.Source: §2.1 · pp. 5–6
2.2. Dyadic simplices.
- A lattice simplex is dyadic exactly when its normalized volume is a power of two, equivalently when its edge vectors dyadically generate its saturated direction lattice.The criterion also holds for edge vectors from any vertex or for the edges of any spanning tree on the vertices; every face of a dyadic simplex is dyadic.Source: §2.2 · pp. 6–7
- Dyadicness is restrictive: the stated 0/1 simplex has normalized volume 3 and is not a delta-matroid polytope because symmetric exchange fails.Its edge vector from 0 is not a type B root.Source: §2.2 · p. 7
2.3. Dyadic complementarity.
- For independent rational subspaces, dyadic complementarity is equivalent to their saturated-lattice sum having index a power of two in the saturated lattice of their combined span.When direction spaces are independent and dyadic-complementary, that condition is preserved by subspaces; direction spaces of delta-matroid polytopes are dyadic-complementary.Source: §2.3 · pp. 7–8
2.4. The join lemma.
- Joining dyadic simplices in consecutive integer slices produces a dyadic simplex when their direction spaces are independent and dyadic-complementary.The join has the vertices of both simplices, with the bridge edge completing the combined edge basis.Source: §2.4 · p. 8
3. Regular dyadic triangulations
A dimension-uniform regular weight yields dyadic triangulations for delta-matroid polytopes and, by coordinate dicing, for integral type B generalized permutohedra. These triangulations also give a dimension-uniform dyadic decomposition property.
3.1. The main theorem.
- Every delta-matroid polytope in R^n admits a regular dyadic triangulation induced by a dimension-uniform weight built recursively from B-generic functionals.Genericity makes the two face directions in each slice independent and dyadic-complementary, so joining dyadic cells preserves dyadicness.Source: §3.1 · pp. 9–10
3.2. Integral type B generalized permutohedra.
- Every integral type B generalized permutohedron admits a regular dyadic triangulation, and the same conclusion holds in type C with lattice Z^n and for integral type D polytopes.Integer coordinate dicing cuts the polytope into translates of delta-matroid polytopes, whose triangulations are glued by a global regular dicing construction.Source: §3.2 · pp. 10–11
3.3. The dyadic decomposition property.
- Exponent 0 of the dyadic decomposition property is precisely IDP, and Morales showed that it need not work for a delta-matroid polytope; any working exponent also permits every larger exponent.Source: §3.3 · p. 11
- For each dimension n, one exponent m_n works for every integral type B_n generalized permutohedron: 2^m_n x is a sum of 2^m_n k lattice points of P whenever x is in kP.The bound follows from a uniform upper bound on maximal simplex volumes among the finitely many delta-matroid polytopes in that dimension.Source: §3.3 · p. 11