Part I Combinatorics
1 Eulerian numbers ............................................. 3
1.1 Binomial coefficients ................................... 3
1.2 Generating functions .................................... 5
1.3 Classical Eulerian numbers .............................. 6
1.4 Eulerian polynomials .................................... 9
1.5 Two important identities ............................... 10
1.6 Exponential generating function ........................ 12
Problems .................................................... 14
2 Narayana numbers ............................................ 19
2.1 Catalan numbers ........................................ 19
2.2 Pattern-avoiding permutations .......................... 20
2.3 Narayana numbers ....................................... 23
2.4 Dyck paths ............................................. 26
2.4.1 Counting all Dyck paths ......................... 27
2.4.2 Counting Dyck paths by peaks .................... 29
2.4.3 A bijection with 231-avoiding permutations ...... 31
2.5 Planar binary trees .................................... 34
2.6 Noncrossing partitions ................................. 36
Problems .................................................... 40
3 Partially ordered sets ...................................... 47
3.1 Basic definitions and terminology ...................... 47
3.2 Labeled posets and P-partitions ........................ 50
3.3 The shard intersection order ........................... 54
3.4 The lattice of noncrossing partitions .................. 57
3.5 Absolute order and Noncrossing partitions .............. 61
Problems .................................................... 64
4 Gamma-nonnegativity ......................................... 71
4.1 The idea of gamma-nonnegativity ........................ 71
4.2 Gamma-nonnegativity for Eulerian numbers ............... 72
4.3 Gamma-nonnegativity for Narayana numbers ............... 76
4.4 Palindromicity, unimodality, and the gamma basis ....... 77
4.5 Computing the gamma vector ............................. 80
4.6 Real roots and log-concavity ........................... 81
4.7 Symmetric boolean decomposition ........................ 84
Problems .................................................... 88
5 Weak order, hyperplane arrangements, and the Tamari
lattice ..................................................... 95
5.1 Inversions ............................................. 95
5.2 The weak order ......................................... 98
5.3 The braid arrangement ................................. 100
5.4 Euclidean hyperplane arrangements ..................... 102
5.5 Products of faces and the weak order on chambers ...... 105
5.6 Set compositions ...................................... 108
5.7 The Tamari lattice .................................... 113
5.8 Rooted planar trees and faces of the associahedron .... 115
Problems ................................................... 123
6 Refined enumeration ........................................ 127
6.1 The idea of a q-analogue .............................. 127
6.2 Lattice paths by area ................................. 129
6.3 Lattice paths by major index .......................... 132
6.4 Euler-Mahonian distributions .......................... 134
6.5 Descents and major index .............................. 137
6.6 q-Catalan numbers ..................................... 139
6.7 q-Narayana numbers .................................... 140
6.8 Dyck paths by area .................................... 143
Problems ................................................... 149
7 Cubes, Carries, and an Amazing Matrix: (Supplemental) ...... 151
7.1 Slicing a cube ........................................ 151
7.2 Carries in addition ................................... 154
7.3 The amazing matrix .................................... 156
Part II Combinatorial topology
8 Simplicial complexes ....................................... 163
8.1 Abstract simplicial complexes ......................... 163
8.2 Simple convex polytopes ............................... 166
8.3 Boolean complexes ..................................... 167
8.4 The order complex of a poset .......................... 169
8.5 Flag simplicial complexes ............................. 170
8.6 Balanced simplicial complexes ......................... 172
8.7 Face enumeration ...................................... 173
8.8 The h-vector .......................................... 175
8.9 The Dehn-Sommerville relations ........................ 177
Problems ................................................... 181
9 Barycentric subdivision .................................... 185
9.1 Barycentric subdivision of a finite cell complex ...... 185
9.2 The barycentric subdivision of a simplex .............. 187
9.3 Brenti and Welker's transformation .................... 190
9.4 The h-vector of sd(Δ) and j-Eulerian numbers ......... 193
9.5 Gamma-nonnegativity of h(sd(Δ)) ....................... 196
9.6 Real roots for barycentric subdivisions ............... 200
Problems ................................................... 201
10 Characterizing ƒ-vectors: (Supplemental) ................... 203
10.1 Compressed simplicial complexes ....................... 203
10.2 Proof of the compression lemma ........................ 207
10.3 Kruskal-Katona-Schiitzenberger inequalities ........... 215
10.4 Frankl-Fiiredi-Kalai inequalities ..................... 219
10.5 Multicomplexes and M-vectors .......................... 223
10.6 The Stanley-Reisner ring .............................. 225
10.7 The upper bound theorem and the g-theorem ............. 228
10.8 Conjectures for flag spheres 230
Part III Coxeter groups
11 Coxeter groups ............................................. 237
11.1 The symmetric group ................................... 237
11.2 Finite Coxeter groups: generators and relations ....... 243
11.3 IV-Mahonian distribution .............................. 246
11.4 VK-Eulerian numbers ................................... 246
11.5 Finite reflection groups and root systems ............. 250
11.5.1 Type An-1 ...................................... 254
11.5.2 Type Bn ........................................ 254
11.5.3 Type Cn ........................................ 255
11.5.4 Type Dn ........................................ 255
11.5.5 Roots for I2(m) ................................ 256
11.6 The Coxeter arrangement and the Coxeter complex ....... 257
11.7 Action of W and cosets of parabolic subgroups ......... 259
11.8 Counting faces in the Coxeter complex ................. 262
11.9 The W-Euler-Mahonian distribution ..................... 264
11.10 The weak order ....................................... 266
11.11 The shard intersection order ......................... 269
Problems ................................................... 271
12 W-Narayana numbers ......................................... 273
12.1 Reflection length and Coxeter elements ................ 273
12.2 Absolute order and W-noncrossing partitions ........... 276
12.3 W-Catalan and W-Narayana numbers ...................... 277
12.4 Coxeter-sortable elements ............................. 280
12.5 Root posets and W-nonnesting partitions ............... 282
12.6 The W-associahedron ................................... 287
Problems ................................................... 290
13 Combinatorics for Coxeter groups of types Bn and Dn:
(Supplemental) ............................................. 293
13.1 Type Bn Eulerian numbers .............................. 293
13.2 Type Bn gamma-nonnegativity ........................... 297
13.3 Type Dn Eulerian numbers .............................. 301
13.4 Type Dn gamma-nonnegativity ........................... 303
13.5 Combinatorial models for shard intersections .......... 307
13.5.1 Type An-1 ...................................... 307
13.5.2 Type Bn ........................................ 311
13.5.3 Type Dn ........................................ 316
13.6 Type Bn noncrossing partitions and Narayana numbers ... 320
13.7 Gamma-nonnegativity for Cat(Bn;t) ..................... 325
13.8 Type Dn noncrossing partitions and Narayana numbers ... 327
13.9 Gamma-nonnegativity for Cat(Dn; t) .................... 330
14 Afflne descents and the Steinberg torus: (Supplemental) .... 333
14.1 Affine Weyl groups .................................... 333
14.2 Faces of the affine Coxeter complex ................... 334
14.3 The Steinberg torus ................................... 338
14.4 Affine Eulerian numbers ............................... 341
14.4.1 Type An-1 ...................................... 341
14.4.2 Type Bn ........................................ 342
14.4.3 Type Cn ........................................ 343
14.4.4 Type Dn ........................................ 344
References .................................................... 347
Hints and Solutions ........................................... 359
Index ......................................................... 453
|
