%% 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]{FPSAC2020}
\articlenumber{7}
\addbibresource{fpsac.bib}
%% 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}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{conj}[theorem]{Conjecture}
\crefname{theorem}{Theorem}{Theorems}
\crefname{conj}{Conjecture}{Conjectures}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{quest}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\crefname{example}{Example}{Examples}


\DeclareMathOperator{\spn}{span}

\usepackage{todonotes}

%% define your title in the usual way
\title[Separable elements of Weyl groups]{Separable elements: linear extensions, graph associahedra, and splittings of Weyl groups}

%% 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 \thanks{\href{mailto:gaetz@mit.edu}{gaetz@mit.edu}. Partially supported by the National Science Foundation Graduate Research
Fellowship under Grant No. 1122374.}\addressmark{1} \and Yibo Gao \thanks{\href{mailto:gaoyibo@mit.edu}{gaoyibo@mit.edu}.} \addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA}

%% 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{We introduce \emph{separable elements} in finite Weyl groups, generalizing the well-studied class of separable permutations.  We prove that the principal upper and lower order ideals in weak Bruhat order generated by a separable element are rank-symmetric and rank-unimodal, and that the product of their rank generating functions equals that of the whole group, answering an open problem of Fan Wei (2012), who proved this result in type $A$.

We prove that the multiplication map $W/V \times V \to W$ for a generalized quotient of the symmetric group is always surjective when $V$ is an order ideal in right weak order; interpreting these sets of permutations as linear extensions of 2-dimensional posets gives the first direct combinatorial proof of an inequality due originally to Sidorenko in 1991, answering an open problem Morales, Pak, and Panova.  We show that this multiplication map is a bijection if and only if $V$ is an order ideal in right weak order generated by a separable element, thereby classifying those generalized quotients which induce \emph{splittings} of the symmetric group, answering a question of Bj\"{o}rner and Wachs (1988).  All of these results are conjectured to extend to arbitrary finite Weyl groups.

Next, we show that separable elements in $W$ are in bijection with the faces of all dimensions of two copies of the graph associahedron of the Dynkin diagram of $W$.  This correspondence associates to each separable element $w$ a certain \emph{nested set}; we give elegant product formulas for the rank generating functions of the principal upper and lower order ideals generated by $w$ in terms of these nested sets.

Finally we show that separable elements, although initially defined recursively, have a non-recursive characterization in terms of root system pattern avoidance in the sense of Billey and Postnikov.
}



%% 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{Weyl group, generalized quotient, linear extension, weak Bruhat order, associahedra, separable permutation, pattern avoidance}

