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

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

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{proposition}[theorem]{Proposition}

\newcommand\knuth{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $K$}}}{\cong}}}
\newcommand\knuthq{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $K^{'}$}}}{\cong}}}
\newcommand\knutha{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily 1}}}{\cong}}}
\newcommand\knuthb{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily 2}}}{\cong}}}
\newcommand\knuthi{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $i$}}}{\cong}}}
\newcommand\knuthj{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $j$}}}{\cong}}}
\newcommand\knuthl{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $l$}}}{\cong}}}
\newcommand\knuthab{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily 1,2}}}{\cong}}}
\newcommand\rs{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily RS}}}{\longrightarrow}}}
\newcommand\pequiv{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $P$}}}{\cong}}}
\newcommand\dualknutha{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $1^*$}}}{\cong}}}
\newcommand\dualknuthb{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $2^*$}}}{\cong}}}
\newcommand\dualknuthi{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $i^*$}}}{\cong}}}
\newcommand\dualknuthj{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $j^*$}}}{\cong}}}
\newcommand\dualknuthl{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $l^*$}}}{\cong}}}
\newcommand\dualknuthK{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $K^*$}}}{\cong}}}


\newcommand\dualtwothree{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $d_2,d_3$}}}{\cong}}}
\newcommand\dualtwo{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $d_2$}}}{\cong}}}
\newcommand\dualthree{\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily $d_3$}}}{\cong}}}

\newcommand\rw{\text{\bf rw}}
\newcommand\sig{\text{\bf sig}}



\usepackage{lipsum}
\usepackage{graphicx}
\usepackage{tikz,pgf}
\usetikzlibrary{fit,scopes,calc,matrix,positioning,decorations.pathmorphing,shapes,snakes}
\usepackage[vcentermath]{youngtab}
\usepackage{hyperref}
\usepackage{epstopdf}
\usepackage{multicol}
\usepackage{mwe}
\usepackage{graphbox}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{chngcntr}
\captionsetup[subfigure]{labelfont=rm}
\usepackage{wrapfig}
\usepackage{lscape}
\usepackage{rotating}
\usepackage{epstopdf}
\usepackage{float}

%% define your title in the usual way
\title{Dual Equivalence Graphs and CAT(0) Combinatorics}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Anastasia Chavez\thanks{\href{a.chavez@berkeley.edu}{a.chavez@berkeley.edu}. Anastasia Chavez was partially supported by NSF-AGEP DMS-1049513.}\addressmark{1} \and 
John Guo\thanks{\href{jguo@mail.sfsu.edu}{jguo@mail.sfsu.edu}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of California, Davis, One Shields Ave., Davis, CA 95616 USA\\ \addressmark{2}Department of Mathematics, San Francisco State University, 1600 Holloway Ave, San Francisco, CA 94132, 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{In this paper we explore the combinatorial structure of dual equivalence graphs $G_{\lambda}$. The vertices are Standard Young tableaux of a fixed shape $\lambda$ that allows us to further understand the combinatorial structure of $G_{\lambda}$, and the edges are given by dual Knuth equivalences. The graph $G_{\lambda}$ is the $1$-skeleton of a cubical complex $C_{\lambda}$, and one can ask whether the cubical complex is CAT(0); this is a desirable metric property that allows us to describe the combinatorial structure of $G_{\lambda}$ very explicitly. We prove that $C_{\lambda}$ is CAT(0) if and only if $\lambda$ is a hook.}

%% 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{dual equivalence graphs, CAT(0), Standard Young tableaux, posets with inconsistent pairs, RS correspondence}

%% 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{92-Chavez-Guo.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}
Dual equivalence graphs are rooted in the exploration of Hall--Littlewood polynomials, Macdonald polynomials, and Schur positivity \cite{Assaf, haiman92, KNU70, sc77}. More recently, dual equivalence graphs have been used to generalize these polynomials \cite{Assaf,ROB14,ROB17}. Much of the graphical structure of dual equivalence graphs has been explored. We wish to expand on this knowledge by providing a geometric description of these graphs as the 1-skeleton of a cubical complex.

The theory of reconfigurable systems and transition graphs have been used to analyze the space of potential states a particular object can take. Considering the 1-skeleton of a transition graph as a cubical complex, one may ask if the metric property called CAT(0) holds. This allows for questions of optimization, computational complexity, and feasible state spaces to be addressed. In their seminal work, Abrams--Ghrist \cite{AbramsGhrist2004} developed this theory and gave a path-optimizing algorithm with respect to time from one robot state to another. Building on this work, Ardila--Baker--Yatchak \cite{ArdilaBakerYatchak} showed how to find the optimal path between any two robotic arm states with respect to distance, number of moves, number of steps of simultaneous moves, as well as time. Furthermore, Billera--Holmes--Vogtmann \cite{BHV2001} used this theory to determine classes of comparable phylogenetic trees. 

A purely combinatorial characterization of CAT(0) cubical complexes was introduced by Ardila--Owen--Sullivant who gave a bijection between these complexes and posets with inconsistent pairs \cite{ArdilaOwenSullivant}. This description provides combinatorial motivation for seeking the CAT(0) property of cubical complexes of various objects, in addition to the traditional questions outlined above. 

In this paper we take a new perspective regarding $G_{\lambda}$ as the $1$-skeleton of a cubical complex, $C_{\lambda}$. We analyze whether $C_{\lambda}$ has the CAT(0) property and shed light on the combinatorics of dual equivalence graphs. 

This paper is organized as follows. Section 2 provides necessary background, Section 3 reviews cubical complexes and the CAT(0) property in terms of posets with inconsistent pairs, and Section 4 presents our main results. 

\section{Background}

For the remainder of this paper we assume all permutations are presented in one line notation.
%The goal of this section is to provide the definitions and results necessary to introduce dual equivalence graphs. 

\begin{flushleft}
\large{\bf Standard Young tableaux}
\end{flushleft}

Denote the partition $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k)$ of $n$ as $\lambda\vdash n$, where $\lambda_1\geq\lambda_2\geq\dots\geq\lambda_k$ and $|\lambda|=\sum_{i=1}^k\lambda_i=n$. 
\begin{definition}
The \emph{Ferrers diagram}, or \emph{shape}, of $\lambda$ is an array of $n$ boxes having $k$ left-justified rows with row $i$ containing $\lambda_i$ boxes for $1\leq i \leq k$. A \emph{standard Young tableau}, SYT, is a Ferrers diagram where the boxes are filled with elements from $[n]$ such that no element is repeated and rows and columns are strictly increasing.
\end{definition}

