Metraipolis › archive › dc_229a577f0785

Log-concavity and Approximate Counting for Totally Unimodular Polytopes — arXiv:2609.39917

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.39917
License (as archived)
CC0-1.0
Archived
2026-10-07T14:19:10.020Z
SHA-256 of the archived text
d0185e85fa90f342f82d6c4f3a51009416ddc5d41ddcc1c281307b449e94039b
Stable URL of this page
https://metraipolis.com/documento/dc_229a577f0785

How to cite

Log-concavity and Approximate Counting for Totally Unimodular Polytopes — arXiv:2609.39917 — arXiv (en), https://arxiv.org/abs/2609.39917 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_229a577f0785 (Metraipolis archive dc_229a577f0785, sha256 d0185e85fa90f342f82d6c4f3a51009416ddc5d41ddcc1c281307b449e94039b)
BibTeX
@misc{dc229a577f0785,
  title = {Log-concavity and Approximate Counting for Totally Unimodular Polytopes — arXiv:2609.39917},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.39917},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_229a577f0785; sha256 d0185e85fa90f342f82d6c4f3a51009416ddc5d41ddcc1c281307b449e94039b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39917. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We present a new lower bound on the number of lattice points of all totally unimodular polytopes, generalizing previous lower bounds on contingency tables, integer flows, and beyond. Our bound is based on the Gurvits capacity convex optimization problem, and thus our result implies an efficient deterministic algorithm for approximate counting of the lattice points up to an explicit exponential factor. We achieve our bounds by showing that the associated generating polynomials fit into a new general class of log-concave polynomials called VLC ("variable-wise log-concavity''). This also implies a conjecture of Ferroni and Higashitani on the evaluations of the Ehrhart polynomials of unimodular polytopes. The essential ingredient for these results is the resolution of Barvinok's log-concavity conjecture for contingency tables on lines, which was proven using ChatGPT 6 Astra. We conjecture a generalization of Barvinok's conjecture, which we believe will lead to stronger and more general bounds.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.39917 — 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-07T14:05:16.440Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).