%% 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, ie. [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
%% 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{Background and definitions} \label{sec:background}

This section consists of background and definitions relating to root systems, Weyl groups, and the weak Bruhat order; all of this material is standard and most may be found, for example, in \cite{Bjorner-Brenti}.

Throughout the paper, $\Phi$ will denote a finite, crystallographic root system with chosen set of simple roots $\Delta$ and corresponding set of positive roots $\Phi^+$.  We freely use the well-known Cartan-Killing classification of irreducible root systems into types $A_n, B_n, C_n, D_n, G_2, F_4, E_6, E_7$, and $E_8$.

The \emph{root poset} is the partial order $(\Phi^+, \leq)$ where $\beta \leq \beta'$ if $\beta'-\beta$ is a nonnegative sum of simple roots.

We write $s_{\alpha}$ for the simple reflection across the hyperplane orthogonal to the simple root $\alpha \in \Delta$, and $W(\Phi)$ for the Weyl group, which is generated by the simple reflections.  Given an element $w\in W(\Phi)$, its \emph{length} $\ell(w)$ is defined to be the smallest $\ell$ such that $w=s_{\alpha_1} \cdots s_{\alpha_{\ell}}$ for some sequence of simple reflections.  The \emph{inversion set} of $w$ is: 
\[
I_{\Phi}(w) = \{ \beta \in \Phi^+ \: | \: w\beta \in \Phi^-\}.
\]
It is well-known that $\ell(w)=|I_{\Phi}(w)|$ and that $W(\Phi)$ has a unique element $w_0$ of maximal length; $w_0$ is an involution and has $I_{\Phi}(w_0)=\Phi^+$.  Inversions $\beta$ which are simple roots are called \emph{descents}.

\begin{proposition} \label{prop:biconvex}
Elements $w \in W(\Phi)$ are uniquely determined by their inversion sets, and $S \subseteq \Phi^+$ is the inversion set of some element if and only if it is \emph{biconvex}:
\begin{itemize}
    \item For each pair $\alpha, \beta \in S$, if $\alpha + \beta \in \Phi^+$, then $\alpha + \beta \in S$, and
    \item If $\gamma \in S$ and $\gamma = \alpha + \beta$ with $\alpha, \beta \in \Phi^+$, then at least one of $\alpha, \beta$ must be in $S$.
\end{itemize}
\end{proposition}

The \emph{left weak order} (sometimes called the \emph{left weak Bruhat order}) on $W(\Phi)$ is determined by its cover relations: $w \lessdot_L s_{\alpha}w$ whenever $\ell(s_{\alpha}w)=\ell(w)+1$.  The \emph{right weak order} is defined analogously, except with right multiplication by $s_{\alpha}$.  All Weyl groups are assumed to be ordered by left weak order unless otherwise specified.  It is a nontrivial fact that the weak orders are lattices.  We denote the lattice operations of join and meet by $\lor$ and $\land$ respectively, with superscripts $L$ or $R$ to indicate either the left or right weak order.

\begin{proposition} \label{prop:weak-given-by-inversions}
The left weak order on $W(\Phi)$ is given by containment of inversion sets, that is: $u \leq_L w$ if and only if $I_{\Phi}(u) \subseteq I_{\Phi}(w)$.
\end{proposition}

The map $w \mapsto w^{-1}$ defines a poset isomorphism between left and right weak orders.  Each has a unique minimal element $e$, the group identity element, and $w_0$ as its unique maximal element, called the \emph{longest element}.  Both left and right multiplication by $w_0$ determine poset anti-automorphisms of both left and right weak order.  We note that $I_{\Phi}(w_0w)=\Phi^+ \setminus I_{\Phi}(w)$.

If $W=W(\Phi)$ is a Weyl group with simple roots $\Delta$, and $J \subseteq \Delta$, we let $W_J$ denote the \emph{parabolic subgroup} of $W$ generated by $\{s_{\alpha}\}_{\alpha \in J}$.  The \emph{parabolic quotient} $W^J$ is the set of elements of $W$ with no descents in $J$.  We let $\Phi_J$ be the root system of those roots in $\Phi$ which are linear combinations of elements of $J$.

\begin{proposition} \label{prop:parabolic-quotient}
Let $W=W(\Phi)$ and let $J \subseteq \Delta$, then:
\begin{itemize}
    \item $W^J$ forms a system of coset representatives for $W_J$ in $W$; in particular, each $w \in W$ has a unique expression $w=w^J w_J$ with $w^J \in W^J$ and $w_J \in W_J$.  For each $J$, by taking $w=w_0$ this expression determines important elements $w_0^J$ and $w_{0,J}$.
    \item $W^J=[e,w_0^J]_L$ and $W_J=[e,w_{0,J}]_L=[e,w_{0,J}]_R$.
    \item The elements of $W^J$ are the unique elements of minimal length in their $W_J$-cosets, and the above expression for $w$ is \emph{length-additive}: $\ell(w)=\ell(w^J)+\ell(w_J)$.
\end{itemize}
\end{proposition}

Let $\Phi$ be a root system with positive roots $\Phi^+$.  A subset $\Phi' \subset \Phi$ is a \emph{subsystem} of $\Phi$ if $\Phi'=\Phi \cap U$ for some linear subspace $U$ of $\spn(\Phi)$.  It is clear that any such $\Phi'$ is itself a root system.  The following generalization of pattern avoidance to finite Weyl groups was introduced by Billey and Postnikov \cite{Billey2005Smoothness}.  For $w \in W(\Phi)$, we say $w$ \emph{contains the pattern} $(w',\Phi')$ if $I_{\Phi}(w)\cap U = I_{\Phi'}(w')$; we write $w|_{\Phi'}=w'$ in this case.  If $\Phi'$ is the set of roots in the span of $J \subseteq \Delta$ then $w|_{\Phi'}=w_J$, if we identify $W(\Phi')$ with $W_J$ in the natural way; note, however, that many subsystems are not of this form.  We say $w$ \emph{avoids} $(w',\Phi')$ if it does not contain any pattern isomorphic to $(w',\Phi')$.

A ranked poset $P=P_0 \sqcup P_1 \sqcup \cdots \sqcup P_r$ (such as the left or right weak order on a Weyl group, which are ranked by length) is \emph{rank-symmetric} if $|P_i|=|P_{r-i}|$ for all $i$, and \emph{rank-unimodal} if $|P_0|\leq \cdots \leq |P_j| \geq \cdots \geq |P_r|$ for some $j$.  Its \emph{rank generating function} $P(q)$ is $\sum_{i=0}^r |P_i| q^i$.  It is well known that $W_J$ and $W^J$ are rank-symmetric and rank-unimodal for all $J \subseteq \Delta$, and \cref{prop:parabolic-quotient} implies that 
\begin{equation} \label{eq:parabolic-product}
W^J(q)W_J(q)=W(q).
\end{equation}
Finally, we let $\Lambda^L_w=[e,w]_L$ and $V^L_w=[w,w_0]_L$ denote the principal lower and upper ideals respectively in left weak order, and similarly for right weak order; we sometimes suppress the decorations $L$ or $R$ if a claim works just as well in either left or right weak order.  We make the convention that the rank function on $V_w$ is the natural one viewing $V_w$ as a poset in its own right: an element $u$ of $V_w$ has rank $\ell(u)-\ell(w)$.