\begin{example}\label{exSYT}
Let $\lambda \vdash 8$ be the partition $\lambda=(4,2,1,1)$. Then a SYT $Q$ of shape $\lambda$ is 
$$\young(1346,27,5,8).$$
\end{example}


The \emph{row reading word of $Q$}, denoted $\rw(Q)$, is the permutation $\pi_Q$ formed by reading the entries, row by row, of a SYT $Q$ from bottom to top and left to right. Note that the row reading word of a SYT is a permutation.

The \emph{(descent) signature} of a permutation $\pi$, denoted $\sig(\pi)$, is a sequence of $+$'s and $-$'s such that position $i$ is a $+$ if and only if $i$ comes before $i+1$ in $\pi$, and $-$ otherwise. As in \cite{Assaf}, we extend this definition to tableau so that the signature of a SYT $Q$ is $\sig(Q) = \sig(\pi_Q)$.

The row reading word and signature of example \ref{exSYT} are $\pi_Q=\rw(Q)=85271346$ and $\sig(Q)=-++-+--$.



\begin{flushleft}
\large{\bf Dual Knuth equivalence}
\end{flushleft}


Dual Knuth equivalence, introduced by Haiman \cite{haiman92}, may be defined as the following function on permutations.

\begin{definition}
A \emph{dual Knuth equivalence}, denoted $d_i$, is a function that reorders the values $i-1, i$ and $i+1$ in a permutation of $S_n$. Explicitly, the function $d_i$ acts in the following way:
\begin{align*}
d_i(\cdots i \cdots i-1 \cdots i+1 \cdots) &= (\cdots i+1 \cdots i-1 \cdots i \cdots),\\
d_i(\cdots i \cdots i+1 \cdots i-1 \cdots) &= (\cdots i-1 \cdots i+1 \cdots i \cdots),
\end{align*}
or it leaves the permutation unchanged if $i$ is between $i-1$ and $i+1$. Two permutations are \emph{dual equivalent} if a sequence of dual Knuth equivalences transforms one into the other. 
\end{definition}

It is not hard to check that the dual Knuth relations form an equivalence relation on $S_n$. 


\begin{example}
The non-trivial dual Knuth equivalence classes for $S_4$.
\begin{center}
$1243\dualthree 1342\dualtwo 2341$\hspace{.5cm}
$2314\dualtwo 1324\dualthree 1423$\hspace{.5cm}
$1432\dualtwo 2431 \dualthree 3421$\\
$3241\dualthree 4231 \dualtwo 4132$\hspace{.5cm}
$2134 \dualtwo 3124\dualthree 4123$\hspace{.5cm}
$3214\dualtwothree 4213$\\ 
$2413\dualtwothree 3412$\hspace{.5cm}
$2143 \dualtwothree 3142$
\end{center}
\end{example}


We would like to note that dual Knuth equivalence is related to the well-known Knuth equivalence, an equivalence among permutations defined by swaps performed on values of the permutation. More precisely, the permutations $\pi$ and $\sigma$ are dual equivalent if and only if $\pi^{-1}$ and $\sigma^{-1}$ are Knuth equivalent. Another characterization of dual equivalence is in terms of SYT. The Robinson--Schensted correspondence bijectively assigns to each permutation $\pi$ a pair of SYT $(P(\pi),Q(\pi))$ of the same shape $\lambda$. Two permutations are dual equivalent if they map to the same $Q$ tableau under the RS algorithm \cite{KNU70,ROB38,SCH61}.




%\begin{example}
%Permutations $2341$ and $1243$ are dual equivalent because $$d_3(d_2(2341))=1243.$$
%\end{example}
Dual equivalence can also be performed on entries of SYT $Q$ by applying $d_i$ to the row word of $Q$. Thus, the equivalence relation passes to the SYT, as stated in the following theorem.

\begin{theorem}[{\cite[Proposition 2.4]{haiman92}}]\label{dualQequiv}
Two SYT on partition shapes $\lambda$ and $\tau$ are dual equivalent if and only if $\lambda=\tau$.
\end{theorem}

Furthermore, by \cite[Lemma 2.3]{haiman92} dual equivalence acts on SYT nicely,
$$d_i(Q(\pi))=Q(d_i(\pi)),$$
which will be useful in the proof of our main theorem.



