CS Paper Radar

Regular dyadic triangulations of delta-matroid polytopes

Mathieu Vallée

cs.DM math.CO ·submitted 2026-09-16 08:55 UTC · v1
theory

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.

Comment
12 pages, comments are welcome

Closest papers

Nearest neighbours by meaning across the whole index.

Neither simpliciality nor mutation connectivity: conjectures of Las Vergnas and Cordovil-Las Vergnas fail

cs.DM math.CO ·2026-09-14 ·Qiyuan Gu, Kolja Knauer
similarity 0.60
Abstract · 9 pages

We construct a simple rank-$7$ oriented matroid on $24$ elements with no simplicial tope, disproving the Las Vergnas simplex conjecture from 1980. We then show that the mutation graph on uniform oriented matroids is disconnected for infinitely many values of rank $r$ and ground-set size $n$, disproving the Cordovil--Las Vergnas conjecture from 1988.

0.51

Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection

cs.DM math.CO ·2026-09-18 ·Yu Cong, Yajie Zhao
theory similarity 0.60
Abstract

The weighted $k$-matroid intersection problem asks for a maximum-weight set that is independent in each of $k$ matroids on a common ground set. The natural LP relaxation optimizes over the intersection of the $k$ matroid independent set polytopes. It is conjectured that this LP has integrality gap at most $k-1$. The conjecture is known for $k\le3$, but for $k\ge4$ the best general upper bound was $k$. We improve this bound to $k-1+1/k$. More generally, we prove that the natural LP of a $p$-matchoid has integrality gap at most $p-1+1/p$, with a deterministic LP-relative algorithm attaining the same factor. The matchoid extension resolves the $p$-matchoid part of a conjecture of Lee, Sviridenko, and Vondrák; projective planes give explicit tight instances whenever one of order $p-1$ exists.

0.25

Equitable Subpartitionability Does Not Characterize Box-TDI Polyhedra

cs.DM ·2026-10-09 ·Emiliano Lancini, Francesco Pisanu
similarity 0.55
Abstract · 6 pages

Equitable subpartitionability (ESP) is a sufficient condition for an integral system to be box-totally dual integral. We show that the converse fails even when alternative descriptions of the same polyhedron are allowed. We provide a geometrical characterization of polyhedra that can be described by ESP systems in terms of normal cones. We construct a four-dimensional integer polytope described by a totally equimodular matrix that admits no integral ESP description. This answers negatively a previously posed question by the same authors.

0.18

On integral polytopes related to Edmonds' problem

cs.DM math.CO ·2026-09-17 ·Hiroshi Hirai
similarity 0.54
Abstract

In this paper, we study polyhedral aspects on commutative and noncommutative Edmonds' problems for computing the rank of linear symbolic matrix $A = \sum_{k=1}^m A_k x_k$. We regard them as linear optimization over integral polytopes ${\cal P}(A)$ and ${\cal Q}(A)$, respectively, which are obtained by the convex hulls of exponent vectors of subdeterminants of~$A$ and its blow-ups $A^{\{d\}} = \sum_{k=1}^m A_k \otimes X_k$ $(d=1,2,\ldots)$. By extending previously known results on nc-rank, we establish a hierarchy of integral polytopes ${\cal P}(A) \subseteq {\cal P}^{\leq 2}(A) \subseteq {\cal P}^{\leq 3}(A) \subseteq \cdots = {\cal Q}(A)$ and show that the integrality gap of ${\cal Q}(A)$ relative to ${\cal P}(A)$ is at least $1/2$. Further, we show that if each $A_k$ is rank-2 skew-symmetric, then the above hierarchy terminates at the second level and the integrality gap is improved to $2/3$.

0.23

The Stable Marriage Polytope is Box-Totally Dual Integral

cs.DM math.CO ·2026-10-08 ·Michele Barbato, Emiliano Lancini
theory similarity 0.53
Abstract · 6 pages

A stable matching in a bipartite preference system is a matching that has no unmatched pair whose endpoints both prefer each other to their current assignments. Rothblum gave a linear description of the stable marriage polytope, the convex hull of the incidence vectors of stable matchings. We prove that this polytope is box-totally dual integral. The proof uses the affine representation of the stable marriage polytope as an order polytope together with the matricial characterization of box-TDI polyhedra. Since Kiraly and Pap proved that Rothblum's description is totally dual integral, our result further implies that Rothblum's system is box-totally dual integral.

0.34

Computing the minimal perimeter polygon for digital objects in the triangular tiling

cs.CG ·2026-09-12 ·Petra Wiederhold
published similarity 0.53
Abstract · Preprint from November 11, 2024

This work presents an algorithm, together with its correctness proof, to determine the minimum perimeter polygon (MPP) for digital objects given as regular complexes in the triangular plane tiling. Such objects are edge-adjacency-connected sets of triangle tiles that have no end tiles, and the point set union of all their tiles forms a simple polygon. Nevertheless, the boundary paths of the objects are not assumed to be simple. Then the MPP is a weakly simple polygon that coincides with the relative convex hull (i.e., geodesic hull) of a set $A$ with respect to a simple polygon $B$, where $A\subset B$, but $A$ is not necessarily a polygon, in fact it is generally not connected. Our MPP algorithm relies on constructing and iteratively constraining cones of visibility through forthcoming boundary tiles, it uses the structure of the canonical boundary path, the MPP frontier is the shortest polygonal curve following this path. We also propose a boundary tracing algorithm to obtain such paths from the objects.

0.58

Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration

cs.LO math.COmath.OC ·2026-10-08 ·Xavier Allamigeon, Yazid Id-Sahra, Pierre-Yves Strub
similarity 0.53
Abstract · 20 pages, 3 figures, 2 tables

The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed list of vertices, our method allows to certify in the proof assistant Rocq that the list is complete, or even exact. The cornerstone of the method is a new completeness criterion based on an abstract simplicial complex that generalizes a triangulation of the normal fan of the polyhedron. A significant advantage over previous approaches is that the usually expensive numerical computations are essentially reduced to membership tests to the polyhedron, while the other steps are cheap combinatorial tests. We implement the certification method and prove its correctness in the proof assistant Rocq. We experiment with it on a variety of polyhedra, including Birkhoff polytopes, cross-polytopes, cubes, permutahedra, hypersimplices, and high-dimensional polytopes involved in the disproof of the Hirsch conjecture. Our experiments show that certification with the Rocq-to-OCaml extracted checker is typically 1.5x to over 5x faster than vertex enumeration by the state-of-the-art informal C implementation lrslib of the reverse search method.

0.28

Tiling 3D by Translates of a Single Polycube is Undecidable

cs.CG math.COmath.MG ·2026-10-08 ·Erik D. Demaine, Stefan Langerman
theory similarity 0.53
Abstract · 7 pages, 1 figure, 1 table

We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations. We reduce from Wang tiling using the decorated two-prime Sudoku construction of Greenfeld and Tao and a cyclic encoding adapted from OpenAI's 3D aperiodic tile, and apply a reduction of Kim to make the prototile connected (via faces). Dimension three is optimal: translational monotiling is known to be decidable in $\mathbb{Z}^2$ and for a single (possibly disconnected) polyomino in $\mathbb{R}^2$.

0.43