Counting chains in noncrossing partition lattices

Nathan Reading

Description

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 ...

Informations

• Publié par: Fuiv
• Nombre de lectures: 30
• Langue: English

Extrait

Counting chains

in noncrossing partition lattices

Nathan Reading

NC State University

NCSU Algebra Seminar, November 16, 2007

1

Counting chains in noncrossing partition

Classical noncrossing partitions

Coxeter groups and noncrossing partitions

Counting maximal chains

lattices

2

Classical noncrossing partitions

(Kerewars,1972)

Identify the numbers 12   nwithndistinct points in cyclic order on a circle. For each blockBof a partitionπ, draw the convex polygon whose vertices are the points inB. If|B|is 1 or 2, this “polygon” is a point or a line segment.

The partitionπisnoncrossingif and only if in its planar diagram, the blocks are disjoint (i.e. don’t cross).

Example Crossing and noncrossing: 1 9 2

8

7

6 5

3

4

8

7

9

1

6 5

2

3

4

3

The

classical

Ordered

by

noncrossing

refinement

of

partition

partitions.

lattice

4

1

3

2

4

Enumeration

Noncrossing partitions Noncrossing partitions of [n] are counted by the famous Catalan numbers

C n := n1 1 +  2 n n  

Chains Detailed enumeration formulas exist counting chains (totally ordered subsets) in the noncrossing partition lattice according to the set of ranks visited. (Edelman, 1980).

Maximal chains There aren n−2  is a nice bijection with Theremaximal chains. parking functions (Stanley, 1997).

5

Example

4 4−2

=

16

maximal

chains

for

n

=

4.

6

Finite reflection groups

Finite groupsWgenerated by (Euclidean) orthogonal reflections. Examples: symmetry groups of regular polytopes, Weyl groups. Coxeter arrangementA={All reflecting hyperplanes forW}. Simple reflections: Fix a connected componentRof the complement of S A. LetSbe the set of reflections in the facet-hyperplanes ofR.

W=S 4 :

(3 4)

(2 3)

R

(1 2)

7

Coxeter groups

Coxeter group group with a presentation of the form: a

hS|s 2 = 1(st) m(st) = 1i

Finite Coxeter groups↔finite reflection groups.

Coxeter diagram the presentation.: encodes •Vertex set:S •Edges:s—twhenm(st)>2, labeled bym(st) when m(st)>3.

IrreducibleCoxeter group: a Coxeter group having a connected diagram.

8

itacfiissalCefiblcidureirofonorpuetgroCexinets

r

r r r

r

r

r r r

F 4 H 3 H 4 I 2 (m) (m≥5)

E 8

9

r r r 4 r r r r ❍ ❍ ✟ r r r✟ r r r r r r r r r r r r 4 r r r 5 r r r r 5 r r m r r

r r r r

E 7

A n (n≥1) B n (n≥2) D n (n≥4) E 6

r

r

r

r

r

r r r

r r r r

r

Types A, B and D

• •

•

A n−1 =S n : Reflecting hyperplanes arex i =x j fori6=j. B n (the symmetry group of then-cube orn-octohedron): Reflecting hyperplanes arex i = 0 andx i =±x j fori6=j.

D n : Reflecting hyperplanes arex i =±x j fori6=j.

01

Intersection lattices

Intersection lattice intersections ofof the Coxeter arrangement: sets of hyperplanes, ordered by reverse inclusion. Key point:The intersection lattice forS n is the lattice of partitions.

S 9 example:

T {x 1 =x 2 x 2 =x 8 x 3 =x 7 x 3 =x 9 x 5 =x 6 } l {128}{379}{4}{56}

B n intersection lattice: partitions of±[n] fixed byi7→ −i, at most one block containing a pair (i−i).

B 9 example:

T {x 1 = 0x 2 = 0x 2 =−x 7  x 4 =−x 9 x 5 =x 7 x 6 =x 8 } l {±1±2±5±7}{3}{−3} {4−9}{−49}{68}{−6−6}

11