%In order to define dual equivalence graphs, we first introduce dual Knuth equivalence for permutations. Dual Knuth equivalence is really an equivalence on the inverse of permutations. More precisely, the permutations $\pi$ and $\sigma$ are dual equivalent if $\pi^{-1}\knuth\sigma^{-1}$. We also provide a more direct definition that avoids inverse permutations.
%
%\begin{definition}
%A \emph{dual Knuth equivalence}, denoted $d_i$, is a function that reorders the values $i-1, i$ and $i+1$ in a permutation of $S_n$. Explicitly, the function $d_i$ acts in the following way:
%\begin{align*}
%d_i(\cdots i \cdots i-1 \cdots i+1 \cdots) &= (\cdots i+1 \cdots i-1 \cdots i \cdots),\\
%d_i(\cdots i \cdots i+1 \cdots i-1 \cdots) &= (\cdots i-1 \cdots i+1 \cdots i \cdots),
%\end{align*}
%or it leaves the permutation unchanged if $i$ is between $i-1$ and $i+1$. Two permutations are \emph{dual equivalent} if a sequence of dual Knuth equivalences transforms one into the other. 
%\end{definition}
%
%
%\begin{example}
%Permutations $2341$ and $1243$ are dual equivalent because $$d_3(d_2(2341))=1243.$$
%\end{example}
%
%Just as before, dual equivalence is an equivalence relation on the symmetric group. Dual equivalence can also abe performed on entries of a SYT $Q$ by applying $d_i$ to the row word of $Q$. Thus, the equivalence relation passes to the SYT, as stated in the following theorem.
%
%\begin{theorem}\cite[Proposition 2.4]{haiman92}\label{dualQequiv}
%Two SYT on partition shapes $\lambda$ and $\tau$ are dual equivalent if and only if $\lambda=\tau$.
%\end{theorem}
%
%Furthermore, by \cite[Lemma 2.3]{haiman92} dual equivalence acts on SYT nicely,
%$$d_i(Q(\pi))=Q(d_i(\pi)),$$
%which will be useful in the proof of our main theorem.

\begin{flushleft}
\large{\bf Dual equivalence graphs}
\end{flushleft}

We now define dual equivalence graphs, first introduced by Assaf \cite{Assaf} and recently extended by Roberts \cite{ROB14,ROB17}.


\begin{definition}
For a given  $\lambda\vdash n$, the \emph{dual equivalence graph} is a graph $G_{\lambda}$ whose vertices are the set of SYT of shape $\lambda$. Each vertex is labeled by the associated tableau signature and an edge labeled $i$ exists between dual equivalent tableaux $Q$ and $Q^{'}$ such that $d_i(Q)=Q^{'}$.
\end{definition}

\begin{example}
All dual equivalence graphs for partitions of $n=4$.


\begin{center}
 \includegraphics[scale=1.2]{dualequiv4}
 \end{center}

\end{example}

%Note every node of a dual equivalence graph represents a class of dual equivalent permutations. 






\section{CAT(0) Cubical Complexes and Posets with Inconsistent Pairs}\label{cat}

Informally, a \emph{reconfigurable system} is a collection of states with a set of reversible moves that are used to navigate from one state to another. These moves are tethered to particular states and can only be used to traverse back and forth between them. Moves are \emph{commutative} if they are physically independent of one another, and thus can be done simultaneously. The notion of reconfigurable system is formalized in \cite{AbramsGhrist2004,GP}. 

\begin{definition}[\cite{AbramsGhrist2004,GP}]
A \emph{cubical complex} $X$ is a polyhedral complex formed by joining cubes of various dimensions such that the intersection of any two cubes is a face of both.
\end{definition}

\begin{definition}
In this paper we consider a certain cubical complex associated to dual equivalence graphs. Define \emph{$C_{\lambda}$} to be the cubical complex whose 1-skeleton is the dual equivalence graph $G_{\lambda}$ for a given $\lambda$.
\end{definition}

\begin{definition} The \emph{state complex} $\mathcal{S(R)}$ of a reconfigurable system $\mathcal R$ is a cubical complex whose vertices correspond to the states of $\mathcal R$. There is an edge between two states if they differ by an application of a single move. The $k$-cubes are associated to $k$-tuples of commutative moves.
\end{definition}

\begin{remark}
The $1$-skeleton of $\mathcal{S(R)}$ is the \textit{transition graph} $\mathcal{T(R)}$, a graph whose vertices are the states of the system and whose edges correspond to the permissible moves between them. 
\end{remark}


\begin{definition} A metric space $X$ is said to be CAT(0) if:
\begin{itemize}
\item there is a unique geodesic (shortest) path between any two points in $X$, and

\item $X$ has non-positive global curvature.
\end{itemize}
\end{definition}

The second property of being CAT(0) can be described as follows. Let $X$ be a metric space with a unique geodesic (shortest) path between any two points. Consider a triangle $T$ in $X$ with side lengths $a,b,$ and $c$, and construct a comparison triangle $T'$ with the same lengths in Euclidean space. If every chord in the comparison triangle $T'$ is of equal or greater length than the corresponding chord in $T$ (in Figure \ref{triangles}, $|xy|\leq |x'y'|$), for every triangle $T$ in $X$, then we say that $X$ is CAT(0). 

\begin{figure}[ht]
    \centering
    \includegraphics[scale=.7]{triangles}\\
    \vspace{.5cm}
    $T$\hspace{6cm}$T'$
    \caption{The CAT(0) property: $X$ has non-positive global curvature.}\label{triangles}
