×

Noncrossing partitions and the shard intersection order. (English) Zbl 1290.05163

Summary: We define a new lattice structure \((W,\preceq)\) on the elements of a finite Coxeter group \(W\). This lattice, called the shard intersection order, is weaker than the weak order and has the noncrossing partition lattice NC\((W)\) as a sublattice. The new construction of NC\((W)\) yields a new proof that NC\((W)\) is a lattice. The shard intersection order is graded and its rank generating function is the \(W\)-Eulerian polynomial. Many order-theoretic properties of \((W,\preceq)\), like Möbius number, number of maximal chains, etc., are exactly analogous to the corresponding properties of NC\((W)\). There is a natural dimension-preserving bijection between simplices in the order complex of \((W,\preceq)\) (i.e. chains in \((W,\preceq))\) and simplices in a certain pulling triangulation of the \(W\)-permutohedron. Restricting the bijection to the order complex of NC\((W)\) yields a bijection to simplices in a pulling triangulation of the \(W\)-associahedron.
The lattice \((W,\preceq)\) is defined indirectly via the polyhedral geometry of the reflecting hyperplanes of \(W\). Indeed, most of the results of the paper are proven in the more general setting of simplicial hyperplane arrangements.

MSC:

05E45 Combinatorial aspects of simplicial complexes
05A18 Partitions of sets
20F55 Reflection and Coxeter groups (group-theoretic aspects)

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aguiar, M., Sottile, F.: Structure of the Malvenuto-Reutenauer Hopf algebra of permutations. Adv. Math. 191(2), 225-275 (2005) · Zbl 1056.05139 · doi:10.1016/j.aim.2004.03.007
[2] Athanasiadis, C.A., Reiner, V.: Noncrossing partitions for the group Dn. SIAM J. Discrete Math. 18(2), 397-417 (2004) · Zbl 1085.06001 · doi:10.1137/S0895480103432192
[3] Athanasiadis, C.A., Brady, T., Watt, C.: Shellability of noncrossing partition lattices. Proc. Am. Math. Soc. 135(4), 939-949 (2007) · Zbl 1171.05053 · doi:10.1090/S0002-9939-06-08534-0
[4] Athanasiadis, C.A., Brady, T., McCammond, J., Watt, C.: h-vectors of generalized associahedra and non-crossing partitions. Int. Math. Res. Not., 69705 (2006) · Zbl 1112.20032
[5] Bessis, D.: The dual braid monoid. Ann. Sci. École Norm. Super. (4) 36(5), 647-683 (2003) · Zbl 1064.20039
[6] Biane, P.: Some properties of crossings and partitions. Discrete Math. 175(1-3), 41-53 (1997) · Zbl 0892.05006 · doi:10.1016/S0012-365X(96)00139-2
[7] Björner, A., Edelman, P., Ziegler, G.: Hyperplane arrangements with a lattice of regions. Discrete Comput. Geom. 5, 263-288 (1990) · Zbl 0698.51010 · doi:10.1007/BF02187790
[8] Brady, T., Watt, C.: A partial order on the orthogonal group. Commun. Algebra 30(8), 3749-3754 (2002) · Zbl 1018.20040 · doi:10.1081/AGB-120005817
[9] Brady, T., Watt, C.: From permutahedron to associahedron. Preprint (2008). arXiv:0804.2331 · Zbl 1187.05086
[10] Brady, T., Watt, C.: Non-crossing partition lattices in finite real reflection groups. Trans. Am. Math. Soc. 360, 1983-2005 (2008) · Zbl 1187.20051 · doi:10.1090/S0002-9947-07-04282-1
[11] Brady, T., Watt, C.: K(π,1)’s for Artin groups of finite type. In: Proceedings of the Conference on Geometric and Combinatorial Group Theory, Part I (Haifa, 2000). Geom. Dedicata, vol. 94, pp. 225-250 (2002) · Zbl 1053.20034
[12] Chajda, I., Snášel, V.: Congruences in ordered sets. Math. Bohem. 123(1), 95-100 (1998) · Zbl 0897.06004
[13] Chapoton, F.: Enumerative properties of generalized associahedra. Sémin. Lothar. Comb. 51, B51b (2004) · Zbl 1160.05342
[14] Chindris, C.: Cluster fans, stability conditions, and domains of semi-invariants. Trans. Am. Math. Soc. (2010, to appear) · Zbl 1272.16016
[15] Fomin, S., Reading, N.: Generalized cluster complexes and Coxeter combinatorics. Int. Math. Res. Not. 44, 2709-2757 (2005) · Zbl 1117.52017 · doi:10.1155/IMRN.2005.2709
[16] Fomin, S., Zelevinsky, A.: Y-systems and generalized associahedra. Ann. Math. (2) 158(3), 977-1018 (2003) · Zbl 1057.52003 · doi:10.4007/annals.2003.158.977
[17] Freese, R., Ježek, J., Nation, J.: Free Lattices. Mathematical Surveys and Monographs, vol. 42. Am. Math. Soc., Providence (1995) · Zbl 0839.06005
[18] Grätzer, G.: General Lattice Theory, 2nd edn. Birkhäuser, Basel (1998) · Zbl 0909.06002
[19] Hohlweg, C., Lange, C., Thomas, H.: Permutohedra and generalized associahedra. Preprint (2007). arXiv:0709.4241
[20] Igusa, K., Orr, K., Todorov, G., Weyman, J.: Cluster complexes via semi-invariants. Compos. Math. 145(4), 1001-1034 (2009) · Zbl 1180.14047 · doi:10.1112/S0010437X09004151
[21] Ingalls, C., Thomas, H.: Noncrossing partitions and representations of quivers. Compos. Math. 145(6), 1533-1562 (2009) · Zbl 1182.16012 · doi:10.1112/S0010437X09004023
[22] Jedlička, P.: A combinatorial construction of the weak order of a Coxeter group. Commun. Algebra 33, 1447-1460 (2005) · Zbl 1079.20058 · doi:10.1081/AGB-200060517
[23] Kreweras, G.: Sur les partitions non croisées d’un cycle. Discrete Math. 1(4), 333-350 (1972) · Zbl 0231.05014 · doi:10.1016/0012-365X(72)90041-6
[24] Lee, C. W., Subdivisions and triangulations of polytopes, 271-290 (1997), Boca Raton · Zbl 0917.52012
[25] Loday, J.-L., Parking functions and triangulation of the associahedron, No. 431, 327-340 (2007), Providence · Zbl 1130.52006
[26] Postnikov, A.: Permutohedra, associahedra and beyond. Int. Math. Res. Not. 6, 1026-1106 (2009) · Zbl 1162.52007
[27] Reading, N.: Lattice and order properties of the poset of regions in a hyperplane arrangement. Algebra Univers. 50, 179-205 (2003) · Zbl 1092.06006 · doi:10.1007/s00012-003-1834-0
[28] Reading, N.: The order dimension of the poset of regions in a hyperplane arrangement. J. Comb. Theory Ser. A 104(2), 265-285 (2003) · Zbl 1044.52010 · doi:10.1016/j.jcta.2003.08.002
[29] Reading, N.: The cd-index of Bruhat intervals. Electron. J. Comb. 11(1), 74 (2004) (electronic) · Zbl 1067.20050
[30] Reading, N.: Lattice congruences of the weak order. Order 21(4), 315-344 (2004) · Zbl 1097.20036 · doi:10.1007/s11083-005-4803-8
[31] Reading, N.: Lattice congruences, fans and Hopf algebras. J. Comb. Theory Ser. A 110(2), 237-273 (2005) · Zbl 1133.20027 · doi:10.1016/j.jcta.2004.11.001
[32] Reading, N.: Cambrian lattices. Adv. Math. 205(2), 313-353 (2006) · Zbl 1106.20033 · doi:10.1016/j.aim.2005.07.010
[33] Reading, N.: Clusters, Coxeter-sortable elements and noncrossing partitions. Trans. Am. Math. Soc. 359(12), 5931-5958 (2007) · Zbl 1189.05022 · doi:10.1090/S0002-9947-07-04319-X
[34] Reading, N.: Sortable elements and Cambrian lattices. Algebra Univers. 56(3-4), 411-437 (2007) · Zbl 1184.20038 · doi:10.1007/s00012-007-2009-1
[35] Reading, N.: Chains in the noncrossing partition lattice. SIAM J. Discrete Math. 22(3), 875-886 (2008) · Zbl 1168.05008 · doi:10.1137/07069777X
[36] Reading, N.: Noncrossing partitions and the shard intersection order (Extended abstract). In: FPSAC 2009, Hagenberg, Austria. DMTCS Proc., vol. AK, pp. 745-756 (2009) · Zbl 1391.05283
[37] Reading, N., Speyer, D.: Cambrian fans. J. Eur. Math. Soc. 11(2), 407-447 · Zbl 1213.20038
[38] Reading, N., Speyer, D.: Sortable elements in infinite Coxeter groups. Trans. Am. Math. Soc. (2010, to appear). arXiv:0803.2722 · Zbl 1231.20036
[39] Reiner, V.: The distribution of descents and length in a Coxeter group. Electron. J. Comb. 2, 25 (1995) (electronic) · Zbl 0849.20032
[40] Reiner, V.: Non-crossing partitions for classical reflection groups. Discrete Math. 177(1-3), 195-222 (1997) · Zbl 0892.06001 · doi:10.1016/S0012-365X(96)00365-2
[41] Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. Published electronically at www.research.att.com/ njas/sequences · Zbl 1044.11108
[42] Ziegler, G.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995) · 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. 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.