%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{82}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
%\usepackage{setpartitions}

\usepackage{cleveref}%[noabbrev,capitalise,nameinlink]

\usepackage[all]{xy}
%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{mathtools,tikz}
\usepackage{tkz-euclide}
\usetikzlibrary{arrows,calc} 
\tikzset{hidden/.style = {thick, dashed}}
\usepackage{mathdots,enumitem,xcolor}
%\usepackage{hyperref}
%\hypersetup{
%    colorlinks,
%    linkcolor={teal!50!black},
%    citecolor={teal!50!black},
%    urlcolor={teal!80!black}
%}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{algorithm}{Algorithm}
\newtheorem{problem}{Problem}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}
\newtheorem*{note}{Note}

\definecolor{forestgreen}{rgb}{0.0, 0.27, 0.13}
\newcommand{\gpoint}{\large{{\color{forestgreen}{\circ}}}}

\newcommand{\triang}[1]{
	\foreach \i in {1,...,#1}
	{
		\node at (\i,0) {\i};
	}
	\pgfmathtruncatemacro{\n}{#1 -1};
	\foreach \i in {1,...,\n}
	{
		\foreach \j in {1,...,\i}
		{
			\draw[fill=lightgray,thick] (1+ \i - 1/2*\j,1/2*\j) circle (2pt);
		}
	}
}

\newcommand{\pretriang}[1]{
	\pgfmathtruncatemacro{\n}{#1 -1};
	\foreach \i in {1,...,\n}
	{
		\foreach \j in {1,...,\i}
		{
			\draw[fill=lightgray,thick] ({0.5*(1+ \i - 1/2*\j)},1/4*\j) circle (2pt);
		}
	}
}


\newcommand{\Dyck}[2]{\draw[fill=blue] (#1,#2) circle (2pt);}

%

\newcommand{\marked}[2]{
	\node at (1/2*#1 + 1/2*#2,1/2*#2 - 1/2*#1) {\scalebox{1.3}{$\textcolor{red}{\varheartsuit}$}};
}

\newcommand{\filled}[2]{
	\draw[fill=gray] (1/4*#1 + 1/4*#2,1/4*#2 - 1/4*#1) circle (2.5pt);
}

\newcommand{\unfilled}[2]{
	\draw[fill=white] (1/4*#1 + 1/4*#2,1/4*#2 - 1/4*#1) circle (2.5pt);
}

\newcommand{\ctriang}{
\triang{9}
\marked{2}{3}
\marked{2}{4}
\marked{2}{7}
\marked{3}{5}
\marked{3}{6}
\marked{3}{8}
\marked{4}{5}
\marked{4}{6}
\marked{4}{8}
\marked{5}{7}
\marked{6}{7}
\marked{7}{8}
}

\newcommand{\cbot}{
\draw[ultra thick] (1.15,.15) -- (1.25,.25);
\draw[ultra thick] (3.15,.15) -- (3.25,.25);
\draw[ultra thick] (6.15,.15) -- (6.25,.25);
\draw[ultra thick] (5.85,.15) -- (5.75,.25);
\draw[ultra thick] (6.85,.15) -- (6.75,.25);
\draw[ultra thick] (7.85,.15) -- (7.75,.25);
}

\newcommand{\cptriang}{
\triang{9}
\marked{1}{2}
\marked{1}{5}
\marked{1}{7}
\marked{1}{8}
\marked{2}{3}
\marked{2}{4}
\marked{2}{6}
\marked{2}{9}
\marked{3}{5}
\marked{3}{7}
\marked{3}{8}
\marked{4}{5}
\marked{4}{7}
\marked{4}{8}
\marked{5}{6}
\marked{5}{9}
\marked{6}{7}
\marked{6}{8}
\marked{7}{9}
\marked{8}{9}
}


\usepackage{transparent}
\renewcommand{\S}{S}

\DeclareSymbolFont{extraup}{U}{zavm}{m}{n}
\DeclareMathSymbol{\varheartsuit}{\mathalpha}{extraup}{86}

\newcommand\precdot{\mathrel{\ooalign{$\prec$\cr
  \hidewidth\raise.25ex\hbox{$\scalebox{.6}{$\cdot$}\mkern0.5mu$}\cr}}}

\newcommand{\nc}{\pi}%
\newcommand{\nn}{p}%
\newcommand{\Kr}{\mathrm{Krew}}
\newcommand{\Cat}{\mathrm{Cat}}
\newcommand{\NC}{\mathrm{NC}}
\newcommand{\NN}{\mathrm{NN}}
\newcommand{\Abs}{\mathrm{Abs}}
\newcommand{\Weak}{\mathrm{Weak}}
\newcommand{\Camb}{\mathrm{Camb}}
\newcommand{\Roww}{\mathrm{Row}}
\newcommand{\Supp}{\mathrm{Supp}}
\renewcommand{\L}{\mathcal{L}}
\renewcommand{\a}{w}
\renewcommand{\r}{r}
\newcommand{\Out}{\mathrm{Out}}
\newcommand{\In}{\mathrm{In}}
\renewcommand{\sc}{\mathsf{c}}
\newcommand{\w}{\mathsf{w}}
\newcommand{\T}{\mathsf{T}}
\newcommand{\sT}{\mathsf{T}'}
\renewcommand{\t}{\mathrm{tog}}
\newcommand{\p}{P}
\newcommand{\tog}{\t}
\newcommand{\Bal}{\mathrm{Bal}}
\newcommand{\ARc}{\mathrm{AR}(c)}
\newcommand{\AR}{\mathrm{AR}}
\newcommand{\co}{c_1}
\newcommand{\rot}{\mathrm{rot}}
\newcommand{\row}{\mathrm{Row}}
\newcommand{\Charm}{\mathrm{Charm}}
\newcommand{\ARcp}{\mathrm{AR}(c')}
\newcommand{\nns}{x}
\newcommand{\QD}{Q_\Delta}
\newcommand{\Qc}{Q_c}
\newcommand{\inv}{\mathrm{inv}}
\newcommand{\tQc}{\widetilde{Q}_c}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Ext}{\operatorname{Ext}}
\newcommand{\M}{\varheartsuit}
\newcommand{\bigheart}{\scalebox{3.5}{\textcolor{red}{\heart}}}
\newcommand{\heart}{\ensuremath\varheartsuit}
\usepackage{scalerel,adjustbox}
\newcommand{\butt}{\rotatebox[origin=c]{180}{\heart}}
\newcommand{\lheart}{L}
\newcommand{\rheart}{R}

\DeclareMathOperator{\bijK}{\phi}
\DeclareMathOperator{\dyck}{\mathrm{Dyck}}
\DeclareMathOperator{\thicken}{\mathrm{Match}}
\DeclareMathOperator{\mrho}{\mathrm{Krow}} %
\DeclareMathOperator{\Krow}{\mrho}
\DeclareMathOperator{\Krew}{\Kr}

\newcommand{\orbsupp}{\mathrm{OrbitSupp}}

\definecolor{darkblue}{rgb}{0.0,0,0.7}
\newcommand{\darkblue}{\color{darkblue}}
\newcommand{\defn}[1]{\emph{\color{red!50!black} #1}}

\usepackage{tikz-cd} 
\usetikzlibrary{tikzmark}

\usepackage{verbatim}
\newif\ifshowtikz
\showtikztrue
%\showtikzfalse   % <---- comment/uncomment that line

\let\oldtikzpicture\tikzpicture
\let\oldendtikzpicture\endtikzpicture

\renewenvironment{tikzpicture}{%
    \ifshowtikz\expandafter\oldtikzpicture%
    \else\comment%   
    \fi
}{%
    \ifshowtikz\oldendtikzpicture%
    \else\endcomment%
    \fi
}



%\usepackage{lipsum}

%% define your title in the usual way
\title[Charmed roots and the Kroweras complement]{Charmed roots and the Kroweras complement}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%\author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}


\author[B.~Dequ\^ene, G.~Frieden, A.~Iraci, F.~Schreier-Aigner, H.~Thomas, and N.~Williams]{Benjamin Dequ\^ene\thanks{\href{mailto:dequene.benjamin@courrier.uqam.ca}{dequene.benjamin@courrier.uqam.ca}}\addressmark{1}, Gabriel Frieden\thanks{\href{mailto:gabefri@gmail.com}{gabefri@gmail.com}}\addressmark{2}, Alessandro Iraci\thanks{\href{mailto:alessandro.iraci@unipi.it}{alessandro.iraci@unipi.it}}\addressmark{3}, Florian Schreier-Aigner\thanks{\href{mailto:florian.schreier-aigner@univie.ac.at}{florian.schreier-aigner@univie.ac.at}}\addressmark{4}, Hugh Thomas\thanks{\href{mailto:thomas.hugh\_r@uqam.ca}{thomas.hugh\_r@uqam.ca}}\addressmark{1}, \and Nathan Williams\thanks{\href{mailto:nathan.f.williams@gmail.com}{nathan.f.williams@gmail.com}}\addressmark{5}}


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}D\'epartement de math\'ematiques, LaCIM, Universit\'e du Qu\'ebec \`a Montr\'eal \\ \addressmark{2}McGill University, Montr\'eal, Canada \\ \addressmark{3}Universit\`a di Pisa, Italy \\ \addressmark{4}University of Vienna, Austria \\ \addressmark{5}The University of Texas at Dallas}

%\addressmark{5}D\'epartement de math\'ematiques, Universit\'e du Qu\'ebec \`a Montr\'eal\\
%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Although both noncrossing partitions and nonnesting partitions are uniformly enumerated for Weyl groups, the exact relationship between these two sets of combinatorial objects remains frustratingly mysterious.  In this abstract, we give a precise combinatorial answer in the case of the symmetric group using a new definition of \emph{charmed roots}.}%: for any standard Coxeter element, we construct an equivariant bijection between noncrossing partitions under the \emph{Kreweras complement} and nonnesting partitions under a Coxeter-theoretically natural cyclic action we call the \emph{Kroweras complement}.  Our equivariant bijection is the unique bijection that is both equivariant and support-preserving, and is built using local rules depending on a new definition of \emph{charmed roots}.  Charmed roots are determined by the choice of Coxeter element---in the special case of the linear Coxeter element $(1,2,\ldots,n)$, we recover one of the standard bijections between noncrossing and nonnesting partitions.}

%% put your French abstract here, or comment this out if you don't have one
\resume{Les partitions non-crois\'ees et les partitions non-embo\^it\'ees soient uniform\'ement \'enum\'er\'ees pour les groupes de Weyl, la relation exacte entre ces deux ensembles d'objets combinatoires reste frustrante. Dans cet abstrait, nous donnons une r\'eponse combinatoire pr\'ecise dans le cas du groupe sym\'etrique en utilisant une nouvelle d\'efinition de \emph{racines charm\'ees}.}% : pour tout \'el\'ement de Coxeter standard, nous construisons une bijection \'equivariante entre les partitions non-crois\'ees sous le \emph{compl\'ement de Kreweras} et les partitions non-embo\^it\'ees sous une action cyclique naturelle de Coxeter que nous appelons le \emph{compl\'ement de Kroweras}. Notre bijection \'equivariante est la bijection unique qui soit \`a la fois \'equivariante et qui pr\'eserve le support, et elle est construite \'`a l'aide de r\`egles locales d\'e\'ependant d'une nouvelle d\'efinition des \emph{racines charm\'ees}. Les racines charm\'ees sont d\'e\'etermin\'ees par le choix de l'\'el\'ement de Coxeter --- dans le cas particulier de l'\'el\'ement de Coxeter lin\'eaire $(1,2,\ldots,n)$, nous retrouvons l'une des bijections standard entre les partitions non-crois\'ees et on-embo\^it\'ees.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Catalan combinatorics, noncrossing, nonnesting, Kreweras complement}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle


%\section{Introduction}
%\label{sec:intro}

\section{Introduction}
%This is an extended abstract of the paper~\cite{dequene2022charmed}.
\subsection{Noncrossing and nonnesting partitions}
Let $W \subseteq \mathrm{GL}(V)$ be a finite complex reflection group acting in its reflection representation on a complex vector space $V$ of dimension $\r$ with reflections $T$~\cite{Humphreys1990,lehrer2009unitary}.  Our results will mostly concern the symmetric group $W=\S_n$, where the set of reflections is the set of all transpositions $(i,j)$.  The ring of $W$-invariants $\mathbb{C}[V]^W$ is a polynomial ring generated by invariants of degrees $d_1\leq d_2 \leq \cdots \leq d_\r$.  The \defn{Coxeter number} of a well-generated $W$ (that is, $W$ is generated by $r$ reflections) is $h=d_\r$ and the \defn{$W$-Catalan number} is

\begin{equation}
	\label{eq:catalan}
	\mathrm{Cat}(W) \coloneqq \prod_{i=1}^\r \frac{h+d_i}{d_i}.
\end{equation}

The \defn{$c$-noncrossing partition lattice} $\NC(W,c)$ is the interval $[e,c]_T$ in the absolute order.  
  For $\S_n$, the absolute length of a permutation $w \in \S_{n}$ is $n$ minus the number of cycles of $w$; the cycles of $w \in \NC(W,c)$ are the blocks of a noncrossing partition.  Until very recently, the number of noncrossing partitions had only been computed case-by-case; a uniform proof was found in the case of real $W$ in~\cite{galashin2022rational}.  For $W$ a well-generated finite complex reflection group with Coxeter element $c$, $|\NC(W,c)| = \mathrm{Cat}(W)$.
 
Let now $W$ be a Weyl group (a crystallographic real reflection group), with positive roots $\Phi^+$.  In this abstract, we will systematically replace positive roots by their corresponding reflections.  The positive root poset is the partial order on $\Phi^+$ defined by $\alpha \leq \beta$ iff $\beta-\alpha$ is a nonnegative sum of positive roots; for $\S_n$, $\Phi^+$ is the partial order defined on the transpositions $(i,j)$ with covering relations $(i+1,j) \lessdot (i,j) \lessdot (i,j+1)$ (see~\Cref{fig: root poset} for an example).  %The minimal elements of $\Phi^+$ are the \defn{simple roots} $\alpha_i$ for $1 \leq i < n$, which we also denote by $(i,i+1)$.
The \defn{nonnesting partitions} $\NN(W)$ are the order ideals in the positive root poset~\cite[Remark 2]{reiner1997non}.  There are uniform proofs that $|\NN(W)| = \Cat(W)$.
%---this was proven uniformly by combining a bijection of Cellini and Papi~\cite[Theorem 1]{cellini2002ad} with an argument of Haiman~\cite[Theorem 7.4.2]{haiman1994conjectures} and an observation of Thiel~\cite[Lemma 8.2]{thiel2016anderson}.

Despite the fact that they are both counted by $\mathrm{Cat}(W)$, there are at least two Incongruities between $\NC(W,c)$ and $\NN(W)$:

\begin{enumerate}
	\item $\NC(W,c)$ is defined for well-generated complex reflection groups, while $\NN(W)$ is only defined for Weyl groups;
	      \item\label{it:2} the definition of $\NC(W,c)$ requires the choice of a Coxeter element, while $\NN(W)$ has no such dependence;
	      %
%	      \item\label{it:3} When $c$ is a \defn{standard Coxeter element} in a real reflection group---that is, when $c$ is a product of the simple reflections in some order---and $s$ is initial in $c$, the map $w \mapsto s^{-1} w s$ gives a bijection $\NC(W,c) \simeq \NC(W,s^{-1}cs)$ and leads to the \emph{Kreweras complement} and the \emph{Cambrian recurrence} for real $W$, while there is no obvious similar action of the initial $s$ on $\NN(W)$.%\footnote{Outside of this introduction, we will always assume that $c$ is a standard Coxeter element.}
\end{enumerate}
%Two additional Incongruities have only been very recently resolved in~\cite{galashin2022rational}:
%\begin{enumerate}[resume]
%	\item\label{it:4} $\NC(W,c)$ had only \emph{Fuss--Catalan} and \emph{Fuss--Dogolon} generalizations, while $\NN(W)$ was easily generalized to rational parameters $p$ coprime to the Coxeter number $h$; %
%	\item the enumeration of $\NC(W,c)$ was only case-by-case, while the enumeration of $\NN(W)$ was uniform.
%\end{enumerate}
%
The exact relationship between noncrossing and nonnesting partitions remains frustratingly mysterious, and finding a uniform ``natural'' bijection is perhaps the biggest open question in Coxeter--Catalan combinatorics.  To our taste, there are two approaches to this problem: the first approach is based on the case-by-case combinatorial models available in the classical types $A,B,D$~\cite{giraldo2009bijections,stump2010crossings,conflitti2011noncrossing,kim2011new,stump2008non,athanasiadis1998noncrossing}; the second approach was pioneered in~\cite{armstrong2013uniform} based on observations in~\cite{panyushev2009orbits,BessisReiner2011}, and uses a mysterious coincidence of two cyclic actions to induce a bijection.  Our main theorem refines both of these approaches in the special case of the symmetric group $\S_n$.  %We discuss these actions now.

%\begin{problem}
%\label{prob:main_question}
%Fix $W$ a finite Weyl group and $c$ a Coxeter element.  Find a ``natural'' bijection between $\NC(W,c)$ and $\NN(W)$.
%\end{problem}

%Historically---if one interprets ``natural'' as meaning ``uniform''---finding such a bijection was viewed as a promising way to give a uniform proof that $|\NC(W,c)|=\Cat(W)$.


%, recovering one of the standard bijections between noncrossing and nonnesting partitions in the case of the linear Coxeter element $(1,2,\ldots,n)$.

\subsection{Cyclic actions}
For $W$ a well-generated complex reflection group and $c$ a Coxeter element, the \defn{$c$-Kreweras complement} on the noncrossing partition lattice is the anti-automorphism of $\NC(W,c)$ defined by $\Kr_c(\nc) = \nc^{-1}c$~\cite[Section 4.2]{Armstrong2009}, \cite{kreweras1972partitions}.  Since $\Kr_c^2(\nc) = c^{-1} \nc c$ and $c$ has order $h$, $\Kr_c$ has order $h$ if $-1 \in W$, and $2h$ otherwise.

For $W$ a Weyl group, \defn{rowmotion} on nonnesting partitions is the map $\Roww(\nn)= \min_{\Phi^+} \{\alpha \mid \alpha \not \leq \beta \text{ for any } \beta \in \nn\}$.  Panyushev conjectured that the order of $\Roww$ on $\NN(W)$ was $h$ if $-1 \in W$ and $2h$ otherwise~\cite{panyushev2009orbits}, and Bessis and Reiner refined Panyushev's conjecture by observing that $\Roww$ had the same orbit structure on $\NN(W)$ as $\Kr$ on $\NC(W,c)$~\cite{BessisReiner2011}.  This was proven by Armstrong, Stump, and Thomas~\cite{armstrong2013uniform}.%

But Incongruity~\eqref{it:2} remains---while the definitions of $\NC(W,c)$ and $\Kr_c$ depend on the choice of a Coxeter element, the set $\NN(W)$ and its action $\Roww$ do not depend on any such choice.   We address this lack of dependence on the Coxeter element $c$ by modifying the definition of $\Roww$~\cite{williams2013cataland,williams2014bijactions}.  It is well-known that rowmotion can be written as a sequence of local moves as follows~\cite{cameron1995orbits,striker2012promotion}.  A \emph{toggle} $\t_\alpha(\nn)$ of a nonnesting partition $\nn$ at a positive root $\alpha$ either adds $\alpha$ to $\nn$ (when $\alpha \not \in \nn$) or removes $\alpha$ from $\nn$ (when $\alpha \in \nn$), provided that the result is again a nonnesting partition.   For nonnesting partitions, $\row$ can be computed by toggling each root of the root poset in order of height (or by \emph{row}).  It is natural to modify the order of these toggles.

For $c$ a standard Coxeter element and $\sc$ a particular choice of reduced word for $c$, the \defn{$c$-sorting word} for the long element $w_\circ$ is the leftmost reduced word in simple reflections for $w_\circ$ in $\sc^\infty$.  Write $\w_\circ(\sc)=[r_1,r_2,\ldots,r_N]$, with each $r_i \in S$ and define the inversion sequence $\inv(\w_\circ(\sc))=[t_1,t_2,\ldots,t_N]$, where $t_a \coloneqq (r_{1} r_{2} \cdots r_{a-1}) r_a (r_{1} r_{2} \cdots r_{a-1})^{-1}.$  Then $\inv(\w_\circ(\sc))$ totally orders the reflections of $W$.

%We are now in a position to address Incongruity~\eqref{it:2}~\cite{williams2013cataland,williams2014bijactions}: in contrast to the $c$-Kreweras complement, $\row$ has no dependence on the Coxeter element $c$.
We can now address Incongruity~\eqref{it:2} by defining a modification of rowmotion to accomodate a Coxeter element $c$:
\begin{align}\label{eq:krow} \Krow_c: \NN(W) &\to \NN(W) \\ \nonumber \nn &\mapsto \left(\t_{t_{N}}\circ\cdots\circ\t_{t_{2}}\circ\t_{t_{1}}\right)(\nn).\end{align}
We call this map the \defn{$c$-Kroweras complement}.









%Write $[n] \coloneqq \{1,2,\ldots,n\}$; we work modulo $n$ so that for $0< i<n$, we may write $-i$ for $n-i$ and $n+1$ for $1$.

%We construct a novel bijection between $c$-noncrossing partitions and nonnesting partitions for the symmetric group $\S_n$ using the combinatorics of certain kissing families of lattice paths whose local behavior is dependent on a novel definition of \emph{$c$-charmed roots}.  

\subsection{Main Theorem}
Our main theorem uses the $c$-Kreweras and $c$-Kroweras complements to relate noncrossing and nonnesting partitions.  Recall that the \defn{support} of a noncrossing partition $\nc \in \NC(W,c)$ is the set $\Supp(\nc)$ of simple reflections required to write a reduced word in simple reflections for $\nc$; similarly, the \emph{support} of a nonnesting partition $\nn \in \NN(W)$ is the set $\Supp(\nn)$ of simple roots that lie in $\nn$ (as an order ideal of $\Phi^+$).
\begin{theorem}
	\label{thm:main_theorem}
	Let $\S_n$ be the symmetric group, and fix a standard Coxeter element $c \in \S_n$. Then there is a unique bijection $\Charm_c \colon \NC(\S_n,c) \to \NN(\S_n)$ satisfying
	%\begin{itemize}
		$\Charm_c \circ \Krew_c = \Krow_c \circ \; \Charm_c$ and
		 $\Supp = \Supp \circ \Charm_c$.
	%\end{itemize}
\end{theorem}

%It is easy to directly read the blocks of the noncrossing partition from the corresponding intimate family.
%We prove \Cref{thm:main_theorem} using \defn{Cambrian induction}, relying on the facts that (1) $\Charm_{\co}$ recovers a standard bijection for the linear Coxeter element $\co = s_1s_2 \cdots s_{n-1} = (1,2,\ldots,n)$, and (2) all standard  Coxeter elements are conjugate by a sequence of conjugations by initial simple reflections.  %Our proof strategy is summarized in~\Cref{ex:running_example}.


%---that is, we will show
%\begin{itemize}
%	\item the \emph{base case}: the theorem holds for the linear Coxeter element $\co = s_1s_2 \cdots s_{n-1}$.  In this case, $\Krow_{\co}$ is order ideal promotion, as defined by Striker and Williams \cite{striker2012promotion}, and $\Charm_{\co}$ recovers a standard bijection; and
%	\item the \emph{inductive step}: suppose \Cref{thm:main_theorem} holds for $c$.  We argue that if $s$ is initial in $c$ and $c'=scs$, then \Cref{thm:main_theorem} also holds for $c'$---we understand how $\Charm_{c'}$ differs from $\Charm_{c}$ using the relation between the set of $c$-charmed and $c'$-charmed roots in~\Cref{prop:c_charmed}.
%\end{itemize}
%Since all standard Coxeter elements are conjugate by a sequence of conjugations by initial simple reflections, the theorem, therefore, holds for all standard Coxeter elements.  

In particular, for any standard Coxeter element $c \in \S_n$, the order of $\Krow_c$ on $\NN(W)$ is $2h$.  	The statement of the main theorem in Armstrong-Stump-Thomas~\cite{armstrong2013uniform} can be obtained from the statement of our~\Cref{thm:main_theorem} by replacing $\Krow_c$ by $\row$, and replacing the symmetric group by any finite Weyl group; the main difference from the result in~\cite{armstrong2013uniform} is that we resolve Incongruity~\eqref{it:2}, constructing truly different bijections between noncrossing and nonnesting partitions for each Coxeter element.

%A priori, there is no reason for an arbitrary product of toggles to have well-behaved order.  As a consequence of~\Cref{thm:main_theorem}, we have the following surprising result.
%\begin{corollary}
%	For any standard Coxeter element $c \in \S_n$, the order of $\Krow_c$ on $\NN(W)$ is $2h$.
%\end{corollary}

%\begin{remark}
%	The statement of the main theorem in Armstrong-Stump-Thomas~\cite{armstrong2013uniform} can be obtained from the statement of our~\Cref{thm:main_theorem} by replacing $\Krow_c$ by $\row$, and replacing the symmetric group by any finite Weyl group. In particular, in the result from~\cite{armstrong2013uniform}, only one toggle sequence is ever employed in the poset of positive roots.   Thus, our main theorem is much richer than the~\cite{armstrong2013uniform} result (when restricted to the symmetric group) because we consider a different toggle sequence for each standard Coxeter element.  Indeed, the fact that the Coxeter element only plays a role on the noncrossing side of the bijection means that in~\cite{armstrong2013uniform}, it is sufficient to consider one preferred Coxeter element (a \emph{bipartite} Coxeter element), and find one corresponding bijection---whereas here we construct truly different bijections for each Coxeter element.
%\end{remark}



%\section{The Kroweras complement}%

%\subsection{Armstrong-Stump-Thomas}
%For $W$ a well-generated complex reflection group, we define  Since $\Kr_c^2(\nc) = c^{-1} \nc c$ and $c$ has order $h$, $\Kr_c$ has order $h$ if $-1 \in W$, and $2h$ otherwise.%

%For $W$ a Weyl group, \defn{rowmotion} on nonnesting partitions is the map \begin{align}\label{eq:row} \Roww: \NN(W) &\to \NN(W) \\ \nonumber \nn &\mapsto \min_{\Phi^+} \{\alpha \mid \alpha \not \leq \beta \text{ for any } \beta \in \nn\}.\end{align} Panyushev conjectured that the order of $\Roww$ on $\NN(W)$ was $h$ if $-1 \in W$ and $2h$ otherwise~\cite{panyushev2009orbits}, and Bessis and Reiner refined Panyushev's conjecture by observing that $\Roww$ had the same orbit structure on $\NN(W)$ as $\Kr$ on $\NC(W,c)$~\cite{BessisReiner2011}.  This conjecture was proven by Armstrong, Stump, and Thomas, using a uniformly-stated---but only case-by-case verified---inductive bijection between nonnesting and noncrossing partitions~\cite{armstrong2013uniform}.%

%Thus, partitioning the sets $\NC(W,c)$ and $\NN(W)$ into orbits under $\Kr_c$ and $\Roww$ refines the problem of finding a ``natural'' bijection.  But Incongruity~\eqref{it:2} remains---while the definitions of $\NC(W,c)$ and $\Kr_c$ depend on the choice of a Coxeter element, the set $\NN(W)$ and its action $\Roww$ do not depend on any such choice.

%\subsection{Flips and the Kreweras Complement on Noncrossing Partitions}
%Let $W$ be a finite Coxeter group. For $c$ a standard Coxeter element and $\sc$ a particular choice of reduced word for $c$, the \defn{$c$-sorting word} $\w(\sc)$ for $w \in W$ is the leftmost reduced word in simple reflections for $w$ in $\sc^\infty$.  An element is \defn{$c$-sortable} if its $c$-sorting word uses a weakly decreasing subset of simple reflections in each successive copy of $\sc$.  The \defn{weak order} is the poset given by the Cayley graph of $W$ generated by $S$, with the longest element $w_\circ$.  The restriction of the weak order to the $c$-sortable elements is Nathan Reading's $c$-Cambrian lattice, with edges labeled by roots.  The inversion sequence $\inv(\w_\circ(\sc))=[\alpha^{(1)},\alpha^{(2)},\ldots,\alpha^{(N)}]$ gives total ordering on the set of roots of $W$.% (see~\Cref{sec:sort_ar} for more details on this ordering).

%In~\cite{thomas2019rowmotion}, a subset of the authors showed that it is possible to compute the $c$-Kreweras complement in ``slow motion'' as a sequence of local \emph{flips} on the edges of the $c$-Cambrian lattice in $\inv(\w_\circ(\sc))$ order.

%\begin{theorem}[{\cite[Theorem 1.2]{thomas2019rowmotion}}] %\label{thm:slow}
%	For $W$ a real reflection group, $\Kr_c(\nc)$ can be computed as a sequence of flips on $\Camb(W,c)$.
%\end{theorem}

%\subsection{Toggles and the Kroweras Complement on Nonnesting Partitions}


\section{Coxeter elements and charmed roots}
% The \defn{support} of an element $w \in W$ is the set of simple reflections below $w$ in absolute order: \[\Supp(w) = \{s \in S \mid s \leq_T w\}.\]

%\subsection{Roots}
%Let $\{e_i\}_{i=1}^n$ be the standard basis of $\mathbb{R}^n$.  The \defn{positive roots} of type $A_{n-1}$ are the following normal vectors to the reflecting hyperplanes in the braid arrangement \begin{equation}\label{eq:roots}
%	\alpha_{i,j} \coloneqq e_j-e_i \text{ with } 1 \leq i < j \leq n.
%\end{equation}

%To reduce subscripts, we denote $\alpha_{i,j}$ by its corresponding reflection $(i,j) \in S_n$.  The \defn{root poset} of type $A_{n-1}$ is the poset $\Phi^+ \coloneqq \Phi^+(A_{n-1})$ defined on the positive roots with covering relations $(i+1,j) \lessdot (i,j) \lessdot (i,j+1)$.  The minimal elements of $\Phi^+$ are the \defn{simple roots} $\alpha_i$ for $1 \leq i < n$, which we also denote by $(i,i+1)$.  The \defn{support} of a root $(i,j)$ is the set of simple roots $\Supp(i,j)$ less than $(i,j)$ in the root poset.  The root poset of type $A_8$ is illustrated in~\Cref{fig: root poset}.%


\begin{comment}
\begin{figure}[htbp]
	\begin{center}
		\begin{tikzpicture}[scale=.95]
			\pgfmathtruncatemacro{\n}{9};
			\pgfmathtruncatemacro{\none}{\n-1};
			\pgfmathtruncatemacro{\ntwo}{\n-2};
			\pgfmathtruncatemacro{\nthree}{\n-3};
			\foreach \yy in {0,...,\ntwo}{
					\pgfmathtruncatemacro{\y}{\none-\yy};
					\foreach \x in {1,...,\y}{
							\pgfmathtruncatemacro{\i}{2*\x+\yy};
							\pgfmathtruncatemacro{\j}{\yy};
							\pgfmathtruncatemacro{\k}{\x+\yy+1};
							\node (\x\k) at (\i,\j) {$(\x\k)$};
						};
				};
			\foreach \yy in {0,...,\nthree}{
					\pgfmathtruncatemacro{\y}{\ntwo-\yy};
					\foreach \x in {1,...,\y}{
							\pgfmathtruncatemacro{\i}{2*\x+\yy};
							\pgfmathtruncatemacro{\j}{\yy};
							\pgfmathtruncatemacro{\k}{\x+\yy+1};
							\pgfmathtruncatemacro{\xone}{\x+1};
							\pgfmathtruncatemacro{\xmone}{\x-2};
							\pgfmathtruncatemacro{\kone}{\k+1};
							\draw (\x\k) -- (\x\kone);
							\draw (\xone\kone) -- (\x\kone);
						};
				};
			\foreach \i in {3,4,7}{
					\foreach \j in {2,5,6,8}{
							\pgfmathtruncatemacro{\x}{min(\i,\j)};
							\pgfmathtruncatemacro{\y}{max(\i,\j)};
							\draw (\x\y) node[opacity=0.5,yshift=-.3em] {\bigheart};
						};
				};
		\end{tikzpicture}
	\end{center}
	\caption{\label{fig: root poset} The Hasse diagram of the positive root poset $\Phi^+$ of type $A_8$.  The label $(ij)$ represents the positive root $e_j - e_i$.  For $c=s_2s_1s_3s_6s_5s_4s_8s_7$, the $c$-charmed roots from~\Cref{def:charmed} are marked using hearts.}
\end{figure}
\end{comment}

%\subsection{Coxeter elements}
%\label{sec:coxeter_els}

%When $c$ is a standard Coxeter element of $\S_n$, $c$ consists of a single cycle $(\a_1,\a_2, \ldots, \a_m,\a_{m+1} \dots, \a_n)$ with an initial increasing subsequence $1 = \a_1 < \a_2 < \dots < \a_m = n$, followed by a decreasing sequence $n = \a_m > \a_{m+1} > \dots > \a_n$ of the remaining unused entries.  We say that the reflection $(\a_i,\a_j)$ is \defn{$c$-charmed} if $1 < i < m$ and $m < j \leq n$, and \defn{$c$-ordinary} otherwise.

%Our bijection is the unique equivariant support-preserving bijection between $\NC(W,c)$ under the $c$-Kreweras complement and $\NN(W)$ under the $c$-Kroweras complement, and is based on \emph{intimate families} of lattice paths (see \Cref{sec:intimate}).


%\begin{definition}
%	\label{def:coxeter_element}
%	A \defn{(standard) Coxeter element} $c$ is a product of the simple reflections in any order.
%\end{definition}
  %We will drop the word ``standard'' when talking about standard Coxeter elements, as we only use standard Coxeter elements in this paper.

Recall that a \defn{(standard) Coxeter element} $c$ is a product of the simple reflections in any order.  
To ease notation, we reserve the symbols $r_i$ to refer to a fixed ordering $\sc \coloneqq [r_1,r_2,\ldots,r_{n-1}]$ of $S$ and define $c \coloneqq r_1 r_2 \cdots r_{n-1}$.  We also reserve the symbol $s_k = r_1$ for the first simple reflection in the chosen reduced word, and write $c' = r_2 \cdots r_{n-1} r_1$.

%We say that a simple reflection $s$ is \defn{initial} in $c$ if $\ell_S(s c) \leq \ell_S(c)$, and that a simple reflection $s$ is \defn{final} in $c$ if $\ell_S(c s) \leq \ell_S(c)$.   If $s=s_k=(k,k+1)$ is initial in $c$, then $c' = scs$ is also a Coxeter element of $\S_n$, and we will denote this by the writing $c \xrightarrow{k} c'$.  It is a basic fact for finite Coxeter groups---relying only on the fact that the underlying Dynkin diagram is a tree---that all standard Coxeter elements are conjugate~\cite[Section 3.16]{Humphreys1990}.  In fact, they are conjugate by a sequence of conjugations by initial simple reflections~\cite[Lemma 1.7]{reading2007clusters}: \[c=c^{(0)} \xrightarrow{k_1} c^{(1)} \xrightarrow{k_2} c^{(2)} \xrightarrow{k_3} \cdots \xrightarrow{k_m} c^{(m)} = c'.\]  

%\begin{lemma}[{\cite[Lemma 1.7]{reading2007clusters}}]\label{lem:initial_conj}
%	Let $c$ and $c'$ be two Coxeter elements of a finite Coxeter group $W$.  Then $c$ and $c'$ are conjugate by a sequence of conjugations by initial simple reflections: \[c=c^{(0)} \xrightarrow{k_1} c^{(1)} \xrightarrow{k_2} c^{(2)} \xrightarrow{k_3} \cdots \xrightarrow{k_m} c^{(m)} = c'.\]
%\end{lemma}

%In $\S_n$ and for $1 \leq k < n$, we write $c_k$ for the Coxeter element with $s_k$ as its unique initial simple reflection---that is, $c_k=s_k s_{k+1}\cdots s_{n-1} s_{k-1}s_{k-2} \cdots s_1$.  As a special case, the \defn{linear Coxeter element} $c_1=s_1 s_2\cdots s_{n-1}$ has cycle notation $(1,2,\ldots,n)$.

%\subsection{Charmed Roots}
It is easy to show that the cycle notation of any Coxeter element in the symmetric group has a particularly simple form: $c \in \S_n$ consists of a single cycle with an initial increasing subsequence starting at $1$ and ending at $n$, followed by a decreasing sequence of the remaining unused entries.
Let $c$ be a Coxeter element with cycle notation $(\a_1,\a_2, \ldots, \a_m,\a_{m+1} \dots, \a_n)$, where $1 = \a_1 < \a_2 < \dots < \a_m = n$ and $n = \a_m > \a_{m+1} > \dots > \a_n>\a_1=1$.
Write \begin{align*}
	\lheart_c \coloneqq \{\a_2,\ldots,\a_{m-1}\} \text{  and  }
	\rheart_c \coloneqq \{\a_{m+1},\ldots,\a_n\}.
\end{align*}
%

%\begin{proposition}
%	An element $w \in \S_n$ is a Coxeter element if and only if it has cycle notation \[w = (\a_1,\a_2, \ldots, \a_m,\a_{m+1} \dots, w_n),\] where $1 = \a_1 < \a_2 < \dots < \a_m = n$ and $n = \a_i > \a_{m+1} > \dots > \a_n>\a_1=1$.
%\end{proposition}


\begin{definition}
	\label{def:charmed}
	For $1<i<j<n$, we say that a root $(i,j)$ is \defn{$c$-charmed} if $i \in \lheart_c$ and $j \in \rheart_c$ or if $i \in \rheart_c$ and $j \in \lheart_c$ and \defn{$c$-ordinary} otherwise.  We write $\heart_c$ for the set of $c$-charmed roots.
\end{definition}

In figures, we depict $c$-charmed roots with a $\textcolor{red}{\heart}$ and ordinary roots by a circle.  The root poset of type $A_8$ is illustrated in~\Cref{fig: root poset}.%

\begin{figure}[htbp]
	\begin{center}
 \scalebox{.6}{
		\begin{tikzpicture}[scale=.95]
			\pgfmathtruncatemacro{\n}{9};
			\pgfmathtruncatemacro{\none}{\n-1};
			\pgfmathtruncatemacro{\ntwo}{\n-2};
			\pgfmathtruncatemacro{\nthree}{\n-3};
			\foreach \yy in {0,...,\ntwo}{
					\pgfmathtruncatemacro{\y}{\none-\yy};
					\foreach \x in {1,...,\y}{
							\pgfmathtruncatemacro{\i}{2*\x+\yy};
							\pgfmathtruncatemacro{\j}{\yy};
							\pgfmathtruncatemacro{\k}{\x+\yy+1};
							\node (\x\k) at (\i,\j) {$(\x\k)$};
						};
				};
			\foreach \yy in {0,...,\nthree}{
					\pgfmathtruncatemacro{\y}{\ntwo-\yy};
					\foreach \x in {1,...,\y}{
							\pgfmathtruncatemacro{\i}{2*\x+\yy};
							\pgfmathtruncatemacro{\j}{\yy};
							\pgfmathtruncatemacro{\k}{\x+\yy+1};
							\pgfmathtruncatemacro{\xone}{\x+1};
							\pgfmathtruncatemacro{\xmone}{\x-2};
							\pgfmathtruncatemacro{\kone}{\k+1};
							\draw (\x\k) -- (\x\kone);
							\draw (\xone\kone) -- (\x\kone);
						};
				};
			\foreach \i in {3,4,7}{
					\foreach \j in {2,5,6,8}{
							\pgfmathtruncatemacro{\x}{min(\i,\j)};
							\pgfmathtruncatemacro{\y}{max(\i,\j)};
							\draw (\x\y) node[opacity=0.5,yshift=-.3em] {\bigheart};
						};
				};
		\end{tikzpicture}}
	\end{center}
	\caption{\label{fig: root poset} The Hasse diagram of the positive root poset $\Phi^+$ of type $A_8$.  For $c=s_2s_1s_3s_6s_5s_4s_8s_7$, the $c$-charmed roots from~\Cref{def:charmed} are marked using hearts.}
\end{figure}

\begin{example}
	\label{ex:1}
	Consider the Coxeter element $c=s_2s_1s_3s_6s_5s_4s_8s_7$ in $\S_9$.  The element $c$ has cycle notation $(1,3,4,7,9,8,6,5,2)$, so that \[\lheart_c = \{3,4,7\} \text{ and } \rheart_c = \{8,6,5,2\}.\]
\end{example}


%As a special case, a simple root $(i,i+1)$ for $1<i<n-1$ is $c$-charmed if and only if it is initial or final in $c$; more precisely, $(i,i+1)$ is initial when $i+1 \in \lheart_c$ and $i \in \rheart_c$, and $(i,i+1)$ is final when $i \in \lheart_c$ and $i+1 \in \rheart_c$.  

We visualize the cycle notation of $c$ by drawing it as points labeled $w_1,w_2,\ldots,w_n$ %
counter-clockwise around a circle.  We visualize a root $(i,j)$ by connecting the vertices labeled $i$ and $j$ by a line segment.  For any $a,b,c,d \in [n]$, we say that $(a,b)$ \defn{crosses} $(c,d)$ if and only if $(a,b)$ and $(c,d)$ are crossing in their interior (note that $(a,b)$ does not cross itself).  For $1<i<j<n$, it is easy to check that a root $(i,j)$ is $c$-charmed if and only if $(i,j)$ crosses $(i-1,j+1)$.   \Cref{fig:c_visualization} illustrates this visualization.


%For $s=s_k=(k,k+1)$, conjugating $c$ by $s$ interchanges the positions of $k$ and $k+1$ in the cycle notation of $c$.  When $s$ is initial in $c$, then $c'=scs$ is again a Coxeter element and we recall that we write this using the notation $c \xrightarrow{k} c'$.  We obtain the following relationship between $c$-charmed roots and $c'$-charmed roots.

%\begin{proposition}
%	\label{prop:c_charmed}
%	Let $c \xrightarrow{k} c'$.  Then for $1<i<j<n$,
%	\[ (i,j) \text{ is $c$-charmed if and only if it is }
%		\begin{cases}
%			\text{$c'$-charmed}  & \text{and } |\{i,j\} \cap \{k,k+1\}| = 0 \mod 2,  \\
%			\text{$c'$-ordinary} & \text{ and } |\{i,j\} \cap \{k,k+1\}| = 1 \mod 2.
%		\end{cases}
%	\]
%\end{proposition}


	\begin{figure}[htbp]
 \begin{center}
		\begin{tikzpicture}
			\def\c{{1,3,4,7,9,8,6,5,2}};
			\pgfmathtruncatemacro{\n}{dim(\c)};
			\pgfmathtruncatemacro{\no}{\n-1};
			\draw (0,0) circle (1cm);
			\foreach \i in {0,...,\no}{
					\pgfmathtruncatemacro{\j}{\c[\i]};
					\node (\j) at ({cos(360*\i/\n)},{sin(360*\i/\n)}){};
					\filldraw[red] (\j) circle (1.5pt);
					\node (p\j) at ({1.2*cos(360*\i/\n)},{1.2*sin(360*\i/\n)}){\j};
				};
			\draw[red, thick, fill=red!40!white] (6.center) -- (7.center);
			\draw[black, dashed, fill=red!40!white] (5.center) -- (8.center);
		\end{tikzpicture}\hspace{2em}
		\begin{tikzpicture}
			\def\c{{1,3,4,7,9,8,6,5,2}};
			\pgfmathtruncatemacro{\n}{dim(\c)};
			\pgfmathtruncatemacro{\no}{\n-1};
			\draw (0,0) circle (1cm);
			\foreach \i in {0,...,\no}{
					\pgfmathtruncatemacro{\j}{\c[\i]};
					\node (\j) at ({cos(360*\i/\n)},{sin(360*\i/\n)}){};
					\filldraw[red] (\j) circle (1.5pt);
					\node (p\j) at ({1.2*cos(360*\i/\n)},{1.2*sin(360*\i/\n)}){\j};
				};
			\draw[red, thick, fill=red!40!white] (4.center) -- (6.center);
			\draw[black, dashed, fill=red!40!white] (3.center) -- (7.center);
		\end{tikzpicture}
  \end{center}
		\caption{The visualization of the cycle notation $(1,3,4,7,9,8,6,5,2)$ of $c=s_2s_1s_3s_6s_5s_4s_8s_7$.  {\it Left:} the initial $c$-charmed simple root $(6,7)$ (in red) intersecting the root $(5,8)=(6-1,7+1)$ (dashed).  {\it Right:} the $c$-charmed root $(4,6)$ (in red) intersecting the root $(3,7)=(4-1,6+1)$ (dashed).}
		\label{fig:c_visualization}
	\end{figure}%


\begin{comment}
\subsection{Coxeter-sorting words and Auslander--Reiten quivers}
\label{sec:sort_ar}

Let $c \in \S_n$ be a Coxeter element, and fix $\sc = [r_{1},r_2 \ldots, r_{n-1}]$
a reduced word for $c$. Define the \defn{$c$-sorting word} of the long element $w_\circ$ to be the leftmost reduced word $\w_\circ(\sc)$ for $w_\circ$ in $\sc^\infty$.  Up to commutations, $\w_\circ(\sc)$ does not depend on the choice of reduced word for $c$, and so we shall denote it by $\w_\circ(c)$.
%
Write the $c$-sorting word for the long element $\w_\circ(c) = [t_1,t_2, \ldots, t_N]$, with each $t_i \in S$ a simple reflection and $N=|T|=\binom{n}{2}$ the number of reflections in $\S_n$. For $a = 1,2, \ldots, N$, define the inversion
\begin{equation}
	\label{eq:root_order}
	\alpha^{(a)} \coloneqq t_{1} t_{2} \cdots t_{a-1}(\alpha_{t_a}),
\end{equation}
where $\alpha_{t_a}$ is the simple root corresponding to the simple reflection $t_a$.  Since $w_\circ$ has every positive root as an inversion, each positive root appears exactly once in the inversion sequence $\inv(\w_\circ(c)) \coloneqq [\alpha^{(1)},\alpha^{(2)}, \ldots, \alpha^{(N)}]$.

\begin{example}
	\label{ex:c_sorting}
	For $\sc=[s_2,s_1,s_3,s_6,s_5,s_4,s_8,s_7]$, we have \begin{align*} \w_\circ(c) & = s_2s_1s_3s_6s_5s_4s_8s_7s_2s_1s_3s_6s_5s_4s_8s_7s_2s_1s_3s_6s_5s_4s_8s_7s_2s_1s_3s_6s_5s_4s_8s_7s_2s_6s_5s_8 \text{ and } \\ \inv(\w_\circ(c)) & =[(23), (13), (24), (67), (57), (27), (89), (69), (14), (34), (17), (59),\\ &\phantom{=[} (29), (19), (68), (58), (37), (47), (39), (28), (18), (38), (56), (26),\\ &\phantom{=[} (49), (79), (48), (16), (36), (46), (25), (15), (78), (35), (45), (12)].
	\end{align*}
\end{example}
\end{comment}


\begin{comment}
It is helpful to arrange the letters in the Coxeter-sorting word $\w_\circ(c)= [t_1,t_2, \ldots, t_N]$ in a quiver $\ARc$---if we replace each letter $t_a$ by the reflection corresponding to the positive root $\alpha^{(a)}$ in the inversion sequence, this is known as the \defn{Auslander--Reiten quiver} $\ARc$~\cite[Sections 3.1.1 and 3.1.2.2]{schiffler2014quiver}. %
A combinatorial description of $\ARc$ is given as follows:
\begin{itemize}
	\item the vertices are the roots $(i,j)$ for $1 \leq i <j \leq n$;
	\item if $(i,i+1)$ is initial in $c$, then $(i,i+1)$ appears as the leftmost vertex in the $i$th row from the top;
	\item if $(i,i+1)$ is final in $c$, then $(i,i+1)$ appears as the rightmost vertex in the $i$th row from the bottom.
	\item for $i<j$ we draw a south-east arrow $(i,j) \longrightarrow (i,c(j))$ if $i<c(j)$; and
	\item for $i<j$ we draw a north-east arrow $(i,j) \longrightarrow (c(i),j)$ if $c(i)<j$.
\end{itemize}
It will be useful to consider the example Auslander--Reiten quiver shown in Figure \ref{fig:tri9} while digesting this description.

Representation-theoretically, the vertices of $\ARc$ are the indecomposable representations of $\Qc$, but these are naturally labelled by positive roots using Gabriel's theorem. We now provide some more details on the structure of $\ARc$.

It follows immediately from the above description that the labels $(i,j)$ appearing on each SW-NE diagonal have $j$ fixed, while those appearing
on each NW-SE diagonal have $i$ fixed; we therefore index the diagonals by the corresponding label. One SW-NE diagonal appears for each value of $j$ except 1; one NW-SE diagonal appears for each value of $i$ except $n$.
It is also immediate that the NW-SE diagonals appear in left-to-right order given by $c$, and similarly for the SW-NE diagonals. For $j$ in $\lheart\cap [2,n-1]$, the righthand end of the SW-NE diagonal labelled by $j$ is $(c^{-1}(j),j)$. The lefthand end of the SW-NE diagonal
labelled by $j$ begins one step to the right from $(c^{-1}(j),j)$, at $(j,c(j))$. For $i$ in $\rheart\cap [2,n-1]$, the righthand end of the NW-SE diagonal labelled by $i$ ends at $(i,c^{-1}(i))$ and the SW-NE-diagonal labelled by $i$ starts one step to the right, at $(c(i),i)$.

Let $s=s_k$ be initial in $c$. It is convenient to write $c=(a_1, \dots a_n)$ where $a_1=k$. We have that $\{a_1,\dots,a_k\}=\{1,\dots,k\}$, $a_{k+1}=k+1$, and $\{a_{k+1},\dots,a_n\}=\{k+1,\dots,n\}$. The $(k+1)$ SW-NE diagonals starting with the diagonal containing containing $(k,k+1)$ are numbered $k=a_1,\dots,a_k,a_{k+1}=k+1$ in that order. The $(n-k+2)$ NW-SE diagonals starting with the diagonal containing $(k,k+1)$ are numbered $k+1=a_{k+1},\dots,a_n,a_1=k$ in that order. In addition to Figure \ref{fig:tri9}, it will also be useful to consult Figure \ref{fig: AR arround k}, which provides a schematic description of a generic AR quiver with $s_k$ initial.

The diagonals labelled by $k$ and $k+1$ form a rectangle with three missing corners. We have already observed that the top and bottom corners of the rectangle are missing; these are the positions where the two diagonals labelled $k$, or the two diagonals labelled $k+1$, should cross. We see that the righthand corner is also missing; it is at the intersection of the SW-NE diagonal labelled $k$ and the NW-SE diagonal labelled $k+1$, so that its label would be $(k+1,k)$, which is not a valid label; however, the labels to its NW and SW are the (valid) labels $(c^{-1}(k+1),k)$ and $(k+1,c^{-1}(k))$, so all the rest of the roots along the edges of the rectangle are indeed present.

We will need the following lemma, which characterizes the labels whichappear outside this rectangle.

\begin{lemma}
	\label{lem:outside}
	Let $s=s_k$ be initial in $c$.
	In $\ARc$, all the roots above the SW-NE diagonal labelled $k+1$ or below the SW-NE diagonal labelled by $k$ have both entries less than $k$.
	Similarly, all the roots above the NW-SE diagonal labelled by $k+1$ or below the NW-SE diagonal labelled $k$ have both entries greater than $k+1$.
\end{lemma}

\begin{proof}
	Recall that each set of diagonals appears in the order given by $c$. This implies that the NW-SE diagonals with labels greater than $k$ are between the one labelled $k+1$ and the one labelled $k$. The SW-NE diagonals less than $k+1$ are between the one labelled $k+1$ and the one labelled $k$.
	It follows that the roots in the region above the SW-NE diagonal labelled by $k+1$ lie on diagonals which are both labelled by numbers less than $k$. A similar argument applies to the three other regions.
\end{proof}

Let $c'=s_kcs_k$, so $c \xrightarrow{k} c'$. In this case, we can relate the Auslander--Reiten quivers $\AR(c)$ and $\AR(c')$.

\begin{proposition}
	\label{prop:ARc}
	Let $c \xrightarrow{k} c'$. Then $\AR(c')$ is obtained from $\ARc$ by replacing every label $k$ by $k+1$ and vice versa, while also removing the root labelled $(k,k+1)$ and replacing it where the SW-NE diagonal labelled $k+1$ and the NW-SE diagonal labelled $k$ now cross.
\end{proposition}

\begin{proof}
	Another way to describe the transformation of the roots (other than $(k,k+1)$) is that we replace the label $(i,j)$ by $(s(i),s(j))$. Since $c'=scs$, if $c(j)=\tilde j$, then $c'(s(j))=s(\tilde j)$. All the edges of the quiver except those involving $(k,k+1)$ will remain, because the action of $s$ will not change whether or not the inequalities from the description of the Auslander--Reiten quiver hold. In $\ARcp$, the label $(k,k+1)$ must lie at the intersection of the SW-NE diagonal labeled by $k+1$ and the NW-SE diagonal labelled by $k$; as we have already observed, this position was empty in the Auslander--Reiten quiver of $c$.
\end{proof}

\begin{figure}[htbp]
	\[
		%\scalebox{0.66}{
			\begin{tikzpicture}
				\node (1) at (0,8) {{  $1$}};
				\node (3) at (2,8) {{  $3$}};
				\node (4) at (4,8) {{  $4$}};
				\node (7) at (6,8) {{  $7$}};
				\node (9) at (-1,-1) {{  $9$}};
				\node (8) at (1,-1) {{  $8$}};
				\node (6) at (3,-1) {{  $6$}};
				\node (5) at (5,-1) {{  $5$}};
				\node (2) at (7,-1) {{  $2$}};

				\draw[dashed] (-1,2) -- (6,9) -- (10,5) -- (3,-2) -- (-1,2);

				\node (67) at (0,2) {(67)};
				\node[circle,draw,thick] (57) at (1,3) {(57)};
				\node[circle,draw,thick] (27) at (2,4) {(27)};
				\node[circle,draw,thick] (17) at (3,5) {(17)};
				\node[circle,draw,thick] (37) at (4,6) {(37)};
				\node[circle,draw,thick] (47) at (5,7) {(47)};
				\node[circle,draw,thick] (69) at (1,1) {(69)};
				\node (59) at (2,2) {(59)};
				\node (29) at (3,3) {(29)};
				\node (19) at (4,4) {(19)};
				\node (39) at (5,5) {(39)};
				\node (49) at (6,6) {(49)};
				\node[circle,draw,thick] (68) at (2,0) {(68)};
				\node (58) at (3,1) {(58)};
				\node (28) at (4,2) {(28)};
				\node (18) at (5,3) {(18)};
				\node (38) at (6,4) {(38)};
				\node (48) at (7,5) {(48)};
				\node[circle,draw,thick,dotted] (78) at (8,6) {(78)};
				\node (89) at (0,0) {(89)};
				\node[circle,draw,thick,dotted] (79) at (7,7) {(79)};
				\node[circle,draw,thick,dotted] (56) at (4,0) {(56)};
				\node (25) at (6,0) {(25)};
				\node (12) at (8,0) {(12)};
				\node (13) at (1,7) {(13)};
				\node (34) at (3,7) {(34)};
				\node[circle,draw,thick,dotted] (26) at (5,1) {(26)};
				\node (15) at (7,1) {(15)};
				\node (23) at (0,6) {(23)};
				\node (14) at (2,6) {(14)};
				\node[circle,draw,thick,dotted] (16) at (6,2) {(16)};
				\node (35) at (8,2) {(35)};
				\node (24) at (1,5) {(24)};
				\node[circle,draw,thick,dotted] (36) at (7,3) {(36)};
				\node (45) at (9,3) {(45)};
				\node[circle,draw,thick,dotted] (46) at (8,4) {(46)};

				\draw[->] (13)--(14);\draw[->] (14)--(34);\draw[->] (14)--(17);\draw[->] (15)--(35);\draw[->] (15)--(12);\draw[->] (16)--(36);\draw[->] (16)--(15);\draw[->] (17)--(37);\draw[->] (17)--(19);\draw[->] (18)--(38);\draw[->] (18)--(16);\draw[->] (19)--(39);\draw[->] (19)--(18);\draw[->] (23)--(13);\draw[->] (23)--(24);\draw[->] (24)--(14);\draw[->] (24)--(27);\draw[->] (25)--(15);\draw[->] (26)--(16);\draw[->] (26)--(25);\draw[->] (27)--(17);\draw[->] (27)--(29);\draw[->] (28)--(18);\draw[->] (28)--(26);\draw[->] (29)--(19);\draw[->] (29)--(28);\draw[->] (34)--(37);\draw[->] (35)--(45);\draw[->] (36)--(46);\draw[->] (36)--(35);\draw[->] (37)--(47);\draw[->] (37)--(39);\draw[->] (38)--(48);\draw[->] (38)--(36);\draw[->] (39)--(49);\draw[->] (39)--(38);\draw[->] (46)--(45);\draw[->] (47)--(49);\draw[->] (48)--(78);\draw[->] (48)--(46);\draw[->] (49)--(79);\draw[->] (49)--(48);\draw[->] (56)--(26);\draw[->] (57)--(27);\draw[->] (57)--(59);\draw[->] (58)--(28);\draw[->] (58)--(56);\draw[->] (59)--(29);\draw[->] (59)--(58);\draw[->] (67)--(57);\draw[->] (67)--(69);\draw[->] (68)--(58);\draw[->] (69)--(59);\draw[->] (69)--(68);\draw[->] (79)--(78);\draw[->] (89)--(69);
			\end{tikzpicture}%
			\begin{tikzpicture}
				\node (1) at (0,8) {{  $1$}};
				\node (3) at (2,8) {{  $3$}};
				\node (4) at (4,8) {{  $4$}};
				\node (7) at (6,8) {{  $6$}};
				\node (9) at (-1,-1) {{  $9$}};
				\node (8) at (1,-1) {{  $8$}};
				\node (6) at (3,-1) {{  $7$}};
				\node (5) at (5,-1) {{  $5$}};
				\node (2) at (7,-1) {{  $2$}};
				\draw[dashed] (-1,2) -- (6,9) -- (10,5) -- (3,-2) -- (-1,2);
				\node (67) at (9,5) {(67)};
				%
				\node[circle,draw,thick,dotted] (57) at (1,3) {(56)};
				%
				\node[circle,draw,thick,dotted] (27) at (2,4) {(26)};
				%
				\node[circle,draw,thick,dotted] (17) at (3,5) {(16)};
				\node[circle,draw,thick,dotted] (37) at (4,6) {(36)};
				\node[circle,draw,thick,dotted] (47) at (5,7) {(46)};

				\node[circle,draw,thick,dotted] (69) at (1,1) {(79)};
				%
				\node (59) at (2,2) {(59)};
				%
				\node (29) at (3,3) {(29)};
				%
				\node (19) at (4,4) {(19)};
				\node (39) at (5,5) {(39)};

				\node (49) at (6,6) {(49)};

				\node[circle,draw,thick,dotted] (68) at (2,0) {(78)};
				%
				\node (58) at (3,1) {(58)};
				\node (28) at (4,2) {(28)};
				%
				\node (18) at (5,3) {(18)};
				%
				\node (38) at (6,4) {(38)};
				%
				\node (48) at (7,5) {(48)};
				%
				\node[circle,draw,thick] (78) at (8,6) {(68)};
				%
				\node (89) at (0,0) {(89)};
				%
				\node[circle,draw,thick] (79) at (7,7) {(69)};

				\node[circle,draw,thick] (56) at (4,0) {(57)};
				\node (25) at (6,0) {(25)};
				\node (12) at (8,0) {(12)};
				\node (13) at (1,7) {(13)};
				\node (34) at (3,7) {(34)};

				\node[circle,draw,thick] (26) at (5,1) {(27)};
				\node (15) at (7,1) {(15)};
				\node (23) at (0,6) {(23)};
				\node (14) at (2,6) {(14)};

				\node[circle,draw,thick] (16) at (6,2) {(17)};
				\node (35) at (8,2) {(35)};
				\node (24) at (1,5) {(24)};
				%

				\node[circle,draw,thick] (36) at (7,3) {(37)};
				\node (45) at (9,3) {(45)};
				%

				\node[circle,draw,thick] (46) at (8,4) {(47)};

				\draw[->] (13)--(14);\draw[->] (14)--(34);\draw[->] (14)--(17);\draw[->] (15)--(35);\draw[->] (15)--(12);\draw[->] (16)--(36);\draw[->] (16)--(15);\draw[->] (17)--(37);\draw[->] (17)--(19);\draw[->] (18)--(38);\draw[->] (18)--(16);\draw[->] (19)--(39);\draw[->] (19)--(18);\draw[->] (23)--(13);\draw[->] (23)--(24);\draw[->] (24)--(14);\draw[->] (24)--(27);\draw[->] (25)--(15);\draw[->] (26)--(16);\draw[->] (26)--(25);\draw[->] (27)--(17);\draw[->] (27)--(29);\draw[->] (28)--(18);\draw[->] (28)--(26);\draw[->] (29)--(19);\draw[->] (29)--(28);\draw[->] (34)--(37);\draw[->] (35)--(45);\draw[->] (36)--(46);\draw[->] (36)--(35);\draw[->] (37)--(47);\draw[->] (37)--(39);\draw[->] (38)--(48);\draw[->] (38)--(36);\draw[->] (39)--(49);\draw[->] (39)--(38);\draw[->] (46)--(45);\draw[->] (47)--(49);\draw[->] (48)--(78);\draw[->] (48)--(46);\draw[->] (49)--(79);\draw[->] (49)--(48);\draw[->] (56)--(26);\draw[->] (57)--(27);\draw[->] (57)--(59);\draw[->] (58)--(28);\draw[->] (58)--(56);\draw[->] (59)--(29);\draw[->] (59)--(58);\draw[->] (46)--(67);\draw[->] (78)--(67);\draw[->] (68)--(58);\draw[->] (69)--(59);\draw[->] (69)--(68);\draw[->] (79)--(78);\draw[->] (89)--(69);
			\end{tikzpicture}%}
	\]

	\caption{The Coxeter element $c=s_2s_1s_3s_6s_5s_4s_8s_7$ has cycle notation $(1,3,4,7,9,8,6,5,2)$.  The simple reflection $s=s_6$ is initial in $c$, and we set $c'=scs$, with cycle notation $(1,3,4,6,9,8,7,5,2)$.  The quivers $\AR(c)$ ({\it left}) and $\AR(c')$ ({\it right}) are illustrated above.  The roots in $\T_6$ defined in~\Cref{eq:tk} are marked by solid circles in $\AR(c)$ and $\AR(c')$, while the roots in $\sT_6$ are marked by dotted circles.}%
	\label{fig:tri9}
\end{figure}

\begin{figure}[htbp]
	\begin{center}
		\begin{tikzpicture}[scale=1.3]
			\draw[teal, fill=teal!40!white] (3.75,4.5) -- (.5,1.25) -- (-.5,2.25) -- (.25,3) -- (0,3.25) -- (.5,3.75) -- (-.25,4.5) -- (3.75,4.5);
			\node at (1,3) {$\leq k$};%
			\draw[red, fill=red!40!white] (3.5,-4.5) -- (0.25,-1.25) -- (-.25,-1.75) -- (.25,-2.25) -- (-.25,-2.75) -- (0,-3) -- (-.5,-3.5) -- (.25,-4.25) -- (0,-4.5) -- (3.5,-4.5);
			\node at (1,-3) {$\geq k+1$};%

			\draw[red, fill=red!40!white] (4.75,4.5) -- (8.5,.5) -- (9.5,.5) -- (10.25,1.25) -- (9.75,1.75) -- (10.25,2.25) -- (9.75,2.75) -- (10,3) -- (9.5,3.5) -- (10.25,4.25) -- (10,4.5) -- (4.75,4.5);
			\node at (8.5,3) {$\geq k+1$};%
			\draw[teal, fill=teal!40!white] (4.75,-4.5) -- (8.5,-.5) -- (9.5,-.5) -- (10.25,-1.25) -- (9.25,-2.25) -- (10,-3) -- (9.75,-3.25) -- (10.25,-3.75) -- (9.5,-4.5) -- (4.75,-4.5);
			\node at (8.5,-3) {$\leq k$};%

			%
			\node at (4.5,0) {};%
			\node at (0,0) {$(k,k+1)$};
			\draw[->, thick] (.25,.25) -- (.75,.75);
			\node at (1,1) {$(a_2,k+1)$};
			\draw[->, thick] (1.35,1.35) -- (1.85,1.85);

			%
			\draw[dotted, thick] (2,2) -- (3,3);
			\draw[->, thick] (3.1,3.1) -- (3.6,3.6);
			\node at (4,4) {$(a_{k-1},k+1)$};
			\draw[<-, thick, dotted] (4.75,4) -- (5.5,4);
			\node at (6,4) {$(k,a_{k+1})$};
			\draw[->, thick] (6.35,3.65) -- (6.85,3.15);
			\draw[dotted, thick] (7,3) -- (8,2);
			\draw[->, thick] (8.1,1.9) -- (8.6,1.4);
			\node at (8.9,1) {$(k,a_{n})$};

			\draw[->, thick] (0.25,-.25) -- (0.75,-0.75);
			\node at (1,-1) {$(k,a_{k+1})$};
			\draw[->, thick] (1.35,-1.35) -- (1.85,-1.85);
			\draw[dotted, thick] (2,-2) -- (3,-3);
			\draw[->, thick] (3.1,-3.1) -- (3.6,-3.6);
			\node at (3.9,-4) {$(k,a_n)$};
			\draw[<-, thick, dotted] (4.75,-4) -- (5.5,-4);
			\node at (6,-4) {$(a_{2},k)$};
			\draw[->, thick] (6.35,-3.65) -- (6.85,-3.15);
			\draw[dotted, thick] (7,-3) -- (8,-2);
			\draw[->, thick] (8.1,-1.9) -- (8.6,-1.4);
			\node at (9,-1) {$(a_{k-1},k)$};
		\end{tikzpicture}
	\end{center}
	\caption{This provides a generic description of $\ARc$ where $s_k$ is initial in $c$. Here $c$ has cycle notation $(a_1,\ldots,a_k,a_{k+1},\ldots,a_{n})$ with $a_1=k$, $a_{k+1}=k+1$, $\{a_1,\ldots,a_k\} = \{1,\ldots,k\}$, and $\{a_{k+1},\ldots,a_{n}\} = \{k+1,\ldots,n\}$. The regions shaded in green consist of roots with
	both labels $\leq k$, while the regions shaded in red consist of roots with both labels $\geq k+1$, as guaranteed by Lemma \ref{lem:outside}.}
	\label{fig: AR arround k}
\end{figure}


\end{comment}


\section{Charmed bijections}
\label{sec:bij}

In this section, we define a general family of \emph{charmed bijections} between \emph{balanced pairs} of subsets and nonnesting partitions.  Our charmed bijections depend on a choice of decoration of the roots in $\Phi^+=\Phi^+(A_{n-1})$, and use certain \emph{intimate} families of lattice paths as intermediate objects.
Specializing to the $c$-charmed roots coming from a Coxeter element $c$, we obtain our \emph{$c$-charmed bijections} between $\NC(\S_n,c)$ and $\NN(\S_n)$.

\subsection{Balanced pairs and noncrossing partitions}
\begin{definition}
	Say that a pair of sets $(O,I)$ with $O,I \subseteq [n]$ is \defn{balanced} if  $|O|=|I|$ and $|O\cap [k]| \geq |I \cap [k]|$ for all $1\leq k \leq n$.  Write $\Bal(n)$ for all balanced pairs of subsets of $[n]$.
\end{definition}

We first show that balanced pairs are naturally in bijection with $c$-noncrossing partitions.  Let $\nc \in \NC(\S_n,c)$.
We define $O(\nc)$ to be the set of integers $i$ for which there exists an $j>i$ in the same block as $i$, and we define the set $I(\nc)$ to be the set of integers $j$ such that there exists an $i<j$ in the same block as $j$. It is immediate from the definition that $(O,I)\in \Bal(n)$.

\begin{proposition}
	\label{prop:bal_to_nc}
	The map\footnote{To be precise, both $O$ and $I$ depend on $c$, however since $c$ will always be clear from the context we omit it in the notation.} $\nc \mapsto (O(\nc),I(\nc))$ is a bijection between $\NC(\S_n,c)$ and $\Bal(n)$.
\end{proposition}

\begin{proof}
	We construct its inverse.  For a given pair $(O,I) \in \Bal(n)$, we can construct a $\nc \in \NC(\S_n,c)$ with $O(\nc)=O$ and $I(\nc)=I$ as follows.  The \defn{closed singletons} of $\nc$ are the integers that are neither in $O$ nor $I$. We place each integer in $O\setminus I$ in its own block and call these blocks \textcolor{teal}{\it open}. Then we add iteratively the integers in $I$ to the open blocks, starting with the smallest integer, such that the intermediate partition is always noncrossing.  This is achieved by adding an integer $x$ to the first open block we visit when walking from $x$ towards $n$ via $1$ in the cycle notation of $c$.  If an integer in $I\setminus O$ is added to a block we call this block \defn{closed} and thereafter do not add any integers to it. By construction we have $O(\nc)=O$ and $I(\nc)=I$.
\end{proof}

The bijection of~\Cref{prop:bal_to_nc} is illustrated in~\Cref{fig: pi to OI}.

\begin{figure}[htbp]
\begin{center}
\scalebox{.7}{
	\begin{tikzpicture}[scale=1.5]
		\def\c{{1,3,4,7,9,8,6,5,2}};
		\pgfmathtruncatemacro{\n}{dim(\c)};
		\pgfmathtruncatemacro{\no}{\n-1};
		\draw (0,0) circle (1cm);
        \node (t) at (0,-1.5) {$O\setminus I = \{\textcolor{teal}{1},\textcolor{teal}{3}\}$};
		\foreach \i in {0,...,\no}{
				\pgfmathtruncatemacro{\j}{\c[\i]};
				\node (\j) at ({cos(360*\i/\n)},{sin(360*\i/\n)}){};
				\filldraw (\j) circle (1pt);
				\node (p\j) at ({1.2*cos(360*\i/\n)},{1.2*sin(360*\i/\n)}){\j};
			};
        \filldraw[red] (2.center) circle (1pt);
        \filldraw[red] (4.center) circle (1pt);
        \filldraw[red] (5.center) circle (1pt);
        \filldraw[red] (9.center) circle (1pt);
		\filldraw[teal] (1.center) circle (1pt);
		\filldraw[teal] (3.center) circle (1pt);
		\draw[teal, dashed, very thick] (1.center) circle (3pt);
		\draw[teal, dashed, very thick] (3.center) circle (3pt);
	\end{tikzpicture} \hspace{2cm}
	\begin{tikzpicture}[scale=1.5]
		\def\c{{1,3,4,7,9,8,6,5,2}};
		\pgfmathtruncatemacro{\n}{dim(\c)};
		\pgfmathtruncatemacro{\no}{\n-1};
		\draw (0,0) circle (1cm);
        \node (t) at (0,-1.5) {$I = \{\textcolor{teal}{\mathbf{6}},7,8\}$};
		\foreach \i in {0,...,\no}{
				\pgfmathtruncatemacro{\j}{\c[\i]};
				\node (\j) at ({cos(360*\i/\n)},{sin(360*\i/\n)}){};
				\filldraw (\j) circle (1pt);
				\node (p\j) at ({1.2*cos(360*\i/\n)},{1.2*sin(360*\i/\n)}){\j};
			};
           \filldraw[red] (2.center) circle (1pt);
        \filldraw[red] (4.center) circle (1pt);
        \filldraw[red] (5.center) circle (1pt);
        \filldraw[red] (9.center) circle (1pt);
		\filldraw[teal] (1.center) circle (1pt);
		\filldraw[teal] (3.center) circle (1pt);
		\filldraw[teal] (6.center) circle (1pt);
		\draw[teal, dashed, very thick] (3.center) circle (3pt);
		\draw[teal, dashed, thick, fill=red!40!white] (1.center) -- (6.center);
	\end{tikzpicture}
\hspace{2cm}
	\begin{tikzpicture}[scale=1.5]
		\def\c{{1,3,4,7,9,8,6,5,2}};
		\pgfmathtruncatemacro{\n}{dim(\c)};
		\pgfmathtruncatemacro{\no}{\n-1};
		\draw (0,0) circle (1cm);
        \node (t) at (0,-1.5) {$I = \{6,\textcolor{red}{\mathbf{7}},8\}$};
		\foreach \i in {0,...,\no}{
				\pgfmathtruncatemacro{\j}{\c[\i]};
				\node (\j) at ({cos(360*\i/\n)},{sin(360*\i/\n)}){};
				\filldraw (\j) circle (1pt);
				\node (p\j) at ({1.2*cos(360*\i/\n)},{1.2*sin(360*\i/\n)}){\j};
			};
           \filldraw[red] (2.center) circle (1pt);
        \filldraw[red] (4.center) circle (1pt);
        \filldraw[red] (5.center) circle (1pt);
        \filldraw[red] (9.center) circle (1pt);
		\filldraw[teal] (1.center) circle (1pt);
		\filldraw[red] (3.center) circle (1pt);
		\filldraw[teal] (6.center) circle (1pt);
		\filldraw[red] (7.center) circle (1pt);
		\draw[teal, dashed, thick] (1.center) -- (6.center);
		\draw[red, thick] (3.center) -- (7.center);
	\end{tikzpicture}\hspace{2cm}
	\begin{tikzpicture}[scale=1.5]
		\def\c{{1,3,4,7,9,8,6,5,2}};
		\pgfmathtruncatemacro{\n}{dim(\c)};
		\pgfmathtruncatemacro{\no}{\n-1};
		\draw (0,0) circle (1cm);
  \node (t) at (0,-1.5) {$I = \{6,7,\textcolor{red}{\mathbf{8}}\}$};
		\foreach \i in {0,...,\no}{
				\pgfmathtruncatemacro{\j}{\c[\i]};
				\node (\j) at ({cos(360*\i/\n)},{sin(360*\i/\n)}){};
				\filldraw[red] (\j) circle (1pt);
				\node (p\j) at ({1.2*cos(360*\i/\n)},{1.2*sin(360*\i/\n)}){\j};
			};
		\draw[red, thick, fill=red!40!white] (1.center) -- (6.center) -- (8.center) -- (1.center);
		\draw[red, thick, fill=red!40!white] (3.center) -- (7.center);
	\end{tikzpicture}}
 \end{center}
	\caption{\label{fig: pi to OI} The construction of a noncrossing partition in $\NC(\S_9,c)$ for $c= s_2s_1s_3s_6s_5s_4s_8s_7 = (1\, 3\, 4\, 7\, 9\, 8\, 6\, 5\, 2)$ starting with the outgoing set $O=\{1,3,6\}$ and incoming set $I=\{6,7,8\}$. We depict open blocks in dashed teal, and closed blocks in solid red; we circle open and closed singletons using the same color code.}
\end{figure}


\subsection{Intimate families}
\label{sec:intimate}

We draw the root poset for $\S_n$ by placing the root $(i,j)$ in the plane with coordinates $((i+j-1)/2,(j-i)/2)$ and---since the label $(i,j)$ is implied by the position---we may omit the labels on the roots. For $1 \leq i \leq n$, we draw $n$ additional points labeled by $i$ at coordinates $(i-1/2,0)$ and call these extra points \defn{integral vertices}. For $\M \subseteq \Phi^+$, we call a root $(i,j)$ \defn{charmed} if $(i,j) \in \M$ and \defn{ordinary} otherwise.  We depict charmed roots using hearts $\textcolor{red}{\varheartsuit}$ and ordinary roots using circles---an example of $c$-charmed roots is illustrated in \Cref{fig: root poset}.

A \defn{path} is a lattice path with step set $\{(1/2,1/2),(1/2,-1/2)\}$ that starts and ends at an integral vertex and stays strictly above the $x$-axis.  We call $(1/2,1/2)$-steps \defn{up}, and $(1/2,-1/2)$-steps \defn{down}; a \defn{peak} (resp. \defn{valley}) of a path is a root contained in an up step to its left (resp.~right) and a down step to its right (resp.~left).  Two paths are \defn{kissing} if they do not cross or share edges---they may \emph{meet} at a vertex, where they are said to \defn{kiss}. (Note, though, that kisses are not required for two paths to be kissing.) A family of paths is \defn{kissing} if they are pairwise kissing.  A path \defn{feints} at a root $(i,j)$ if $(i,j)$ is a valley, but the path does not kiss any path at $(i,j)$.  These definitions are illustrated on the right of~\Cref{fig: path configurations}: the top configuration is a feint at a charmed root, while the bottom one is a kiss at an ordinary root.

For $\M \subseteq \Phi^+$, a family $\L$ of kissing paths is called \defn{$\M$-charmed} if:
\begin{itemize}
	\item paths only kiss at charmed roots and
	\item paths only feint at ordinary roots.%
\end{itemize}

In other words, a family of paths is charmed if it avoids the two local configurations shown on the right of~\Cref{fig: path configurations}.%

\begin{definition}
	A family $\L$ of $\M$-charmed kissing paths is called \defn{$\M$-intimate} if:
	\begin{itemize}
		\item every ordinary root either lies above all paths in $\L$ or is contained in some path in $\L$ and
		\item no path contains a root above a charmed peak of a path in $\L$, unless that charmed peak is the location of a kiss.
	\end{itemize}
\end{definition}
%

\begin{figure}
	\begin{center}
		\begin{tikzpicture}
			\draw (1,-.5) -- (1.5,0) -- (2,-.5);
			\draw (2.5,-.5) -- (3,0) -- (3.5,.5);
			\draw (4,.5) -- (4.5,0) -- (5,-.5);
			\draw (5.5,.5) -- (6,0) -- (6.5,.5);
			\draw[very thick] (5.5,-.5) -- (6,0) -- (6.5,-.5);
			\draw (9.5,.5) -- (10,0) -- (10.5,.5);
			\marked{0}{0}
			\marked{1.5}{1.5}
			\marked{3}{3}
			\marked{4.5}{4.5}
			\marked{6}{6}
			\marked{10}{10}

			\begin{scope}[yshift=-2cm]
				\draw (1,-.5) -- (1.5,0) -- (2,-.5);
				\draw (2.5,-.5) -- (3,0) -- (3.5,.5);
				\draw (4,.5) -- (4.5,0) -- (5,-.5);
				\draw (5.5,.5) -- (6,0) -- (6.5,.5);
				\draw (9.5,.5) -- (10,0) -- (10.5,.5);
				\draw[very thick] (9.5,-.5) -- (10,0) -- (10.5,-.5);
				\draw[fill=lightgray,thick] (0,0) circle (2pt);
				\draw[fill=lightgray,thick] (1.5,0) circle (2pt);
				\draw[fill=lightgray,thick] (3,0) circle (2pt);
				\draw[fill=lightgray,thick] (4.5,0) circle (2pt);
				\draw[fill=lightgray,thick] (6,0) circle (2pt);
				\draw[fill=lightgray,thick] (10,0) circle (2pt);
			\end{scope}
		\end{tikzpicture}
	\end{center}
	\caption{{\it Left:} the five allowed local configurations for charmed families. {\it Right:} the two local configurations are forbidden for charmed families.}
	\label{fig: path configurations}
\end{figure}

\subsection{Balanced pairs and intimate families}
We now relate balanced pairs and intimate families of paths.  For a family $\L$ of paths, we call an integral vertex on the $x$-axis \defn{outgoing} if it is incident to an up step and \defn{incoming} if it is incident to a down step (an integral vertex can be both outgoing and incoming).  Denote by $\Out(\L)$  (resp.~$\In(\L)$) the set of labels of outgoing (resp.~incoming) vertices of $\L$.  It is clear that $(\Out(\L),\In(\L))$ is balanced.

\begin{lemma}
	\label{lem: bij help in-out}
	Let $\M \subseteq \Phi^+$ and let $(O,I) \in \Bal(n)$. Then there is a unique $\M$-inimate family $\L_{(O,I)}$ with $\Out(\L_{(O,I)}) = O$ and $\In(\L_{(O,I)})=I$.
\end{lemma}
\begin{proof}
	We first construct a well-formed word of parentheses from the subsets $O$ and $I$. For $i$ from $1$ to $n$, write:
	\begin{itemize}
		\item a $(_i$ parenthesis if $i \in O\setminus I$,
		\item a $)_i$ parenthesis if $i \in I \setminus O$, and
		\item $)_i(_i$ parentheses if $i \in O \cap I$.
	\end{itemize}
	We now construct an $\M$-intimate family $\L$ recursively, starting with the empty family of paths. At each step, we pick neighbouring parentheses of the form $(_i)_j$, delete them, and add the path $\p$ that starts at $i$ and ends at $j$ that takes a down step whenever possible without violating the condition that the family is charmed, and an up step otherwise.  Then $\L \cup \{\p\}$ is intimate:
	\begin{itemize}
		\item If there were an ordinary root below $\L \cup \{\p\}$ that wasn't part of a path, then that root would lie between $p$ and $\L$, since $\L$ was intimate.  But then $\p$ took an up step instead of a possible down step, contradicting the definition of $\p$.
		\item If a previously constructed path $\p'$ in $\L$ started at an integral vertex after $i$, ended before $j$, and had a charmed peak which is not the location of a kiss, then our new path $\p$ will kiss $\p'$ at that charmed peak.
	\end{itemize}
	The order of choosing two neighbouring parentheses is irrelevant.  The family produced is unique, since if at any point a path uses a step different from those prescribed by the algorithm above, then the resulting family of paths will be non-intimate.  This non-intimacy will persist, regardless of how the family is extended.
	%
	\qedhere
\end{proof}

An example of the algorithm used in the proof of~\Cref{lem: bij help in-out} is given in~\Cref{fig: ex for path const 1}.

\begin{figure}[htbp]
	\begin{center}
 \scalebox{.8}{
		\begin{tikzpicture}[scale=.8]
			\ctriang
			\cbot

			\begin{scope}[xshift = 9.5cm]
				\draw[ultra thick] (6.15,.15) -- (6.5,.5) -- (6.85,.15);
				\ctriang
				\cbot
			\end{scope}

			\begin{scope}[yshift = -5.5cm]
				\draw[ultra thick] (3.15,.15) -- (4.5,1.5) -- (5.85,.15);
				\draw[ultra thick] (6.15,.15) -- (6.5,.5) -- (6.85,.15);
				\ctriang
				\cbot
			\end{scope}

			\begin{scope}[yshift = -5.5cm, xshift=9.5cm]
				\draw[ultra thick] (1.15,.15) -- (3,2) -- (3.5,1.5) -- (4,2) -- (4.5,1.5) -- (5,2) -- (6.5,.5) -- (7,1) -- (7.85,.15);
				\draw[ultra thick] (3.15,.15) -- (4.5,1.5) -- (5.85,.15);
				\draw[ultra thick] (6.15,.15) -- (6.5,.5) -- (6.85,.15);
				\ctriang
				\cbot
			\end{scope}
		\end{tikzpicture}}
  	\end{center}
		\caption{
			The construction of an intimate family of paths with outgoing set $\{1,3,6\}$ and incoming set $\{6,7,8\}$.  The corresponding word of parentheses is $(_1 (_3 )_6(_6)_7)_8$.
		}
		\label{fig: ex for path const 1}
\end{figure}


%\subsection{Intimate families and nonnesting partitions}
Let $\L$ be an $\M$-intimate family of paths. We define the order ideal $J(\L)$ of $\L$ to be the set of all roots $(i,j)$ which lie on or below a path in $\L$. It is clear that $J(\L)$ is an order ideal and hence is in $\NN(\S_n)$.

\begin{lemma}
	\label{lem: bij help order ideal}
	Let $\M\subseteq \Phi^+$ and $J \in \NN(\S_n)$. Then there exists a unique $\M$-intimate family $\L_J$ with $J(\L_J)=J$.
\end{lemma}
\begin{proof}
	We construct an $\M$-intimate family $\L$ recursively, starting with the empty family of paths.   At each step, we add a maximal path $p$ to $\L$ such that all roots contained in $p$ lie in $J$.  We then replace $J$ by the order ideal generated by all ordinary roots in $J$ not contained in a path of $\L$, all charmed feints of paths of $\L$, and roots in $J$ not lying below a path of $\L$.  The recursion stops when $J$ is empty.  It is clear that the resulting family $\L$ is the unique $\M$-intimate family of paths with order ideal $J$.
\end{proof}%


An example of the algorithm used in the proof of~\Cref{lem: bij help order ideal} is given in~\Cref{fig: ex for path const 2}.

\begin{figure}[htbp]
	\begin{center}
 \scalebox{.8}{
		\begin{tikzpicture}[scale=.8]
			\draw[teal, fill=teal!40!white] (1.15,.15) -- (3,2) -- (3.5,1.5) -- (4,2) -- (4.5,1.5) -- (5,2) -- (6.5,.5) -- (7,1) -- (7.85,.15);
			\ctriang

			\begin{scope}[xshift = 9.5cm]
				\draw[teal, fill=teal!40!white] (3.15,.15) -- (4.5,1.5) -- (5.85,.15);
				\draw[teal, fill=teal!40!white] (6.15,.15) -- (6.5,.5) -- (6.85,.15);
				\draw[ultra thick] (1.15,.15) -- (3,2) -- (3.5,1.5) -- (4,2) -- (4.5,1.5) -- (5,2) -- (6.5,.5) -- (7,1) -- (7.85,.15);
				\ctriang
			\end{scope}

			\begin{scope}[yshift = -5.5cm, xshift=0cm]
				\draw[teal, fill=teal!40!white] (6.15,.15) -- (6.5,.5) -- (6.85,.15);
				\draw[ultra thick] (1.15,.15) -- (3,2) -- (3.5,1.5) -- (4,2) -- (4.5,1.5) -- (5,2) -- (6.5,.5) -- (7,1) -- (7.85,.15);
				\draw[ultra thick] (3.15,.15) -- (4.5,1.5) -- (5.85,.15);
				\ctriang
			\end{scope}

			\begin{scope}[yshift = -5.5cm, xshift=9.5cm]
				\draw[ultra thick] (1.15,.15) -- (3,2) -- (3.5,1.5) -- (4,2) -- (4.5,1.5) -- (5,2) -- (6.5,.5) -- (7,1) -- (7.85,.15);
				\draw[ultra thick] (3.15,.15) -- (4.5,1.5) -- (5.85,.15);
				\draw[ultra thick] (6.15,.15) -- (6.5,.5) -- (6.85,.15);
				\ctriang
			\end{scope}
		\end{tikzpicture}}
	\end{center}
	\caption{
		The construction of the intimate family of paths with order ideal $J$, where $J$ contains the roots in the grey-shaded region of the top left picture.  At each step, the order ideal under consideration consists of the roots contained in the teal-shaded region.
	}
	\label{fig: ex for path const 2}
\end{figure}

\subsection{Charmed bijections between balanced pairs and nonnesting partitions}

As a direct consequence of~\Cref{lem: bij help in-out,lem: bij help order ideal}, we obtain the following family of bijections between balanced pairs and nonnesting partitions.
\begin{proposition}
	\label{prop: J_S bijection}
	Fix a collection of charmed roots $\M \subseteq \Phi^+$. Then the map $J_\M \colon \Bal(n) \to \NN(\S_n)$ defined by $J_\M(O,I) = J(\L_{(O,I)})$ is a bijection.
\end{proposition}

Charmed roots along the upper boundary of $\Phi^+$ do not affect the bijection of Proposition \ref{prop: J_S bijection}.  On the other hand, each of the $2^{\binom{n-2}{2}}$ charming choices for the the roots $(i,j)$ with $1 < i < j < n$ gives rise to a distinct bijection between $\NN(\S_n)$ and $\Bal(n)$.



\section{Charmed bijections between noncrossing and nonnesting partitions}
\label{sec: the bijection}
Let $c \in \S_n$ be a Coxeter element.
Using~\Cref{prop:bal_to_nc} and~\Cref{prop: J_S bijection}, we now construct a bijection between $c$-noncrossing partitions and nonnesting partitions \emph{that depends on the choice of Coxeter element $c$}, resolving Incongruity~\eqref{it:2}.
\begin{definition}
	\label{def:bij}
	The \defn{$c$-charmed bijection} between $c$-noncrossing partitions and nonnesting partitions is given by
	\begin{align*}
		\Charm_c \colon \NC(\S_n,c) & \rightarrow \NN(\S_n)            \\
		\nc                         & \mapsto J_{\M_c}(O(\nc),I(\nc)),
	\end{align*}
	where the set $\heart_c$ of $c$-charmed roots is defined in~\Cref{def:charmed} and the map $J_{\M_c}$ is defined in \Cref{prop: J_S bijection}.
\end{definition}

\begin{theorem}
	\label{thm:charm}
	For all Coxeter elements $c$, the bijection $\Charm_c$ is the unique support-preserving bijection between $\NC(\S_n,c)$ and $\NN(\S_n)$ satisfying
	$\Krow_{c} \circ \; \Charm_{c} = \Charm_{c} \circ \Krew_{c}$.
\end{theorem}

For reasons of space, we only sketch the idea of the proof and refer the reader to the full version of this extended abstract for the details~\cite{dequene2022charmed}.   We say that a simple reflection $s$ is \defn{initial} in $c$ if $\ell_S(s c) \leq \ell_S(c)$.   If $s=s_k=(k,k+1)$ is initial in $c$, then $c' = scs$ is also a Coxeter element of $\S_n$, and we will denote this by writing $c \xrightarrow{k} c'$. \Cref{thm:charm} (and hence \Cref{thm:main_theorem}) are proven using \defn{Cambrian induction}---that is, we show that the theorem holds for a particular Coxeter element $\co$ (the \emph{base case}), and then we show that if $c \xrightarrow{k} c'$ and the theorem holds for $c$, then the theorem also holds for $c'$ (the \emph{inductive step}).  Since all Coxeter elements in $\S_n$ are conjugate by a sequence of conjugations by initial simple reflections~\cite[Lemma 1.7]{reading2007clusters}, the theorem holds for all Coxeter elements.

%\begin{remark}
%	Note that this proof technique differs from the usual Cambrian induction used in~\cite{reading2007clusters,armstrong2013uniform}: the base case of our proof is the statement for the linear Coxeter element in $\S_n$, and not the statement for the Coxeter group $\S_2$---that is, we do not need to descend to parabolic subgroups.
%\end{remark} 
%Fix the symmetric group $\S_n$, let $c$ be a Coxeter element, and let $s=s_k=(k,k+1)$ be initial in $c$. Then $c' = scs$ is also a Coxeter element of $\S_n$, and recall from~\Cref{sec:coxeter_els} that we write $c \xrightarrow{k} c'$.%

As a consequence of our proof, we obtain a simple description for reading the blocks of the noncrossing partition from the corresponding intimate family.

\begin{corollary}
	\label{cor:tails}
	Let $\L$ be an $\heart_c$-intimate family and $\nc \in \NC(\S_n,c)$ the corresponding noncrossing partition with $(\Out(\L),\In(\L))=(O(\nc),I(\nc))$. The blocks of $\nc$ consist of the integers which are connected by paths in $\L$ after reinterpreting each kiss between a pair of paths in $\L$ at a charmed root as a crossing.
\end{corollary}


%In~\Cref{sec:proof}, we will show that $\Charm_c$ is the desired bijection from the introduction. We give also an alternative description for the inverse in \Cref{cor:tails} which allows one to directly read the blocks of the noncrossing partition from the corresponding intimate family.

%\section{Proof of the main theorem}
%\label{sec:proof}

%In this section, we prove \Cref{thm:main_theorem}, which states that the bijection $\Charm_c$ from~\Cref{sec: the bijection} is the unique support-preserving bijection between noncrossing and nonnesting partitions that is equivariant with respect to $\Krew_c$ and $\Krow_c$.




\acknowledgements{B.D.~thanks the Institut des Sciences Math\'ematiques of Canada for its partial support.
G.F. was partially supported by the Canada Research Chairs program.
F.S.-A.\ acknowledges the financial support from the Austrian Science Foundation FWF, grant J 4387 and P34931.
H.T.~was partially supported by the Canada Research Chairs program and an NSERC Discovery Grant.
N.W.~was partially supported by NSF Grant No.~2246877.  Nous pr\'esentons nos excuses \`a Germain Kreweras pour notre jeu de mots.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