\end{figure}

There are several characterizations of being CAT(0). Combinatorial descriptions were introduced by Sageev \cite{Sageev} and Roller \cite{Roller}. We utilize a similar, but more compact characterization given by Ardila--Owen--Sullivant \cite{ArdilaOwenSullivant} in terms of partially ordered sets with inconsistent pairs (PIPs). 

\begin{definition}
If $X$ is a CAT(0) cubical complex and $v$ is any vertex of $X$, then $(X,v)$ is a \emph{rooted CAT(0) cubical complex} rooted at $v$. This can be thought of as identifying a home state if the cubical complex is a \emph{state complex}.
\end{definition}

%Another characterization of being CAT(0) was given by Ardila--Owen--Sullivant \cite{ArdilaOwenSullivant} in terms of partially ordered sets with inconsistent pairs.

\begin{definition} A \emph{poset with inconsistent pairs (PIP)} is a locally finite poset P of finite width, together with a collection of inconsistent pairs $\{p,q\}$, such that:
\begin{itemize}
\item If $p$ and $q$ are inconsistent, then there is no $r$ such that $r \geq p$ and $r \geq q$.

\item If $p$ and $q$ are inconsistent and $p' \geq p$ and $q' \geq q$, then $p'$ and $q'$ are inconsistent.
\end{itemize}
\end{definition}

The corresponding \emph{Hasse diagram} of a PIP is constructed by taking the poset and appending a dotted line between minimal inconsistent pairs. An \emph{order ideal} of $P$ is a subset $I$ of $P$ such that if $a \leq b$ and $b \in I$ then $a \in I$. A \emph{consistent order ideal} is an order ideal that contains no inconsistent pairs. An \emph{antichain} is a collection of elements in the poset such that any pair of these elements is incomparable.

We provide the following definition which describes the relationship between PIPs and cubical complexes.

\begin{definition}\label{cubecomplex}
If $P$ is a poset with inconsistent pairs, we construct the \textit{cube complex of $P$}, which we denote $X(P)$. The vertices of $X(P)$ are identified with the consistent order ideals of $P$. There will be a cube $C(I,M)$ for each pair $(I,M)$ of a consistent order ideal $I$ and a subset $M\subset I_{max}$, where $I_{max}$ is the set of maximal elements of $I$. This cube has dimension $|M|$, and its vertices are obtained by removing from $I$ the $2^{|M|}$ possible subsets of $M$. The cubes are naturally glued along their faces according to their labels. 
\end{definition}

\begin{remark}
When $P$ has no inconsistent pairs, this is precisely the bijection between posets $P$ and distributive lattices $J(P)=L$. To recover $P$ from $L=J(P)$, we consider the poset of join-irreducibles of $L$.
\end{remark}

See Figure \ref{fig:ComplexAndPIPposet} for an example a cubical complex $X(P)$ and the associated PIP $P$. 

\begin{theorem}[\cite{ArdilaOwenSullivant}]\label{piptheorem}
The map $P \rightarrow X(P)$ is a bijection between posets with inconsistent pairs and rooted CAT(0) cube complexes.
\end{theorem}


Theorem \ref{piptheorem} provides a method of proving a cubical complex has the desirable CAT(0) property, namely, by constructing the associated PIP after choosing a root for the cubical complex. 


\section{CAT(0) Dual Equivalence Graphs}

In this section we will prove that the only tableau whose dual equivalence graph $G_{\lambda}$ is the $1$-skeleton of a CAT(0) cubical complex is the hook, namely for $\lambda=(n-k,1^k)$. We will also show that when $\lambda$ contains $(2,2)$ then the cubical complex $C_{\lambda}$ is not CAT(0).

\begin{definition}
Define a \emph{hook} to be a partition of the form $(n-k,1^k)$. 
\end{definition}

Note that we need only consider hooks $\lambda=(n-k,1^k)$ for $k\leq \lfloor{\frac{n}{2}}\rfloor$ since conjugate partitions produce isomorphic equivalence graphs, as stated in the following proposition.

\begin{proposition}[\cite{Assaf}]\label{conjgraphs}
Given partition $\lambda$ and its conjugate $\lambda '$, then $$G_{\lambda}\cong G_{\lambda '}.$$
\end{proposition}


We first establish that if $\lambda$ contains shape $(2,2)$ then the cubical complex $C_{\lambda}$, whose $1$-skeleton is $G_{\lambda}$, is not CAT(0).

\begin{figure}[H]
\begin{center}
 \includegraphics[scale=.8]{PushSignatureGraph}
\end{center}
 \caption{Dual equivalence graph of $\lambda=(3,1,1,1)$.}\label{PushGraph}
\end{figure}
\pagebreak
\begin{theorem}\label{thm:noncat0)}
Let the shape $\lambda$ contain $(2,2)$. Then $C_{\lambda}$ is not a CAT(0) cubical complex. 
\end{theorem}

%\begin{proof}
%Omitted.
%\end{proof}

\begin{proof}
Assume the shape $\lambda$ contains $(2,2)$. By definition, $G_{\lambda}$ will have a vertex labeled with a SYT $Q$ whose row word is of the form $\pi=\dots 3412 \dots$. This means $G_{\lambda}$ will have a double edge connecting the vertices $\pi=\dots 3412\dots$ and $\pi^{'}=\dots 2413\dots$ because $d_2(\pi)=d_3(\pi)=\pi^{'}$. Note these dual equivalences are dependent and therefore do not commute. This implies the edges form a hole and so there are two shortest geodesics between $\pi$ and $\pi'$. Thus $C_{\lambda}$ is not a space with unique geodesics, and therefore cannot be CAT(0).
\end{proof}


