Noncrossing partitions and the shard intersection order
Nathan Reading
DOI: 10.1007/s10801-010-0255-3
Abstract
We define a new lattice structure ( W,\preceq) (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\thinspace ( W) as a sublattice. The new construction of NC\thinspace ( W) yields a new proof that NC\thinspace ( 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) (W,\preceq), like Möbius number, number of maximal chains, etc., are exactly analogous to the corresponding properties of NC\thinspace ( W). There is a natural dimension-preserving bijection between simplices in the order complex of ( W,\preceq) (W,\preceq) (i.e. chains in ( W,\preceq) (W,\preceq)) and simplices in a certain pulling triangulation of the W-permutohedron. Restricting the bijection to the order complex of NC\thinspace ( W) yields a bijection to simplices in a pulling triangulation of the W-associahedron.
Pages: 483–530
Keywords: keywords noncrossing partition; shard; Coxeter group; weak order
Full Text: PDF
References
1. Aguiar, M., Sottile, F.: Structure of the Malvenuto-Reutenauer Hopf algebra of permutations. Adv. Math. 191(2), 225-275 (2005)
2. Athanasiadis, C.A., Reiner, V.: Noncrossing partitions for the group Dn. SIAM J. Discrete Math. 18(2), 397-417 (2004)
3. Athanasiadis, C.A., Brady, T., Watt, C.: Shellability of noncrossing partition lattices. Proc. Am. Math. Soc. 135(4), 939-949 (2007)
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)
5. Bessis, D.: The dual braid monoid. Ann. Sci. École Norm. Super. (4) 36(5), 647-683 (2003)
6. Biane, P.: Some properties of crossings and partitions. Discrete Math. 175(1-3), 41-53 (1997)
7. Björner, A., Edelman, P., Ziegler, G.: Hyperplane arrangements with a lattice of regions. Discrete Comput. Geom. 5, 263-288 (1990)
8. Brady, T., Watt, C.: A partial order on the orthogonal group. Commun. Algebra 30(8), 3749-3754 (2002)
9. Brady, T., Watt, C.: From permutahedron to associahedron. Preprint (2008).
10. Brady, T., Watt, C.: Non-crossing partition lattices in finite real reflection groups. Trans. Am. Math. Soc. 360, 1983-2005 (2008)
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)
12. Chajda, I., Snášel, V.: Congruences in ordered sets. Math. Bohem. 123(1), 95-100 (1998)
13. Chapoton, F.: Enumerative properties of generalized associahedra. Sémin. Lothar. Comb. 51, B51b (2004)
14. Chindris, C.: Cluster fans, stability conditions, and domains of semi-invariants. Trans. Am. Math. Soc. (2010, to appear)
15. Fomin, S., Reading, N.: Generalized cluster complexes and Coxeter combinatorics. Int. Math. Res. Not. 44, 2709-2757 (2005)
16. Fomin, S., Zelevinsky, A.: Y -systems and generalized associahedra. Ann. Math. (2) 158(3), 977-1018 (2003)
17. Freese, R., Ježek, J., Nation, J.: Free Lattices. Mathematical Surveys and Monographs, vol.
42. Am. Math. Soc., Providence (1995)
18. Grätzer, G.: General Lattice Theory, 2nd edn. Birkhäuser, Basel (1998)
19. Hohlweg, C., Lange, C., Thomas, H.: Permutohedra and generalized associahedra. Preprint (2007).
20. Igusa, K., Orr, K., Todorov, G., Weyman, J.: Cluster complexes via semi-invariants. Compos. Math. 145(4), 1001-1034 (2009)
21. Ingalls, C., Thomas, H.: Noncrossing partitions and representations of quivers. Compos. Math. 145(6), 1533-1562 (2009)
22. Jedli\check cka, P.: A combinatorial construction of the weak order of a Coxeter group. Commun. Algebra 33, 1447-1460 (2005)
23. Kreweras, G.: Sur les partitions non croisées d'un cycle. Discrete Math. 1(4), 333-350 (1972)
24. Lee, C.W.: Subdivisions and triangulations of polytopes. In: Handbook of Discrete and Computational Geometry. CRC Press Ser. Discrete Math. Appl., pp. 271-290. CRC Press, Boca Raton (1997) J Algebr Comb (2011) 33: 483-530
25. Loday, J.-L.: Parking functions and triangulation of the associahedron. In: Categories in Algebra, Geometry and Mathematical Physics. Contemp. Math., vol. 431, pp. 327-340. Am. Math. Soc., Providence (2007)
26. Postnikov, A.: Permutohedra, associahedra and beyond. Int. Math. Res. Not. 6, 1026-1106 (2009)
27. Reading, N.: Lattice and order properties of the poset of regions in a hyperplane arrangement. Algebra Univers. 50, 179-205 (2003)
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)
29. Reading, N.: The cd-index of Bruhat intervals. Electron. J. Comb. 11(1), 74 (2004) (electronic)
30. Reading, N.: Lattice congruences of the weak order. Order 21(4), 315-344 (2004)
31. Reading, N.: Lattice congruences, fans and Hopf algebras. J. Comb. Theory Ser. A 110(2), 237-273 (2005)
32. Reading, N.: Cambrian lattices. Adv. Math. 205(2), 313-353 (2006)
33. Reading, N.: Clusters, Coxeter-sortable elements and noncrossing partitions. Trans. Am. Math. Soc. 359(12), 5931-5958 (2007)
34. Reading, N.: Sortable elements and Cambrian lattices. Algebra Univers. 56(3-4), 411-437 (2007)
35. Reading, N.: Chains in the noncrossing partition lattice. SIAM J. Discrete Math. 22(3), 875-886 (2008)
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)
37. Reading, N., Speyer, D.: Cambrian fans. J. Eur. Math. Soc. 11(2), 407-447
38. Reading, N., Speyer, D.: Sortable elements in infinite Coxeter groups. Trans. Am. Math. Soc. (2010, to appear).
2. Athanasiadis, C.A., Reiner, V.: Noncrossing partitions for the group Dn. SIAM J. Discrete Math. 18(2), 397-417 (2004)
3. Athanasiadis, C.A., Brady, T., Watt, C.: Shellability of noncrossing partition lattices. Proc. Am. Math. Soc. 135(4), 939-949 (2007)
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)
5. Bessis, D.: The dual braid monoid. Ann. Sci. École Norm. Super. (4) 36(5), 647-683 (2003)
6. Biane, P.: Some properties of crossings and partitions. Discrete Math. 175(1-3), 41-53 (1997)
7. Björner, A., Edelman, P., Ziegler, G.: Hyperplane arrangements with a lattice of regions. Discrete Comput. Geom. 5, 263-288 (1990)
8. Brady, T., Watt, C.: A partial order on the orthogonal group. Commun. Algebra 30(8), 3749-3754 (2002)
9. Brady, T., Watt, C.: From permutahedron to associahedron. Preprint (2008).
10. Brady, T., Watt, C.: Non-crossing partition lattices in finite real reflection groups. Trans. Am. Math. Soc. 360, 1983-2005 (2008)
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)
12. Chajda, I., Snášel, V.: Congruences in ordered sets. Math. Bohem. 123(1), 95-100 (1998)
13. Chapoton, F.: Enumerative properties of generalized associahedra. Sémin. Lothar. Comb. 51, B51b (2004)
14. Chindris, C.: Cluster fans, stability conditions, and domains of semi-invariants. Trans. Am. Math. Soc. (2010, to appear)
15. Fomin, S., Reading, N.: Generalized cluster complexes and Coxeter combinatorics. Int. Math. Res. Not. 44, 2709-2757 (2005)
16. Fomin, S., Zelevinsky, A.: Y -systems and generalized associahedra. Ann. Math. (2) 158(3), 977-1018 (2003)
17. Freese, R., Ježek, J., Nation, J.: Free Lattices. Mathematical Surveys and Monographs, vol.
42. Am. Math. Soc., Providence (1995)
18. Grätzer, G.: General Lattice Theory, 2nd edn. Birkhäuser, Basel (1998)
19. Hohlweg, C., Lange, C., Thomas, H.: Permutohedra and generalized associahedra. Preprint (2007).
20. Igusa, K., Orr, K., Todorov, G., Weyman, J.: Cluster complexes via semi-invariants. Compos. Math. 145(4), 1001-1034 (2009)
21. Ingalls, C., Thomas, H.: Noncrossing partitions and representations of quivers. Compos. Math. 145(6), 1533-1562 (2009)
22. Jedli\check cka, P.: A combinatorial construction of the weak order of a Coxeter group. Commun. Algebra 33, 1447-1460 (2005)
23. Kreweras, G.: Sur les partitions non croisées d'un cycle. Discrete Math. 1(4), 333-350 (1972)
24. Lee, C.W.: Subdivisions and triangulations of polytopes. In: Handbook of Discrete and Computational Geometry. CRC Press Ser. Discrete Math. Appl., pp. 271-290. CRC Press, Boca Raton (1997) J Algebr Comb (2011) 33: 483-530
25. Loday, J.-L.: Parking functions and triangulation of the associahedron. In: Categories in Algebra, Geometry and Mathematical Physics. Contemp. Math., vol. 431, pp. 327-340. Am. Math. Soc., Providence (2007)
26. Postnikov, A.: Permutohedra, associahedra and beyond. Int. Math. Res. Not. 6, 1026-1106 (2009)
27. Reading, N.: Lattice and order properties of the poset of regions in a hyperplane arrangement. Algebra Univers. 50, 179-205 (2003)
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)
29. Reading, N.: The cd-index of Bruhat intervals. Electron. J. Comb. 11(1), 74 (2004) (electronic)
30. Reading, N.: Lattice congruences of the weak order. Order 21(4), 315-344 (2004)
31. Reading, N.: Lattice congruences, fans and Hopf algebras. J. Comb. Theory Ser. A 110(2), 237-273 (2005)
32. Reading, N.: Cambrian lattices. Adv. Math. 205(2), 313-353 (2006)
33. Reading, N.: Clusters, Coxeter-sortable elements and noncrossing partitions. Trans. Am. Math. Soc. 359(12), 5931-5958 (2007)
34. Reading, N.: Sortable elements and Cambrian lattices. Algebra Univers. 56(3-4), 411-437 (2007)
35. Reading, N.: Chains in the noncrossing partition lattice. SIAM J. Discrete Math. 22(3), 875-886 (2008)
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)
37. Reading, N., Speyer, D.: Cambrian fans. J. Eur. Math. Soc. 11(2), 407-447
38. Reading, N., Speyer, D.: Sortable elements in infinite Coxeter groups. Trans. Am. Math. Soc. (2010, to appear).
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition