SLC,March312010arXiv:0711.1561v1[math.RT]arXiv:0804.3781v1[math.RT]arXiv:0912.2212v1[math.CO]+researchinprogress FlorentHivert AnneSchilling NicolasM.Thi´ery SortingmonoidsonCoxetergroups

1 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Sorting monoids on Coxeter groups

Florent Hivert¹ Anne Schilling² Nicolas M. Thi´ery^2,3

1LITIS/LIFAR, Universit´e Rouen, France

2University of California at Davis, USA

3Laboratoire de Math´ematiques d’Orsay, Universit´e Paris Sud, France

SLC, March 31 2010 arXiv:0711.1561v1 [math.RT]

arXiv:0804.3781v1 [math.RT]

arXiv:0912.2212v1 [math.CO]

+ research in progress

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

1234

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

1234

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

1243

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

1423

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4123

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4123

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4132

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4312

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4312

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4321

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4321

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4321

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4321

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4321

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

2 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Bubble (anti) sort algorithm

4321

Underlying combinatorics: right permutohedron

123

213 132

312 231

321

1234

2134 1324 1243

2314 3124 2143 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

Elementary transpositions: s₁,s₂,s₃, . . .

Relations: s_i²,(s1s2)³ = 1,(s2s3)³= 1,(s1s3)²= 1

3 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Coxeter groups

Definition (Coxeter groupW)

Generators : s1,s2, . . . (simple reflections) Relations: s_i² = 1 and sisj· · ·

| {z }

mi,j

=sjsi· · ·

| {z }

mi,j

, for i 6=j

• Reduced word

• Length

3 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Coxeter groups

Definition (Coxeter groupW)

Generators : s1,s2, . . . (simple reflections) Relations: s_i² = 1 and sisj· · ·

| {z }

mi,j

=sjsi· · ·

| {z }

mi,j

, for i 6=j

• Reduced word

• Length

3 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Coxeter groups

Definition (Coxeter groupW)

Generators : s1,s2, . . . (simple reflections) Relations: s_i² = 1 and sisj· · ·

| {z }

mi,j

=sjsi· · ·

| {z }

mi,j

, for i 6=j

• Reduced word

• Length

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · ·

Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · ·

Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · ·

Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · · Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · · Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · · Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · · Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · · Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

4 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Orders on words and on Coxeter group elements

Definition (Orders on words) Letu =u₁· · ·u_k andv =v₁· · ·v_l:

• u left factorof v ifv =u1· · ·u_k· · ·

• u right factor ofv if v=· · ·u1· · ·uk

• u factor ofv if v=· · ·u1· · ·uk· · ·

• u subwordof v ifv =· · ·u₁· · ·u₂· · ·u_k· · · Definition (Orders on Coxeter group elements)

• Right weak order

• Left weak order

• Left-right weak order

• Bruhat order

5 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Blocks of permutations

Definition (Block of a permutation w)

• Type A: sub-permutation matrix

• Type free: J,K such that W_Jw =wW_K

• Example: w := 36475812

• Simple permutation: cf. [Albert, Atkinson 05]

• {blocks of w}: sub-lattice of the Boolean lattice

1234

1324 1243

3124 1342 1423

3142 1432 4123

3412 4132

4312

1234 1324

3124 1342 3142

3412

1243 1423

4123 1432 4132

4312

5 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Blocks of permutations

Definition (Block of a permutation w)

• Type A: sub-permutation matrix

• Type free: J,K such that W_Jw =wW_K

• Example: w := 36475812

• Simple permutation: cf. [Albert, Atkinson 05]

• {blocks of w}: sub-lattice of the Boolean lattice

1234

1324 1243

3124 1342 1423

3142 1432 4123

3412 4132

4312

1234 1324

3124 1342 3142

3412

1243 1423

4123 1432 4132

4312

5 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Blocks of permutations

Definition (Block of a permutation w)

• Type A: sub-permutation matrix

• Type free: J,K such that W_Jw =wW_K

