%% 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 optionstaken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{70}
%% 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{dsfont, fancyhdr, graphicx, color, tabularx, mathtools, MnSymbol}%hyperref for urls, etc. MnSymbol for shorter \nearrows in mathmode

%\usepackage{geometry}
%\usepackage[shortlabels]{enumitem} %for better lists?
\usepackage[all]{xy} %for commutative diagrams
%\usepackage[capitalize,nameinlink,noabbrev,nosort]{cleveref}

\def\Imm{\operatorname{Imm}}
\def\gr{\operatorname{gr}}

\newcommand{\CC}{{\mathbb C}}
\newcommand{\QQ}{{\mathbb Q}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\FF}{{\mathbb F}}
\newcommand{\PP}{\mathbb P}
\newcommand{\TT}{\mathbb T}
\newcommand{\mcA}{{\mathcal A}}
\newcommand{\mcB}{{\mathcal B}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\Comment}[1]{{\color{blue} \sf ($\clubsuit$ #1 $\clubsuit$)}}
\newcommand{\next}[1]{{\color{red} \sf [$\clubsuit$ #1 $\clubsuit$]}}
\newcommand{\Mat}{\text{Mat}}
\newcommand{\res}[2]{#1|_{#2}}
\newcommand{\pentl}[1]{P^\ell_{#1}}
\newcommand{\pentr}[1]{P^r_{#1}}




\theoremstyle{plain}
\newtheorem{prop}{Proposition}[section] %[section] numbers things section.subsection.thmnumber
\newtheorem{cor}[prop]{Corollary} %[prop] in this position means cor environment uses same counter as prop
\newtheorem{lem}[prop]{Lemma}
\newtheorem{conj}[prop]{Conjecture}
\newtheorem{thm}[prop]{Theorem}

\theoremstyle{definition}
\newtheorem{defn}[prop]{Definition}
\newtheorem{rmk}[prop]{Remark}
\newtheorem{ex}[prop]{Example}
\newtheorem{question}[prop]{Question}

\numberwithin{equation}{section} 

%% define your title in the usual way
\title{123, 2143-avoiding Kazhdan--Lusztig immanants and $k$-positive matrices}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Sunita Chepuri\thanks{\href{mailto:chepu003@umn.edu}{chepu003@umn.edu}. Partially supported by RTG grant NSF/DMS--1148634 }\addressmark{1} \and Melissa Sherman-Bennett\thanks{\href{mailto:m_shermanbennett@berkeley.edu}{m\_shermanbennett@berkeley.edu}. Partially supported by NSF GRFP grant DGE--1752814}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Mathematics, University of Minnesota, Minneapolis, MN, USA \\ \addressmark{2}Department of Mathematics, University of California, Berkeley, CA, 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{		Immanants are functions on square matrices generalizing the determinant and permanent. Stembridge showed that irreducible character immanants are nonnegative on totally nonnegative matrices. Rhoades and Skandera later defined Kazhdan--Lusztig immanants, using specializations of Kazhdan--Lusztig polynomials at 1; results of (Stembridge, 1992) and (Haiman, 1993) show that these are also nonnegative on totally nonnegative immanants. Here, we give conditions on $v\in S_n$ so that the Kazhdan--Lusztig immanant corresponding to $v$ is positive on $k$-positive matrices.}

%% 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{immanants, total positivity}

%% 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
\addbibresource{bibliography.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} 
Given a function $f:S_n \to \CC$, the \emph{immanant} associated to $f$, $\Imm_f:\Mat_{n \times n}(\CC) \to \CC$, is the function

\begin{equation}
M=(m_{ij})_{1 \leq i, j \leq n} \mapsto \Imm_f(M):= \sum_{w \in S_n} f(w) ~m_{1, w(1)} \cdots m_{n, w(n)}.
\end{equation}

Well-studied examples include the determinant, where $f(w)=(-1)^{\ell(w)}$, the permanent, where $f(w)=1$, and more generally \emph{character immanants}, where $f$ is an irreducible character of $S_n$.

We will be interested in immanants evaluated on matrices that meet certain positivity conditions.

\begin{defn}
	Let $M \in \Mat_{n \times n}(\CC)$. We call $M$ $k$\emph{-positive} (respectively, $k$\emph{-nonnegative}) if all minors of size at most $k$ are positive real numbers (respectively, nonnegative real numbers). If $M$ is $n$-positive (respectively, $n$-nonnegative), we also call $M$ \emph{totally positive} (respectively, \emph{totally nonnegative}). 
\end{defn}

Notice that the entries of $M$ are $1 \times 1$ minors, so if $M$ is $k$-nonnegative for any $k\geq 1$, it has real entries.

\begin{ex}
    The matrix
    
    \[ \begin{bmatrix}
    11 & 9 & 3\\
    8 & 7 & 3 \\
    2 & 2 & 1 \\
    \end{bmatrix}
    \]
     is $2$-positive but has negative determinant, so is not $3$-nonnegative (totally nonnegative). 
\end{ex}


The positivity properties of immanants have been of interest since the early 1990s. In \cite{GJ}, Goulden and Jackson conjectured (and Greene \cite{Greene} later proved) that character immanants of Jacobi--Trudi matrices are polynomials with nonnegative coefficients. This was followed by a number of positivity conjectures by Stembridge \cite{StemConj}, including two that were proved shortly thereafter: Haiman showed that character immanants of generalized Jacobi--Trudi matrices are Schur-positive \cite{HaiConj} and Stembridge showed that character immanants of totally nonnegative matrices are nonnegative \cite{StemTNN}. 

In \cite{StemConj}, Stembridge also asks if certain monomial immanants are nonnegative on $k$-nonnegative matrices. More generally, it is natural to ask what one can say about the signs of immanants on $k$-nonnegative matrices. Stembridge's proof in \cite{StemTNN} does not extend to $k$-nonnegative matrices, as it relies on the existence of a certain factorization for totally nonnegative matrices which does not exist for all $k$-nonnegative matrices. 

Here, we will focus on the signs of \emph{Kazhdan--Lusztig immanants}, which were defined by Rhoades and Skandera \cite{RS}. 

Before giving the definition of Kazhdan--Lusztig immanants, we briefly review some basic notions from Coxeter theory, which we will need in what follows. For details, see e.g. \cite{BB}. For $1 \leq i \leq n-1$, let $s_i \in S_n$ be the permutation exchanging $i$ and $i+1$ and fixing all other elements of $\{1, \dots, n\}$. We call $s_1, \dots, s_{n-1}$ \emph{simple transpositions}. Any permutation $v \in S_n$ can be written as a product of simple transpositions. If an expression for $v$ as a product of simple transpositions uses the smallest possible number of simple transpositions, it is called a \emph{reduced expression}. The \emph{length} of $v$, denoted $\ell(v)$, is the number of simple transpositions in a reduced expression for $v$. The length of $v$ is also the number of inversions of $v$ (that is, the number of pairs of integers $1 \leq i < j \leq n$ such that $v(i)>v(j)$). There is a unique element of $S_n$ of maximum length, which is $w_0:= n~ (n-1)~ \dots~ 2~1$.
For $w, v \in S_n$, $v$ is smaller than $w$ in the (strong) Bruhat order, which we denote by $v \leq w$, if some (equivalently, every) reduced expression for $w$ contains as a subexpression a reduced expression for $v$.

\begin{defn}
	Let $v \in S_n$. The \emph{Kazhdan--Lusztig immanant} $\Imm_v: \Mat_{n \times n}(\CC) \to \CC$ is given by 
	\begin{equation} \label{eq:immFormula1}
	\Imm_v(M):= \sum_{w \in S_n} (-1)^{\ell(w)-\ell(v)} P_{w_0w, w_0v}(1) ~m_{1, w(1)} \cdots m_{n, w(n)}
	\end{equation}
	where $P_{x, y}(q)$ is the Kazhdan--Lusztig polynomial associated to $x,y \in S_n$ and $w_0 \in S_n$ is the longest permutation.
\end{defn}

For the definition of Kazhdan--Lusztig polynomials and their basic properties, see e.g. \cite{BB}. It is a fact that $P_{x, y}(q)=0$ if $x$ is not less than or equal to $y$ in the Bruhat order, and that $P_{x, w_0}(q)=1$ for all $x \in S_n$. Using these two facts, we can compute that, for example, $\Imm_{e}(M)=\det M$ and $\Imm_{w_0}(M)=m_{n, 1}m_{n-1, 2} \cdots m_{1, n}$. 

Using results of \cite{ HaiConj, StemTNN}, Rhoades and Skandera \cite{RS} show that Kazhdan--Lusztig immanants are nonnegative on totally nonnegative matrices, and are Schur-positive on generalized Jacobi--Trudi matrices. Further, they show that character immanants are nonnegative linear combinations of Kazhdan--Lusztig immanants, so from the perspective of positivity, Kazhdan--Lusztig immanants are the more fundamental object to study.

We will call an immanant \emph{$k$-positive} if it is positive on all $k$-positive matrices. We are interested in the following question.

\begin{question} \label{quest:KLImmkPos}
	Let $0<k<n$ be an integer. For which $v \in S_n$ is $\Imm_v(M)$ $k$-positive?
\end{question}

Notice that $\Imm_e(M)=\det M$ is $k$-positive only for $k=n$. On the other hand, $\Imm_{w_0}$ is $k$-positive for all $k$, since it is positive as long as the entries (i.e. the $1 \times 1$ minors) of $M$ are positive. So, the answer to \cref{quest:KLImmkPos} is a nonempty proper subset of $S_n$.

Pylyavskyy conjectured that there is a link between $\Imm_v(M)$ being $k$-positive and $v$ avoiding certain patterns.

\begin{defn}
	Let $v \in S_n$, and let $w\in S_m$. Suppose $v=v_1\cdots v_n$ and $w=w_1 \cdots w_m$ in one-line notation. We say that the pattern $w_1 \cdots w_m$ \emph{occurs} in $v$ if there exist $1\leq i_1< \dots <i_m\leq n$ such that $v_{i_1} \cdots v_{i_m}$ are in the same relative order as $w_1 \cdots w_m$. We say $v$ \emph{avoids} the pattern $w_1 \cdots w_m$ if it does not occur in $v$.
\end{defn}

More precisely, Pylyavskyy conjectured the following.

\begin{conj}[\cite{Pyl}] \label{conj:pasha}
    Let $0<k<n$ be an integer and let $v \in S_n$ avoid $12\cdots (k+1)$. 
Then $\Imm_v(M) $ is $k$-positive. 
\end{conj}

Our main result is a description of some $k$-positive Kazhdan--Lusztig immanants, in the spirit of Pylyavskyy's conjecture.

\begin{thm}  \label{thm:123avoiding}
	Let $0<k <n$ be an integer and let $v \in S_n$ be 123-, 2134-, $1(2k)(2k-1)...2$-, and $(2k-1)(2k-2)...1(2k)$-avoiding. Then $\Imm_v(M)$ is $k$-positive.
\end{thm}

\begin{ex}
Consider $v=2413$ in $S_4$. It avoids the patterns $123$, $2134$, $1432$, and $3214$, so \cref{thm:123avoiding} guarantees that
\begin{align*} \Imm_v(M)&= m_{12}m_{24}m_{31}m_{43} -m_{14}m_{22}m_{31}m_{43}- m_{13}m_{24}m_{31}m_{42}+m_{14}m_{23}m_{31}m_{42}\\
&-m_{12}m_{24}m_{33}m_{41}+m_{14}m_{22}m_{33}m_{41}+m_{13}m_{24}m_{32}m_{41}-m_{14}m_{23}m_{32}m_{41}
\end{align*}
is positive on all 2-positive $4 \times 4$ matrices.
\end{ex}

\begin{rmk}
    For $k=2$, \cref{thm:123avoiding} concerns permutations which are 123-, 2134-, 1432-, and 3214-avoiding. According to \cite{oeis}, the number of such permutations in $S_n$ is given by the coefficient of $x^n$ in the power series
    \[\sum_{i=0}^{\infty} c_n x^n= \frac{1-x}{1-2x-x^3}.
    \]
    
    For other $k$, the number of permutations avoiding 123, 2134, $1(2k)(2k-1)...2$, and $(2k-1)(2k-2)...1(2k)$ is not known.
\end{rmk}

Note that \cref{thm:123avoiding} supports \cref{conj:pasha}. Indeed, if $k=1$, the $(2k-1)(2k-2)...1(2k)$-avoiding condition reduces to avoiding $12$. For $k \geq 2$, the 123-avoiding condition ensures that $v$ also avoids $12\cdots(k+1)$.

Before outlining the the proof of \cref{thm:123avoiding}, we would like to provide some additional motivation and context for \cref{quest:KLImmkPos}. For an arbitrary reductive group $G$, Lusztig~\cite{LusTPGr} defined the totally positive part $G_{>0}$ and showed that elements of the dual canonical basis of $\mc{O}(G)$ are positive on $G_{>0}$. Fomin and Zelevinsky~\cite{FZTNNSemisimple} later showed that for semisimple groups, $G_{>0}$ is characterized by the positivity of generalized minors, which are dual canonical basis elements corresponding to the fundamental weights of $G$ and their images under Weyl group action. Note that the generalized minors are a finite subset of the (infinite) dual canonical basis, but their positivity guarantees the positivity of all other elements of the basis. 

In the case we are considering, $G=GL_n(\CC)$, $G_{>0}$ consists of the totally positive matrices and generalized minors are just ordinary minors. Skandera~\cite{Skan} showed that Kazhdan--Lusztig immanants are part of the dual canonical basis of $\mc{O}(GL_n(\CC))$, which gives another perspective on their positivity properties. (In fact, Skandera proved that every dual canonical basis element can be obtained from a Kazhdan--Lusztig immanant evaluated on matrices with repeated rows and columns.) In light of these facts, \cref{quest:KLImmkPos} becomes a question of the following kind.

\begin{question} \label{quest:CanBasiskPos}
	Suppose some finite subset $S$ of the dual canonical basis is positive on $M \in G$. Which other elements of the dual canonical basis are positive on $M$? In particular, what if $S$ consists of the generalized minors corresponding to the first $k$ fundamental weights and their images under the Weyl group action?
\end{question}

These questions have a similar flavor to positivity tests arising from cluster algebras, which is different than the approach we take here. The coordinate ring of $GL_n$ is a cluster algebra, with some clusters given by double wiring diagrams \cite{CA3}. The minors are cluster variables. If we restrict our attention to the minors of size at most $k$ in the clusters for $GL_n$, we obtain a number of sub-cluster algebras, investigated by the first author in \cite{kPosTests}. The cluster monomials in those sub-algebras will be positive on $k$-positive matrices. Thus, one strategy to show $\Imm_v(M)$ is $k$-positive is to show it is a cluster monomial in a sub-cluster algebra. Interestingly, the Kazhdan--Lusztig immanants of 123-, 2143-, 1423-, and 3214-avoiding permutations do appear in sub-cluster algebras of this kind for $k=2$. In general, however, it is not known if $\Imm_v$ is a cluster variable in the cluster structure on $GL_n$, or in the sub-cluster algebras using only minors of size at most $k$. It is conjectured that cluster monomials form a (proper) subset of the dual canonical basis, so the cluster algebra approach would at best provide a partial answer to \cref{quest:CanBasiskPos}.



\section{Results}

To prove \cref{thm:123avoiding}, we first note that \cref{eq:immFormula1} has a much simpler form when $v$ is $1324$- and $2143$-avoiding. By \cite{KLPoincare}, $P_{x, y}(q)$ is the Poincar\'e polynomial of the local intersection cohomology of the Schubert variety indexed by $y$ at any point in the Schubert variety indexed by $x$; by \cite{LSsmoothSchub}, the Schubert variety indexed by $y$ is smooth precisely when $y$ is $4231$- and $3412$-avoiding. These results imply that $P_{x, y}(q)=1$ for $y$ avoiding 4231 and 3412. Together with the fact that $P_{x, y}(q)=0$ for $x \nleq y$ in the Bruhat order, this gives the following lemma.


\begin{lem} \label{lem:immSimple}
	Let $v\in S_n$ be $1324$- and $2143$-avoiding. Then 
	\begin{equation} \label{eq:immSimple} \Imm_v(M)= (-1)^{\ell(v)} \sum_{w \geq v} (-1)^{\ell(w)} ~m_{1, w(1)} \cdots m_{n, w(n)}.
	\end{equation}
\end{lem} 


The coefficients in the formula in \cref{lem:immSimple} suggest a strategy for analyzing\linebreak $\Imm_v(M)$ for $v\in S_n$ $1324$- and $2143$-avoiding: find some matrix $\tilde{M}$ such that $\det(\tilde{M})=\pm \Imm_v(M)$. If such a matrix $\tilde{M}$ exists, the sign of $\Imm_v(M)$ is the sign of some determinant, which we have tools (e.g. the Desnanot--Jacobi identity) to analyze. The most straightforward candidate for $\tilde{M}$ is a matrix obtained from $M$ by replacing some entries with $0$.

\begin{defn}
	Let $P \subseteq\{1, \dots, n\}^2$ and let $M=(m_{ij})$ be in $\Mat_{n \times n}(\CC)$. The \emph{restriction of }$M$ \emph{to } $P$, denoted $\res{M}{P}$, is the matrix with entries 
	\[\tilde{m}_{ij}= \begin{cases}
	m_{ij} & \text{if } (i, j) \in P\\
	0 & \text{else}.
	\end{cases}
	\]
\end{defn}

For a fixed $v \in S_n$ that avoids $1324$ and $2143$, suppose there exists $P \subseteq\{1, \dots, n\}^2$ such that $\Imm_v(M)=\pm \det \res{M}{P}$. Given the terms appearing in \cref{eq:immSimple}, $P$ must include $\{(i, w(i)): w \in [v, w_0]\}$, the union of graphs of permutations in the Bruhat interval $[v, w_0]$. In fact, the minimal choice of $P$ suffices.

\begin{prop} \label{prop:fullIntervals}
	Let $v \in S_n$ be $1324$- and $2143$-avoiding, and let $M\in \Mat_{n \times n}(\CC)$. Denote by $\gr[v, w_0]:= \{(i, w(i)): w \in [v, w_0]\}$. Then 
	\[ \det(\res{M}{\gr[v, w_0]})=\sum_{w \geq v} (-1)^{\ell(w)}~m_{1, w(1)} \cdots m_{n, w(n)}.
	\]
\end{prop}


Before discussing the proof of \cref{prop:fullIntervals}, we mention that $\gr[v, w_0]$ is easy to characterize as a subset of $\ZZ^2$.

\begin{lem} \label{lem:graphCharacterization}
	Let $v \in S_n$. Then $\gr[v, w_0]$ consists exactly of the points $(i, j)$ such that there exist $k, \ell \in \{1, \dots, n\}$ where $k\leq i \leq \ell \text{ and } v_k \leq j \leq v_\ell.$
\end{lem}

\begin{rmk} Index the rows and columns of an $n \times n$ grid so that row indices increase going down and column indices increase going right.
	\cref{lem:graphCharacterization} gives a method for drawing $\gr[v, w_0]$ in the grid. First, put a dot in positions $(i, v(i))$ for $i=1, \dots, n$. Then, put a cross in all positions that are weakly southeast of one dot and weakly northwest of another (see \cref{fig:graph}).
\end{rmk}

\begin{figure} 
	\centering
	\includegraphics[height=1.5in]{graph}
	\caption{\label{fig:graph} An example of $\gr[v, w_0]$ for $v=1 4 2 5 3$. Dots mark the positions $(i, v(i))$, and crosses mark all other elements of $\gr[v, w_0]$.}
\end{figure}

Returning to \cref{prop:fullIntervals}, notice that by definition, 
\begin{equation}
\det(\res{M}{\gr[v, w_0]})= \sum_{\substack{w \in S_n \\ \gr(w)\subseteq \gr[v, w_0]}} (-1)^{\ell(w)}~m_{1, w(1)} \cdots m_{n, w(n)}
\end{equation}
where $\gr(w):=\{(i, w(i)):i=1, \dots, n\}$ is the graph of $w$. So the content of \cref{prop:fullIntervals} is that for permutations $v$ avoiding the appropriate patterns, $[v, w_0]=\{w \in S_n: \gr(w) \subseteq \gr[v, w_0]\}$. This does not hold for arbitrary permutations $v$, as the following example shows.

\begin{ex}
	Consider $v=1 4 2 5 3$. Then $x= 1 2 4 5 3$ is not in the Bruhat interval $[v,w_0]$, but $\gr(x) \subseteq \gr[v, w_0]$.  This can easily be seen from \cref{fig:graph}.
\end{ex}


\cref{prop:fullIntervals} follows from \cref{lem:graphCharacterization} and a result of Sj\"{o}strand \cite{Sjo}. \cref{lem:graphCharacterization} shows that for arbitrary $v \in S_n$, $\gr[v, w_0]$ is equal to what Sj\"{o}strand calls the ``right convex hull" of $v$. Theorem 4 of \cite{Sjo} establishes that the right convex hull of $v$ contains only the graphs of $w \geq v$ if and only if $v$ avoids the patterns 1324, 24153, 31524, and 426153. The latter 3 patterns contain an occurrence of 2143, so if $v$ avoids 2143, it also surely avoids these patterns.


In light of \cref{prop:fullIntervals}, it remains to analyze the sign of $\det(\res{M}{\gr[v, w_0]})$. In particular, we would like to find some $k$ for which $\det(\res{M}{\gr[v, w_0]})$ has the same sign for all $k$-positive matrices $M$. We will do this in the special case when $v$ avoids 123 and 2143 by describing $\gr[v, w_0]$ more explicitly as a region in an $n \times n$ grid.  We restrict to this case so we can use a result of Tenner:

\begin{thm}[{\cite{Ten}}]
	A permutation $y \in S_n$ avoids 321 and 3412 if and only if in every (equivalently, one) reduced expression for $y$, each simple transposition appears at most once. 
\end{thm}

If $v$ avoids 123 and 2143, then $w_0v$ will avoid 321 and 3412. So, we can use Tenner's result to describe $\gr[v, w_0]$ for $v$ $123$- and $2143$-avoiding. The building blocks for these graphs are pentagonal collections of dots, which we define next.

\begin{defn}
	Let $0<a,b\leq n$. If $(a, b)$ is above the antidiagonal, we define $\pentl{a, b}$ as the left-justified collection of dots in rows $a$ through $n-b+1$ where row $i$ has $\min\{n-b-i+3, n-b-a+2\}$ dots and the first dot in each row is in column $b$. Similarly, if $(a, b)$ is below the antidiagonal, $\pentr{a, b}$ is the right-justified collection of dots in rows $n-b+1$ through $a$ where row $i$ has $\min\{b-n+i+1,b-n+a\}$ dots and the last dot in each row is in column $b$. We call $\pentl{a, b}$ and $\pentr{a, b}$ \emph{pentagonal shapes}. See \cref{fig:pentagons} for an example.
\end{defn}

\begin{figure}
	\centering
	\includegraphics[height=2in]{pentagons}
	\caption{\label{fig:pentagons} $\pentl{a, b}$ 
	(on the left) and $\pentr{a, b}$ (on the right). The boxes on the antidiagonal are shown in green.}
\end{figure}

Notice that $\pentl{a, b}$ is related to $\pentr{a, b}$ by reflection across the antidiagonal.

\begin{prop} \label{prop:graphCoxeterelt}


Let $n>2$. Suppose $v \in S_n$ avoids 123 and 2143 and $\ell(v)=\binom{n-1}{2}$. Define $L:=\{i:v(i)<n-i\}$ and $R:=\{i:v(i)>n-i+2\}$. Then
\[
\gr[v, w_0]= \left (\bigcup_{i \in L} \pentl{i, v(i)} \right )~ \bigcup~ \left ( \bigcup_{i \in R} \pentr{i, v(i)} \right ).
\]

	\noindent Moreover, the pentagonal shapes alternate between $\pentl{a, b}$ and $\pentr{c,d}$ down the antidiagonal, and $\pentl{a, b}$ intersects $\pentr{c, d}$ either nowhere or in a $2 \times 2$ square of dots.
\end{prop}

We have the following immediate corollary.


\begin{cor} \label{cor:graphGeneral}
	Let $v \in S_n$ avoid 123 and 2143. Then $\gr[v, w_0]$ is block antidiagonal. Consider each minimal block of $\gr[v, w_0]$ as a $m \times m$ grid. Then either the block consists of a single dot, consists of a $2 \times 2$ square of dots, or has shape described by \cref{prop:graphCoxeterelt}.
\end{cor}

\begin{figure}
	\centering
	
	\includegraphics[height=3in]{graphWithPentagons}
	\caption{\label{fig:graphWithPentagons} Let $v=4~10~9~2~8~6~3~ 2~ 1~ 5$. It is 123- and  2143-avoiding and every simple transposition occurs once in each reduced expression for $w_0v$. The decomposition of $\gr[v, w_0]$ into a union of pentagon shapes, guaranteed by \cref{prop:graphCoxeterelt}, is shown here. All $\pentl{a, b}$'s are shown in red; all $\pentr{a, b}$'s are shown in blue.}
\end{figure}

With this description of $\gr[v, w_0]$ we can prove the following.

\begin{thm} \label{thm:ImmkPosCoxeter}
	Let $v \in S_n$ be 123- and 2143-avoiding, and suppose $k$ is the size of the largest square appearing in $\gr[v, w_0]$. Then $\Imm_v(M)$ is $k$-positive.
\end{thm}

\begin{proof}[Proof sketch]
	By \cref{prop:fullIntervals}, it suffices to show that $\det(\res{M}{\gr[v, w_0]})$ is nonzero and has sign $\ell(v)$. We prove this first for $v$ such that $\gr[v, w_0]$ has a single antidiagonal block, in which case $\ell(v)=n-1$. The proof is by induction, and relies on the Desnanot--Jacobi identity (also known as Dodgson condensation), which is as follows.
	
	For $N \in \Mat_{n \times n}(\CC)$ and $I, J \subseteq \{1, \dots, n\}$, let $N_I^J$ denote the submatrix obtained by removing rows indexed by $I$ and columns indexed by $J$. Then for $1 \leq a <a'\leq n$ and $1 \leq b < b' \leq n$, we have
	
	\begin{equation}
	\det N \det N_{a, a'}^{b, b'}= \det N_{a}^b \det N_{a'}^{b'} - \det N_{a}^{b'} \det N_{a'}^b.
	\end{equation}
	
	\cref{prop:graphCoxeterelt} plays a crucial role in understanding the determinants of the matrices appearing in the Desnanot--Jacobi identity for $N=\res{M}{\gr[v, w_0]}$.
	
	Once we know the case when $\gr[v, w_0]$ is a single block, we use \cref{cor:graphGeneral} and the following lemma to establish the result for all $v$ avoiding 123 and 2143.
	
	\begin{lem}
		Let $M \in \Mat_{n \times n}(\CC)$ be block-antidiagonal, with blocks $M_1, \dots, M_r$ of size\linebreak $n_1, \dots n_r$. Then 
		
		\[\det M= (-1)^{\binom{n}{2}} \prod_{i=1}^{r} (-1)^{\binom{n_i}{2}} \det M_i.
		\]
	\end{lem}
\end{proof}


To obtain \cref{thm:123avoiding} from \cref{thm:ImmkPosCoxeter}, we simply translate the condition "$k$ is the size of the largest square appearing in $\gr[v, w_0]$" into pattern avoidance language.

The assumptions of \cref{thm:ImmkPosCoxeter} are stronger than those of \cref{prop:fullIntervals}, so it's natural to conjecture that they can be weakened. In work following the completion of this abstract \cite{paper}, we prove the following statement.

\begin{thm}[{\cite{paper}}] \label{thm:big}
	Suppose $v \in S_n$ avoids 1324 and 2143, and let $k$ be the size of the largest square in $\gr[v, w_0]$. Then $\Imm_v(M)$ is $k$-positive.
\end{thm}


\begin{ex}
	Let $v=236145$.  Then $\gr[v, w_0]$ is the following grid:
	\begin{center}
	    \includegraphics[height=1.5in]{conjEx}
	\end{center}
	
	The largest square in $\gr[v, w_0]$ is of size 4 (one choice of such a square is highlighted in green).  Since $v$ avoids 1324 and 2143, we know that $\Imm_v(M)=(-1)^{\ell(v)}\det(\res{M}{\gr[v, w_0]})$.  \cref{thm:big} states that if $M$ is 4-positive, then $\Imm_v(M)$ is positive.
	
\end{ex}


To prove \cref{thm:big}, we again use the Desnanot--Jacobi identity to determine the sign of $\det(\res{M}{\gr[v, w_0]})$ for $v$ and $M$ satisfying the appropriate conditions. The key observation is that, for certain choices of deleted rows and columns, every term of the Desdanot--Jacobi identity is of the form $\det(\res{M}{\gr[v', w_0]})$ for some $v'$ which avoids 1324 and 2143. After this observation, the argument proceeds by induction.


\acknowledgements{ We would like to thank Pavlo Pylyavskyy for suggesting this problem to us, and for helpful discussions on Lusztig's dual canonical basis. We would also like to thank Alejandro Morales for pointing us towards \cite{Sjo}, and Lauren Williams for helpful comments during the preparation of this abstract.}

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