Extensions of partial cyclic orders and consecutive coordinate polytopes. (Extensions d’ordres cycliques partiels et polytopes à coordonnées consécutives.) (English. French summary) Zbl 1443.05004
Summary: 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 R. P. Stanley [Enumerative combinatorics. Vol. 1. Cambridge: Cambridge University Press (1997; Zbl 0889.05001)]. We also provide a combinatorial interpretation of the Ehrhart \(h^\ast\)-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.
MSC:
| 05A05 | Permutations, words, matrices |
| 05A10 | Factorials, binomial coefficients, combinatorial functions |
| 06A75 | Generalizations of ordered sets |
| 52B11 | \(n\)-dimensional polytopes |
| 52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |
| 11B68 | Bernoulli and Euler numbers and polynomials |
Keywords:
partial cyclic orders; circular extensions; lattice polytopes; Ehrhart polynomials; Narayana numbers; Euler numbers; Eulerian numbersCitations:
Zbl 0889.05001Software:
OEISOnline Encyclopedia of Integer Sequences:
Triangle of Narayana numbers T(n,k) = C(n-1,k-1)*C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle.n! times the volume of the polytope x_i >= 0 for 1 <= i <= n and x_i + x_{i+1} + x_{i+2} <= 1 for 1 <= i <= n-2.
3-Springer numbers.
References:
| [1] | Batyrev, Victor; Nill, Benjamin, Integer points in polyhedra—geometry, number theory, representation theory, algebra, optimization, statistics, 452, Combinatorial aspects of mirror symmetry, 35-66 (2008), American Mathematical Society · Zbl 1161.14037 · doi:10.1090/conm/452/08770 |
| [2] | Beck, Matthias; Robins, Sinai, Computing the continuous discretely, xx+285 p. pp. (2015), Springer · Zbl 1339.52002 · doi:10.1007/978-1-4939-2969-6 |
| [3] | Corteel, Sylvie; Kim, Jang Soo; Mészáros, Karola, Flow polytopes with Catalan volumes, C. R. Math. Acad. Sci. Paris, 355, 3, 248-259 (2017) · Zbl 1358.05129 · doi:10.1016/j.crma.2017.01.007 |
| [4] | Chan, Clara S.; Robbins, David P.; Yuen, David S., On the volume of a certain polytope, Exp. Math., 9, 1, 91-99 (2000) · Zbl 0960.05004 · doi:10.1080/10586458.2000.10504639 |
| [5] | Diaconis, Persi; Wood, Philip Matchett, Random doubly stochastic tridiagonal matrices, Random Struct. Algorithms, 42, 4, 403-437 (2013) · Zbl 1278.15035 · doi:10.1002/rsa.20452 |
| [6] | Flajolet, Philippe; Sedgewick, Robert, Analytic combinatorics, xiv+810 p. pp. (2009), Cambridge University Press · Zbl 1165.05001 |
| [7] | Hibi, Takayuki, Dual polytopes of rational convex polytopes, Combinatorica, 12, 2, 237-240 (1992) · Zbl 0758.52009 · doi:10.1007/BF01204726 |
| [8] | Han, Guo-Niu; Josuat-Vergès, Matthieu, Flag statistics from the Ehrhart \(h^*\)-polynomial of multi-hypersimplices, Electron. J. Comb., 23, 1, 20 p. pp. (2016) · Zbl 1336.05151 · doi:10.37236/5538 |
| [9] | Inc., OEIS Foundation, The On-Line Encyclopedia of Integer Sequences (2020) |
| [10] | Megiddo, Nimrod, Partial and complete cyclic orders, Bull. Am. Math. Soc., 82, 2, 274-276 (1976) · Zbl 0361.06001 · doi:10.1090/S0002-9904-1976-14020-7 |
| [11] | Ramassamy, Sanjay, Extensions of partial cyclic orders, Euler numbers and multidimensional boustrophedons, Electron. J. Comb., 25, 1, 20 p. pp. (2018) · Zbl 1476.06004 · doi:10.37236/7145 |
| [12] | Schrijver, Alexander, Theory of linear and integer programming, xii+471 p. pp. (1986), John Wiley & Sons · Zbl 0665.90063 |
| [13] | Schumacher, Paul R. F., Parking functions and generalized Catalan numbers (2009) |
| [14] | Stanley, Richard P.; Macdonald, Ian. G.; Nelsen, Roger B., Problems and Solutions: Solutions of Elementary Problems: E2701, Am. Math. Mon., 86, 5, 396 p. pp. (1979) · doi:10.2307/2321106 |
| [15] | Stanley, Richard P.; Aigner, M., Higher Combinatorics. Proceedings of the NATO Advanced Study Institute held in Berlin (West Germany), September 1-10, 1976, Eulerian partitions of a unit hypercube, 49-49 (1977), Reidel, Dordrecht ; Springer · Zbl 0359.05001 |
| [16] | Stanley, Richard P.; Srivastava, J., 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), 6, Decompositions of rational convex polytopes, 333-342 (1980), North-Holland · Zbl 0812.52012 |
| [17] | Stanley, Richard P., Two poset polytopes, Discrete Comput. Geom., 1, 1, 9-23 (1986) · Zbl 0595.52008 · doi:10.1007/bf02187680 |
| [18] | Stanley, Richard P., Enumerative combinatorics. Vol. 2, 62, xii+581 p. pp. (1999), Cambridge University Press · Zbl 0928.05001 · doi:10.1017/CBO9780511609589 |
| [19] | Stanley, Richard P., Enumerative combinatorics. Volume 1, 49, xiv+626 p. pp. (2012), Cambridge University Press · Zbl 1247.05003 |
| [20] | Stanley, Richard P., A polynomial recurrence involving partial derivatives (2012) |
| [21] | Zeilberger, Doron, Proof of a conjecture of Chan, Robbins, and Yuen, Electron. Trans. Numer. Anal., 9, 147-148 (1999) · Zbl 0941.05006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
