###
Charmed Roots and the Kroweras Complement
###
Nonnesting vs. Noncrossing
###
Roots
- Let $\Phi$ be an irreducible root system of rank $r$ with Weyl group $W$. - The
*positive root poset*
$\Phi^+$ is defined by $\alpha < \beta$ iff $\beta-\alpha \in \mathbb{Z}_{\geq 0} \Phi^+$.
###
Type $F_4$
###
Roots and Exponents
- The
*positive root poset*
$\Phi^+$ is defined by $\alpha < \beta$ iff $\beta-\alpha \in \mathbb{Z}_{\geq 0} \Phi^+$. - The minimal elements are the $r$
*simple roots*
; - The maximal element is the
*highest root*
, with rank $h-1$; and - The
*exponents*
$e_1,e_2,\ldots,e_r$ are the dual partition of the rank sizes.
###
Roots and Exponents
> The exponents for type $A_n$ are $1,2,\ldots,n.$ > > The exponents for type $B_n$ are $1,3,\ldots,2n-1.$ > > The exponents for type $F_4$ are $1,5,7,11.$
###
Roots and Exponents
###
Nonnesting Gauss
- Gauss's elementary school teacher's punishment: > Sum the exponents for $\Phi$ of type $A_{100}.$
###
Nonnesting Gauss
- Gauss's elementary school teacher's punishment: > Sum the exponents for $\Phi$ of type $A_{100}.$ - Gauss immediately noticed that $e_i + e_{r+1-i} = h$.
###
Nonnesting Gauss
- By definition of the exponents, $e_1+e_2+\cdots+e_r = |\Phi^+| = N.$ - Gauss's computation: $$\begin{array}{llllllllll} & e_1 &+&e_2 &+&\cdots &+&e_r &=& N \\\ +& e_r &+&e_{r-1} &+&\cdots &+&e_1 &=& N \\\ \hline & h &+&h &+&\cdots &+& h &=& 2N \\\ &&&&rh&&& &=& 2N \end{array}$$ - Therefore, $e_1+\cdots+e_r = N = \frac{rh}{2}.$
###
Nonnesting Gauss
> $$\begin{aligned} \text{Type $A_n$}&: 1+2+\cdots+n &&= \frac{n(n+1)}{2} \\\ \\ \text{ Type $B_n$}&: 1+3+\cdots+(2n-1) &&= n^2.\end{aligned}$$
###
Nonnesting Gauss
> $$\text{Type $F_4$}: 1+5+7+11 = 24.$$
###
Noncrossing Gauss
###
Noncrossing Gauss
- A
*(standard) Coxeter element*
is a product of the $r$ simple reflections of $W$ (in any order). > In $S_n$, a Coxeter element is a long cycle with cycle notation $$(\mathbf{1} \textcolor{#3498db}{< a_2 < \cdots < a_{m-1} <} \mathbf{n} \textcolor{#3498db}{> a_{m+1} > \cdots> a_n}).$$ > In $S_9$, $(\mathbf{1} \textcolor{#3498db}{, 3, 4, 7,} \mathbf{9} \textcolor{#3498db}{, 8, 6, 5, 2})$ is a Coxeter element. - Because Dynkin diagrams are trees, all Coxeter elements are conjugate by a sequence of *initial* (or *final*) simple reflections $s$: $$c \to scs \to \cdots$$
###
Noncrossing Gauss
- Because Dynkin diagrams are trees, all Coxeter elements are conjugate by a sequence of
*initial*
(or
*final*
) simple reflections:
###
Noncrossing Gauss
- Let $c \in W$ be a Coxeter element with reduced word $\mathbf{c}$ (of length $r$). - The
*$c$-sorting word*
$\mathbf{w}(\mathbf{c})$ is the leftmost reduced word for $w\in W$ in $\mathbf{c}^\infty$. - Let $w_\circ$ be the long element of $W$ (of length $N$). Up to commutations: $$\mathbf{w}\_\circ(\mathbf{c}) \mathbf{w}\_\circ(\widetilde{\mathbf{c}}) \simeq \mathbf{c}^h.$$
- Every root must appear twice in the inversion sequence (since $w_\circ^2=e$): $$2N = rh.$$
###
Noncrossing Gauss
> In type $A_n$ and $c=(1,2,\ldots,n)$, we recover Gauss's identity. > > But because we have choices for $c$, we get $2N=rh$ in many ways.
###
Nonnesting Partitions
###
Nonnesting Reiner + Postnikov
- The
*nonnesting partitions*
of type $A_n$ are the antichains
(or order ideals/filters/etc.)
in the positive root poset $\Phi^+$.
###
Nonnesting Reiner + Postnikov
- The
*nonnesting partitions*
of type $W$ are the antichains
(or order ideals/filters/etc.)
in the positive root poset $\Phi^+$. > Called
**nonnesting**
because in type $A_{n-1}$, antichains correspond to collections of
**nonnesting**
arcs on $n$ vertices. - $\mathrm{NN}(W)$ is counted by the Catalan number $$\mathrm{Cat}(W)=\prod_{i=1}^r \frac{h+1+e_i}{d_i}.$$
###
Nonnesting Reiner + Postnikov
###
Nonnesting Reiner + Postnikov
> $$\begin{aligned}\mathrm{Cat}(A\_{n-1})&=\prod\limits\_{i=1}^{n-1} \frac{n+1+i}{i+1} = \frac{1}{n+1}\binom{2n}{n} = \mathrm{Cat}(n). \\\\ \mathrm{Cat}(B_n)&=\prod\limits_{i=1}^{n} \frac{2n+2i}{2i} = \binom{2n}{n}.\\\\ \mathrm{Cat}(F_4)&=105. \end{aligned}$$
###
Noncrossing Partitions
###
Noncrossing Reiner + Bessis
###
Noncrossing Reiner + Bessis
- Fix $c$ a Coxeter element of $W$. - The
*$c$-noncrossing*
partitions of type $W$ are collections of $r$ reflections in $\mathrm{inv}(\mathbf{c}^h)$ that product to $c$.
(Restricting to the first $\mathbf{w}_\circ(\mathbf{c})$ gives an element $\leq_T c$.)
> Called
**noncrossing**
because in type $A_n$, these can be drawn as collections of
**noncrossing**
blocks. - $\mathrm{NC}\_{c}(W)$ is counted by $\mathrm{Cat}(W)$.
###
Noncrossing Reiner + Bessis
- The
*$c$-noncrossing partitions*
of type $A_n$ are set partitions whose blocks are noncrossing when drawn on the cycle notation of $c$.
###
Nonnesting and Noncrossing Partitions
###
NN = NC ?
###
NN = NC ?
Last(?) open(?) problem in Coxeter-Catalan combinatorics (since ~1995): > Find a
**uniform**
bijection between $\mathrm{NN}(W)$ and $\mathrm{NC}\_c(W).$
###
Open?
###
NN = NC ?
|year|authors|type|result| |---|---|---|---| |???|everybody|type $A$| resolve crossings into nestings| |~1998|Athanasiadis|type $A$| bijections for specific $c$ (type)| |~2008|Fink, Giraldo|classical| bijections for specific $c$ (type)| |~2009|Stump, Ruby|classical| specific $c$ (openers-closers)| |~2011| Armstrong, Stump, Thomas| all types| inductive characterization for $c$ bipartite via support and rowmotion/the Panyushev map| |~2013| W| all types| (no proofs) conjectures for all $c$, checked by computer in low rank| |2023| DFISATW| type $A$| all $c$|
###
NN $\neq$ NC: Discrepencies
1. $\mathrm{NC}\_c(W)$ requires the choice of a Coxeter element; $\mathrm{NN}(W)$ does not. - This choice doesn't change the combinatorics of noncrossing partitions, since there is an easy bijection between $\mathrm{NC}\_c(W)$ and $\mathrm{NC}\_{scs}(W)$: $$\alpha\_{c,s} : \textcolor{purple}{\pi} \mapsto \textcolor{purple}{s\pi s}.$$
###
NN $\neq$ NC: Discrepencies
2. $\mathrm{NC}\_c(W)$ has the
*Kreweras complement*
(of order $2h$); $\mathrm{NN}(W)$... $$\mathrm{Krew}\_c : \textcolor{purple}{\pi} \mapsto \textcolor{green}{\pi^{-1}c}.$$
###
NN $\neq$ NC: Discrepencies
> These two maps on $\mathrm{NC}\_c(W)$ are compatible, in the sense that $$\alpha\_{c,s} \circ \mathrm{Krew}\_c = \mathrm{Krew}\_{scs} \circ \alpha\_{c,s}.$$
###
NN $\neq$ NC: Discrepencies
> So we want two maps on $\mathrm{NN}\_c(W)$ that are similarly compatible... $$\beta\_{c,s} \circ \mathrm{Krow}\_c = \mathrm{Krow}\_{scs} \circ \beta\_{c,s},$$
###
NN $\neq$ NC: Discrepencies
> ...and a bijection $\mathrm{Charm}_c$ between noncrossing and nonnesting partitions such that $$ \mathrm{Charm}\_c \circ \mathrm{Krew}\_c = \mathrm{Krow}\_c \circ \mathrm{Charm}\_c.$$
###
The K**row**eras complement
###
The K**row**eras complement
| NN/NC | discoverer | statement | | -------- | ------- | ------- | |$\mathrm{NC}_c(W)$ | ??? | The Kreweras complement has order $2h$| |$\mathrm{NN}(W)$ | Panyushev + AST | *Rowmotion* has order $2h$| |$\mathrm{NN}(S_n)$ | Striker and W + White | SW *promotion* has order $2n$| |$\mathrm{NC}_c(W)$ | Thomas and W | $\mathrm{Krew}_c$ can be computed by associahedron flips (*slow motion*) in $\mathrm{inv}(\mathbf{w}\_\circ(\mathbf{c}))$ order | | $\mathrm{NN}(n)$ | Thomas | SW *promotion* toggles in $\mathrm{inv}(\mathbf{w}_\circ(\mathbf{c}))$ order for $c=(1,2,3,\ldots,n)$| | $\mathrm{NN}(W)$ | Thomas and W | Toggling in $\mathrm{inv}(\mathbf{w}_\circ(\mathbf{c}))$ order *appears* to always have order $2h$ |
###
The K**row**eras complement
- The
*Kroweras complement*
toggles in $\mathrm{inv}(\mathbf{w}_\circ(\mathbf{c}))$ order.
###
The K**row**eras complement
- The
*Kroweras complement*
toggles in $\mathrm{inv}(\mathbf{w}_\circ(\mathbf{c}))$ order. - The bijection $\beta_{c,s}$ can be explicitly constructed in the
*toggle group*
. - So we'll concentrate on $\mathrm{Charm}_c$ today.
###
Charmed Bijections
###
Charmed bijections
###
$c$-Charmed roots
For $c = (\mathbf{1} \textcolor{#3498db}{< a_2 < \cdots < a_{m-1} <} \mathbf{n} \textcolor{#3498db}{> a_{m+1} > \cdots> a_n}),$ define $L_c = \\{\textcolor{#3498db}{a_2,\ldots,a_{m-1}}\\}$ and $R_c = \\{\textcolor{#3498db}{a_{m+1}, \ldots, a_n}\\}.$ > **Def.** A root $(i, j)$ is **$c$-charmed** if $\begin{cases} i \in L_c \\\ j \in R_c \end{cases}$ or $\begin{cases} i \in R_c \\\ j \in L_c\end{cases}.$
###
$c$-Charmed roots
###
$c$-Charmed bijections
> **Thm (DFISATW).** For any standard Coxeter element $c \in S_n$, there is a unique (support-preserving) bijection $$\mathrm{Charm}\_c: \mathrm{NC}_c(n) \to \mathrm{NN}(S_n)$$ satisfying $$ \mathrm{Charm}\_c \circ \mathrm{Krew}\_c = \mathrm{Krow}\_c \circ \mathrm{Charm}\_c.$$
###
$c$-Charmed bijections
###
$c$-Charmed bijections: Proof
###
THANK YOU
###
Questions
> -
Question
: What about other types? > > -
Answer
: Yes, this would be awesome! We do type $B$ by folding. > -
Question
: Explain again about the question mark on NN=NC? > > -
Answer
: No. (Come see me after.) > -
Question
: Are there applications of general charmed bijections? > > -
Answer
: I don't know.
### Thanks to
**all of you**
for making this another wonderful FPSAC!
### And thank you to the
**program and organizing committees**
for all their work behind the scenes!
### And, of course, to
**all**
the committees.
### Especially to
**Christian G., K., and S.**
### And let's please give a *very warm and extended* thank you to all the
**local organizers**
for making sure everything ran so smoothly this week! | | | | -------- | ------- | Ashleigh Adams | Kudret Bostanci Florian Buck | Nathan Chapelier Galen Dorpalen-Barry | Thomas Gerber Lorenzo Giordani | Lydia Gösmann Hy Khang Hoang | Elena Hoster Max Osterlitz | Timm Peerenboom Lars Rupieper | Annika Schulte Christian Stump | Laura Voggesberger Sven Wiesner | Mike Zabrocki