As noted earlier, dual equivalence on SYT and their row words translates nicely. It is particularly nice when SYT $Q$ is a hook shape. The action of $d_i(Q)$ literally swaps entries $i-1, i$, and $i+1$ in $Q$. The signature of $Q$ is similarly affected. The function $d_i$ swaps signs of entries $i-1$ and $i$, i.e. $+-$ becomes $-+$. See Figure \ref{PushGraph} to see how successive applications of $d_i$ effectively pushes $+$ to the right or left of the signatures.

\begin{theorem}\label{GeneralHookCAT(0)}
When $\lambda$ is a hook, then $C_{\lambda}$ is a CAT(0) cubical complex.
\end{theorem}

%\begin{proof}
%Omitted.
%\end{proof}

%%%%%%%%%% NEW PROOF USING DUAL EQUIVALENCE GRAPHS %%%%%%
\begin{proof}
We begin by describing the vertex labels of $G_{\lambda}$ in terms of SYT and signatures. Our goal is to provide a new, simpler vertex-edge labeling of $G_{\lambda}$. Since any $Q$ in $G_{\lambda}$ is a hook, then $\rw(Q)=w_1w_2\dots w_k 1 w_{k+2}\dots w_n$ where $w_1>w_2>\dots >w_k$ and $1<w_{k+2}<\dots <w_n$. This implies the only valid dual Knuth operation for any $Q$ is of the form $$d_i(\cdots i \cdots i-1 \cdots i+1 \cdots) = (\cdots i+1 \cdots i-1 \cdots i \cdots).$$ Moreover, this means a dual Knuth move $d_i$ on any tableaux $Q$ of $G_{\lambda}$ will also swap the signs of $\sig(Q)$ in positions $i-1$ and $i$. For example, consider the SYT $Q$ such that $\rw(Q)=n,n+1,\dots,n-k+1,1,2,\dots,n-k$. The associated signature is $\sig(Q)=++\cdots+--\cdots-$, where the first $k-1$ positions are $+$ and it has length $n-1$. Then compositions of dual Knuth functions applied to $Q$ effectively push the $+$'s of $\sig(Q)$ to the right. 

Since $G_{\lambda}$ is uniquely determined by either the tableau or signature labeling, we shall consider only the signatures. We now describe the edges of the graph in terms of the signatures. There is an edge between two signatures when they differ by sign in a pair of adjacent opposite signed positions. As noted above, a dual Knuth operation on a tableau swaps the signs of a pair of adjacent opposite signed entries. Thus, we can introduce a new edge labeling in terms of signatures. An edge is labeled $i$ when positions $i-1$ and $i$ change signs between adjacent signatures. See Figure \ref{PushGraph} for an example of this vertex-edge labeling.

Next we define a poset structure $L_{\lambda}$ on the vertices of $G_{\lambda}$ and prove it is a distributive lattice. The signature labeling of $G_{\lambda}$ produces a natural component-wise ordering on its vertices, where $-<+$. For signatures $s=(i_1,i_2,\dots,i_{n-1})$ and $s'=(j_1,j_2,\dots,j_{n-1})$ in $L_{\lambda}$, we say $s \leq_{L_{\lambda}} s'$ if and only if $i_r < j_r$ for the first $r$ where $s$ and $s'$ differ. Define the function max$:L_{\lambda}^t\rightarrow L_{\lambda}$ to be the component-wise maximum. Define the function min similarly. Since $L_{\lambda}$ is finite, then max and min are well defined. Moreover, since max and min are distributive on each component, it follows that they are distributive on $L_{\lambda}$ as well. Thus, $(L_{\lambda},\leq_{L_{\lambda}})$ is a distributive lattice. 

By Birkhoff's representation theorem \cite{StanelyEC1} there exists a poset of order ideals isomorphic to $L_{\lambda}$. We now construct the poset $P_{\lambda}$ such that $L_{\lambda}\cong J(P_{\lambda})$. We construct $P_{\lambda}$ by describing the join-irreducible elements of $L_{\lambda}$. The order on $P_{\lambda}$ will follow from the component-wise order on $L_{\lambda}$.


