Metraipolis › archive › dc_8da623d8fabb
A lattice path model for the volume of the Monge polytope — arXiv:2609.09508
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.09508
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:16:48.659Z
- SHA-256 of the archived text
880e893818828821a29b8337a9617ecf254e99a56fd56bd7a93dab5e05c8d269- Stable URL of this page
https://metraipolis.com/documento/dc_8da623d8fabb
How to cite
A lattice path model for the volume of the Monge polytope — arXiv:2609.09508 — arXiv (en), https://arxiv.org/abs/2609.09508 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8da623d8fabb (Metraipolis archive dc_8da623d8fabb, sha256 880e893818828821a29b8337a9617ecf254e99a56fd56bd7a93dab5e05c8d269)
BibTeX
@misc{dc8da623d8fabb,
title = {A lattice path model for the volume of the Monge polytope — arXiv:2609.09508},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.09508},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8da623d8fabb; sha256 880e893818828821a29b8337a9617ecf254e99a56fd56bd7a93dab5e05c8d269},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.09508. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Monge matrices arise throughout combinatorial optimization and algorithm design; the Monge polytope $\mathcal{M}_{pq}$ is the set of $p \times q$ Monge matrices lying inside the standard simplex on the set of matrix coordinates. We find a Stanley decomposition of the associated affine semigroup, and use it to obtain a volume formula for $\mathcal{M}_{pq}$ expressed as a sum over "Z-avoiding" Delannoy paths in a $p \times q$ grid. An efficient dynamic-programming implementation of this formula computes the volume in dimensions far beyond the reach of general-purpose exact-volume algorithms (e.g., the volume of $\mathcal{M}_{20,20}$, which has dimension 399, is computed in a fraction of a second). As a corollary of our Stanley decomposition, we also obtain a combinatorial closed form for the Ehrhart series of $\mathcal{M}_{pq}$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Commutative Algebra (math.AC).
Pagina del lavoro: https://arxiv.org/abs/2609.09508 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:47:06.297Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).