zbMATH — the first resource for mathematics

Pattern-avoiding polytopes. (English) Zbl 1398.52014
Summary: Two well-known polytopes whose vertices are indexed by permutations in the symmetric group \(\mathfrak{S}_n\) are the permutohedron \(P_n\) and the Birkhoff polytope \(B_n\). We consider polytopes \(P_n(\varPi)\) and \(B_n(\varPi)\), whose vertices correspond to the permutations in \(\mathfrak{S}_n\) avoiding a set of patterns \(\varPi\). For various choices of \(\varPi\), we explore the Ehrhart polynomials and \(h^\ast\)-vectors of these polytopes as well as other aspects of their combinatorial structure.
For \(P_n(\varPi)\), we consider all subsets \(\varPi \subseteq \mathfrak{S}_3\) and are able to provide results in most cases. To illustrate, \(P_n(123, 132)\) is a Pitman-Stanley polytope, the number of interior lattice points in \(P_n(132, 312)\) is a derangement number, and the normalized volume of \(P_n(123, 231, 312)\) is the number of trees on \(n\) vertices.
The polytopes \(B_n(\varPi)\) seem much more difficult to analyze, so we focus on four particular choices of \(\varPi\). First we show that the \(B_n(231, 321)\) is exactly the Chan-Robbins-Yuen polytope. Next, we prove that for any \(\varPi\) containing \(\{123, 312 \}\) we have \(h^\ast(B_n(\varPi)) = 1\). Finally, we study \(B_n(132, 312)\) and \(\widetilde{B}_n(123)\), where the tilde indicates that we choose vertices corresponding to alternating permutations avoiding the pattern 123. In both cases we use order complexes of posets and techniques from toric algebra to construct regular, unimodular triangulations of the polytopes. The posets involved turn out to be isomorphic to the lattices of Young diagrams contained in a certain shape, and this permits us to give an exact expression for the normalized volumes of the corresponding polytopes via the hook formula. Finally, Stanley’s theory of \((P, \omega)\)-partitions allows us to show that their \(h^\ast\)-vectors are symmetric and unimodal. Various questions and conjectures are presented throughout.