We now describe the cubical complex, $C_{\lambda}$, whose 1-skeleton is $G_{\lambda}$. The vertices of $C_{\lambda}$ are labeled by signatures of SYT of shape $\lambda$. Consider the following edge labeling of $C_{\lambda}$. The edge between signatures $s'$ and $s$ is labeled $d_{i}(j)$ to indicate that $s'$ and $s$ differ by the $j$th $+$ in either position $i-1$ or $i$. Another way to read this is $d_i(j)(s')=s$ means signature $s$ is produced by pushing the $j$th $+$ of $s'$, which is in position $i-1$, to position $i$ and putting a $-$ in position $i-1$. As these edges correspond to dual Knuth moves in $G_{\lambda}$, we will refer to the label $d_{i}(j)$ as a \emph{move}. See Figure \ref{fig:ComplexAndPIPposet}(b) for an example of this labeling. Since $\lambda$ is a hook, there are no double edges in $C_{\lambda}$ so this labeling is well defined. 

The join-irreducible elements of $L_{\lambda}$ are those that have a unique cover relation. For a signature this means there is only one pair of adjacent positions of opposite sign that can be toggled to produce a signature still in $L_{\lambda}$. 
%In particular, they are of the form 
%\begin{align*}
%s=(1,2,\dots,l,j,j+1,\dots,j+m)\text{ such that }l\geq 0, \; j+m< n, \; j>l+1\text{ and }\; l+m=k-1.
%\end{align*} 
When $s$ has a unique cover relation, we identify it with the move $d_{i}(j)$. Define $P_{\lambda}$ to be the set of moves $d_{i}(j)$ associated with the join-irreducible elements $s\in L_{\lambda}$ with the order induced by $L_{\lambda}$. By construction, 
\begin{align*}
d_{i}(j)\in P_{\lambda}\text{ for }2\leq i\leq n-1\text{ and }1\leq j \leq k-1,
\end{align*}
where $1\leq i-j \leq k$.
It follows from the component-wise order on $L_{\lambda}$ that the order on $P_{\lambda}$ is $d_{i}(j)\leq_{P_{\lambda}} d_{a}(b)$ if  either $b < j$ and $i-1 \leq a$, or $b=j$ and $i\leq a$. Thus $P_{\lambda}$ is just the product of two chains $\mathbf{(k)} \times \mathbf{(n-k-1)}$. Therefore $$L_{\lambda}\cong J(\mathbf{(k)} \times \mathbf{(n-k-1)}).$$


We will now regard $P_{\lambda}$ as a PIP with no inconsistent pairs. We will show that the CAT(0) cubical complex $X(P_{\lambda})$ from Definition \ref{cubecomplex} is isomorphic to the cubical complex $C_{\lambda}$ rooted at signature $s=++\cdots +--\cdots -$, where $s$ has length $n-1$ and the first $k-1$ positions are $+$. To do this we will first describe explicitly the bijection between the vertices of $X(P_{\lambda})$ and those of $C_{\lambda}$ which follows directly from Birkhoff's theorem. In particular, the order ideal $I$ generated by the set of moves $\{d_{i}(j)\}$ corresponds to the following signature $s(I)$. The $a$-th entry of $s(I)$ is determined by the move that is maximal among all moves in $I$, in position $a$. For example, consider $P_{\lambda}$ as in Figure \ref{fig:ComplexAndPIPposet}(b). The ideal generated by $\{d_{3}(1)\}$ is $I=\{d_3(2), d_4(2), d_2(1), d_3(1)\}$. Move $d_3(1)$ is maximal among all $d_{i}(1)\in I$ and $d_4(2)$ is maximal among all $d_{i}(2)\in I$. Thus, the corresponding vertex in $C_{\lambda}$ is the signature $s(I)=(--++-)$. Similarly, $I=\{d_2(1),d_3(2), d_4(2)\}$ gives $s(I)=(-+-+-)$.

To complete the proof, we give an explicit bijection between $m$-dimensional cubes of $X(P_{\lambda})$ and $m$-dimensional cubes of $C_{\lambda}$. By Definition \ref{cubecomplex}, this equates to giving a bijection between a set of subideals of a consistent ideal of $P_{\lambda}$ and a set of vertices that form a $m$-cube in $C_{\lambda}$. Since all ideals of $P_{\lambda}$ are consistent, consider any $I\in X(P_{\lambda})$. We know $I$ corresponds to a vertex $s(I)=(i_1,i_2,\dots,i_{n-1})$ of $C_{\lambda}$. Let $M$ be the set of moves determined by the entries of $s(I)$. For example, for $I=\{d_2(1),d_3(2), d_4(2)\}$, we have $s(I)=(-+-+-)$ and $M=\{d_2(1),d_4(2)\}$. Then $I$ is equal to the ideal generated by $M$. 


Let $M_{max}=I_{max}$ and $m=|M_{max}|$. Then vertices of a $m$-cube in $X(P_{\lambda})$ are obtained by removing from $I$ the $2^m$ possible subsets of $M_{max}$. For $M'\subset M_{max}$, removing $M'$ from $I$ corresponds to changing the signs of entries $s(I)$ in positions $i-1,i$ for every $d_i(j)\in M'$. So the set of $2^m$ subsets of $I$ obtained by removing subsets $M'$ corresponds to the set of $2^m$ vertices of $C_{\lambda}$ achieved by changing signs of signature $s(I)$ in all positions determined by $M'$. This completes the bijection and concludes the proof.


\end{proof}

\begin{figure}[ht]
\centering
\begin{subfigure}[b]{1\textwidth}
\begin{center}
     \includegraphics[align=c,scale=0.6]{NewDualGraphforPip}
    \end{center}
    \caption{A vertex labeling by signatures and an edge labeling by dual equivalences on signature position for $C_{\lambda}$ where $\lambda=(3,1^3)$}
\end{subfigure}
\\
\begin{subfigure}[b]{1\textwidth}
    \centering
    \includegraphics[scale=0.8]{PIPdual}
    \caption{The PIP $P_{\lambda}$ constructed from edge labels of $C_{\lambda}$ for $\lambda=(3,1^3)$, such that the order ideals of $P_{\lambda}$ correspond to vertex labels of $C_{\lambda}$.}
    \end{subfigure}
    \caption{Given $\lambda=(3,1,1,1)$, we construct $C_{\lambda}$ and the associated PIP $P_{\lambda}$.}\label{fig:ComplexAndPIPposet}
\end{figure}






%%%%%%%%%% OLD PROOF - NEED THIS FOR THE GENERAL OUTLINE %%%%%%%
%\begin{proof}
%We begin by describing $G_{\lambda}$ in terms of permutations. Consider the permutation $\pi=n,n-1,\dots,n-k+1,1,2, ...,n-k$ which, after applying the Robinson--Schensted algorithm, has insertion tableau $P(\pi)$ of shape $\lambda = (n-k,1^k)$, a hook. Notice a series of Knuth moves beginning with $\pi$ effectively pushes entries $\{n,n-1,\dots,n-k+1\}$ to the right. As consecutive integers will never be swapped by a Knuth move, it follows that the Knuth equivalence class generated by $\pi$ consists of the permutations that have the integers $\{n,n-1,\dots,n-k+1\}$ in decreasing order and the integers $\{1,2,\dots,n-k\}$ in increasing order. Thus, these determine the vertices of $G_{\lambda}$ where there is an edge between vertices $\pi$ and $\sigma$ when $\pi\knuthab \sigma$.
%
%We now will describe $G_{\lambda}$ in terms of sequences. From above it follows that the vertices of $G_{\lambda}$ can be uniquely determined by the positions of the integers $n,n-1,\dots,n-k+1$ in the associated permutation. With this observation we introduce a new labeling of each vertex of $G_{\lambda}$ to be the index sequence of the positions of the integers $n,n-1,\dots,n-k+1$ in the corresponding permutation. See Figure \ref{fig:ComplexAndPIPposet}(a) for an example of this labeling. Recall an edge between vertices means a Knuth swap occurred; that is, an integer from $n,n-1,\dots,n-k+1$ moved from position $i$ to $i+1$. In terms of this new labeling, this means two vertices share an edge when the corresponding sequences have a difference of 1 in only one position. 
%
%
%
%\begin{figure}[ht]
%\centering
%\begin{subfigure}[b]{1\textwidth}
%\begin{center}
%    \begin{tabular}{cc}
%    $\young(1234,5,6):$ & \includegraphics[align=c,scale=0.55]{HookComplexLabeling}
%    \end{tabular}
%    \end{center}
%    \caption{A vertex labeling by index sets and an edge labeling by Knuth moves for $C_{\lambda}$ where $\lambda=(4,1^2)$}
%\end{subfigure}
%\\
%\begin{subfigure}[b]{1\textwidth}
%    \centering
%    \includegraphics[scale=0.6]{PIPposet}
%    \caption{The PIP $P_{\lambda}$ constructed from edge labels of $C_{\lambda}$ for $\lambda=(4,1^2)$, such that the order ideals of $P_{\lambda}$ correspond to vertex labels of $C_{\lambda}$.}
%    \end{subfigure}
%    \caption{Given $\lambda=(4,1,1)$, we construct $C_{\lambda}$ and the associated PIP $P$.}\label{fig:ComplexAndPIPposet}
%\end{figure}
%
%Next we define a poset structure $L_{\lambda}$ on the vertices of $G_{\lambda}$ and prove it is a distributive lattice. The sequence description of $G_{\lambda}$ produces a natural component-wise ordering on its vertices. For sequences $s=(i_1,i_2,\dots,i_{k})$ and $s'=(j_1,j_2,\dots,j_k)$ in $L_{\lambda}$, we say $s \leq_{L_{\lambda}} s'$ if $i_r\leq j_r$ for $1\leq r\leq k$. Define the function max$:L_{\lambda}^t\rightarrow L_{\lambda}$ to be the component-wise maximum. Define the function min similarly. Since $L_{\lambda}$ is finite, then max and min are well-defined. Moreover, since max and min are distributive on each component, it follows that they are distributive on $L_{\lambda}$ as well. Thus, $(L_{\lambda},\leq_{L_{\lambda}})$ is a distributive lattice. 
%
%By Birkhoff's representation \cite{StanelyEC1} theorem there exists a poset of order ideals isomorphic to $L_{\lambda}$. We now construct the poset $P_{\lambda}$ such that $L_{\lambda}\cong J(P_{\lambda})$. We construct $P_{\lambda}$ by describing the join-irreducible elements of $L_{\lambda}$. The order on $P_{\lambda}$ will follow from the component-wise order on $L_{\lambda}$.
%
%
%Consider the following edge labeling of $G_{\lambda}$. The edge between $s'$ and $s$ is labeled $M_{i,i+1}(l)$ to indicate that position $l$ is the location where $s'$ and $s$ differ by 1. As these edges correspond to Knuth moves in $G_{\lambda}$, we will refer to the label $M_{i,i+1}(l)$ as a \emph{move}. See Figure \ref{fig:ComplexAndPIPposet}(b) for an example of this labeling. Since $\lambda$ is a hook, there are no double edges in $G_{\lambda}$ so this labeling is well-defined. 
%
%The join-irreducible elements of $L_{\lambda}$ are those that have a unique cover relation. For a sequence this means there is only one entry that can be decreased by 1 and produce a sequence still in $L_{\lambda}$. In particular, they are of the form 
%\begin{align*}
%s=(1,2,\dots,l,j,j+1,\dots,j+m)\text{ such that }l\geq 0, \; j+m< n, \; j>l+1\text{ and }\; l+m=k-1.
%\end{align*} 
%When $s$ has a unique cover relation, we identify it with the move $M_{j-1,j}(l+1)$. Define $P_{\lambda}$ to be the set of moves $\{M_{j-1,j}(l+1)\}$ associated with the join-irreducible elements $s\in L_{\lambda}$ with the order induced by $L_{\lambda}$. By construction, 
%\begin{align*}
%M_{j-1,j}(l+1)\in P_{\lambda}\text{ for }0\leq l \leq k-1\text{ and }l+2\leq j \leq l+k+2.
%\end{align*}
%It follows from the component-wise order on $L_{\lambda}$ that the order on $P_{\lambda}$ is 
%\begin{align*}
%M_{i-1,i}(l+1)\leq_{P_{\lambda}} M_{j-1,j}(m+1)\text{ if }l\geq m\text{ and }i-l\leq j.
%\end{align*} 
%Thus $P_{\lambda}$ is just the product of two chains $\mathbf{(k)} \times \mathbf{(n-k-1)}$. Therefore $$L_{\lambda}\cong J(\mathbf{(k)} \times \mathbf{(n-k-1)}).$$
%
%
%We will now regard $P_{\lambda}$ as a PIP with no inconsistent pairs and show that the CAT(0) cubical complex $X(P_{\lambda})$ from Definition \ref{cubecomplex} is isomorphic to the cubical complex $C_{\lambda}$ of $G_{\lambda}$ rooted at $\pi$. To do this we will first describe explicitly the bijection between the vertices of $X(P_{\lambda})$ and those of $C_{\lambda}$ which follows directly from Birkhoff's theorem. In particular, the order ideal $I$ generated by the set of moves $\{M_{i,i+1}(l)\}$ corresponds to the following $k$-sequence $s(I)$. The $l$-th entry of $s(I)$ is determined by the move that is maximal among all moves in position $l$ in $I$. For example, consider $P_{\lambda}$ as in Figure \ref{fig:ComplexAndPIPposet}(b). The ideal generated by $\{M_{23}(1)\}$ is $I=\{M_{23}(2), M_{34}(2), M_{12}(1), M_{23}(1)\}$. Move $M_{23}(1)$ is maximal among all $M_{i,i+1}(1)\in I$ and $M_{34}(2)$ is maximal among all $M_{i,i+1}(2)\in I$. Thus, the corresponding vertex in $C_{\lambda}$ is the sequence $s(I)=(3,4)$. Similarly, $I=\{M_{12}(1),M_{23}(2), M_{34}(2)\}$ gives $s(I)=(2,4)$.
%
%To complete the proof, we give an explicit bijection between $d$-dimensional cubes of $X(P_{\lambda})$ and $d$-dimensional cubes of $C_{\lambda}$. By Definition \ref{cubecomplex}, this equates to giving a bijection between a set of subideals of a consistent ideal of $P_{\lambda}$ and a set of vertices that form a $d$-cube in $C_{\lambda}$. Since all ideals of $P_{\lambda}$ are consistent, consider any $I\in X(P_{\lambda})$. We know $I$ corresponds to a vertex $s(I)=(i_1,i_2,\dots,i_k)$ of $C_{\lambda}$. Let $M$ be the set of moves determined by the entries of $s(I)$. For example, for $I=\{M_{12}(1),M_{23}(2), M_{34}(2)\}$, we have $s(I)=(2,4)$ and $M=\{M_{12}(1),M_{34}(2)\}$. Then $I$ is equal to the ideal generated by $M$. Let $M_{max}=I_{max}$ and $d=|M_{max}|$. Then vertices of a $d$-cube in $X(P_{\lambda})$ are obtained by removing from $I$ the $2^d$ possible subsets of $M_{max}$. For $M'\subset M_{max}$, removing $M'$ from $I$ corresponds to decreasing the entries of $s(I)$ in position $l$ for every $M_{j,j+1}(l)\in M'$. So the set of $2^d$ subsets of $I$ obtained by removing subsets $M'$ corresponds to the set of $2^d$ vertices of $C_{\lambda}$ achieved by decreasing $s(I)$ in all positions determined by $M'$. This completes the bijection and concludes the proof.
%\end{proof}

Theorems \ref{thm:noncat0)} and \ref{GeneralHookCAT(0)} can be combined and restated in the following theorem.

