\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.41}{22(1)}{2015}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

%\documentclass{amsart}
%\usepackage[final]{epsfig}
%\usepackage{graphics}
%\usepackage{float}
\usepackage{amsmath,amsthm,amssymb}
%\usepackage{amsfonts}
%\usepackage{latexsym}
%\usepackage{amssymb}
%\usepackage{graphicx}
%\usepackage{url}
%\usepackage{epstopdf}
%\usepackage{verbatim}
%\usepackage[margin=1in]{geometry}
%\usepackage{amsthm}
%\usepackage{tikz}
%\usepackage{caption}
%\usepackage{tikz-cd}
%\usepackage{enumitem}

%\makeatletter
\newtheorem*{rep@theorem}{\rep@title}
%\newcommand{\Comment}[1]{{\color{blue} \sf ($\clubsuit$ #1 $\clubsuit$)}}
%\newcommand{\CommentE}[1]{{\color{cyan} \sf ($\diamondsuit$ #1 $\diamondsuit$)}}

\newcommand{\newreptheorem}[2]{%
\newenvironment{rep#1}[1]{%
 \def\rep@title{#2 \ref{##1}}%
 \begin{rep@theorem}}%
 {\end{rep@theorem}}}
\makeatother

\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem{case}{Case}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{example}[lemma]{Example}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{problem}{Problem}
\newtheorem{conjecture}[lemma]{Conjecture}
\newtheorem*{theorem*}{Theorem}
\newreptheorem{theorem}{Theorem}
\newtheorem{question}{Question}[section]

\newcommand{\eps}{{\varepsilon}}
\newcommand{\g}{{\gamma}}
\newcommand{\G}{{\Gamma}}
%\newcommand{\proofend}{$\Box$\bigskip} 
\newcommand{\CP}{{\mathbf {CP}}}
\newcommand{\PP}{{\mathsf P}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\RP}{{\mathbb {RP}}}  
\newcommand{\Tr}{{\rm Tr\ }}
%\def\proof{\paragraph{Proof.}}
%\def\proof{\par{\it Proof}. \ignorespaces}
%\def\endproof{{\ \vbox{\hrule\hbox{%
%     \vrule height1.3ex\hskip0.8ex\vrule}\hrule }}\par}

\DeclareMathOperator{\convex}{Conv}
\DeclareMathOperator{\conv}{Conv}
\DeclareMathOperator{\CH}{Conv}
\DeclareMathOperator{\Perm}{Perm}

\DeclareMathOperator{\M}{\mathcal M}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\newcommand*{\argminl}{\argmin\limits}
\newcommand*{\argmaxl}{\argmax\limits}
\newcommand{\overlim}[1]{{\buildrel{#1}\over\longrightarrow\;}}
\DeclareMathOperator{\Inc}{Inc}

\newtheorem*{thm*}{Theorem}
\newtheorem*{thma*}{Theorem A}
\newtheorem*{thmb*}{Theorem B}
\newtheorem*{thmc*}{Theorem C}
\newtheorem*{thmd*}{Theorem D}

\begin{document}

\title{\bf The Maximum Difference between the\\ Number of Atoms and Number of Coatoms\\ of a Bruhat interval of the Symmetric Group}

\author{Emmanuel Tsukerman\\
\small Department of Mathematics\\[-0.8ex]
\small University of California\\[-0.8ex]
\small Berkeley, CA 94720-3840, U.S.A.\\
\small \texttt{e.tsukerman@berkeley.edu}
}

\date{\dateline{Aug 9, 2014}{Jan 29, 2015}{Feb 25, 2015}\\
\small Mathematics Subject Classifications: 20B30; 05E15}


\maketitle
%\setcounter{tocdepth}{1}

\begin{abstract}
We determine the largest difference between the number of atoms and number of coatoms of a Bruhat interval of the symmetric group $S_n$. We then pose the question of describing such extremal intervals $[u,v] \subset S_n$ and give a partial description by specifying the elements $v$ that can occur. 

\bigskip\noindent \textbf{Keywords:}  Symmetric group; Bruhat order
\end{abstract}



\section{Introduction}

Much work has been done on understanding the structure of Bruhat intervals of the symmetric group (see, e.g., \cite{MR644668}, \cite{MR1970983} and \cite{BB} along with references therein).
Recently, particular interest has arisen in understanding the number of atoms and coatoms of Bruhat intervals of the symmetric group \cite{MR2221362, MR2727461}. There, the maximum number of atoms and coatoms of an interval of a given length is determined. In this note, we determine the largest difference between the number of atoms and the number of coatoms of a Bruhat interval of $S_n$.

Our main results in this note are as follows.

\begin{reptheorem}{maxDiff}
Let $\mathcal{I}$ be the set of intervals in $S_n$ and for $I \in \mathcal{I}$, let $a(I)$ and $c(I)$ denote the number of atoms and coatoms of $I$ respectively. Then
\[
\max_{I \in \mathcal{I}} c(I)-a(I) = \lfloor n^2/4 \rfloor -n+1.
\]
\end{reptheorem}

\begin{reptheorem}{maximizes}
Let $n \geq 4$. An interval $I=[u,v] \subset S_n$ maximizes $c(I)-a(I)$ if and only if $c(I)=\lfloor n^2/4 \rfloor$ and $a(I)=n-1$.
\end{reptheorem}

Since the symmetric group is self-dual via an order-reversing automorphism, all the results above hold when $c(I)$ and $a(I)$ are switched.

\section{Facts about Bruhat Intervals in $S_n$}


We will be needing the following definition and three results.


\begin{definition}\cite[Definition 4.9]{1406.5202}\label{defGat}
Let $u \leq v$ be permutations in $S_n$,
 and let $\overline{T}([u,v]):=\{t  \in T : u \lessdot ut \leq v\}$ 
and $\underline{T}([u,v]):=\{t  \in T : v \gtrdot vt \geq u\}$
be the 
transpositions labeling the cover relations corresponding
to the atoms and coatoms in the interval. Define a labeled graph $G^{at}$ (resp. $G^{coat}$) on $[n]$ such that $G^{at}$ (resp. $G^{coat}$) has an edge
between $a$ and $b$ if and only if 
the transposition $(a b)$ is a member of $\overline{T}([u,v])$ (resp. $(a b)$ is a member of $\underline{T}([u,v])$). 
\end{definition}

The next result allows us to relate the atoms and coatoms of a Bruhat interval.

\begin{theorem}\cite[Proposition 4.10]{1406.5202} \label{atomPartition}
Let $[u,v] \subset S_n$.
The labeled graphs  $G^{at}$ and $G^{coat}$ have the same connected components.
\end{theorem}

The following result on the structure of  $G^{at}$ and $G^{coat}$ is a slight generalization of \cite[Lemma 2.7]{MR2221362}. An ordered graph $G$ is a graph with a total order over its nodes. For instance, $G^{at}$ and $G^{coat}$ inherit a total order from $[n]$. A \emph{cycle} of an ordered graph is a tuple of vertices $(v_0,v_1,\ldots,v_{k})$ such that $v_k=v_0$, $v_i$ is adjacent to $v_{i+1}$ for each $0 \leq i \leq k-1$, and $v_0<v_1< \cdots < v_{k-1}$.

\begin{proposition} \label{noOrderedCycles} The ordered graphs $G^{at}$ and $G^{coat}$ have no cycles. In particular, they are simple and triangle-free. 
\end{proposition}

\begin{proof}
The assertion that $G^{at}$ is simple is immediate. Assume by contradiction that $C=(v_0,v_1,\ldots,v_k)$ is a cycle in $G^{at}$ with $k \geq 2$. By properties of Bruhat order on the symmetric group, the existence of an edge $\{a,b\}$ with $a<b$ implies that $u(a)<u(b)$ and for any $a < c < b$, $u(c) \not \in [u(a),u(b)]$. Looking at edges $\{v_{i} v_{i+1}\}, i=0,1,\ldots,k-2$, of cycle $C$, we see that
\[
u(v_0)<u(v_1)<\ldots<u(v_{k-1}).
\]
However, the existence of edge $\{v_{k-1},v_{k}\}=\{v_0,v_{k-1}\}$ implies that $u(v_i) \not \in [u(v_0),u(v_{k-1})]$ for any $1 \leq i \leq k-2$, which is a contradiction. The proof for $G^{coat}$ is analogous.

Finally, any triangle gives rise to an ordered cycle since it is a complete graph. This proves that the graphs are triangle-free.
\end{proof}

The final result describes the permutations $v$ for which the number of coatoms is maximal.

\begin{theorem}\label{whenMaxAtom}\cite[Proposition 2.9]{MR2221362} 
For every positive integer $n$,
\[
\# \{v \in S_n \, \vert \, \#\underline{T}([1,v])=\lfloor n^2/4 \rfloor\}=\begin{cases}
n, & \text{ if } n \text{ is odd}; \\
n/2, & \text{ if } n \text{ is even}.
\end{cases}
\]
Each such permutation has the form
\begin{align}\label{optTop}
v=[t+m+1,t+m+2,\ldots,n,t+1,t+2,\ldots,t+m,1,2,\ldots,t],
\end{align}
where $m \in \{ \lfloor n/2 \rfloor, \lceil n/2 \rceil\}$ and $1 \leq t \leq n-m$.
\end{theorem}


\section{Largest gap between the number of atoms and coatoms of an interval in the symmetric Group}

In this section, we consider the question of how large a gap can there be between the number of atoms and coatoms  of a Bruhat interval of the symmetric group $S_n$. The first result is a simple inequality that will be used later in finding a maximum.

\begin{lemma} \label{floorLemma}
For all $k_1,k_2 \in \N$ with $k_i \geq 2$,
\[
\lfloor k_1^2/4 \rfloor+\lfloor k_2^2/4 \rfloor+1 < \lfloor (k_1+k_2)^2/4 \rfloor.
\]
\end{lemma}

\begin{proof}
We have
\[
\lfloor k_1^2/4 \rfloor+\lfloor k_2^2/4 \rfloor \leq \lfloor k_1^2/4+k_2^2/4 \rfloor.
\]
Therefore it suffices to prove that 
\[
\lfloor k_1^2/4+k_2^2/4 \rfloor+1 <  \lfloor (k_1+k_2)^2/4 \rfloor.
\]
Observe that for $k_1,k_2 \geq 2$,
\begin{equation*}
k_1^2/4+k_2^2/4+1 < k_1^2/4+k_2^2/4+\frac{k_1 k_2}{2}=(k_1+k_2)^2/4. 
\end{equation*} 
\end{proof}

We now prove the main result of this note, which states that the largest difference between the number of coatoms and atoms of an interval of $S_n$ is equal to $\lfloor n^2/4 \rfloor -n+1$.

\begin{theorem}\label{maxDiff}
Let $\mathcal{I}$ be the set of intervals in $S_n$ and for $I \in \mathcal{I}$, let $a(I)$ and $c(I)$ denote the number of atoms and coatoms of $I$ respectively. Then
\[
\max_{I \in \mathcal{I}} c(I)-a(I) = \lfloor n^2/4 \rfloor -n+1.
\]
\end{theorem}

\begin{proof}
Let $I \in \mathcal{I}$ and consider $G^{at}$ and $G^{coat}$ as in Definition \ref{defGat}. 
By Theorem \ref{atomPartition}, $G^{at}$ and $G^{coat}$ have the same connected components. Let $\mathcal{K}_i$, $i=1,2,\ldots,m$, be the connected components of $G^{at}$ and $G^{coat}$, and let $k_i \geq 1$ denote their respective number of vertices. Let $p$ be the number of active components, i.e., components with more than one vertex, and let $q=m-p$. By Proposition \ref{noOrderedCycles} and Tur\'{a}n's Theorem, a connected component of $G^{at}$ or $G^{coat}$ with $k$ vertices can have at most $\lfloor k^2/4 \rfloor$ edges. Consequently, the total number of edges $c(I)$ satisfies
\[
c(I) \leq \sum_{i=1}^m \lfloor k_i^2/4 \rfloor.
\]
Also, since each $\mathcal{K}_i$ is connected, it must have at least $k_i-1$ edges. Consequently,
\[
a(I) \geq \sum_{i=1}^m (k_i-1).
\]
Therefore
\begin{align} \label{eq1}
 c(I)-a(I) \leq \sum_{i=1}^m \lfloor k_i^2/4 \rfloor -(k_i-1).
\end{align}
We maximize the right side of (\ref{eq1}) over possible $\mathcal{K}_i$. Let $f(x)=\lfloor x^2/4 \rfloor-x+1$, so that
\[
c(I)-a(I) \leq \sum_{i=1}^m f(k_i).
\]
By Lemma \ref{floorLemma}, if $k_1,k_2 \geq 2$, then
\begin{align}\label{ineq}
f(k_1+k_2) > f(k_1)+f(k_2).
\end{align}
Note that $\sum k_i=n-q$ because the number of connected components with no edges is $q$. Using this statement and inequality (\ref{ineq}) yields
\[
\sum_{i=1}^m f(k_i) \leq f(n-q).
\]
Since 
\[
\Delta[f](n):=f(n+1)-f(n)=\begin{cases}
\frac{n}{2}-1 & \text{if } n \text{ is even} \\
\frac{n+1}{2}-1 & \text{if } n \text{ is odd},
\end{cases}
\]
the function $f:\N \rightarrow \R$ is monotonically increasing. It follows that for every $I \in \mathcal{I}$,
\[
c(I)-a(I) \leq f(n).
\]
Next we show that the value $f(n)$ is attained for some interval $I=[u,v]$. We consider any $v$ of the form (\ref{optTop}). By Theorem \ref{whenMaxAtom}, the interval $[1,v]$ has $\lfloor n^2/4 \rfloor$ coatoms. The identity permutation has exactly $n-1$ elements covering it. It follows that $c(I)-a(I) \geq  f(n)$, so that equality must hold.
\end{proof}

\begin{theorem}\label{maximizes}
Let $n \geq 4$. An interval $I=[u,v] \subset S_n$ maximizes $c(I)-a(I)$ if and only if $c(I)=\lfloor n^2/4 \rfloor$ and $a(I)=n-1$.
\end{theorem}
\begin{proof}
From the proof of Theorem \ref{maxDiff}, 
\[
c(I)-a(I) \leq f(n-q).
\]
The assumption that $n \geq 4$ implies that $f(n)>f(n-q)$ for every $q>0$. Moreover, we know that the maximum value of $f(n)$ is attainable. Therefore $c(I)-a(I)$ is maximized only if $q=0$. So assume that $q=0$. Let $K$ be the single connected component of $G^{at}$ and $G^{coat}$ which contains $n$ vertices. Then
\[
c(I) \leq \lfloor n^2/4 \rfloor
\]
and
\[
a(I) \geq n-1. 
\]
\end{proof}

\begin{corollary}\label{optV}
Let $n \geq 4$. Suppose that $I=[u,v] \subset S_n$ is an interval for which $c(I)-a(I)$ is maximized. Then $v$ is of the form \normalfont{(\ref{optTop})}.
\end{corollary}

\begin{proof}
The number of coatoms of $[u,v]$ is less than or equal to the number of coatoms of $[1,v]$. By Theorem \ref{whenMaxAtom}, the number of coatoms of $[1,v]$ is $\lfloor n^2/4 \rfloor$ only for $v$ of the form (\ref{optTop}).
\end{proof}

A family of intervals for which the optimal value $c(I)-a(I) = \lfloor n^2/4 \rfloor -n+1$ is attained is given by
\[
I=[1,v]
\]
for $v$ as in (\ref{optTop}). There exist other intervals for which this maximum is attained. For example, in $S_4$, the intervals for which the maximum is attained are 
\[
[1234,3412],[1234,4231],[1243,4231],[2134,4231].
\]

It is natural, then, to ask the following question:

\begin{question}
What are the intervals $I \subset S_n$ such that $c(I)-a(I)$ is equal to the maximum value  $\lfloor n^2/4 \rfloor -n+1$?
\end{question}

Corollary \ref{optV} shows that if $I=[u,v]$ then $v$ is of the form (\ref{optTop}). It remains to be understood which combinations of $u$ and $v$ are extremal.

\subsection*{Acknowledgments}
This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE 1106400. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the authors(s) and do not necessarily reflect the views of the National Science Foundation.


\begin{thebibliography}{Kob11}

\bibitem[AR06]{MR2221362}
Ron~M. Adin and Yuval Roichman.
\newblock On degrees in the {H}asse diagram of the strong {B}ruhat order.
\newblock {\em S\'em. Lothar. Combin.}, 53:Art. B53g, 12 pp. (electronic),
  2004/06.

\bibitem[BB05]{BB}
A.~Bj{\"o}rner and F.~Brenti.
\newblock {\em Combinatorics of {C}oxeter groups}, volume 231 of {\em Graduate
  Texts in Mathematics}.
\newblock Springer, New York, 2005.

\bibitem[BW82]{MR644668}
Anders Bj{\"o}rner and Michelle Wachs.
\newblock Bruhat order of {C}oxeter groups and shellability.
\newblock {\em Adv. in Math.}, 43(1):87--100, 1982.

\bibitem[Hul03]{MR1970983}
Axel Hultman.
\newblock Bruhat intervals of length 4 in {W}eyl groups.
\newblock {\em J. Combin. Theory Ser. A}, 102(1):163--178, 2003.

\bibitem[Kob11]{MR2727461}
Masato Kobayashi.
\newblock The maximum number of atoms of {B}ruhat intervals in the symmetric
  groups.
\newblock {\em European J. Combin.}, 32(1):67--71, 2011.

\bibitem[TW14]{1406.5202}
Emmanuel Tsukerman and Lauren Williams.
\newblock Bruhat interval polytopes.
\newblock Preprint, 2014. \arxiv{1406.5202} 

\end{thebibliography}

%\bibitem{BB1} A. Bj\"{o}rner and F. Brenti. \textit{Combinatorics of Coxeter Groups.}

%\end{thebibliography}



\end{document}

