Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 59 min ago
PreprintCC BY 4.0arXiv

A lattice path model for the volume of the Monge polytope

  • William Q. Erickson
  • Nicholas B. Jones
Open at sourcePDFDOICite

Abstract

Monge matrices arise throughout combinatorial optimization and algorithm design; the Monge polytope ℳpq is the set of p × 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 ℳpq expressed as a sum over "Z-avoiding" Delannoy paths in a p × 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 ℳ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 ℳpq.

Related

  1. The face lattice of any simplicial polytope is Hamiltonian
    Robert Lauff
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Ehrhart positivity for lattice path matroids
    Luis Ferroni, Alejandro H. Morales, Greta Panova
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Certain Standard Young Tableaux of Non-Classical Shapes and Lattice Path Enumeration
    Ping Sun, Chen Xu
    MathematicsPeer-reviewedCC BY 4.0Combinatorics & discrete mathematicsCrossref
  4. A note on the ideal lattice of a weighted Leavitt path algebra
    Raimund Preusser
    arXivPreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv
  5. A lattice path model for Schubert and forest polynomials: positivity and combinatorial interpretations
    Hojoon Lee
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{erickson2026lattice,
  title = {{A lattice path model for the volume of the Monge polytope}},
  author = {William Q. Erickson and Nicholas B. Jones},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.09508},
  eprint = {2609.09508},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.09508},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A lattice path model for the volume of the Monge polytope
AU  - William Q. Erickson
AU  - Nicholas B. Jones
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.09508
UR  - https://arxiv.org/abs/2609.09508
AB  - Monge matrices arise throughout combinatorial optimization and algorithm design; the Monge polytope ℳ_pq is the set of p × 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 ℳ_pq expressed as a sum over "Z-avoiding" Delannoy paths in a p × 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 ℳ_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 ℳ_pq.
ER  -