%% 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]{FPSAC2023}
\articlenumber{11}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{conj}{Conjecture}
\newtheorem{prop}{Proposition}
\newtheorem{defin}{Definition}
\newtheorem{cor}{Corollary}
\newtheorem{def-prop}{Definition-Proposition}
\newtheorem{remark}{Remark}

\usepackage{mathtools,tikz}


\DeclareMathOperator{\supp}{Supp}
\DeclareMathOperator{\aut}{Aut}
\newcommand{\bs}{\boldsymbol}
\newcommand{\mc}{\mathcal}
\renewcommand{\tilde}{\widetilde}
\newcommand{\Inv}{\mathrm{Inv}}
%% define your title in the usual way
\title{Automorphisms of undirected Bruhat graphs}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Christian Gaetz, Yibo Gao]{Christian Gaetz\thanks{\href{mailto:crgaetz@gmail.com}{crgaetz@gmail.com}. C.G. was supported by a Klarman Postdoctoral Fellowship at Cornell University and by a National Science Foundation Postdoctoral Research Fellowship (DMS-2103121).}\addressmark{1},
\and Yibo Gao\thanks{\href{mailto:gaoyibo@umich.edu}{gaoyibo@umich.edu}.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Cornell University, Ithaca, NY \\ \addressmark{2}Department of Mathematics, University of Michigan, Ann Arbor, MI}

%% 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{The \emph{undirected Bruhat graph} $\Gamma(u,v)$ has the elements of the Bruhat interval $[u,v]$ as vertices, with edges given by multiplication by a reflection. Famously, $\Gamma(e,v)$ is regular if and only if the Schubert variety $X_v$ is smooth, and this condition on $v$ is characterized by pattern avoidance. In this work, we classify when $\Gamma(e,v)$ is \emph{vertex-transitive}; surprisingly this class of permutations is also characterized by pattern avoidance and sits nicely between the classes of smooth permutations and self-dual permutations. This leads us to a general investigation of automorphisms of $\Gamma(u,v)$ in the course of which we show that \emph{special matchings}, which originally appeared in the theory of Kazhdan--Lusztig polynomials, can be characterized, for the symmetric and right-angled groups, as certain $\Gamma(u,v)$-automorphisms which are conjecturally sufficient to generate the orbit of $e$ under $\aut(\Gamma(e,v))$.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Bruhat order, Bruhat graph, vertex transitive, Schubert variety, smooth}

%% 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
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

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

The \emph{(directed) Bruhat graph} $\widehat{\Gamma}$ of a Coxeter group $W$ is the directed graph with vertex set $W$ and directed edges $w \to wt$ whenever $\ell(wt)>\ell(w)$ and $t$ is a reflection. Write $\widehat{\Gamma}(u,v)$ for its restriction to a Bruhat interval $[u,v] \subset W$, and simply $\widehat{\Gamma}(v)$ for its restriction to $[e,v]$. These graphs appear ubiquitously in the combinatorics of Coxeter groups and Bruhat order \cite{dyer-bruhat-graph}, the topology of flag, Schubert, and Richardson varieties as the GKM-graph for the natural torus action \cite{GKM, guillemin-holm-zara}, and in the geometry of these varieties and related algebra, for example in the context of Kazhdan--Lusztig polynomials \cite{blundell2021towards, Brenti-combinatorial-formula, davies2021advancing, Dyer-hecke-algebras}.

In all of these contexts, the directions of the edges, and sometimes additional edge labels, are centrally important. In this work, however, we study the associated \emph{undirected} graphs $\Gamma(u,v)$ and $\Gamma(v) \coloneqq \Gamma(e,v)$. In particular, from the perspective of the undirected graph, it is very natural to study graph automorphisms (in contrast, the directed Bruhat graph $\widehat{\Gamma}$ has very few automorphisms \cite{Waterhouse}), and these automorphisms end up having close connections to previous work on smooth Schubert varieties \cite{lakshmibai-sandhya, Carrell-smoothness}, self-dual Bruhat intervals \cite{self-dual}, Billey--Postnikov decompositions \cite{billey-postnikov, richmond-slofstra-fiber-bundle}, and special matchings \cite{SM-advances}.

\subsection{Regular, vertex-transitive, and self-dual Bruhat graphs}

The following well-known theorem, combining results of Lakshmibai--Sandhya \cite{lakshmibai-sandhya} and Carrell--Peterson \cite{Carrell-smoothness}, helped establish the fundamental nature of both the Bruhat graph and pattern avoidance conditions in the combinatorial and geometric study of Schubert varieties.

\begin{thm}[Lakshmibai--Sandhya \cite{lakshmibai-sandhya}, Carrell--Peterson \cite{Carrell-smoothness}]
\label{thm:smoothness}
The following are equivalent for a permutation $w$ in the symmetric group $\mathfrak{S}_n$:
\begin{enumerate}[label={\rm(S\arabic*)}, leftmargin=*, labelindent=10pt]
    \item\label{itm:S1} the undirected Bruhat graph $\Gamma(w)$ is a regular graph,  
    \item\label{itm:S2} the permutation $w$ avoids the patterns $3412$ and $4231$, 
    \item\label{itm:S3} the poset $[e,w]$ is rank-symmetric, and
    \item\label{itm:S4} the Schubert variety $X_w$ is smooth.
\end{enumerate}
\end{thm}

In light of \ref{itm:S3}, it is natural to ask whether $[e,w]$ is in fact self-dual as a poset when $X_w$ is smooth. This turns out to not always be the case, but the smaller class of self-dual intervals also admits a nice characterization by pattern avoidance:

\begin{thm}[G.--G. \cite{self-dual}]
\label{thm:self-dual}
The following are equivalent for a permutation $w \in \mathfrak{S}_n$:
\begin{enumerate}[label={\rm(SD\arabic*)}, leftmargin=*, labelindent=10pt]
    \item\label{itm:SD1} the Bruhat interval $[e,w]$ is self-dual as a poset, and
    \item\label{itm:SD2} the permutation $w$ avoids the patterns $3412$ and $4231$ as well as $34521, 54123, 45321,$ and $54312$.
\end{enumerate}
\end{thm}

In our first main theorem here, we characterize by pattern avoidance those permutations $w$ such that $\Gamma(w)$ is \emph{vertex-transitive}; this characterization implies that this class of permutations sits nicely between the classes of self-dual permutations (\cref{thm:self-dual}) and smooth permutations (\cref{thm:smoothness}).

\begin{thm}
\label{thm:vertex-transitive}
The following are equivalent for a permutation $w \in \mathfrak{S}_n$:
\begin{enumerate}[label={\rm(VT\arabic*)}, leftmargin=*, labelindent=10pt]
    \item\label{itm:VT1} the undirected Bruhat graph $\Gamma(w)$ is a vertex-transitive graph,
    \item\label{itm:VT2} the permutation $w$ avoids the patterns $3412$ and $4231$ as well as $34521$ and $54123$.
\end{enumerate}
\end{thm}
The proof of \cref{thm:vertex-transitive} is quite technical and is omitted in this extended abstract.

Since vertex-transitive graphs are necessarily regular, it is clear that the permutations from \cref{thm:vertex-transitive} are a subset of those from \cref{thm:smoothness}, and this is borne out by comparing conditions \ref{itm:S2} and \ref{itm:VT2}. It is not at all conceptually clear, however, why the self-dual permutations of \cref{thm:self-dual} should in turn be a subset of those from \cref{thm:vertex-transitive}, even though this fact is easily seen by comparing conditions \ref{itm:VT2} and \ref{itm:SD2}. A conceptual bridge between these two classes of permutations is provided by \cref{conj:orbit-is-interval}.

\begin{conj}
\label{conj:orbit-is-interval}
Let $w \in \mathfrak{S}_n$ and let $\mc{O}=\{\varphi(e) \mid \varphi \in \aut(\Gamma(w))\}$ be the orbit of the identity under graph automorphisms of $\Gamma(w)$, then $\mc{O}=[e,v]$ for some $v \leq w$.
\end{conj}

Indeed, if $[e,w]$ is self-dual, then $w \in \mathcal{O}$, and so if \cref{conj:orbit-is-interval} holds we must have $\mathcal{O}=[e,w]$. That is, $\Gamma(w)$ must be vertex-transitive.

In the course of the proof of \cref{thm:vertex-transitive} and the refinement (see \cref{sec:orbits}) of \cref{conj:orbit-is-interval}, we are led to consider certain automorphisms of $\Gamma(u,v)$ arising from perfect matchings on the Hasse diagram of $[u,v]$. That these automorphisms are the same thing as the previously well-studied \emph{special matchings} on $[u,v]$ is the subject of our second main theorem.

\subsection{Special matchings and Bruhat automorphisms}
\emph{Special matchings} (see the definition in \cref{sec:intro-SM}) on Bruhat intervals were introduced \cite{SM-original, SM-advances} because they can be used to define a recurrence for \emph{Kazhdan--Lusztig $R$-polynomials} \cite{kazhdan-lusztig-polynomials} which allows for the resolution of the \emph{Combinatorial Invariance Conjecture} in the case of lower intervals $[e,w]$. These matchings are intended to generalize many of the combinatorial properties of the matching on $W$ induced by multiplication by a simple reflection $s$. Special matchings on Bruhat intervals and related posets have since found several other combinatorial and topological applications and been generalized in several ways \cite{SM-topology, SM-diamonds, SM-zircon}, and are completely classified on lower Bruhat intervals. \cite{SM-lower-classification}.

In \cref{thm:SM-equals-automorphism-classical-type} and \cref{conj:SM-equals-automorphism-general} below we give a new characterization of special matchings of Bruhat intervals $[u,v]$ in terms of automorphisms of $\Gamma(u,v)$. This characterization is notable because it expresses the special matching condition, originally formulated as a condition only on Bruhat covers, as a condition on the global structure of the undirected Bruhat graph.

A Coxeter group $W$ is called \emph{right-angled} if every pair of simple generators either commutes or generates an infinite dihedral group.

\begin{thm}
\label{thm:SM-equals-automorphism-classical-type}
Let $W$ be a right-angled Coxeter group or the symmetric group and let $u \leq v$ be elements of $W$. Then a perfect matching of the Hasse diagram of $[u,v]$ is a special matching if and only if it is an automorphism of $\Gamma(u,v)$. 
\end{thm}

\begin{conj}
\label{conj:SM-equals-automorphism-general}
\cref{thm:SM-equals-automorphism-classical-type} holds for arbitrary Coxeter groups $W$.
\end{conj}

\subsection{Outline}

In \cref{sec:background}, we cover background and definitions relating to Coxeter groups, Bruhat order and Bruhat graphs, Billey--Postnikov decompositions, and special matchings. In \cref{sec:orbits} we give a more precise version of \cref{conj:orbit-is-interval} in terms of \emph{almost reducible decompositions} and some partial results towards resolving the conjecture. \cref{sec:auto-to-special-matchings} outlines the proof of  \cref{thm:SM-equals-automorphism-classical-type}. The proof of \cref{thm:SM-equals-automorphism-classical-type} relies on a structural property of Bruhat order, the existence of upper bounds of \emph{butterflies}, which may be of independent interest.
Most of the proofs are omitted for this extended abstract, notably including those of \cref{thm:vertex-transitive}, \cref{thm:commute-pairwise}, \cref{prop:confirm-conj-for-vt}, \cref{lem:butterfly} and \cref{lem:simply-laced-join}. Readers may refer to \cite{VT-original} for additional details.
\section{Background and definitions}
\label{sec:background}

\subsection{Bruhat graphs and Bruhat order}

The \emph{directed Bruhat graph} $\widehat{\Gamma}$ of a Coxeter group $W$ is the directed graph with vertex set $W$ and directed edges $w \to wt$ whenever $t$ is a reflection with $\ell(wt)>\ell(w)$. Note that, since $T$ is closed under conjugation, the ``left" and ``right" versions of $\widehat{\Gamma}$ in fact coincide. The \emph{(undirected) Bruhat graph} $\Gamma$ is the associated simple undirected graph.  The directed graph $\widehat{\Gamma}$ is much more commonly considered in the literature, and often called ``the Bruhat graph" but, since our focus in this work is on the undirected graph $\Gamma$, when directedness is not specified we mean the undirected graph.

The \emph{(strong) Bruhat order} $(W,\leq)$ is the partial order on $W$ obtained by taking the transitive closure of the relation determined by $\widehat{\Gamma}$. We write $[u,v]$ for the interval $\{w \in W \mid u \leq w \leq v\}$ in Bruhat order. For $u \leq v$, we write $\widehat{\Gamma}(u,v)$ and $\Gamma(u,v)$ for the restrictions of $\widehat{\Gamma}, \Gamma$ to the vertex set $[u,v]$; when $u$ is the identity element $e$, we sometimes write simply $\widehat{\Gamma}(v)$ and $\Gamma(v)$.

Fundamental properties of Bruhat order can be found in \cite{bjorner-brenti}.


For $w \in W$, we write $\supp(w)$ for the \emph{support} of $w$: the set of simple reflections appearing in some (equivalently, every) reduced word for $w$. We say the element $w\in W$ has a \emph{disjoint support decomposition} if it may be expressed as a nontrivial product $w=w'w''$ with $\supp(w') \cap \supp(w'') = \emptyset$ (note that, in this case, we have $w'=w^J$ and $w''=w_J$ with $J=\supp(w'')$). 

\begin{prop}
\label{prop:disjoint-support}
Let $w=w'w''$ be a disjoint support decomposition, then:
\begin{align*}
    \widehat{\Gamma}(w) &\cong \widehat{\Gamma}(w') \times \widehat{\Gamma}(w''), \\
    \Gamma(w) &\cong \Gamma(w') \times \Gamma(w''),\\
    [e,w] &\cong [e,w'] \times [e,w'']. 
\end{align*}
In each case, the isomorphism is given by group multiplication.
\end{prop}

\cref{prop:disjoint-support} implies that when $w=w'w''$ is a disjoint support decomposition, $\Gamma(w),\widehat{\Gamma}(w),$ and $[e,w]$ have automorphisms induced by automorphisms for $w',w''$.

\subsection{Billey--Postnikov decompositions}

\begin{defin}[Billey--Postnikov \cite{billey-postnikov}, Richmond--Slofstra \cite{richmond-slofstra-fiber-bundle}]
\label{def:BP-decomposition}
Let $W$ be a Coxeter group and $J \subseteq S$, the parabolic decomposition $w=w^Jw_J$ of $w$ is a \emph{Billey--Postnikov decomposition} or \emph{BP-decomposition} if
\[
\supp(w^J) \cap J \subseteq D_L(w_J).
\]
\end{defin}

BP-decompositions were introduced by Billey and Postnikov in \cite{billey-postnikov} in the course of their study of pattern avoidance criteria for smoothness of Schubert varieties in all finite types. The following characterizations of BP-decompositions will be useful to us.

\begin{prop}[Richmond--Slofstra \cite{richmond-slofstra-fiber-bundle}]
\label{prop:BP-equivalences}
For $w \in W$ and $J \subseteq S$, the following are equivalent:
\begin{enumerate}
    \item $w=w^Jw_J$ is a BP-decomposition,
    \item the multiplication map $\left( [e,w^J] \cap W^J \right) \times [e,w_J] \to [e,w]$ is a bijection,
    \item $w_J$ is the maximal element of $W_J \cap [e,w]$.
\end{enumerate}
\end{prop}

\subsection{Special matchings}
\label{sec:intro-SM}

The \emph{Hasse diagram}, denoted $H(P)$, of a poset $P$ is the undirected graph with vertex set $P$ and edges $(x,y)$ whenever $x \lessdot_P y$ is a cover relation in $P$. Note that the Hasse diagram $H(W)$ of Bruhat order on $W$ is a (non-induced) subgraph of $\Gamma$. A \emph{perfect matching} of a graph $G$ is a fixed-point-free involution $M:G \to G$ such that $(x,M(x))$ is an edge of $G$ for all $x \in G$.

\begin{defin}[Brenti \cite{SM-original}, Brenti--Caselli--Marietti \cite{SM-advances}]
\label{def:special-matching}
A perfect matching $M$ on the Hasse diagram of a poset $P$ is a \emph{special matching} if, for every cover relation $x \lessdot_P y$, either $M(x)=y$ or $M(x) <_P M(y)$.
\end{defin}

For $u \leq v \in W$ it is not hard to check, using the Lifting Property, that for $s \in D_L(v) \setminus D_L(u)$ (resp. $s \in D_R(v) \setminus D_R(u)$) left (resp. right) multiplication by $s$ determines a special matching of the Hasse diagram $H([u,v])$. In fact, this motivated the definition of special matching \cite{SM-original}. \cref{prop:middle-mult-is-special-matching} below, a special case of the classification by Caselli and Marietti \cite{SM-first-lower-classification, SM-lower-classification} of special matchings of lower Bruhat interval, observes that \emph{middle multiplication} is also a special matching for lower intervals. 

\begin{prop}[Special case of Theorem 5.1 in \cite{SM-first-lower-classification}]
\label{prop:middle-mult-is-special-matching}
Suppose $w=w^Jw_J$ is a BP-decom\-position of $w$ and in addition we have $\supp(w^J) \cap \supp(w_J) =\{s\}$, then the middle multiplication map 
\[
\phi: x \mapsto x^J s x_J, 
\]
is a special matching of $[e,w]$.
\end{prop}


\subsection{From special matchings to Bruhat automorphisms}
\label{sec:automorphisms}
The following result of Waterhouse shows that $\widehat{\Gamma}$ has no nontrivial automorphisms as a directed graph.

\begin{thm}[Waterhouse \cite{Waterhouse}]
Let $W$ be an irreducible Coxeter group which is not dihedral, then $\aut((W,\leq))$ (equivalently, $\aut(\widehat{\Gamma})$) is generated by the graph automorphisms of the Dynkin diagram of $W$ and the group inversion map on $W$.
\end{thm}

In this paper we study the much richer sets of automorphisms of $\Gamma$ and particularly of its subgraphs $\Gamma(u,v)$. Although it is stated only for lower intervals $[e,v]$, the proof of Theorem 10.3 in \cite{SM-advances} also applies to general intervals $[u,v]$ and yields \cref{thm:SM-implies-auto} below:

\begin{thm}[Theorem 10.3 of \cite{SM-advances}]
\label{thm:SM-implies-auto}
Let $u \leq v$ be elements of a Coxeter group $W$. Any special matching $M$ of the Hasse diagram $H([u,v])$ is an automorphism of $\Gamma(u,v)$. 
\end{thm}

\begin{cor}
\label{cor:RL-middle-mult-give-autos}
Let $w \in W$. If $s \in D_L(w)$ (resp. $D_R(w)$) then left (resp. right) multiplication by $s$ is an automorphism of $\Gamma(w)$. If $w=w^J w_J$ is a BP-decomposition of $w$ with $\supp(w^J) \cap \supp(w_J) =\{s\}$, then middle multiplication by $s$ is an automorphism of $\Gamma(w)$. 
\end{cor}

\cref{thm:SM-implies-auto} provides one direction of \cref{thm:SM-equals-automorphism-classical-type} and \cref{conj:SM-equals-automorphism-general} for arbitrary Coxeter groups. This implies that special matchings on Bruhat intervals, although defined by a local condition (that is, a condition on cover relations), respect the global structure of Bruhat graphs. The reverse direction is the subject of \cref{sec:auto-to-special-matchings}.

\section{Identity orbits in Bruhat graphs}
\label{sec:orbits}
We describe a more precise version of \cref{conj:orbit-is-interval}, taking into account the automorphisms described in \cref{sec:automorphisms} and \cref{thm:vertex-transitive}. In light of \cref{prop:disjoint-support}, it is sufficient to consider permutations $w \in \mathfrak{S}_n$ which have full support and do not admit a disjoint support decomposition; we call such permutations \emph{Bruhat irreducible}.

\begin{defin}
\label{def:almost-reducible}
A Bruhat irreducible permutation $w\in \mathfrak{S}_n$ is \emph{almost reducible} at $(J,i)$ if $w=w^Jw_J$ is a BP-decomposition with $\supp(w^J) \cap J = \{s_i\}$ and $s_i\notin D_L(w),D_R(w)$.
\end{defin}

\begin{def-prop}
If a Bruhat irreducible $w\in \mathfrak{S}_n$ is almost reducible at $(J,i)$, then $J=\{s_1,\ldots,s_i\}$ or $\{s_i,\ldots,s_{n-1}\}$. We say it is \emph{left-almost-reducible} at $i$ if $J=\{s_1,\ldots,s_i\}$, and \emph{right-almost-reducible} at $i$ if $J=\{s_i,\ldots,s_{n-1}\}$.
\end{def-prop}


\begin{defin}
For a Bruhat irreducible permutation $w \in \mathfrak{S}_n$, let 
\[
\{i_1<\cdots<i_k\} = \{i \mid \text{$w$ is right-almost-reducible at $i$}\}
\]
and define $A_R(w):=s_{i_1}\cdots s_{i_k}$. Similarly, let $\{j_1<\cdots<j_t\}$ be the set of $j$ at which $w$ is left-almost-reducible and define $A_L(w):=s_{j_t}\cdots s_{j_1}.$
\end{defin}

\begin{thm}\label{thm:commute-pairwise}
Let $w$ be Bruhat irreducible. Then the following three elements commute pairwise: \[A_R(w),A_L(w),w_0(D_L(w)\cap D_R(w)).\]
\end{thm}

The following is a strengthened version of \cref{conj:orbit-is-interval}.

\begin{conj}
\label{conj:strengthened-orbit-conjecture}
Let $w \in \mathfrak{S}_n$ be Bruhat irreducible and let $\mc{O}$ denote the orbit of $e$ under graph automorphisms of $\Gamma(w)$. Define
\[
v(w) \coloneqq w_0(D_L(w))\cdot A_R(w) \cdot w_0(D_L(w)\cap D_R(w)) \cdot A_L(w)\cdot w_0(D_R(w)),
\]
then $\mc{O}=[e,v(w)]$. 
\end{conj}

\begin{prop}
\label{prop:confirm-conj-for-vt}
Let $w \in \mathfrak{S}_n$ be Bruhat irreducible and such that $\Gamma(w)$ is vertex-transitive, then $v(w)=w$, so \cref{conj:strengthened-orbit-conjecture} holds in this case.
\end{prop}

The following proposition shows that the element $v(w)$ is indeed in the identity orbit of $\Gamma(w)$. An automorphism of $\Gamma(w)$ sending $e$ to $v(w)$ may be obtained by composing various left, right, and middle multiplication automorphisms (see \cref{sec:automorphisms}).

\begin{prop}
\label{prop:v-is-in-orbit}
Let $w \in \mathfrak{S}_n$ be Bruhat irreducible and let $\mc{O}$ be the orbit of $e$ under graph automorphisms of $\Gamma(w)$, then $v(w) \in \mc{O}$.
\end{prop}


\section{From Bruhat automorphisms to special matchings via butterflies}
\label{sec:auto-to-special-matchings}

In \cref{thm:auto-implies-SM} below we give a converse to \cref{thm:SM-implies-auto} for certain Coxeter groups. \cref{thm:SM-implies-auto} and \cref{thm:auto-implies-SM} together imply \cref{thm:SM-equals-automorphism-classical-type}.

\begin{thm}
\label{thm:auto-implies-SM}
Let $u \leq v$ be elements of a Coxeter group $W$ which is right-angled or a symmetric group, then any perfect matching of $H([u,v])$ which is an automorphism of $\Gamma(u,v)$ is a special matching.
\end{thm}

The proof of \cref{thm:auto-implies-SM} relies on \cref{lem:butterfly}, a structural property of Bruhat order involving \emph{butterflies}. 

\begin{defin}\label{def:butterfly}
We say that elements $x_1,x_2,y_1,y_2$ of a Coxeter group $W$ form a \emph{butterfly} if $x_1 \lessdot y_1,y_2$ and $x_2 \lessdot y_1,y_2$.
\end{defin}
The butterfly structures are essential to the analysis of Bruhat automorphisms and special matchings, and are of interest on their own.

\begin{lem}
\label{lem:butterfly}
Let $W$ be a Coxeter group which is right-angled or the symmetric group, and suppose that $x_1,x_2,y_1,y_2 \in [u,v]$ form a butterfly. Then there is an element $z \in [u,v]$ with $y_1,y_2 \lessdot z$.  
\end{lem}

\begin{proof}[Proof of \cref{thm:auto-implies-SM} given \cref{lem:butterfly}]
Let $u \leq v$ be elements of a Coxeter group $W$ which is right-angled or the symmetric group, and let $M$ be a perfect matching of $H([u,v])$ which is an automorphism of $\Gamma(u,v)$. Suppose that $M$ is not a special matching; since $M$ is a $\Gamma(u,v)$-automorphism, the violation of the special matching property must consist of elements $x \lessdot y$ with $M(y) \lessdot M(x)$. Choose $x,y$ so that $y$ has maximal length among all such violations in $[u,v]$. 

Now, note that $x,M(y),y,M(x)$ form a butterfly, so by \cref{lem:butterfly} there exists an element $z \in [u,v]$ with $y,M(x) \lessdot z$. We must have $M(z)>z$, for otherwise each of $y,M(x),$ and $M(z)$ would each cover both $x$ and $M(y)$, but this substructure cannot occur in Bruhat order of a Coxeter group (see Theorem 3.2 of \cite{SM-advances}). Since height-two intervals in Bruhat order are diamonds (see Chapter 2 of \cite{bjorner-brenti}), there exists an element $w\neq z$ with $y \lessdot w \lessdot M(z)$.

Suppose that $M(w)<w$, then since $M$ is an automorphism of the Bruhat graph we must have $M(w) \lessdot z$ and $M(y) \lessdot M(w)$. Now, since $y \lessdot z$, we know $M(y) \to M(z)$ in $\widehat{\Gamma}(u,v)$, but the height-three interval $[M(y),M(z)]$ contains at least three elements---$y,M(w),$ and $M(x)$ at height one, contradicting Proposition 3.3 of \cite{dyer-bruhat-graph}.

We conclude that $w\lessdot M(w)$. However this too is a contradiction, since $w \lessdot M(z)$ is a violation of the special matching condition with $\ell(M(z))>\ell(y)$. Thus $M$ must be a special matching.
\end{proof}

We conjecture that a slight weakening of \cref{lem:butterfly} holds for arbitrary Coxeter groups.

\begin{conj}
\label{conj:general-butterfly}
Let $W$ be any Coxeter group, and suppose that the elements $x_1,x_2,y_1,y_2 \in [u,v]$ form a butterfly. Then there is an element $z \in [u,v]$ with $y_1,y_2 \lessdot z$ or with $z \lessdot x_1,x_2$.
\end{conj}

\begin{remark}
The weakening of \cref{lem:butterfly} conjectured for general Coxeter groups in \cref{conj:general-butterfly} is necessary even for finite Coxeter groups. For example, the finite Coxeter group of type $F_4$ has a butterfly:
\begin{align*}
    x_1 &= s_2 s_3 s_4 s_2 s_3 s_1 s_2 s_3 s_4 s_3s_2s_3s_1s_2s_3s_1s_2, \\
    x_2 &=
s_3s_2s_3s_4s_3s_2s_3s_1s_2s_3s_4s_2s_3s_1s_2s_3s_2, \\
    y_1&=
s_2s_3s_1s_2s_3s_4s_3s_2s_3s_1s_2s_3s_4s_2s_3s_1s_2s_3, \\
    y_2 &=
s_3s_2s_3s_4s_3s_2s_3s_1s_2s_3s_4s_2s_3s_1s_2s_3s_1s_2,
\end{align*}
which has a lower bound $z=s_2s_3s_4s_2s_3s_1s_2s_3s_4s_3s_2s_3s_1s_2s_3s_2 \lessdot x_1,x_2$ but no upper bound $y_1,y_2 \lessdot z'$. See \cref{fig:F4} for a Bruhat interval that contains $z\lessdot x_1,x_2\lessdot y_1,y_2$.
\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=0.7]
\draw(1.5,-1)--(0,0);
\draw(1.5,-1)--(1,0);
\draw(1.5,-1)--(2,0);
\draw(1.5,-1)--(3,0);
\draw(1.5,3)--(0,2);
\draw(1.5,3)--(1,2);
\draw(1.5,3)--(2,2);
\draw(1.5,3)--(3,2);
\draw(0,0)--(-1,1)--(1,0);
\draw[red,thick](0,0)--(0,1)--(2,0);
\draw[red,thick](0,0)--(1,1)--(2,0);
\draw(1,0)--(2,1)--(2,0);
\draw(0,0)--(3,1)--(3,0);
\draw(2,0)--(4,1)--(3,0);
\draw(0,2)--(-1,1)--(1,2);
\draw(0,2)--(0,1)--(2,2);
\draw(1,2)--(1,1)--(3,2);
\draw(0,2)--(2,1)--(1,2);
\draw(2,2)--(3,1)--(3,2);
\draw(2,2)--(4,1)--(3,2);
\node at (1.5,-1) {$\bullet$};
\node at (0,0) {$\bullet$};
\node at (1,0) {$\bullet$};
\node at (2,0) {$\bullet$};
\node at (3,0) {$\bullet$};
\node at (-1,1) {$\bullet$};
\node at (0,1) {$\bullet$};
\node at (1,1) {$\bullet$};
\node at (2,1) {$\bullet$};
\node at (3,1) {$\bullet$};
\node at (4,1) {$\bullet$};
\node at (0,2) {$\bullet$};
\node at (1,2) {$\bullet$};
\node at (2,2) {$\bullet$};
\node at (3,2) {$\bullet$};
\node at (1.5,3) {$\bullet$};
\node[left] at (0,0) {$x_1$};
\node[right] at (2,0) {$x_2$};
\node[left] at (0,1) {$y_1$};
\node[right] at (1,1) {$y_2$};
\node[left] at (1.5,-1) {$z$};
\end{tikzpicture}
\caption{A butterfly in $F_4$ which does not admit an upper bound.}
\label{fig:F4}
\end{figure}
\end{remark}

We end with a few more structural results concerning butterflies, in the setting of finite Weyl groups.
\begin{lem}\label{lem:weyl-cover}
In a finite Weyl group, $w\lessdot ws_{\alpha}$ if and only if $\alpha\notin\Inv_R(w)$ and there does not exist $\beta_1,\beta_2\in\Inv_R(w)$ such that $\beta_2=-s_{\alpha}\beta_1$. Moreover, if $w\lessdot ws_{\alpha}$ and $\beta\in\Phi^+$ satisfies $s_{\alpha}\beta\in\Phi^-$, then $\beta\in\Inv_R(w)$ if and only if $\beta\in\Inv_R(ws_{\alpha})$.
\end{lem}
\begin{lem}\label{lem:simply-laced-join}
Let $W$ be a finite Weyl group of simply-laced type, and let $x_1,x_2\lessdot y_1,y_2$ form a butterfly. Then there exists $u\lessdot x_1,x_2$ and $z\gtrdot y_1,y_2$ in $W$.
\end{lem}


\acknowledgements{We are very grateful to Thomas Lam and Grant Barkley for their helpful comments and suggestions. We also wish to thank Mario Marietti for alerting us to important references.}

%% 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}
