Nous introduisons plusieurs classes de polytopes contenus dans et définis par des inégalités impliquant des sommes de coordonnées consécutives. Nous montrons que le volume normalisé de ces polytopes énumère les extensions circulaires de certains ordres cycliques partiels. Cela apporte entre autres un éclairage nouveau sur une question popularisée par Stanley. Nous fournissons aussi une interprétation combinatoire des –polynômes d’Ehrhart de certains de ces polytopes en termes de descentes dans les ordres cycliques totaux. Les nombres d’Euler, les nombres Eulériens et les nombres de Narayana apparaissent comme des cas particuliers.
We introduce several classes of polytopes contained in and cut out by inequalities involving sums of consecutive coordinates. We show that the normalized volumes of these polytopes enumerate circular extensions of certain partial cyclic orders. Among other things this gives a new point of view on a question popularized by Stanley. We also provide a combinatorial interpretation of the Ehrhart –polynomials of some of these polytopes in terms of descents of total cyclic orders. The Euler numbers, the Eulerian numbers and the Narayana numbers appear as special cases.
Révisé le :
Accepté le :
Publié le :
Mots clés : Partial cyclic orders, circular extensions, lattice polytopes, Ehrhart polynomials, Narayana numbers, Euler numbers, Eulerian numbers
@article{AHL_2020__3__275_0, author = {Ayyer, Arvind and Josuat-Verg\`es, Matthieu and Ramassamy, Sanjay}, title = {Extensions of partial cyclic orders and consecutive coordinate polytopes}, journal = {Annales Henri Lebesgue}, pages = {275--297}, publisher = {\'ENS Rennes}, volume = {3}, year = {2020}, doi = {10.5802/ahl.33}, language = {en}, url = {http://archive.numdam.org/articles/10.5802/ahl.33/} }
TY - JOUR AU - Ayyer, Arvind AU - Josuat-Vergès, Matthieu AU - Ramassamy, Sanjay TI - Extensions of partial cyclic orders and consecutive coordinate polytopes JO - Annales Henri Lebesgue PY - 2020 SP - 275 EP - 297 VL - 3 PB - ÉNS Rennes UR - http://archive.numdam.org/articles/10.5802/ahl.33/ DO - 10.5802/ahl.33 LA - en ID - AHL_2020__3__275_0 ER -
%0 Journal Article %A Ayyer, Arvind %A Josuat-Vergès, Matthieu %A Ramassamy, Sanjay %T Extensions of partial cyclic orders and consecutive coordinate polytopes %J Annales Henri Lebesgue %D 2020 %P 275-297 %V 3 %I ÉNS Rennes %U http://archive.numdam.org/articles/10.5802/ahl.33/ %R 10.5802/ahl.33 %G en %F AHL_2020__3__275_0
Ayyer, Arvind; Josuat-Vergès, Matthieu; Ramassamy, Sanjay. Extensions of partial cyclic orders and consecutive coordinate polytopes. Annales Henri Lebesgue, Tome 3 (2020), pp. 275-297. doi : 10.5802/ahl.33. http://archive.numdam.org/articles/10.5802/ahl.33/
[BN08] Combinatorial aspects of mirror symmetry, Integer points in polyhedra—geometry, number theory, representation theory, algebra, optimization, statistics (Contemporary Mathematics), Volume 452, American Mathematical Society, 2008, pp. 35-66 | DOI | MR | Zbl
[BR15] Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, 2015, xx+285 pages | DOI | MR | Zbl
[CKM17] Flow polytopes with Catalan volumes, C. R. Math. Acad. Sci. Paris, Volume 355 (2017) no. 3, pp. 248-259 | DOI | MR | Zbl
[CRY00] On the volume of a certain polytope, Exp. Math., Volume 9 (2000) no. 1, pp. 91-99 | DOI | MR | Zbl
[DW13] Random doubly stochastic tridiagonal matrices, Random Struct. Algorithms, Volume 42 (2013) no. 4, pp. 403-437 | DOI | MR | Zbl
[FS09] Analytic combinatorics, Cambridge University Press, 2009, xiv+810 pages | Zbl
[Hib92] Dual polytopes of rational convex polytopes, Combinatorica, Volume 12 (1992) no. 2, pp. 237-240 | DOI | MR | Zbl
[HJV16] Flag statistics from the Ehrhart -polynomial of multi-hypersimplices, Electron. J. Comb., Volume 23 (2016) no. 1, P1.55, 20 pages | DOI | MR | Zbl
[Inc20] The On-Line Encyclopedia of Integer Sequences, 2020 (Published electronically at http://oeis.org)
[Meg76] Partial and complete cyclic orders, Bull. Am. Math. Soc., Volume 82 (1976) no. 2, pp. 274-276 | DOI | MR | Zbl
[Ram18] Extensions of partial cyclic orders, Euler numbers and multidimensional boustrophedons, Electron. J. Comb., Volume 25 (2018) no. 1, P1.66, 20 pages | DOI | MR | Zbl
[Sch86] Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, 1986, xii+471 pages | MR | Zbl
[Sch09] Parking functions and generalized Catalan numbers, Ph. D. Thesis, Texas A & M University (USA) (2009)
[SMN79] Problems and Solutions: Solutions of Elementary Problems: E2701, Am. Math. Mon., Volume 86 (1979) no. 5, p. 396 | DOI | MR
[Sta77] Eulerian partitions of a unit hypercube, Higher Combinatorics. Proceedings of the NATO Advanced Study Institute held in Berlin (West Germany), September 1–10, 1976 (Aigner, M., ed.) (Nato Science Series C), Reidel, Dordrecht ; Springer, 1977, p. 49-49 | Zbl
[Sta80] Decompositions of rational convex polytopes, Combinatorial mathematics, optimal designs and their applications (Papers presented at the International Symposium held at Colorado State University, Fort Collins, Colorado, June 5-9, 1978) (Srivastava, J., ed.) (Annals of Discrete Mathematics), Volume 6, North-Holland, 1980, pp. 333-342 | MR | Zbl
[Sta86] Two poset polytopes, Discrete Comput. Geom., Volume 1 (1986) no. 1, pp. 9-23 | DOI | MR | Zbl
[Sta99] Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, 1999, xii+581 pages | DOI | MR | Zbl
[Sta12a] Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, 2012, xiv+626 pages | MR | Zbl
[Sta12b] A polynomial recurrence involving partial derivatives, 2012 (https://mathoverflow.net/q/87801, accessed June 20 2018)
[Zei99] Proof of a conjecture of Chan, Robbins, and Yuen, Electron. Trans. Numer. Anal., Volume 9 (1999), pp. 147-148 | MR | Zbl
Cité par Sources :