%% 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]{FPSAC2021}
\articlenumber{41}
%% 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}
\usepackage{mathtools}
\usepackage{tikz}
\usepackage{todonotes}
\DeclareMathOperator{\conv}{Conv}
\DeclareMathOperator{\wid}{width}
\DeclareMathOperator{\cay}{Cay}

\DeclareMathOperator{\di}{\delta^{\text{ideal}}}
\DeclareMathOperator{\bi}{\textit{b}^{\text{ideal}}}

\newcommand{\mc}{\mathcal}
\newcommand{\mf}{\mathfrak}
\newcommand{\bs}{\boldsymbol}

\newcommand{\GL}{\mathrm{GL}}
\newcommand{\height}{\mathrm{ht}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Vol}{\mathrm{Vol}}
\newcommand{\id}{\mathrm{id}}
\renewcommand{\O}{\mathcal{O}}

\newcommand\precdot{\mathrel{\ooalign{$\prec$\cr
  \hidewidth\raise0.001ex\hbox{$\cdot\mkern0.6mu$}\cr}}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{def-prop}[theorem]{Definition-Proposition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{quest}{Question}
\newtheorem{defin}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem{remark}{Remark}

\usepackage{lipsum}

%% define your title in the usual way
\title{The $1/3$--$2/3$ Conjecture for Coxeter 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:crgaetz@gmail.com}{crgaetz@gmail.com}. C.G. was partially supported by an NSF 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{The $1/3$--$2/3$ Conjecture, originally formulated in 1968, is one of the best-known open problems in the theory of posets, stating that the \emph{balance constant} of any non-total order is at least $1/3$.  By reinterpreting balance constants of posets in terms of convex subsets of the symmetric group, we extend the study of balance constants to convex subsets $C$ of any Coxeter group\footnote{See \cite{arxiv-version} for a full version of this work.}.  Remarkably, we conjecture that the lower bound of $1/3$ still applies in any finite Weyl group, with new and interesting equality cases appearing.

We generalize several of the main results towards the $1/3$--$2/3$ Conjecture to this new setting: we establish our conjecture when $C$ is a weak order interval below a fully commutative element in any acyclic Coxeter group (a generalization of the case of width-two posets), we give a uniform lower bound for balance constants in all finite Weyl groups using a new generalization of order polytopes to this context, and we introduce \emph{generalized semiorders} for which we resolve the conjecture.

We hope this new perspective may shed light on the proper level of generality in which to consider the $1/3$--$2/3$ Conjecture, and therefore on which methods are likely to be successful in resolving it.}

%% 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{linear extension, balance constant, Coxeter group, Weyl group, fully commutative, order polytope, semiorder.}

%% 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
\usepackage[backend=bibtex]{biblatex}
\addbibresource{41Gaetz.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}

\subsection{The $1/3$--$2/3$ Conjecture}

Given a finite poset $P$ on $n$ elements, a \emph{linear extension} of $P$ is an order-preserving bijection $\lambda:P \to [n]$, where $[n]=\{1,2,\ldots,n\}$.  Let $x,y \in P$ and consider the quantity
\begin{equation}
\label{eq:def-delta-for-posets}
\delta_P(x,y)=\frac{|\{\text{linear extensions } \lambda:P \to [n] \text{ such that } \lambda(x) > \lambda(y) \}|}{|\{\text{linear extensions } \lambda:P \to [n]\}|}.
\end{equation}

The quantity $\delta$ is of considerable interest.  If $P$ represents random partial information about some underlying total order on the same ground set, then $\delta_P(x,y)$ gives information about the probability that $x$ actually precedes $y$ in the total order.  Unfortunately, neither the numerator nor denominator may be easily computed, as computing the number of linear extensions of a poset is known \cite{Brightwell-Winkler} to be $NP$-hard, even \cite{Dittmer-Pak} for the important case of two-dimensional posets which we will encounter later.  

Despite these difficulties, one could hope that there exist $x,y \in P$ with 
\[
\min(\delta_P(x,y), 1-\delta_P(x,y))
\]
large, so that the additional information of whether $x$ precedes $y$ would reduce the number of linear extensions, and thus the remaining uncertainty, as much as possible.  It thus makes sense to study the \emph{balance constant}
\[
b(P)=\max_{x,y} \min(\delta_P(x,y), 1-\delta_P(x,y)),
\]
to establish "information theoretic" bounds for the above problem \cite{Linial}.  It is in this context that the following well-known conjecture has been made three times independently by Kislicyn in 1968, Freedman in 1974, and Linial in 1984 \cite{Kislicyn,Linial}.

\begin{conj}[The $1/3$--$2/3$ Conjecture]
\label{conj:1-3-2-3}
For any finite poset $P$ which is not a total order, $b(P) \geq \frac{1}{3}$.
\end{conj}

This conjecture has received considerable attention, with many weaker bounds and special cases having been established, see Brightwell's survey \cite{Brightwell}.  

\subsection{Posets as convex subsets of the symmetric group}
\label{sec:intro-convex-sets}

Let $P$ be a poset on $\{p_1,\ldots, p_n\}$, so any linear extension $\lambda: P \to [n]$ may be thought of as a permutation $w_{\lambda} \in S_n$ with $w_{\lambda}(i)=\lambda(p_i)$.  Let
\[
C(P)=\{w_{\lambda} \: | \: \lambda \text{ a linear extension of $P$}\}
\]
be the set of these permutations as $\lambda$ ranges over all linear extensions of $P$; clearly the set $C(P)$ determines the poset $P$.  It is a folklore fact that the sets $C \subseteq S_n$ which come in this way from a poset are exactly the \emph{convex} subsets: those $C$ such that any element on a minimal length path between two elements of $C$ in the standard Cayley graph for $S_n$ also lies in $C$.  In the dual picture of the braid arrangement, these are exactly the $C$ such that the union of the closed regions corresponding to the permutations in $C$ is a (convex) cone.

Taking the perspective of posets as convex subsets of the symmetric group, notice that 
\[
\delta_P(p_i,p_j)=\frac{|\{w \in C(P) \: | \: w(i) > w(j)\}|}{|C(P)|}.
\]
The right-hand-side is the fraction of permutations in $C(P)$ with a given \emph{inversion}, and this perspective admits a natural generalization to convex sets in any Coxeter group.

\subsection{Balance constants for Coxeter groups}
See Section~\ref{sec:background} for background and definitions on Coxeter groups and Weyl groups.

For any convex set $C$ in a Coxeter group $W$ and any reflection $t$ we define
\[
\delta_C(t)=\frac{|C_t|}{|C|},
\]
where $C_t=\{w \in C \: | \: \ell(wt)<\ell(w)\}$ is the set of elements in $C$ having $t$ as an inversion; when $C$ is clear we often simply write $\delta(t)$.  In light of the discussion in Section~\ref{sec:intro-convex-sets} this definition is exactly analogous to (\ref{eq:def-delta-for-posets}), recovering $\delta_P(x,y)$ when $W=S_n$, $C$ is the convex set associated to $P$, and $t$ is the transposition swapping $\lambda(x)$ and $\lambda(y)$.  It thus makes sense to define the \emph{balance constant}
\[
b(C)=\max_t \min(\delta_C(t), 1-\delta_C(t)).
\]
Remarkably, when $W$ is a finite Weyl group, Conjecture~\ref{conj:1-3-2-3} appears still to hold:

\begin{conj}\label{conj:1-3-2-3-weyl}
Let $W$ be any finite Weyl group and $C \subseteq W$ a convex set which is not a singleton, then $b(C) \geq \frac{1}{3}$.
\end{conj}

In this extended abstract we show that many known partial results towards Conjecture~\ref{conj:1-3-2-3} can be generalized to the context of Conjecture~\ref{conj:1-3-2-3-weyl} or even further.  

The remainder of the abstract is organized as follows: in Section~\ref{sec:background} we give background on Coxeter groups, Weyl groups, and convex subsets of these.  Section~\ref{sec:fully-commutative} resolves Conjecture~\ref{conj:1-3-2-3-weyl} in the case $C$ is an interval below a \emph{fully commutative} element of $W$ in the increased generality of acyclic Coxeter groups; this generalizes a classical result of Linial \cite{Linial} that Conjecture~\ref{conj:1-3-2-3} holds for width-two posets.  Section~\ref{sec:equality-cases} also gives examples of convex sets achieving equality in Conjecture~\ref{conj:1-3-2-3-weyl}; this is a richer set of examples than exists for posets, where there is (conjecturally) only one irreducible example.  Section~\ref{sec:semiorders} resolves Conjecture~\ref{conj:1-3-2-3-weyl} in the context of \emph{generalized semiorders}, which we introduce; this is a generalization of Brightwell's result \cite{Brightwell-semiorder} for semiorder posets.  Section~\ref{sec:bounds-Weyl} outlines our type-independent proof of a uniform lower bound $b(C) \geq \varepsilon > 0$ for Conjecture~\ref{conj:1-3-2-3-weyl}; this is inspired by Kahn and Linial's proof for posets \cite{Kahn-Linial} and relies on a new generalization of order polytopes.  

The \emph{generalized semiorders} and \emph{generalized order polytopes} we introduce may be of independent interest.

\section{Background on Coxeter groups and root systems}
\label{sec:background}

\subsection{Coxeter groups}
\label{sec:background-cox-groups}
Let $(W,S)$ be a Coxeter system; we follow the conventions of \cite{Bjorner-Brenti}.  We write $\Gamma$ for the associated \emph{Coxeter diagram}, the graph with vertex set $S$ and an edge labelled $m_{ij}$ between vertices $s_i$ and $s_j$ whenever the quantity $m_{ij}$ giving the defining relation $(s_is_j)^{m_{ij}}=\id$ of $W$ is at least $3$.  We say $W$ is \emph{acyclic} if the graph $\Gamma$ contains no cycles, and \emph{irreducible} if $\Gamma$ is connected.  

For $w \in W$, the \emph{length} $\ell(w)$ is the smallest number $\ell$ such that $w=s_1 \cdots s_{\ell}$ with the $s_i \in S$.  Such an expression of minimal length is called a \emph{reduced word} or \emph{reduced expression}.  The \emph{left (resp. right) weak order} is the partial order on $W$ with cover relations $u \lessdot_L su$ (resp. $u \lessdot_R us)$ whenever $\ell(su)=\ell(u)+1$ (resp. $\ell(us)=\ell(u)+1$) and $s \in S$.  We write $\cay_L(W)$ and $\cay_R(W)$ for the left and right Cayley graphs for $W$ with respect to the generating set $S$, viewing these as undirected graphs, and often identifying them with the Hasse diagrams of the weak orders.

The set $T=WSW^{-1}$ of conjugates of $S$ is called the set of \emph{reflections}.  For $w \in W$ the \emph{right (resp. left) inversion set} $T_R(w)$ is $\{t \in T \: | \: \ell(wt)<\ell(w)\}$ (resp. $\{t \in T \: | \: \ell(tw)<\ell(w)\}$).  It is well known that $|T_R(w)|=|T_L(w)|=\ell(w)$, and that weak order is characterized by containment of inversions sets:
\begin{align*}
   u &\leq_L v \iff T_R(u) \subseteq T_R(v) \\
   u &\leq_R v \iff T_L(u) \subseteq T_L(v).
\end{align*}

For $D \subseteq A \subseteq T$ we write $W_D^A$ for the set of elements in $W$ whose right inversion set lies between $D$ and $A$: $W_D^A=\{w \in W \: | \: D \subseteq T_R(w) \subseteq A\}.$ The reader should not confuse this notation with similar notation often used for parabolic subgroups and quotients of $W$.

A subset $C \subseteq W$ is \emph{left (resp. right) convex} if it is convex with respect to the metric on $W$ determined by the natural graph distance in $\cay_L(W)$ (resp. $\cay_R(W)$).  That is, if all elements of $W$ which lie on some minimal-length path in $\cay_L$ between $u$ and $v$ are in $C$ whenever $u$ and $v$ are.  The \emph{left (resp. right) convex hull} $\conv_L(w_1,\ldots, w_d)$ (resp. $\conv_R(w_1,\ldots, w_d)$) of a collection of elements $w_1, \ldots, w_d \in W$ is defined to be the intersection of all left (resp. right) convex subsets of $W$ which contain $\{w_1,\ldots,w_d\}$; the convex hull is itself clearly convex.

\begin{theorem}[Tits \cite{Tits}]
\label{thm:tits-convexity}
A set $C \subseteq W$ is left convex if and only if it is of the form $W_D^A$ for some $D \subseteq A \subseteq T$.
\end{theorem}

If $W=W_1 \times W_2$ is a reducible Coxeter group, convex sets $C \subseteq W$ are products $C_1 \times C_2$ of convex sets $C_1 \subseteq W_1$ and $C_2 \subseteq W_2$.  This implies that $b(C)=\max(b(C_1), b(C_2))$, so it suffices to consider $W$ irreducible in Conjecture~\ref{conj:1-3-2-3-weyl}.

As the action of $W$ on $\cay_L$ by right multiplication is by graph automorphisms, it is clear that $C$ is convex if and only if $C \cdot w=\{cw \: | \: c \in C\}$ is for every $w \in W$.  Thus, choosing any $c \in C$ we may consider the translated convex set $C \cdot c^{-1}$ which now contains the identity and is equivalent to $C$ for the purposes of Conjecture~\ref{conj:1-3-2-3-weyl}.  Convex sets containing $\id$ are exactly the convex \emph{order ideals}, and by Theorem~\ref{thm:tits-convexity} these are clearly the sets $W_{\emptyset}^A$, for which we will often write simply $W^A$. 

\begin{remark}
We make the convention that when "left" and "right" are not specified it is assumed that we are working with left weak order, left Cayley graphs and convex sets, and so on.
\end{remark}

\subsection{Finite Weyl groups and crystallographic root systems}
\label{sec:background-weyl-groups}

For some of our results we will need to take advantage of additional structure present for finite crystallographic Coxeter groups (finite Weyl groups), some of which is outlined here.  We refer readers to Humphreys \cite{Humphreys} for a detailed exposition on the classical theory of root systems and Weyl groups.

Let $\Phi\subset E$ be a finite crystallographic root system of rank $r$, where $E$ is an ambient Euclidean space of dimension $r$ with a positive definite symmetric bilinear form $\langle-,-\rangle$, with a chosen set of positive roots $\Phi^+\subset\Phi$ and the corresponding simple roots $\Delta=\{\alpha_1,\ldots,\alpha_r\}\subset\Phi^+$. Let the \textit{fundamental coweights} $\omega_1^{\vee},\ldots,\omega_r^{\vee}$ be the dual basis of $\Delta$ with respect to $\langle-,-\rangle$. 
For each root $\alpha\in\Phi$ we have a reflection
$$s_{\alpha}:x\mapsto x-\frac{2\langle \alpha,x\rangle}{\langle\alpha,\alpha\rangle}\alpha\in\GL(E).$$
The Weyl group $W=W(\Phi)$ is a finite subgroup of $\GL(E)$ generated by the $s_{\alpha}$, for $\alpha\in\Phi$, or equivalently, generated by the simple reflections $S=\{s_1,\ldots,s_r\}$ where $s_i=s_{\alpha_i}$.  The pair $(W,S)$ forms a finite Coxeter system, so the material of Section~\ref{sec:background-cox-groups} can be applied.

The root system $\Phi$ is called \textit{irreducible} if it cannot be partitioned into two proper subsets $\Phi_1\sqcup\Phi_2$ such that $\langle \beta_1,\beta_2\rangle=0$ for all $\beta_1\in\Phi_1$ and $\beta_2\in\Phi_2.$ Irreducible root systems are completely classified, with four infinite families, types $A_n$ ($n\geq1$), $B_n$ ($n\geq2$), $C_n$ ($n\geq2$) and $D_n$ ($n\geq4$) and five exceptional types, $E_6$, $E_7$, $E_8$, $F_4$ and $G_2$.  The details of these root systems may be found in \cite{Humphreys}. 

\begin{defin}
The \textit{root poset} is the partial order on the positive roots $\Phi^+$ such that $\alpha\leq\beta$ if $\beta-\alpha$ is a non-negative linear combination of the simple roots $\Delta$.  We will abuse notation by simply writing $\Phi^+$ for the root poset $(\Phi^+, \leq)$.
\end{defin}

The minimal elements of $\Phi^+$ are the simple roots $\Delta$. It is a classical fact that there exists a unique maximum $\xi$ in the root poset when $\Phi^+$ is irreducible, called the \textit{highest root}; we write $\height(\Phi)$ for the sum of the coefficients of $\xi$ when expanded in the basis $\Delta$ for $E$.

\section{The fully commutative case}
\label{sec:fully-commutative}

\subsection{Width-two posets and $321$-avoiding permutations}
\label{sec:width-two}
An \emph{antichain} in a poset $P$ is a collection of pairwise incomparable elements; the size of the largest antichain is the \emph{width} $\wid(P)$ of $P$.  The following result of Linial establishes Conjecture~\ref{conj:1-3-2-3} in the case $\wid(P)=2$.

\begin{theorem}[Linial \cite{Linial}]
\label{thm:width-2}
Let $P$ have width two, then $b(P) \geq \frac{1}{3}$.
\end{theorem}

Although the width-two condition is very restrictive, all known equality cases $b(P)=\frac{1}{3}$ for Conjecture~\ref{conj:1-3-2-3} lie within this class of posets.  Indeed, it is conjectured \cite{Kahn-Saks} that for each $k>2$ there is a lower bound for $b(P)$ on width-$k$ posets which is strictly greater than $\frac{1}{3}$, with these bounds approaching $\frac{1}{2}$ as $k \to \infty$, so that Theorem~\ref{thm:width-2} covers those posets which are (conjecturally) closest to violating Conjecture~\ref{conj:1-3-2-3} (see the survey by Brightwell \cite{Brightwell} for a heuristic discussion).

The \emph{dimension} $\dim(P)$ of $P$ is the smallest number $d$ such that 
\[
C(P)=\conv(w_1,\ldots,w_d)
\]
for $w_1,\ldots,w_d \in S_n$, or equivalently the smallest number of linear extensions needed to uniquely determine the poset $P$.  It was shown by Dilworth \cite{Dilworth} that any finite poset $P$ has $\dim(P) \leq \wid(P)$. In particular, any poset of width two has order dimension two (the only posets of dimension one are the total orders, and these have width one).  Any naturally labelled two-dimensional poset $P$ has 
\[
C(P)=\conv(\id,w)=[\id,w]_L
\]
for some $w \in S_n$, and it is immediate from the definition of $C(P)$ that $P$ is width-two if and only if the permutation $w$ avoids the pattern $321$, meaning that there are no $1 \leq i < j < k \leq n$ such that $w(i)>w(j)>w(k)$.

In this section we will generalize Theorem~\ref{thm:width-2} to all Coxeter groups $W$ with acyclic Coxeter diagrams; the role of $321$-avoiding permutations will be played by \emph{fully commutative elements} of $W$, introduced by Stembridge \cite{Stembridge}.

\subsection{Fully commutative elements in Coxeter groups}

For $(W,S)$ any Coxeter system and $w \in W$, we write $\mc{R}_w$ for the set of reduced words of $w$.  A well-known result of Tits \cite{Tits-words} implies that all elements of $\mc{R}_w$ are connected by relations of the form
\[
s_is_js_i \cdots = s_js_is_j \cdots
\]
with $m_{ij} \geq 2$ factors on each side.  Applying such a relation to a reduced word is called a \emph{commutation move} when $m_{ij}=2$ and a \emph{braid move} otherwise.  Allowing only commutation moves determines an equivalent relation $\sim$ on $\mathcal{R}_w$, and the elements of $\mathcal{R}_w / \sim$ are called commutation classes.

\begin{defin}[Stembridge \cite{Stembridge}]
An element $w \in W$ is called \emph{fully commutative} if $\mc{R}_w$ consists of a single commutation class.  Equivalently, $w$ is fully commutative if no reduced word for $w$ admits a braid move. 
\end{defin}

\begin{prop}[Stembridge \cite{Stembridge}]
\label{prop:fc-iff-321-avoider}
For $W=S_n$, a permutation $w$ is fully commutative if and only if it avoids the pattern $321$.
\end{prop}

Theorem~\ref{thm:fully-comm} is the main theorem of this section, establishing Conjecture \ref{conj:1-3-2-3-weyl} for intervals below fully commutative elements in acyclic Coxeter groups.  By Proposition~\ref{prop:fc-iff-321-avoider} and the discussion in Section~\ref{sec:width-two} it generalizes Theorem~\ref{thm:width-2}, which is the case $W=S_n$.

\begin{theorem}
\label{thm:fully-comm}
Let $W$ be a (not necessarily finite) Coxeter group with acyclic Coxeter diagram, and let $w \in W$ be a nonidentity fully commutative element.  For the convex set $C=[\id,w]_L$ we have
\[
b(C)\geq \frac{1}{3}.
\]
\end{theorem}

The proof of Theorem~\ref{thm:fully-comm}, which we do not have space to reproduce here, uses Viennot's elegant theory of \emph{heaps} \cite{Viennot}.  Results of Stembridge \cite{Stembridge} allow us to translate questions about balance constants of weak order intervals $[e,w]_L$ below fully commutative elements $w$ into questions about order ideals in the corresponding heap poset $H_w$.

\subsection{Equality cases}
\label{sec:equality-cases}
Let $P_3$ denote the unique poset on three elements with a single cover relation.  It is clear that $P_3$ achieves equality in Conjecture~\ref{conj:1-3-2-3}.  In fact, it was shown by Aigner \cite{Aigner} that the only equality cases in Conjecture~\ref{conj:1-3-2-3} among width-two posets occur when $P$ is a direct sum of some number of copies of $P_3$ and some number of singleton posets, and it is generally believed (see Brightwell \cite{Brightwell}) that these are the only equality cases among all finite posets. The examples below show that there is a much richer collection of equality cases in Theorem~\ref{thm:fully-comm}.

\begin{ex}
\label{ex:weyl-equality-cases}
Let $W$ be a finite Weyl group.  One striking feature of Conjecture~\ref{conj:1-3-2-3-weyl} is that the conjectured bound $b(C) \geq \frac{1}{3}$ is type-independent.  Since large finite Weyl groups contain large type $A$ parabolic subgroups, one possible explanation for this type independence would be if there were some larger type-dependent lower bound on $b$ for convex sets which are, say, "genuinely type $B$", but the type $A$ parabolic subgroup would ensure that the overall bound could be no larger than $\frac{1}{3}$.  Here we present some examples to show that this is not the reason.  Instead, all finite Weyl groups have fully commutative elements $w$ such that $b([\id,w]_L)=\frac{1}{3}$ which do not come from known type $A$ equality cases (see Figures \ref{fig:type-D-equality}, \ref{fig:type-B-equality}, and \ref{fig:type-E-equality}).  We think these examples make Conjecture~\ref{conj:1-3-2-3-weyl} all the more interesting: there are several genuinely distinct ways to match and yet not surpass the conjectured bound.
\end{ex}

These examples prompt the following question, in analogy with Aigner's result.

\begin{quest}
Let $w$ be a fully commutative element in a finite Weyl group with 
\[
b([\id,w]_L)=\frac{1}{3}.
\]
Is the heap poset $H_w$ isomorphic to a disjoint union of the heap poset for $P_3$ and those appearing in Figures \ref{fig:type-D-equality}, \ref{fig:type-B-equality}, and \ref{fig:type-E-equality}?
\end{quest}

\begin{figure}
\centering
\begin{tikzpicture}
\node[draw,shape=circle,fill=black,scale=0.5](a)[label=below: {$s_1$}] at (-0.3,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](b)[label=below: {$s_2$}] at (1,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](c)[label=above: {$s_3$}] at (2,0.5) {};
\node[draw,shape=circle,fill=black,scale=0.5](d)[label=below: {$s_4$}] at (2,-0.5) {};

\draw (b)--(a) node [midway, fill=white] {$3$};
\draw (c)--(b) node [midway, fill=white] {$3$};
\draw (b)--(d) node [midway, fill=white] {$3$};
\end{tikzpicture}
\hspace{0.5in}
\begin{tikzpicture}[scale=0.8]
\node[draw,shape=circle,fill=black,scale=0.5](a)[label=right: {$s_2$}] at (0,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](b)[label=below: {$s_1$}] at (0.5,-1) {};
\node[draw,shape=circle,fill=black,scale=0.5](c)[label=below: {$s_3$}] at (-0.5,-1) {};
\node[draw,shape=circle,fill=black,scale=0.5](d)[label=right: {$s_4$}] at (0,1) {};

\draw (b)--(a);
\draw (c)--(a);
\draw (a)--(d);
\end{tikzpicture}
\caption{The Coxeter diagram (left) for the Weyl group of type $D_4$. The fully commutative element $w=s_4s_2s_3s_1$ has heap poset $H_w$ shown on the right; this example is an equality case $b([\id,w]_L)=\frac{1}{3}$.}
\label{fig:type-D-equality}
\end{figure}

\begin{figure}
\centering
\begin{tikzpicture}
\node[draw,shape=circle,fill=black,scale=0.5](a)[label=below: {$s_1$}] at (0,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](b)[label=below: {$s_2$}] at (1,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](c)[label=below: {$s_3$}] at (2,0) {};

\draw (b)--(a) node [midway, fill=white] {$3$};
\draw (c)--(b) node [midway, fill=white] {$4$};
\end{tikzpicture}
\hspace{0.5in}
\begin{tikzpicture}[scale=0.8]
\node[draw,shape=circle,fill=black,scale=0.5](a)[label=right: {$s_2$}] at (0,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](b)[label=below: {$s_1$}] at (0.5,-1) {};
\node[draw,shape=circle,fill=black,scale=0.5](c)[label=below: {$s_3$}] at (-0.5,-1) {};
\node[draw,shape=circle,fill=black,scale=0.5](d)[label=right: {$s_3$}] at (0,1) {};

\draw (b)--(a);
\draw (c)--(a);
\draw (a)--(d);
\end{tikzpicture}
\caption{The Coxeter diagram (left) for the Weyl group of type $B_3$. The fully commutative element $w=s_3s_2s_3s_1$ has heap poset $H_w$ shown on the right; this example is an equality case $b([\id,w]_L)=\frac{1}{3}$.}
\label{fig:type-B-equality}
\end{figure}

\begin{figure}
\centering
\begin{tikzpicture}
\node[draw,shape=circle,fill=black,scale=0.5](a)[label=below: {$s_1$}] at (0,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](b)[label=below: {$s_2$}] at (1,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](c)[label=below: {$s_3$}] at (2,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](d)[label=below: {$s_4$}] at (3,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](e)[label=below: {$s_5$}] at (4,0) {};

\node[draw,shape=circle,fill=black,scale=0.5](f)[label=above: {$s_6$}] at (2,1) {};

\draw (b)--(a) node [midway, fill=white] {$3$};
\draw (b)--(c) node [midway, fill=white] {$3$};
\draw (c)--(d) node [midway, fill=white] {$3$};
\draw (d)--(e) node [midway, fill=white] {$3$};
\draw (c)--(f) node [midway, fill=white] {$3$};
\end{tikzpicture}
\hspace{0.5in}
\begin{tikzpicture}[scale=0.8]
\node[draw,shape=circle,fill=black,scale=0.5](a)[label=below: {$s_1$}] at (-1,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](b)[label=below: {$s_3$}] at (0,0) {};
\node[draw,shape=circle,fill=black,scale=0.5](c)[label=below: {$s_5$}] at (1,0) {};

\node[draw,shape=circle,fill=black,scale=0.5](d)[label=left: {$s_2$}] at (-0.5,1) {};
\node[draw,shape=circle,fill=black,scale=0.5](e)[label=right: {$s_4$}] at (0.5,1) {};

\node[draw,shape=circle,fill=black,scale=0.5](f)[label=right: {$s_3$}] at (0,2) {};

\node[draw,shape=circle,fill=black,scale=0.5](g)[label=right: {$s_6$}] at (0,3) {};

\draw (a)--(d)--(b)--(e)--(c);
\draw (d)--(f)--(e);
\draw (f)--(g);
\end{tikzpicture}
\caption{The Coxeter diagram (left) for the Weyl group of type $E_6$. The fully commutative element $w=s_6s_3s_2s_4s_1s_3s_5$ has heap poset $H_w$ shown on the right; this example is an equality case $b([\id,w]_L)=\frac{1}{3}$.}
\label{fig:type-E-equality}
\end{figure}


\section{Generalized semiorders}\label{sec:semiorders}
Recall that a finite poset $P$ is a \textit{semiorder} (also known as a \emph{unit interval order}) if there exists a function $f:P\rightarrow\R$ such that $x<y$ in $P$ if and only if $f(y)-f(x)\geq1$. It is a standard fact that $P$ is a semiorder if and only if $P$ avoids induced copies of the posets $\mathbf{2}+\mathbf{2}$ and $\mathbf{3}+\mathbf{1}$. This characterization says that, intuitively, semiorders are "tall and thin" so they are good candidates to serve as counterexamples to the $1/3$--$2/3$ Conjecture (see the discussion in \cite{Brightwell}). However semiorders have been ruled out as counterexamples.

\begin{theorem}[Brightwell~\cite{Brightwell-semiorder}]
\label{thm:brightwell-semiorder}
For any semiorder $P$ that is not a total order, $b(P)\geq\frac{1}{3}$. 
\end{theorem}

In Definition~\ref{def:generalized-semiorder} we extend the definition of semiorder to all finite Weyl groups, and in Theorem~\ref{thm:semiorder} we establish Conjecture~\ref{conj:1-3-2-3-weyl} for these convex sets.

\begin{defin}
\label{def:generalized-semiorder}
Let $\Phi$ be a root system with Weyl group $W$. A convex set $C\subseteq W$ is a \textit{generalized semiorder} if $C=W^A$ for some order ideal $A\subseteq\Phi^+$ of the root poset.
\end{defin}

\begin{ex}
Our definition of generalized semiorder recovers the classical definition of semiorder in type $A$. Indeed, given a poset $P$ on $n$ elements and a function $f:P\rightarrow\R$, let $p_1,\ldots,p_n$ be the elements of $P$, indexed such that $f(p_1)\leq f(p_2)\leq\cdots\leq f(p_n)$.

Recall that the type $A_{n-1}$ root system has positive roots $\Phi^+=\{e_i-e_j\:|\:1\leq i<j\leq n\}$, and that $e_{i'}-e_{j'}\leq e_{i}-e_{j}$ in the root poset if and only if $i\leq i'<j'\leq j$. By the discussion in Section~\ref{sec:intro-convex-sets}, the set of linear extensions of $P$ can be identified with $W^A$, where the set of allowed inversions is
\[
A=\{e_i - e_j \in \Phi^+ \: | \: f(p_j)-f(p_i)<1\}.
\]
This subset $A\subseteq\Phi^+$ must be an order ideal in $\Phi^+$: if $e_i-e_j\in A$ and $e_i'-e_j'\leq e_i-e_j$ in the root poset, then $f(p_{j'})\leq f(p_j)$ and $f(p_{i'})\geq f(p_i)$, so $f(j')-f(i')\leq f(j)-f(i)<1$, meaning $e_i'-e_j'\in A$.
\end{ex}

The following theorem is our main result of the section, whose proof is significantly more involved than that of Theorem~\ref{thm:brightwell-semiorder}.
\begin{theorem}\label{thm:semiorder}
Let $C\subseteq W$ be a generalized semiorder with $|C|>1$, then $b(C)\geq\frac{1}{3}$.
\end{theorem}
The main technique of Theorem~\ref{thm:semiorder} relies on the following purely root-theoretic fact (Lemma~\ref{lem:semiorder-orderideal}), for which we prove type by type. 
\begin{lemma}\label{lem:semiorder-orderideal}
Let $J\subseteq\Phi^+$ be a nonempty order ideal. Then there exists a simple root $\alpha_i\in J$ such that we cannot find $\beta_1\neq\beta_2\in J$ with $s_i\beta_1,s_i\beta_2\in\Phi^+\setminus J$.
\end{lemma}

\section{A uniform bound for finite Weyl groups}
\label{sec:bounds-Weyl}

In this section we provide a uniform lower bound for the balance constant of any non-singleton convex subset in any finite Weyl group; in the case of the symmetric group such a constant bound away from zero was first established by Kahn and Saks \cite{Kahn-Saks}. 

\begin{theorem}\label{thm:uniform-bound}
There exists an absolute constant $\epsilon>0$ such that for any non-singleton convex set $C$ in any finite Weyl group we have
\[
b(C)>\epsilon.
\]
\end{theorem}
In particular, we can take $\epsilon=1/2e^{12}$ as a uniform bound. However, the bound for classical types are much better: $1/2e$ for type $A_n$ (obtained by Kahn and Linial~\cite{Kahn-Linial}), $1/2e^2$ for types $B_n$ and $C_n$, and $1/2e^4$ for type $D_n$. 

Our proof of Theorem~\ref{thm:uniform-bound} is type-independent and uses a geometric argument inspired by that of Kahn and Linial \cite{Kahn-Linial}. Below we apply the Brunn--Minkowski Theorem from convex geometry to obtain useful bounds for general polytopes.  Applying these bounds to \emph{generalized order polytopes}, which we introduce in Section~\ref{sec:order-polytopes-bound}, then yields Theorem~\ref{thm:uniform-bound}.

For a convex body $Q\subseteq\R^n$ of full dimension, and a vector $v$ in $\R^n$, define $Q^+_v\coloneqq\{x\in Q\:|\: \langle v,x\rangle\geq0\}$ and $Q_v^-\coloneqq\{x\in Q\:|\:\langle v,x\rangle\leq0\}$, the two pieces of $Q$ split by the hyperplane orthogonal to $v$. 

\begin{prop}\label{cor:bm}
Let $Q\subseteq\R^n$ be a full-dimensional compact convex body with centroid $c_Q$. Let $m\geq1$ and $v\in\R^n$ such that $\langle v,c_Q\rangle\geq\frac{-m}{n+1}$. Suppose that $\min_{x\in Q}\langle v,x\rangle\leq-1$ and $\max_{y\in Q}\langle v,y\rangle\geq1$. Then
$$\frac{\Vol(Q_v^+)}{\Vol(Q)}\geq\frac{1}{2e^m}.$$
\end{prop}

\subsection{A uniform geometric approach via root-system order polytopes}\label{sec:order-polytopes-bound}
In this section, we define an analog of the order polytope of a poset (see \cite{Stanley-poset-polytopes}) for convex sets in any finite Weyl group.

Let $\Phi$ be a root system of rank $r$ with highest root $\xi$. The \textit{fundamental alcove} is
\[
Q_{\id}\coloneqq\{x\in E\:|\:\langle x,\alpha\rangle\geq0\text{ for }\alpha\in\Phi^+,\langle x,\xi\rangle\leq1\}
\]
For $w\in W(\Phi)$, define $Q_{w}\coloneqq w^{-1}Q_{\id}$.

\begin{def-prop}\label{def:order-polytope}
Let $C\subseteq W(\Phi)$ be a convex set. The \textit{generalized order polytope} of $C$ is defined to be
$$\O(C)\coloneqq \bigcup_{w\in C}Q_{w},$$
and this is indeed a convex polytope.
\end{def-prop}

We write $\xi=\sum_{i=1}^r\langle\omega_i^{\vee},\xi\rangle\alpha_i$. We see that $Q_{\id}$ is an $r$-simplex having vertices $0$ and $\{\omega_i^{\vee}/\langle\omega_i^{\vee},\xi\rangle \: | \: i=1,\ldots,r\}$. More explicitly, if we write $\xi=c_1\alpha_1+\cdots+c_r\alpha_r$, then vertices of $Q_{\id}$ are $0,\omega_1^{\vee}/c_1,\ldots,\omega_r^{\vee}/c_r$. This means that the centroid of $Q_{\id}$ is $\frac{1}{r+1}\sum_{i=1}^r\omega_i^{\vee}/\langle\omega_i^{\vee},\xi\rangle$ and the centroid $o_C$ of the order polytope $\O(C)$ is
\[
o_C = \frac{1}{r+1}\frac{1}{|C|}\sum_{w\in C}w^{-1}\left(\sum_{i=1}^r\frac{\omega_i^{\vee}}{\langle\omega_i^{\vee},\xi\rangle}\right).
\]

\begin{lemma}\label{lem:order-polytope-centroid}
Let $C\subseteq W$ be a non-singleton convex set whose order polytope $\O(C)$ has centroid $o_C$. There exists $\beta\in\Phi^+$ such that $\emptyset\neq C_{\beta}:=C_{s_{\beta}}\subsetneq C$ and $|\langle o_C,\beta\rangle|\leq m/(r+1)$ where 
\begin{align*}
&m=\frac{r}{m_0}+\frac{1}{m_1}-\frac{\height(\Phi)}{m_0m_1},&
&m_0=\min_{i\in[r]}\langle\omega_i^{\vee},\xi\rangle,& &m_1=\max_{i\in[r]}\langle\omega_i^{\vee},\xi\rangle.&
\end{align*}
\end{lemma}

Proposition~\ref{cor:bm} and Lemma~\ref{lem:order-polytope-centroid} are the main ingredients used to establish:

\begin{theorem}\label{thm:uniform-bound-specific}
Let $C\subseteq W(\Phi)$ be a non-singleton convex set, then, using the notation of Lemma~\ref{lem:order-polytope-centroid}, \[
b(C)\geq1/2e^{mm_1}.
\]
\end{theorem}

% \acknowledgements{}

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