• Example: w := 36475812

• Simple permutation: cf. [Albert, Atkinson 05]

• {blocks of w}: sub-lattice of the Boolean lattice

1234

1324 1243

3124 1342 1423

3142 1432 4123

3412 4132

4312

1234 1324

3124 1342 3142

3412

1243 1423

4123 1432 4132

4312

5 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Blocks of permutations

Definition (Block of a permutation w)

• Type A: sub-permutation matrix

• Type free: J,K such that W_Jw =wW_K

• Example: w := 36475812

• Simple permutation: cf. [Albert, Atkinson 05]

• {blocks of w}: sub-lattice of the Boolean lattice

1234

1324 1243

3124 1342 1423

3142 1432 4123

3412 4132

4312

1234 1324

3124 1342 3142

3412

1243 1423

4123 1432 4132

4312

5 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Blocks of permutations

Definition (Block of a permutation w)

• Type A: sub-permutation matrix

• Type free: J,K such that W_Jw =wW_K

• Example: w := 36475812

• Simple permutation: cf. [Albert, Atkinson 05]

• {blocks of w}: sub-lattice of the Boolean lattice

1234

1324 1243

3124 1342 1423

3142 1432 4123

3412 4132

4312

1234 1324

3124 1342 3142

3412

1243 1423

4123 1432 4132

4312

5 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Blocks of permutations

Definition (Block of a permutation w)

• Type A: sub-permutation matrix

• Type free: J,K such that W_Jw =wW_K

• Example: w := 36475812

• Simple permutation: cf. [Albert, Atkinson 05]

• {blocks of w}: sub-lattice of the Boolean lattice

1234

1324 1243

3124 1342 1423

3142 1432 4123

3412 4132

4312

1234 1324

3124 1342 3142

3412

1243 1423

4123 1432 4132

4312

6 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The cutting poset of a Coxeter group

Definition (HST09: Cutting poset (W,@)) u@w ifu =w^K with K block









•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•









• (almost) lattice

• M¨obius function: inclusion-exclusion along minimal blocks

6 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The cutting poset of a Coxeter group

Definition (HST09: Cutting poset (W,@)) u@w ifu =w^K with K block









•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•









• (almost) lattice

• M¨obius function: inclusion-exclusion along minimal blocks

6 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The cutting poset of a Coxeter group

Definition (HST09: Cutting poset (W,@)) u@w ifu =w^K with K block









•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•

















•

•

•

•









• (almost) lattice

• M¨obius function: inclusion-exclusion along minimal blocks

7 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Hecke monoid

Definition (0-Hecke monoidH0(W) of a Coxeter groupW) Generators : hπ₁,π2, . . .i (simple reflections)

Relations: π_i²=π_i and braid relations

Theorem (Norton 79, Carter 86, Krob-Thibon 97, Denton 09)

|H₀(W)|=|W|

+ lots of nice properties

Motivation: simple combinatorial model (bubble sort)

appears in Iwahori-Hecke algebras, Schur symmetric functions, Schubert, Kazhdan-Lusztig polynomials, and Macdonald, (affine) Stanley symmetric functions, mathematical physics, Schur-Weyl duality for quantum groups, representations ofGL(Fq), . . .

7 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Hecke monoid

Definition (0-Hecke monoidH0(W) of a Coxeter groupW) Generators : hπ₁,π2, . . .i (simple reflections)

Relations: π_i²=π_i and braid relations

Theorem (Norton 79, Carter 86, Krob-Thibon 97, Denton 09)

|H₀(W)|=|W|

+ lots of nice properties

Motivation: simple combinatorial model (bubble sort)

appears in Iwahori-Hecke algebras, Schur symmetric functions, Schubert, Kazhdan-Lusztig polynomials, and Macdonald, (affine) Stanley symmetric functions, mathematical physics, Schur-Weyl duality for quantum groups, representations ofGL(Fq), . . .

7 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

Hecke monoid