\section{Separable elements of Weyl groups} \label{sec:separable}

A permutation $w=w_1\ldots w_n$ is \emph{separable} if it avoids the patterns 3142 and 2413, meaning that there are no indices $i_1<i_2<i_3<i_4$ such that the values $w_{i_1}w_{i_2}w_{i_3}w_{i_4}$ are in the same relative order as 3142 or 2413.  This well-studied class of permutations arose in the study of pop-stack sorting \cite{Avis} and has found applications in algorithmic pattern matching and bootstrap percolation.  These permutations have a remarkable recursive combinatorial structure and are enumerated by the Schr\"{o}der numbers. 

Fan Wei \cite{Wei2012Product} showed that if $w$ is a separable permutation in the symmetric group $S_n$, then $\Lambda_w$ and $V_w$ are rank-symmetric and rank-unimodal, and the product of their rank generating functions is $[n]_q !=S_n(q)$.  

We now introduce a definition of a separable element in any finite Weyl group.  This definition coincides exactly with separable permutations in the case of the symmetric group, although this is only made clear by the results of \cref{sec:pattern-section}, where separable elements are characterized by root system pattern avoidance \footnote{The material in \cref{sec:separable,sec:pattern-section} appears in \cite{First-separable-paper} and the remainder of the material is contained in \cite{Second-separable-paper}, both by the authors.}.  \cref{thm:bijection-to-faces} in \cref{sec:associahedra} gives another characterization of separable elements.

\begin{definition} \label{def:separable}
Let $w\in W(\Phi)$. Then $w$ is \textit{separable} if one of the following holds:
\begin{enumerate}
\item $\Phi$ is of type $A_1$;
\item $\Phi=\bigoplus\Phi_i$ is reducible and $w|_{\Phi_i}$ is separable for each $i$;
\item $\Phi$ is irreducible and there exists a \textit{pivot} $\alpha_i\in\Delta$ such that $w|_{\Phi_J}\in W(\Phi_J)$ is separable where $\Phi_J$ is generated by $J=\Delta\setminus\{\alpha_i\}$ and such that either 
\begin{align*}
    & \{\beta\in\Phi^+:\beta\geq\alpha_i\}\subset I_{\Phi}(w), \text{ or} \\
    & \{\beta\in\Phi^+:\beta\geq\alpha_i\}\cap I_{\Phi}(w)=\emptyset.
\end{align*}
\end{enumerate}
This notion is well-defined, since, in cases (2) and (3), we reduce to a subsystem of strictly smaller rank.
\end{definition}

\begin{example} \label{ex:sep-in-B4}
Let $\Phi=\{\pm e_i \pm e_j \: | \: 1 \leq i < j \leq 4\} \sqcup \{\pm e_i \: | \: 1 \leq i \leq 4\}$ be the root system of type $B_4$, where the $e_i$ are the standard basis elements in $\mathbb{R}^4$; let $\alpha_1=e_1-e_2$, $\alpha_2=e_2-e_3$, $\alpha_3=e_3-e_4$, and $\alpha_4=e_4$ denote the simple roots.  Let $w \in W(\Phi)$ be the element whose inversion set $I_{\Phi}(w) \subseteq \Phi^+$ is indicated in \cref{fig:B4}.  Then we can conclude $w$ is separable as follows:
\begin{itemize}
    \item First, by the first case in \cref{def:separable} (3), we see that $\alpha_3$ is a pivot since all $\beta \geq \alpha_3$ are in the inversion set.
    \item Now we reduce to checking that $w|_{\Phi_J}$ is separable, with $J=\Delta \setminus \{\alpha_3\}=\{\alpha_1, \alpha_2, \alpha_4\}$.  Notice $\Phi_J = \Psi_1 \oplus \Psi_2$ is reducible, with $\Psi_1^+=\{\alpha_1, \alpha_2, \alpha_1+\alpha_2\}$ and $\Psi_2^+=\{\alpha_4\}$, so by part (2), we need to show that $w|_{\Psi_1}$ and $w|_{\Psi_2}$ are separable.  Since $\Psi_2$ is of type $A_1$, $w|_{\Psi_2}$ is separable by part (1) of the definition.  
    \item Finally, $w|_{\Psi_1}$ has a pivot $\alpha_1$, this is a pivot of the second kind, since neither $\alpha_1$ nor $\alpha_1+\alpha_2$ is an inversion.  We then reduce to the type $A_1$ subsystem spanned by $\alpha_2$, and we are done by part (1) of the definition.
\end{itemize}
\end{example}

\begin{figure}[ht]
    \begin{center}
    \begin{tikzpicture}[scale=0.7]
    \node[draw,shape=circle,fill=white,scale=0.5](a)[label=below: {$\alpha_1$}] at (-4,0) {};
    \node[draw,shape=circle,fill=black,scale=0.5](b)[label=below: {$\alpha_2$}] at (-2,0) {};
    \node[draw,shape=circle,fill=black,scale=0.5](c)[label=below: {$\alpha_3$}] at (0,0) {};
    \node[draw,shape=circle,fill=white,scale=0.5](d)[label=below: {$\alpha_4$}] at (2,0) {};
    
    \node[draw,shape=circle,fill=white,scale=0.5](e)[label=left: {$\alpha_1+\alpha_2$}] at (-3,1) {};
    \node[draw,shape=circle,fill=black,scale=0.5](f) at (-1,1) {};
    \node[draw,shape=circle,fill=black,scale=0.5](g) at (1,1) {};
    
    \node[draw,shape=circle,fill=black,scale=0.5](h) at (-2,2) {};
    \node[draw,shape=circle,fill=black,scale=0.5](i) at (0,2) {};
    \node[draw,shape=circle,fill=black,scale=0.5](j) at (2,2) {};
    
    \node[draw,shape=circle,fill=black,scale=0.5](k) at (-1,3) {};
    \node[draw,shape=circle,fill=black,scale=0.5](l) at (1,3) {};
    
    \node[draw,shape=circle,fill=black,scale=0.5](m) at (0,4) {};
    \node[draw,shape=circle,fill=black,scale=0.5](n) at (2,4) {};
    
    \node[draw,shape=circle,fill=black,scale=0.5](o) at (1,5) {};
    
    \node[draw,shape=circle,fill=black,scale=0.5](p) at (2,6) {};
    
    \draw (a)--(e)--(b)--(f)--(c)--(g)--(d);
    \draw (e)--(h)--(f)--(i)--(g)--(j);
    \draw (h)--(k)--(i)--(l)--(j);
    \draw (k)--(m)--(l)--(n);
    \draw (m)--(o)--(n);
    \draw (o)--(p);
    
    %\draw[dashed] (-5,-.5)--(3,-.5)--(-1,3.5)--(-5,-.5);
    
    \end{tikzpicture}
    \caption{The root poset for type $B_4$ is shown, with the filled nodes indicating the positive roots in the inversion set of the element $w$ from \cref{ex:sep-in-B4}.}
    \label{fig:B4}
    \end{center}
\end{figure}
We now generalize Fan Wei's result for the symmetric group to general finite Weyl groups; \cref{def:separable} and \cref{thm:symmetric-and-unimodal} together answer an open problem posed in \cite{Wei2012Product}.

\begin{theorem} \label{thm:symmetric-and-unimodal}
Let $w \in W$ be separable, then $\Lambda_w$ and $V_w$ are rank-symmetric and rank-unimodal, and
\begin{equation} \label{eq:factorization}
\Lambda_w(q)V_w(q)=W(q).
\end{equation}
\end{theorem}

The similarity of (\eqref{eq:factorization}) to (\eqref{eq:parabolic-product}) suggests that one should look for a length-additive multiplicative decomposition of $W$ corresponding to each separable element $w$, analogous to that in \cref{prop:parabolic-quotient}.  Indeed, such a decomposition is constructed in \cref{sec:gen-quotients}; in addition we show for the symmetric group (and conjecture in other types) that separable elements induce \emph{all} such decompositions.

In \cref{sec:associahedra} we give explicit product formulas for $\Lambda_w(q)$ and $V_w(q)$ when $w$ is separable in terms of the nested set indexing the corresponding face of the graph associahedron, making \cref{thm:symmetric-and-unimodal} even more explicit.

\section{Generalized quotients and splittings of Weyl groups} \label{sec:gen-quotients}
Given any subset $U$ of a Weyl group $W$, Bj\"{o}rner and Wachs \cite{Bjorner-Wachs} introduced the \emph{generalized quotient}:
\[
W/U=\{w \in W \: | \: \ell(wu)=\ell(w)+\ell(u), \forall u \in U\}.
\]

\begin{proposition}[Bj\"{o}rner and Wachs \cite{Bjorner-Wachs}]
Let $u_0=\bigvee^R_{u \in U} u$, then $W/U=[e,w_0u_0^{-1}]_L$.
\end{proposition}

A pair $(X,Y)$ of arbitrary subsets $X,Y \subseteq W$ such that the multiplication map $X \times Y \to W$ sending $(x,y)\mapsto xy$ is \emph{length-additive} (meaning $\ell(xy)=\ell(x)+\ell(y), \forall x \in X, y \in Y$) and bijective is called a \emph{splitting} of $W$.  Generalized quotients generalize the notion of parabolic quotients, since $W^J=W/W_J$; \cref{prop:parabolic-quotient} implies that we have a splitting $(W^J, W_J)$ in this case.

Bj\"{o}rner and Wachs (1988) ask the following question:

\begin{quest}[Bj\"{o}rner and Wachs \cite{Bjorner-Wachs}] \label{quest:splittings}
In the case $W=S_n$, for which $U \subseteq W$ is the multiplication map
\[
W/U \times U \to W
\]
sending $(x,y) \mapsto xy$ a splitting?
\end{quest}

Since this map is length-additive by definition of generalized quotient, \cref{quest:splittings} amounts to asking when it is a bijection.  \cref{thm:separable-splitting} identifies splittings corresponding to separable elements in any finite Weyl group.  Fan Wei  \cite{Wei2012Product} proved an equivalent statement in the case of the symmetric group using explicit manipulations on permutations; our proof is type-independent.

\begin{theorem} \label{thm:separable-splitting}
Let $W$ be any finite Weyl group and $U=[e,u]_R$ with $u$ separable, then $(W/U, U)$ is a splitting of $W$. 
\end{theorem}
\begin{proof}[Proof sketch]
By \cref{cor:closure}, the set of separable elements is closed under the involutions of multiplying on either side by $w_0$ and inversion.  After some manipulations using these operations and known properties of the weak order, one can check that it suffices to prove that the map $\Lambda^L_{\pi} \times V^L_{\pi} \to W$ given by $(x,y) \mapsto yx^{-1}$ is bijective for $\pi$ separable.  In light of \cref{thm:symmetric-and-unimodal}, it suffices to prove surjectivity, so fix $w \in W$ which we will show is in the image of this map.  Assume without loss of generality that $W=W(\Phi)$ is irreducible and $\pi$ is separable with a pivot $\alpha_i$ with $\{\beta \in \Phi^+ \: | \: \beta \geq \alpha_i\} \cap I_{\Phi}(\pi)=\emptyset$, the other case in \cref{def:separable} (3) being analogous.  Let $J=\Delta \setminus \{\alpha_i\}$ and let $\Phi'$ be the parabolic subsystem generated by $J$.

By induction on rank, we may assume that the claim is true for $W(\Phi')$, so there exist elements $x' \in \Lambda_{\pi'}$ and $y' \in V_{\pi'}$ such that $y'(x')^{-1}=w'$, where $\pi'=\pi|_{\Phi'}$ ($\pi'$ is clearly still separable) and $w'=w|_{\Phi'}$.  Now, viewing $w' \in W(\Phi') \subset W(\Phi)$ as an element of the full group, we have that $w \geq_L w'$, by comparing inversion sets and applying \cref{prop:weak-given-by-inversions}.  This means that we can write $w=s_{i_1} \cdots s_{i_k}w'$ with lengths adding.  In fact, we have that $w'=w_J$ and $s_{i_1} \cdots s_{i_k} = w^J \in W^J$.  In particular, since $y' \in W_{J}$ we know that $s_{i_1}\cdots s_{i_k}y'$ is reduced; call this element $y$, so $y \geq_L y' \geq_L \pi'=\pi$, thus $y \in V^L_{\pi}$.  We have
\[
y(x')^{-1}=w(w')^{-1}y'(x')^{-1}=w
\]
as desired.
\end{proof}

The proofs of our remaining main theorems---especially \cref{thm:only-if,thm:surjectivity,thm:pattern-classification}---are significantly harder than that of \cref{thm:separable-splitting}, and we unfortunately have no space to sketch them.

In \cref{thm:only-if} we answer \cref{quest:splittings}; in fact we show more, by ruling out splittings not coming from a generalized quotient.

\begin{theorem} \label{thm:only-if}
Let $(X,Y)$ be an arbitrary splitting of $W=S_n$, then $X=W/Y$ and $Y=[e,u]_R$ with $u$ separable.
\end{theorem}

\cref{thm:separable-splitting,thm:only-if} show that generalized quotients with $U=[e,u]_R$ and $u$ separable are exactly those for which the multiplication map $W/U \times U \to W=S_n$ is a bijection.  \cref{thm:surjectivity} shows that this map is a \emph{surjection} for every $u$.  Despite its simple statement, \cref{thm:surjectivity} is surprisingly difficult to prove, and involves exploiting new connections between the left and right weak orders and the well-known \emph{strong Bruhat order}; much of the argument involves careful analysis of reduced decompositions for certain elements using wiring diagrams, and therefore does not easily extend to other types.  As an indication of the strength of this Theorem, we discuss in \cref{sec:linear-extensions} how it immediately solves an open problem of Pak, Panova, and Morales about linear extensions of posets.

\begin{theorem} \label{thm:surjectivity}
Let $u$ be any element of $W=S_n$ and $U=[e,u]_R$, then the multiplication map $W/U \times U \to W$ is surjective.
\end{theorem}

\subsection{Splittings and surjectivity in other Weyl groups}

Although \cref{thm:separable-splitting} holds for all finite Weyl groups, \cref{thm:only-if,thm:surjectivity} are currently stated only for $W=S_n$.  We conjecture that both extend to arbitrary finite Weyl groups, with an additional restriction in \cref{thm:only-if}.

\begin{conj}
\cref{thm:surjectivity} holds for any finite Weyl group $W$.
\end{conj}

\begin{conj} \label{conj:other-types-only-if}
Let $[e,u]_R=U \subseteq W$, then $(W/U,U)$ is a splitting of $W$ if and only if $u$ is separable.
\end{conj}

\begin{remark}
For the exceptional Weyl group $W$ of type $F_4$, there is a splitting $(W/U,U)$ where $U$ is not an interval in right weak order; this is why the statement of \cref{conj:other-types-only-if} is weaker than that of \cref{thm:only-if}.  It may be that the full strength of \cref{thm:only-if} holds for the remaining infinite families of Weyl groups of types $B_n=C_n$ and $D_n$.
\end{remark}

\subsection{Linear extensions and weak order} \label{sec:linear-extensions}

In this section we sketch how \cref{thm:surjectivity} resolves an open problem of Pak, Panova, and Morales \cite{PPM}.

See \cite{BW-lin-ext} for the following background on linear extensions.  A \emph{linear extension} of a finite poset $P=(\{p_1,\ldots ,p_n\}, \leq_P)$ is an order preserving bijection $\lambda: P \to [n]$, where $[n]$ denotes the set $\{1,\ldots,n\}$ under the usual ordering.  We write $e(P)$ for the number of linear extensions of $P$.  The \emph{order dimension} of $P$ is the smallest number $t$ such that there exist linear extensions $\lambda_1,\ldots,\lambda_t$ such that for all $i,j$ we have $p_i \leq_P p_j$ if and only if $\lambda_k(p_i) \leq \lambda_k(p_j)$ for all $k=1,\ldots,t$.  In this situation we write $P=\bigcap_{k=1}^t \lambda_k$.

We say $P$ is \emph{naturally labelled} if $p_i \mapsto i, \forall i$ is a linear extension.  We may identify linear extensions $\lambda$ of $P$ with permutations in $S_n$ by identifying the linear extension $p_i \mapsto \pi_i, \forall i$ with the permutation $\pi=\pi_1 \ldots \pi_n$, in this case we write $\lambda_{\pi}$ for $\lambda$.  For $\pi \in S_n$, write $P_{\pi}$ for the poset on $\{p_1,...,p_n\}$ defined by $P_{\pi}=\lambda_e \cap \lambda_{\pi}$, such a poset is always naturally labelled.  Two-dimensional posets $P$ have natural \emph{complementary posets} $\overline{P}$ defined as follows: choose an isomorphism from $P$ to some $P_{\pi}$ (this can always be done), and let $\overline{P}=P_{\pi w_0}$.  The poset $\overline{P}$ may not be uniquely determined, as there may be multiple choices for $\pi$, however \cref{thm:sidorenko} holds for any complement formed from this construction.

A poset $P$ is \emph{series-parallel} if can be formed from combining some number of singleton posets using the operations of disjoint union (elements of $Q$ are incomparable with elements of $Q'$ in $Q \sqcup Q'$) and direct sum (all elements of $Q$ are less than all elements of $Q'$ in $Q \oplus Q'$).

\begin{theorem}[Sidorenko \cite{Sidorenko}] \label{thm:sidorenko}
Let $P$ be a two-dimensional poset, then:
\[
e(P)e(\overline{P}) \geq n!
\]
with equality if and only if $P$ is series-parallel.
\end{theorem}

Sidorenko's original proof of \cref{thm:sidorenko} uses intricate analysis of various recurrences and the Max-flow/Min-cut Theorem.  It was reproven by Bollob\'{a}s, Brightwell, and Sidorenko \cite{BBS} using a known special case of the still-open Mahler conjecture from convex geometry and an implication of the difficult Perfect Graph Theorem.  This led Pak, Panova, and Morales \cite{PPM} to state an open problem asking for a direct combinatorial proof; we provide such a proof by applying \cref{thm:surjectivity}.

\begin{proposition}[Bj\"{o}rner and Wachs \cite{BW-lin-ext}] \label{prop:le-from-intervals}
The linear extensions of $P_{\pi}$ are exactly $\{\lambda_u \: | \: u \in [e,\pi]_R\}$.
\end{proposition}

\begin{proof}[New proof of \cref{thm:sidorenko}]
Pick $\pi$ such that $P$ is isomorphic to $P_{\pi}$.  By \cref{prop:le-from-intervals}, we need to show that $|[e,\pi]_R| \cdot |[e,\pi w_0]|_R \geq n!$.  We simply observe that inversion gives a bijection $[e,\pi w_0]_R \to [e,w_0 \pi^{-1}]_L=W/[e,\pi]_R$, and apply \cref{thm:surjectivity}.  Thus we have a simply-defined (just group multiplication) surjection from the set $W/[e,\pi]_R \times [e,\pi]_R$ of cardinality $e(P)e(\overline{P})$ to the set $W=S_n$ of cardinality $n!$. To get the equality case, note that \cref{thm:separable-splitting,thm:only-if,,thm:surjectivity} together imply that we have equality if and only if $\pi$ is separable.  It is easy to check that the two cases in \cref{def:separable} (3) correspond to the operations $\oplus$ and $\sqcup$ on posets, so that $\pi$ is separable if and only if $P_{\pi}$ is series-parallel.
\end{proof}

\section{Product formulas and graph associahedra} \label{sec:associahedra}

In this section we show that separable elements in $W$ are in bijection with the faces (of all dimensions) of two copies of the \emph{graph associahedron} $A(\Gamma)$ of the Dynkin diagram $\Gamma$ for $W$.  The Dynkin diagram is a graph with vertices indexed by the simple roots $\Delta$ and edges $\overline{\alpha \alpha'}$ whenever $s_{\alpha}$ and $s_{\alpha'}$ do not commute.  Much useful information about a separable element $w$, such as its Lehmer code, the rank generating functions $\Lambda_w(q)$ and $V_w(q)$, and a factorization of $w$ as a product of elements of the form $w_{0,J}$ can be read off from the corresponding face.

Given a graph $\Gamma$, the \emph{graph associahedron} $A(\Gamma)$ is a convex polytope which can be defined as the Minkowski sum of coordinate simplices corresponding to the connected subgraphs of $\Gamma$.  First arising in the work of De Concini and Procesi on wonderful models of subspace arrangements \cite{DeConcini-Procesi}, these polytopes have received intensive study, especially in the case when $\Gamma$ is a Dynkin diagram.  When $\Gamma$ is the Dynkin diagram of type $A_n$, a path graph, $A(\Gamma)$ is the usual Stasheff Associahedron.

Since separable elements in $W(\Phi_1 \oplus \Phi_2)=W(\Phi_1) \times W(\Phi_2)$ are just pairs $(w_1,w_2)$ with each $w_i$ separable in $W(\Phi_i)$, throughout this section we assume $W=W(\Phi)$ with $\Phi$ irreducible for simplicity; this corresponds to the Dynkin diagram $\Gamma$ being connected.  We will use a model for the faces of $A(\Gamma)$ due to Postnikov \cite{beyond-paper}. A collection $\mathcal{N}$ of subsets of $\Gamma$ is a \emph{nested set} if:
\begin{itemize}
    \item For all $J \in \mathcal{N}$, the induced subgraph $\Gamma|_J$ on the vertex set $J$ is connected.
    \item For any $I,J \in \mathcal{N}$ we have either $I \subseteq J,$ or $J \subseteq I,$ or $I \cap J = \emptyset$.
    \item For any collection of $k \geq 2$ disjoint subsets $J_1,...,J_k \in \mathcal{N}$, the subgraph $\Gamma|_{J_1 \cup \cdots \cup J_k}$ is \emph{not} connected.
\end{itemize}
The relevant notion of connectivity for directed graphs is the connectivity of the associated simple undirected graph, so the structure of $A(\Gamma)$ does not depend on an orientation of $\Gamma$.  This is why we have omitted reference to the edge multiplicities and orientations in our definition of Dynkin diagrams.

\begin{proposition}[Postnikov \cite{beyond-paper}]
The poset of faces of $A(\Gamma)$ is isomorphic to the poset of nested sets on $\Gamma$ which contain $\Gamma$, ordered by reverse containment.
\end{proposition}

We call a total ordering of the elements of a nested set $\mathcal{N}$ \emph{monotonic} if $J$ appears before $I$ whenever $J \subseteq I$.  The \emph{depth} of $J \in \mathcal{N}$ is the maximum length $k$ of a chain $J \subsetneq I_1 \subsetneq I_2 \subsetneq \cdots \subsetneq I_k$ of elements of $\mathcal{N}$.  We let $\mathcal{N}_{even}$ and $\mathcal{N}_{odd}$ denote the elements of $\mathcal{N}$ of even and odd depth respectively.

\begin{theorem} \label{thm:bijection-to-faces}
Let $W$ be an irreducible finite Weyl group with Dynkin diagram $\Gamma$, then:
\begin{enumerate}
    \item The nested sets on $\Gamma$ are in bijection with the separable elements of $W$ via the map 
    \[
    \mathcal{N} \mapsto \prod_{J \in \mathcal{N}} w_{0,J}:=w(\mathcal{N}), 
    \]
    where the product is taken in a monotonic order.
    \item The weak order rank generating functions of the intervals $[e, w(\mathcal{N})]$ in left and right order are:
    \[
    \Lambda^L_{w(\mathcal{N})}(q)=q^{\ell(w(\mathcal{N}))}\Lambda^R_{w(\mathcal{N})}(q^{-1})=\frac{\prod_{J \in \mathcal{N}_{even}} W_J(q)}{\prod_{J \in \mathcal{N}_{odd}} W_J(q)}.
    \]
\end{enumerate}
\end{theorem}

\begin{remark}
The rank generating functions $W(q)$ for any finite Weyl group are well known to factor as a product of the $q$-integers of the \emph{degrees} of $W$, thus one may expand the formula in \cref{thm:bijection-to-faces} (2) as a quotient of products of $q$-integers.  Note that the $W_J$ appearing in this formula may be of several different Cartan-Killing types and so this product will contain degrees from these several families.  The $q$-integers in the denominator do not always pair up to cancel with those in the numerator, so even the fact that this quotient is a polynomial is nontrivial.

This product formula generalizes several known formulas for rank generating functions of intervals in the weak order (see, e.g. \cite{Wei2012Product} and \cite{Bjorner-Wachs}).  It is known that computing even the size of weak order intervals is $\# P$-complete \cite{Dittmer-Pak}, so there can be no nice formulas for $\Lambda_w(q)$ in general, making this formula all the more notable. 
\end{remark}

\begin{example}
Let $w$ be the element in the Weyl group $W$ of type $B_4$ from \cref{ex:sep-in-B4}.  Let $\Gamma$ be the Dynkin diagram, whose vertices are the simple roots $\alpha_1,\alpha_2, \alpha_3$ and $\alpha_4$.  Then $w$ corresponds to the nested set 
\[
\mathcal{N}_w=\{\{\alpha_1, \alpha_2, \alpha_3, \alpha_4\},\{\alpha_1, \alpha_2\},\{\alpha_2\},\{\alpha_4\}\}.
\]
There is a combinatorial rule for the inverse to the bijection in \cref{thm:bijection-to-faces} (1) used to construct $\mathcal{N}_w$, however we do not have space to describe it here.  The degrees of $W$ are $2,4,6,$ and $8$, and a Weyl group of type $A_{n-1}$ has degrees $2,3,\ldots,n$, thus part (2) of \cref{thm:bijection-to-faces} implies that 
\[
\Lambda_w^L(q)=q^{13}\Lambda^R_w(q^{-1})=\frac{\left([2]_q [4]_q [6]_q [8]_q \right) \left( [2]_q \right)}{\left([2]_q [3]_q\right) \left([2]_q \right)}=[4]_q [8]_q (1+q^3),
\]
where $[k]_q$ denotes the $q$-integer $1+q+\cdots+q^{k-1}$.
\end{example}

\section{A pattern avoidance characterization} \label{sec:pattern-section}

Recall that separable permutations are defined to be those which avoid the patterns 3142 and 2413.  In this section we explain how separable elements of general finite Weyl groups are characterized by pattern avoidance in the sense of Billey and Postnikov (see the discussion after \cref{prop:parabolic-quotient} in \cref{sec:background}).  This has the benefit of giving a non-recursive characterization of separable elements (in contrast to \cref{def:separable}) as well as implying that separable elements in $W=S_n$ are precisely the separable permutations which had received much previous study.

\begin{theorem} \label{thm:pattern-classification}
An element $w \in W(\Phi)$ is separable if and only if $w$ avoids the following root system patterns:
\begin{itemize}
    \item [i] the patterns corresponding to the permutations 3142 and 2413 in the Weyl group of type $A_3$,
    \item [ii] the two patterns of length two in the Weyl group of type $B_2$, and
    \item [iii] the six patterns of lengths two, three, and four in the Weyl group of type $G_2$.
\end{itemize}
\end{theorem}

\begin{cor}
Under the usual identification of the Weyl group $W$ of type $A_{n-1}$ with the symmetric group of permutations of $\{1,\ldots,n\}$, an element $w \in W$ is separable if and only if it corresponds to a separable permutation.
\end{cor}
\begin{proof}
As the type $A_{n-1}$ root system is \emph{simply-laced} (meaning all roots have the same Euclidean length) it does not contain any subsystems of types $B_2$ or $G_2$, which are not simply-laced.  Thus \cref{thm:pattern-classification} implies the desired result.
\end{proof}

\cref{thm:pattern-classification} also makes it clear that the set of separable elements is closed under the natural involutions on Weyl groups $x \mapsto w_0x$, $x \mapsto xw_0$, and $x \mapsto x^{-1}$; the latter two of these are not clear from \cref{def:separable}.

\begin{cor} \label{cor:closure}
Let $w \in W$ be separable.  Then $w_0w, ww_0,$ and $w^{-1}$ are also separable.
\end{cor}
\begin{proof}
The set of forbidden patterns in \cref{thm:pattern-classification} is closed under these three involutions, and it is easy to check that $w$ avoids $u$ if and only if $w^{-1}$ avoids $u^{-1}$ (and similarly for the other two).
\end{proof}


\acknowledgements{We wish to thank Anders Bj\"{o}rner for alerting us to important references and Vic Reiner and Richard Stanley for helpful conversations.  We are especially grateful to our advisor Alex Postnikov for his observation that separable elements may be related to faces of graph associahedra.}

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