52B11 \(n\)-dimensional polytopes
Full Text: DOI arXiv
[1] Athanasiadis, Christos A., Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley, J. Reine Angew. Math., 583, 163-174, (2005) · Zbl 1077.52011
[2] Babson, Eric; Steingrímsson, Einar, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin., 44, B44b, (2000), 18 pp. (electronic) · Zbl 0957.05010
[3] Velleda Baldoni, Nicole Berline, Jesús A. De Loera, Brandon E. Dutra, Matthias Köppe, Stanislav Moreinis, Gregory Pinto, Michele Vergne, Jianqiu Wu, A users guide for latte integrale v1.7.2, 2013. Software package. LattE is available at http://www.math.ucdavis.edu/latte/.
[4] Beck, Matthias; Jochemko, Katharina; McCullough, Emily, \(h^\ast\)-polynomials of zonotopes, Trans. Amer. Math. Soc., (2018), (in press) · Zbl 1402.05100
[5] Beck, Matthias; Pixton, Dennis, The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom., 30, 4, 623-637, (2003) · Zbl 1065.52007
[6] Beck, Matthias; Robins, Sinai, (Computing the Continuous Discretely, Undergraduate Texts in Mathematics, (2015), Springer New York), xx+285, Integer-point enumeration in polyhedra, With illustrations by David Austin · Zbl 1339.52002
[7] Björner, Anders, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc., 260, 1, 159-183, (1980) · Zbl 0441.06002
[8] Björner, Anders; Brenti, Francesco, (Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, vol. 231, (2005), Springer New York), xiv+363 · Zbl 1110.05001
[9] Braun, Benjamin, (Beveridge, Andrew; Griggs, R. Jerrold; Hogben, Leslie; Musiker, Gregg; Tetali, Prasad, Unimodality Problems in Ehrhart Theory, (2016), Springer International Publishing Cham), 687-711
[10] Bruns, Winfried; Römer, Tim, \(h\)-vectors of Gorenstein polytopes, J. Combin. Theory Ser. A, 114, 1, 65-76, (2007) · Zbl 1108.52013
[11] Burggraf, Katherine; De Loera, Jesús; Omar, Mohamed, On volumes of permutation polytopes, (Discrete Geometry and Optimization, Fields Inst. Commun., vol. 69, (2013), Springer New York), 55-77 · Zbl 1281.52010
[12] Chan, Clara S.; Robbins, David P.; Yuen, David S., On the volume of a certain polytope, Experiment. Math., 9, 1, 91-99, (2000) · Zbl 0960.05004
[13] Corteel, Sylvie; Lee, Sunyoung; Savage, Carla D., Enumeration of sequences constrained by the ratio of consecutive parts, Sém. Lothar. Combin., 54A, B54Aa, (2005/07), 12 · Zbl 1086.05010
[14] De Loera, Jesús A.; Kim, Edward D., Combinatorics and geometry of transportation polytopes: an update, (Discrete Geometry and Algebraic Combinatorics, Contemp. Math., vol. 625, (2014), Amer. Math. Soc. Providence, RI), 37-76 · Zbl 1360.90169
[15] Dokos, Theodore; Dwyer, Tim; Johnson, Bryan P.; Sagan, Bruce E.; Selsor, Kimberly, Permutation patterns and statistics, Discrete Math., 312, 18, 2760-2775, (2012) · Zbl 1248.05004
[16] Ehrhart, Eugène, Sur LES polyèdres rationnels homothétiques à \(n\) dimensions, C. R. Acad. Sci. Paris, 254, 616-618, (1962) · Zbl 0100.27601
[17] Ferrari, Luca; Pinzani, Renzo, Lattices of lattice paths, J. Statist. Plann. Inference, 135, 1, 77-92, (2005) · Zbl 1082.06006
[18] Frame, J. S.; Robinson, G. de B.; Thrall, R. M., The hook graphs of the symmetric groups, Canad. J. Math., 6, 316-324, (1954) · Zbl 0055.25404
[19] Grünbaum, Branko, (Convex Polytopes, Graduate Texts in Mathematics, vol. 221, (2003), Springer-Verlag New York), xvi+468, Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler · Zbl 1024.52001
[20] Hohlweg, Christophe; Lange, Carsten E. M. C.; Thomas, Hugh, Permutahedra and generalized associahedra, Adv. Math., 226, 1, 608-640, (2011) · Zbl 1233.20035
[21] Kapranov, Mikhail M., The permutoassociahedron, mac lane’s coherence theorem and asymptotic zones for the KZ equation, J. Pure Appl. Algebra, 85, 2, 119-142, (1993) · Zbl 0812.18003
[22] Lee, Carl W., Regular triangulations of convex polytopes, (Applied Geometry and Discrete Mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, (1991), Amer. Math. Soc. Providence, RI), 443-456 · Zbl 0746.52015
[23] Loday, Jean-Louis, Realization of the stasheff polytope, Arch. Math. (Basel), 83, 3, 267-278, (2004) · Zbl 1059.52017
[24] Onn, Shmuel, Geometry, complexity, and combinatorics of permutation polytopes, J. Combin. Theory Ser. A, 64, 1, 31-49, (1993) · Zbl 0789.05095
[25] Pitman, Jim; Stanley, Richard P., A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom., 27, 4, 603-634, (2002) · Zbl 1012.52019
[26] Postnikov, Alexander, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN, 6, 1026-1106, (2009) · Zbl 1162.52007
[27] Postnikov, Alex; Reiner, Victor; Williams, Lauren, Faces of generalized permutohedra, Doc. Math., 13, 207-273, (2008) · Zbl 1167.05005
[28] Proctor, Robert A., Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly, 89, 10, 721-734, (1982) · Zbl 0509.05007
[29] Reiner, Victor; Ziegler, Günter M., Coxeter-associahedra, Mathematika, 41, 2, 364-393, (1994) · Zbl 0822.52007
[30] Schoute, Pieter Hendrick, Analytic treatment of the polytopes regularly derived from the regular polytopes, Verh. K. Acad. Wet. Amst., 11, 3, (1911)
[31] Simion, Rodica; Schmidt, Frank W., Restricted permutations, European J. Combin., 6, 4, 383-406, (1985) · Zbl 0615.05002
[32] Stanley, Richard P., Supersolvable lattices, Algebra Universalis, 2, 197-217, (1972) · Zbl 0256.06002
[33] Stanley, Richard P., Hilbert functions of graded algebras, Adv. Math., 28, 1, 57-83, (1978) · Zbl 0384.13012
[34] Stanley, Richard P., Decompositions of rational convex polytopes, Ann. Discrete Math., 6, 333-342, (1980), Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978) · Zbl 0812.52012
[35] Stanley, Richard P., Two poset polytopes, Discrete Comput. Geom., 1, 1, 9-23, (1986) · Zbl 0595.52008
[36] Stanley, Richard P., A zonotope associated with graphical degree sequences, (Applied Geometry and Discrete Mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, (1991), Amer. Math. Soc. Providence, RI), 555-570 · Zbl 0737.05057
[37] Stanley, Richard P., (Enumerative Combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, vol. 49, (2012), Cambridge University Press Cambridge), xiv+626 · Zbl 1247.05003
[38] Steingrímsson, Einar, Some open problems on permutation patterns, (Surveys in Combinatorics 2013, London Math. Soc. Lecture Note Ser., vol. 409, (2013), Cambridge Univ. Press Cambridge), 239-263 · Zbl 1300.05020
[39] Sturmfels, Bernd, (Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8, (1996), American Mathematical Society Providence, RI), xii+162 · Zbl 0856.13020
[40] Thrall, R. M., A combinatorial problem, Michigan Math. J., 1, 81-88, (1952) · Zbl 0049.01001
[41] Zeilberger, Doron, Proof of a conjecture of chan, robbins, and yuen, Electron. Trans. Numer. Anal., 9, 147-148, (1999), (electronic) Orthogonal polynomials: numerical and symbolic algorithms (Leganés, 1998) · Zbl 0941.05006
[42] Ziegler, Günter M., (Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, (1995), Springer-Verlag New York), x+370 · Zbl 0823.52002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.