Definition (0-Hecke monoidH0(W) of a Coxeter groupW) Generators : hπ₁,π2, . . .i (simple reflections)

Relations: π_i²=π_i and braid relations

Theorem (Norton 79, Carter 86, Krob-Thibon 97, Denton 09)

|H₀(W)|=|W|

+ lots of nice properties

Motivation: simple combinatorial model (bubble sort)

appears in Iwahori-Hecke algebras, Schur symmetric functions, Schubert, Kazhdan-Lusztig polynomials, and Macdonald, (affine) Stanley symmetric functions, mathematical physics, Schur-Weyl duality for quantum groups, representations ofGL(Fq), . . .

8 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The Big Picture

Hζ( ˜W)

Hζ(W)

H_ζ(Sn) V

H−1( ˜W)

H−1(W)

TLn

Hq( ˜W)

Hq(W)

Hq(Sn) V H0(W)

hπ1,π2, . . .i H0( ˜W) h˜π0π1,π2, . . .i

NDPFn

H0(W) hπ1,π2, . . .i

H0( ˜W) hπ˜0π1,π2, . . .i

NDPFn

NDPFB

HW Q[π₁,π₂, . . . ,s₁,s₂, . . .] Q[π1,π2, . . . ,π1,π2, . . .]

Q[π0π1,π2, . . .]

NDFn

W hs1,s2, . . .i

W˜ h˜s0s1,s2, . . .i

Sn V M1

NDPF(Bruhat(W)) End(<L(W))

hπ1,π2, . . . ,π1,π2, . . .i hπ1,π2, . . . ,s1,s2, . . .i hπ0π1,π2, . . .i End(BooleanLattice)

9 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The bi-Hecke monoid

Question

Size of M(W) =hπ₁,π₂, . . . ,π₁,π₂, . . .i

|M(Sn)|= 1,3,23,477,31103,?

• How to attack such a problem?

• Generators and relations?

• Representation theory?

Theorem (HST08)

M(W)admits |W|simple / indecomposable projective modules

• Why do we care?

|M(W)|= X

w∈W

dimS_w.dimP_w

9 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The bi-Hecke monoid

Question

Size of M(W) =hπ₁,π₂, . . . ,π₁,π₂, . . .i

|M(Sn)|= 1,3,23,477,31103,?

• How to attack such a problem?

• Generators and relations?

• Representation theory?

Theorem (HST08)

M(W)admits |W|simple / indecomposable projective modules

• Why do we care?

|M(W)|= X

w∈W

dimS_w.dimP_w

9 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The bi-Hecke monoid

Question

Size of M(W) =hπ₁,π₂, . . . ,π₁,π₂, . . .i

|M(Sn)|= 1,3,23,477,31103,?

• How to attack such a problem?

• Generators and relations?

• Representation theory?

Theorem (HST08)

M(W)admits |W|simple / indecomposable projective modules

• Why do we care?

|M(W)|= X

w∈W

dimS_w.dimP_w

9 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The bi-Hecke monoid

Question

Size of M(W) =hπ₁,π₂, . . . ,π₁,π₂, . . .i

|M(Sn)|= 1,3,23,477,31103,?

• How to attack such a problem?

• Generators and relations?

• Representation theory?

Theorem (HST08)

M(W)admits |W|simple / indecomposable projective modules

• Why do we care?

|M(W)|= X

w∈W

dimS_w.dimP_w

9 / 19

Bubble sort and Coxeter groups Sorting monoids Combinatorics of the bi-Hecke monoid

The bi-Hecke monoid

Question

Size of M(W) =hπ₁,π₂, . . . ,π₁,π₂, . . .i

|M(Sn)|= 1,3,23,477,31103,?

• How to attack such a problem?

• Generators and relations?

• Representation theory?

Theorem (HST08)

M(W)admits |W|simple / indecomposable projective modules

• Why do we care?

|M(W)|= X

w∈W

dimS_w.dimP_w