\begin{theorem}
The cubical complex $C_{\lambda}$, whose $1$-skeleton is the dual equivalence graph $G_{\lambda}$, is a CAT(0) cubical complex if and only if $\lambda$ is a hook.
\end{theorem}

We have shown the CAT(0) property holds only for cubical complexes associated with dual equivalence graphs for hook shape tableaux. Still, one may hope for something to be said about cubical complexes arising from non-hook tableaux dual equivalence graphs. Two further directions one may take are the following. 

There is a notion of restricting $G_{\lambda}$ to subgraphs whose labeled edges are in a positive interval $I$. One can explore whether there are intervals that produce meaningful subgraphs without double edges. This would be the first indication that a CAT(0) property may hold for cubical complexes arising from subgraphs of dual equivalence graphs of any tableau shape.

A definition of dual equivalence graphs exists for skew tableaux. Perhaps the CAT(0) property can be extended to the dual equivalence graphs of certain skew tableaux.
One can examine the graphs of skew tableaux in search of the appropriate analogue of hooks. 






\acknowledgements{This work is part of Anastasia Chavez's Ph.D. thesis at the University of California, Berkeley and John Guo's Master's thesis at San Francisco State University. We are very thankful to our adviser, Dr.~Federico Ardila for his guidance throughout this project, and to the anonymous reviewers for their insightful feedback.}

\printbibliography



\end{document}
