Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

Cataland: Why the Fuss?
Christian Stump, Hugh Thomas, Nathan Williams
July 6, 2016
Catalan Numbers
\[\mathrm{Cat}(n)=\frac{1}{n}\binom{2n}{n-1}\]
Fuss-Catalan Numbers
\[\mathrm{Cat}^m(n)=\frac{1}{n}\binom{(m+1)n}{n-1}\]
$W$-Catalan Numbers
\[\mathrm{Cat}(W)=\prod_{i=1}^n \frac{h+d_i}{d_i}\]
Fuss $W$-Catalan Numbers
\[\mathrm{Cat}^m(W)=\prod_{i=1}^n\frac{mh+d_i}{d_i}.\]
Two Catalands

Artin Group: $B(W)$

Affine Weyl Group: $\widetilde{W}$



Moral. Fuss-Catalan objects are found by "dilating" in each of these worlds.


Artin Group: $B(W)$











Affine Weyl Group: $\widetilde{W}$











Catalan Numbers
\[\mathrm{Cat}(n)=\frac{1}{n}\binom{2n}{n-1}\]
Dyck Paths


Definition. A Dyck path of order $n$ is a path from $(0,0)$ to $(n+1,n)$ using steps in $\{(1,0),(0,1)\}$ that stays above the diagonal $y=\frac{n}{n+1}x$.


The Cycle Lemma
Cycle Lemma. There are \[\mathrm{Cat}(n)=\frac{1}{2n+1}\binom{2n+1}{n}\] Dyck paths of order $n$.
The Cycle Lemma
Cycle Lemma. There are \[\mathrm{Cat}(n)=\frac{1}{2n+1}\binom{2n+1}{n}\] Dyck paths of order $n$.
The Cycle Lemma
Cycle Lemma. There are \[\mathrm{Cat}(n)=\frac{1}{n}\binom{2n}{n-1}\] Dyck paths of order $n$.
The Cycle Lemma
Cycle Lemma. There are \[\mathrm{Cat}(n)=\frac{1}{n}\binom{2n}{n-1}\] Dyck paths of order $n$.
Fuss-Catalan Numbers
\[\mathrm{Cat}^m(n)=\frac{1}{n}\binom{(m+1)n}{n-1}\]
Rational Dyck Paths
Cycle Lemma. For $n$ and $p$ relatively prime, there are \[\mathrm{Cat}^{(p)}(n)=\frac{1}{n}\binom{p+n-1}{n-1}\] lattice paths from $(0,0)$ to $(p,n)$ that stay above the diagonal $y=\frac{n}{p}x$.
$W$-Catalan Numbers
\[\mathrm{Cat}(W)=\prod_{i=1}^n \frac{h+d_i}{d_i}\]
Weyl Groups
"Definition". A finite Weyl group $W$ is a finite (real) reflection group stabilizing its coroot lattice $\check{Q}$.
\[\mathfrak{S}_{n+1} = \left \langle s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
  • For $\mathfrak{S}_{n+1}$, the generator $s_i$ acts on $\mathbb{R}^{n+1}$ by reflecting in the hyperplane \[x_i-x_{i+1}=0.\]
  • The lattice $\check{Q} = \{(x_1,x_2,\ldots,x_{n+1})\in \mathbb{Z}^{n+1} : \sum_{i=1}^{n+1}x_i = 0\}.$
Nonnesting Partitions
Observation. Dyck paths of order $n$ are order ideals in the positive root poset for $\mathfrak{S}_n$ ($\alpha<\beta$ iff $\beta-\alpha$ is a nonnegative sum of simple roots).
Fact. Root posets have a maximal element--the highest root.
Nonnesting Partitions
Observation (Postnikov). Order ideals in the positive root poset generalize Dyck paths to all finite Weyl groups.
Problem. What do Fuss- or rational-Dyck paths correspond to? We have run out of roots!
Affine Weyl Groups
"Definition". The affine group $\widetilde{W}$ corresponding to $W$ is the group $W \rtimes \check{Q} \simeq \widetilde{W}/W \rtimes W$.
\[\widetilde{\mathfrak{S}}_{n+1} = \left \langle s_0,s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
\[\mathfrak{S}_{n+1} \subset \widetilde{\mathfrak{S}}_{n+1} = \left \langle s_0,s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
\[W \rtimes \check{Q} \simeq \widetilde{W}/W \rtimes W\]
\[\mathfrak{S}_{n+1} \subset \widetilde{\mathfrak{S}}_{n+1} = \left \langle s_0,s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
\[W \rtimes \check{Q} \simeq \widetilde{W}/W \rtimes W\]
\[\mathfrak{S}_{n+1} \subset \widetilde{\mathfrak{S}}_{n+1} = \left \langle s_0,s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
\[W \rtimes \check{Q} \simeq \widetilde{W}/W \rtimes W\]
\[W \rtimes \check{Q} \simeq \widetilde{W}/W \rtimes W\]
\[W \rtimes \check{Q} \simeq \widetilde{W}/W \rtimes W\]
\[ \check{Q} \simeq \widetilde{W}/W \]
Nonnesting Partitions
Problem. We have run out of roots!
Nonnesting Partitions
Solution. We have plenty more roots!
Nonnesting Partitions
Problem. We have run out of roots!
Nonnesting Partitions
Solution. We have plenty more roots!
\[\check{Q} \simeq \widetilde{W}/W\]
\[\check{Q} \simeq \widetilde{W}/W\]
$W$-Catalan Numbers
Theorem. The $W$-Catalan number counts lattice points inside a simplex: \[\mathrm{Cat}(W)=\prod_{i=1}^n\frac{h+d_i}{d_i}=\left|\check{Q} \cap (h+1)A_0\right|.\]
Cycle Lemma. The Catalan number for $\mathfrak{S}_n$ is the number of lattice points inside an $(n+1)$-fold dilation of a simplex: \[\mathrm{Cat}(\mathfrak{S}_n)=\left|\check{Q} \cap (n+1)A_0\right|=\frac{1}{n}\binom{2n}{n-1}.\]
Fuss $W$-Catalan Numbers
\[\mathrm{Cat}^m(W)=\prod_{i=1}^n\frac{mh+d_i}{d_i}.\]
Rational $W$-Catalan Numbers
Theorem. For $p$ coprime to the index of connection: \[\mathrm{Cat}^m(W)=\prod_{i=1}^n\frac{p+e_i}{d_i}=\left|\check{Q} \cap pA_0\right|.\]
Catalan Numbers
\[\mathrm{Cat}(n)=\frac{1}{n}\binom{2n}{n-1}\]
Triangulations
Definition. A triangulation of order $n$ is a collection of pairwise noncrossing diagonals of a convex $(n+2)$-gon.
Theorem (Euler). There are \[\mathrm{Cat}(n)=\frac{1}{n}\binom{2n}{n-1}\] triangulations of order $n$.
Fuss-Catalan Numbers
\[\mathrm{Cat}^m(n)=\frac{1}{n}\binom{(m+1)n}{n-1}\]
Definition. An $(m+2)$-angulation of order $n$ is a collection of pairwise noncrossing diagonals that divide a convex $(mn+2)$-gon into $(m+2)$-gons.
Theorem (Fuss). There are \[\mathrm{Cat}^m(n)=\frac{1}{n}\binom{(m+1)n}{n-1}\] $(m+2)$-angulations of order $n$.
Flips? Tamari Lattice?
$W$-Catalan Numbers
\[\mathrm{Cat}(W)=\prod_{i=1}^n \frac{h+d_i}{d_i}\]
"Definition". A finite Coxeter group $W$ is a finite group with a presentation \[W = \left \langle s_1,\ldots,s_n : \substack{s_i^2=e \\ (s_i s_j)^{m_{ij}} = e \text{ for } s_i \neq s_j} \right \rangle.\]
\[\mathfrak{S}_{n+1} = \left \langle s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
Definition. The weak order on $W$ is the partial order defined by $u \leq v$ iff $u$ is a prefix of some reduced word for $v$.
Facts.
  • (i) The underlying graph of the Hasse diagram of weak order is the Cayley graph of $W$ w.r.t $s_1,\ldots,s_n$.
  • (ii) The identity is the unique minimal element.
  • (iii) There is a unique maximal element $w_0$.
  • (iv) The weak order is a lattice (gcd and lcm).
Tamari Lattices and Weak Order
Definition. A map $\mu$ from permutations to triangulations.
The map $\mu$
123
The map $\mu$
213
The map $\mu$
231
The map $\mu$
321
The map $\mu$
132
The map $\mu$
312
The map $\mu$
The map $\mu$
Tamari Lattices and Weak Order
Theorem (Knuth). There are $\mathrm{Cat}(n)$ $312$-avoiding permutations in $\mathfrak{S}_n$.
Theorem (Bjorner, Wachs).
  • The map $\mu$ is a bijection when restricted to 312-avoiding permutations.
  • The restriction of weak order to 312-avoiding perms is the Tamari lattice.
Cambrian Lattices and Weak Order
Reading extended this to any Coxeter group and any orientation $c$ of the Coxeter diagram. $312$-avoiding permutations become $c$-sortable elements.
Theorem (Reading). There are $\mathrm{Cat}(W)$ many $c$-sortable elements in $W$. The restriction of weak order to $c$-sortable elements is a (Cambrian) lattice that recovers the cluster exchange graph.
Fuss $W$-Catalan Numbers
\[\mathrm{Cat}^m(W)=\prod_{i=1}^n\frac{mh+d_i}{d_i}.\]
Fuss-Cambrian Lattices? Sortables?
\[\mathrm{Cat}(W) \leq |W|\]
\[\mathrm{Cat}^m(W) > |W| \text{ for } m \text{ large enough}.\]
Fuss-Cambrian Lattices and the Artin Monoid
"Definition". The Artin monoid $B^+(W)$ of a finite Coxeter group $W$ is the monoid with presentation \[B^+(W) = \left \langle s_1,\ldots,s_n : \underbrace{s_is_j\cdots}_{m_{ij} \text{ letters}} = \underbrace{s_js_i \cdots}_{m_{ij} \text{ letters}} \right \rangle_+.\]
$B^+(W)$ has a natural weak order, and we can extend the definition of $c$-sortable elements to this monoid.
\[B^+(\mathfrak{S}_{n+1}) = \left \langle s_1,\ldots,s_n : \substack{\\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle_+.\]
The Positive Artin Monoid
The Positive Artin Monoid
Fuss-Cambrian Lattices
Theorem (Stump, Thomas, Williams). There are $\mathrm{Cat}^m(W)$ many $c$-sortable elements in the interval $[e,w_0^m]$. The restriction of weak order to those elements is a lattice.
Fuss-Cambrian Lattices
Theorem (Stump, Thomas, Williams). There are $\mathrm{Cat}^m(W)$ many $c$-sortable elements in the interval $[e,w_0^m]$. The restriction of weak order to those elements is a lattice.
Open Problems


Thank you!




(And enjoy the excursion.)

Use a spacebar or arrow keys to navigate