Extensions of partial cyclic orders and consecutive coordinate polytopes
Annales Henri Lebesgue, Volume 3 (2020) , pp. 275-297.

Metadata

KeywordsPartial cyclic orders, circular extensions, lattice polytopes, Ehrhart polynomials, Narayana numbers, Euler numbers, Eulerian numbers

Abstract

We introduce several classes of polytopes contained in [0,1] n 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 h * –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.


References

[BN08] Batyrev, Victor; Nill, Benjamin 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 | Article | MR 2405763 | Zbl 1161.14037

[BR15] Beck, Matthias; Robins, Sinai Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, 2015, xx+285 pages | Article | MR 3410115 | Zbl 1339.52002

[CKM17] Corteel, Sylvie; Kim, Jang Soo; Mészáros, Karola Flow polytopes with Catalan volumes, C. R. Math. Acad. Sci. Paris, Volume 355 (2017) no. 3, pp. 248-259 | Article | MR 3621250 | Zbl 1358.05129

[CRY00] Chan, Clara S.; Robbins, David P.; Yuen, David S. On the volume of a certain polytope, Exp. Math., Volume 9 (2000) no. 1, pp. 91-99 | Article | MR 1758803 | Zbl 0960.05004

[DW13] Diaconis, Persi; Wood, Philip Matchett Random doubly stochastic tridiagonal matrices, Random Struct. Algorithms, Volume 42 (2013) no. 4, pp. 403-437 | Article | MR 3068032 | Zbl 1278.15035

[FS09] Flajolet, Philippe; Sedgewick, Robert Analytic combinatorics, Cambridge University Press, 2009, xiv+810 pages | Zbl 1165.05001

[Hib92] Hibi, Takayuki Dual polytopes of rational convex polytopes, Combinatorica, Volume 12 (1992) no. 2, pp. 237-240 | Article | MR 1179260 | Zbl 0758.52009

[HJV16] Han, Guo-Niu; Josuat-Vergès, Matthieu Flag statistics from the Ehrhart h * -polynomial of multi-hypersimplices, Electron. J. Comb., Volume 23 (2016) no. 1, P1.55, 20 pages | Article | MR 3484760 | Zbl 1336.05151

[Inc20] Inc., OEIS Foundation The On-Line Encyclopedia of Integer Sequences, 2020 (Published electronically at http://oeis.org)

[Meg76] Megiddo, Nimrod Partial and complete cyclic orders, Bull. Am. Math. Soc., Volume 82 (1976) no. 2, pp. 274-276 | Article | MR 0404065 | Zbl 0361.06001

[Ram18] Ramassamy, Sanjay Extensions of partial cyclic orders, Euler numbers and multidimensional boustrophedons, Electron. J. Comb., Volume 25 (2018) no. 1, P1.66, 20 pages | Article | MR 3785045 | Zbl 06873110

[Sch86] Schrijver, Alexander Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, 1986, xii+471 pages | MR 874114 | Zbl 0665.90063

[Sch09] Schumacher, Paul R. F. Parking functions and generalized Catalan numbers (2009) (Ph. D. Thesis)

[SMN79] Stanley, Richard P.; Macdonald, Ian. G.; Nelsen, Roger B. Problems and Solutions: Solutions of Elementary Problems: E2701, Am. Math. Mon., Volume 86 (1979) no. 5, 396 pages | Article | MR 1539043

[Sta77] Stanley, Richard P. 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 0359.05001

[Sta80] Stanley, Richard P. 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 593545 | Zbl 0812.52012

[Sta86] Stanley, Richard P. Two poset polytopes, Discrete Comput. Geom., Volume 1 (1986) no. 1, pp. 9-23 | Article | MR 824105 | Zbl 0595.52008

[Sta99] Stanley, Richard P. Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, Volume 62, Cambridge University Press, 1999, xii+581 pages | Article | MR 1676282 | Zbl 0928.05001

[Sta12a] Stanley, Richard P. Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, Volume 49, Cambridge University Press, 2012, xiv+626 pages | MR 2868112 | Zbl 1247.05003

[Sta12b] Stanley, Richard P. A polynomial recurrence involving partial derivatives, 2012 (https://mathoverflow.net/q/87801, accessed June 20 2018)

[Zei99] Zeilberger, Doron Proof of a conjecture of Chan, Robbins, and Yuen, Electron. Trans. Numer. Anal., Volume 9 (1999), p. 147-148 | MR 1749805 | Zbl 0941.05006