Counting chains in noncrossing partition lattices

Counting chains in noncrossing partition latticesNathan ReadingNC State UniversityNCSU Algebra Seminar, November 16, 20071Counting chains in noncrossing partition latticesClassical noncrossing partitionsCoxeter groups and noncrossing partitionsCounting maximal chains2Classical noncrossing partitions (Kreweras, 1972)Identify the numbers 1,2,...n with n distinct points in cyclic orderon a circle. For each block B of a partition π, draw the convexpolygon whose vertices are the points in B. If |B| is 1 or 2, this“polygon” is a point or a line segment.The partition π is noncrossing if and only if in its planar diagram,the blocks are disjoint (i.e. don’t cross).ExampleCrossing and noncrossing:1 19 2 9 28 3 8 37 4 7 46 5 6 53The classical noncrossing partition latticeOrdered by refinement of partitions. 14 234EnumerationNoncrossing partitionsNoncrossing partitions of [n] are counted by the famous Catalannumbers 1 2nC := .n nn+1ChainsDetailed enumeration formulas exist counting chains (totallyordered subsets) in the noncrossing partition lattice according tothe set of ranks visited. (Edelman, 1980).Maximal chainsn−2There are n maximal chains. There is a nice bijection withparking functions (Stanley, 1997).5Example4−24 = 16 maximal chains for n = 4.6Finite reflection groupsFinite groups W generated by (Euclidean) orthogonal reflections.Examples: symmetry groups of regular polytopes, Weyl groups.Coxeter arrangement A ={All reflecting ...