×

Rational associahedra and noncrossing partitions. (English) Zbl 1295.05051

Summary: Each positive rational number \(x>0\) can be written uniquely as \(x=a/(b-a)\) for coprime positive integers \(0<a<b\). We will identify \(x\) with the pair \((a,b)\). In this paper we define for each positive rational \(x>0\) a simplicial complex \(\mathsf{Ass}(x)=\mathsf{Ass}(a,b)\) called the rational associahedron. It is a pure simplicial complex of dimension \(a-2\), and its maximal faces are counted by the rational Catalan number \[ \mathsf{Cat}(x)=\mathsf{Cat}(a,b):=\frac{(a+b-1)!}{a!\,b!}. \] The cases \((a,b)=(n,n+1)\) and \((a,b)=(n,kn+1)\) recover the classical associahedron and its “Fuss-Catalan” generalization studied by C. A. Athanasiadis and E. Tzanaki [Isr. J. Math. 167, 177–191 (2008; Zbl 1200.05252)] and S. Fomin and N. Reading [Int. Math. Res. Not. 2005, No. 44, 2709–2757 (2005; Zbl 1117.52017)]. We prove that \(\mathsf{Ass}(a,b)\) is shellable and give nice product formulas for its \(h\)-vector (the rational Narayana numbers) and \(f\)-vector (the rational Kirkman numbers). We define \(\mathsf{Ass}(a,b)\) via rational Dyck paths: lattice paths from \((0,0)\) to \((b,a)\) staying above the line \(y = \frac{a}{b}x\). We also use rational Dyck paths to define a rational generalization of noncrossing perfect matchings of \([2n]\). In the case \((a,b) = (n, mn+1)\), our construction produces the noncrossing partitions of \([(m+1)n]\) in which each block has size \(m+1\).

MSC:

05A19 Combinatorial identities, bijective combinatorics
05E45 Combinatorial aspects of simplicial complexes
52B55 Computational aspects related to convexity

References:

[1] J. Anderson, Partitions which are simultaneously t1- and t2-core. Discrete Math. 248 (2002), no. 1-3, 237-243. · Zbl 1001.05015
[2] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc., 202 (949). · Zbl 1191.05095
[3] D. Armstrong, N. Loehr, and G. Warrington, Rational Parking Functions and the Zeta Map. In preparation, 2012.
[4] C. A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Adv. Math., 122 (1996), 193-233. · Zbl 0872.52006
[5] C. A. Athanasiadis, On a refinement of the generalized Catalan numbers for Weyl groups, Trans. Amer. Math. Soc., 357 (1) (2004), 179-196. · Zbl 1079.20057
[6] M.T.L. Bizley, Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman’s formula for the number of paths which may touch but do not rise above this line, J. Inst. Actuar. 80 (1954), 55-62. · Zbl 0055.00702
[7] A. Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376-378. · JFM 21.0687.01
[8] P. Cellini and P. Papi, Ad-nilpotent ideals of a Borel subalgebra II, J. Algebra 258 (1) (2002), 112-121. · Zbl 1033.17008
[9] A. Dvoretsky and T.H. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305-313. · Zbl 0030.16701
[10] P. Edelman, Chain enumeration and noncrossing partitions, Discrete Math. 31 (2) (1980), 171-180. · Zbl 0443.05011
[11] S. Fishel and M. Vazirani, A bijection between (bounded) dominant Shi regions and core partitions, DMTCS Proceedings, 22nd International Conference on Formal Power Series and Algebraic Combinatorics, (FPSAC 2010). · Zbl 1374.05035
[12] S. Fomin and N. Reading, Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Notices, 44 (2005), 2709-2757. · Zbl 1117.52017
[13] S. Fomin and A. Zelevinsky, Cluster algebras II: Finite type classification, Inventiones Math., 154 (2003), 63-121. · Zbl 1054.17024
[14] A.M. Garsia and M. Haiman, A remarkable q, t-Catalan sequence and q-Lagrange inversion, J. Algebraic Combin. 5 (1996), no. 3, 191-244. · Zbl 0853.05008
[15] I. Gordon, On the quotient ring by diagonal invariants, Invent. Math. 153 (2003), 503-518. · Zbl 1039.20019
[16] M. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994) 17-76. · Zbl 0803.13010
[17] M. Haiman, Hilbert schemes, polygraphs and the Macdonald positivity conjecture. J. Amer. Math. Soc. 14 (4) (2001), 941-1006. the electronic journal of combinatorics 20(3) (2013), #P5426 · Zbl 1009.14001
[18] T.P. Kirkman, On the k-partitions of the r-gon and r-ace, Phil. Trans. Royal Soc. London, 147 (1857), 217-272.
[19] C. Krattenthaler, Non-crossing partitions on an annulus, in preparation.
[20] G. Kreweras, Sur les partitions non crois´ees d’un cycle, Discrete Math. 1 (1972), 333-350. · Zbl 0231.05014
[21] P. McMullen, The maximum numbers of faces of a complex polytope, Mathematika 17 (1970), 179-184. · Zbl 0217.46703
[22] S.G. Mohanty, Lattice path counting and applications, Academic Press, New York (1979). · Zbl 0455.60013
[23] T.V. Narayana, Sur les trellis form´es par les partitions d’un entier et leurs applications ‘a la th´eories des probabilit´es, C. R. Acad. Sci. Paris, 240 (1955), 1188-1189. · Zbl 0064.12705
[24] V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1-3) (1997), 195-222. · Zbl 0892.06001
[25] J.-Y. Shi, Sign types corresponding to an affine Weyl group, J. London Math. Soc., 35 (1987), 56-74. · Zbl 0681.20033
[26] E. Sommers, B-stable ideals in the nilradical of a Borel subalgebra, Canad. Math. Bull. 48 (2005), 460-472. · Zbl 1139.17303
[27] R. Stanley, Catalan addendum.http://www-math.mit.edu/ rstan/ec/catadd. pdf
[28] J. D. Stasheff, Homotopy associativity of H-spaces. I, II. Trans. Amer. Math. Soc. 108 (1963), 275-292; ibid. 293-312. · Zbl 0114.39402
[29] E. Tzanaki, Polygon dissections and some generalizeations of cluster complexes, J. Combin. Theory Ser. A, 113 (6) (2006), 1189-1198. · Zbl 1105.52009
[30] H. Weyl, The classical groups, Princeton University Press, (1939). · JFM 65.0058.02
[31] D. White. Personal communication, 2007.
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.