# Resistance distance in connected balanced digraphs

R. Balakrishnan  Department of Mathematics, Bharathidasan University,
Tiruchirappalli-620024, India,
Email<EMAIL_ADDRESS>,  S. Krishnamoorthy  Indian Institute of Science
Education and Research Thiruvananthapuram, Maruthamala P.O.,Vithura,
Thiruvananthapuram-695551, Kerala, India, Email<EMAIL_ADDRESS>and  W. So  Department of Mathematics, San Jose State University, San Jose, CA
95192-0103, United States, Email<EMAIL_ADDRESS>
###### Abstract.

Let $D=(V,E)$ be a strongly connected and balanced digraph with vertex set $V$
and arc set $E.$ The classical distance $d_{ij}^{D}$ from $i$ to $j$ in $D$ is
the length of a shortest directed path from $i$ to $j$ in $D.$ Let $L$ be the
Laplacian matrix of $D$ and $L^{\dagger}=(l_{ij}^{\dagger})$ be the Moore-
Penrose inverse of $L.$ The resistance distance from $i$ to $j$ is then
defined by $r_{ij}^{D}:=l_{ii}^{\dagger}+l_{jj}^{\dagger}-2l_{ij}^{\dagger}.$
Let $\mathcal{C}$ be a collection of connected, balanced digraphs, each member
of which is a finite union of the form $D_{1}\cup D_{2}\cup....\cup D_{k}$
where each $D_{i}$ is a connected and balanced digraph with
$D_{i}\cap(D_{1}\cup D_{2}\cup....\cup D_{i-1})$ being a single vertex, for
all $i,$ $1<i\leq k.$ In this paper, we show that for any digraph $D$ in
$\mathcal{C}$, $r_{ij}^{D}\leq d_{ij}^{D}\ (*)$. This is established by
partitioning the Laplacian matrix of $D$. This generalizes the main result in
[3]. As a corollary, we deduce a simpler proof of the result in [3], namely,
that for any directed cactus $D$, the inequality (*) holds. Our results
provide an affirmative answer to a well known interesting conjecture ( cf :
Conjecture 1.3 ).

###### Key words and phrases:

Strongly connected balanced digraphs, Laplacian matrix, Moore-Penrose inverse,
resistance distance.

###### 2010 Mathematics Subject Classification:

Primary: 05C50

##  1\. introduction

Let $D=(V,E)$ be a directed graph with vertex set $V=\\{1,2,...,n\\}$ and arc
set $E$. The indegree and outdegree of a vertex $i$ in $D$ are defined by

$\delta^{\mathrm{in}}_{i}=|\\{j\mid(j,i)\in E\\}|,\
\delta^{\mathrm{out}}_{i}=|\\{j\mid(i,j)\in E\\}|$

respectively. The Laplacian matrix of the digraph $D$ is the matrix
$L=(l_{ij})$ of order $n$, where

$l_{ij}=\begin{cases}\delta^{\mathrm{out}}_{i}\ \mathrm{if}\ i=j\\\ -1\
\mathrm{if}\ (i,j)\in E\\\ 0\ \mathrm{otherwise}.\end{cases}$

######  Definition 1.1.

A digraph $D=(V,E)$ is balanced if
$\delta^{\mathrm{in}}_{i}=\delta^{\mathrm{out}}_{i}$ for all $i\in V$.

######  Definition 1.2.

A digraph $D$ is strongly connected if there is a directed path from any
vertex of $D$ to any other vertex of $D$.

Throughout this paper, we consider only finite digraphs.
Let $A$ be a complex $m\times n$ matrix. The Moore-Penrose inverse
$A^{\dagger}=(a_{ij}^{\dagger})$ of $A=(a_{ij})$ is the unique matrix of size
$n\times m$ which satisfies $AA^{\dagger}A=A,\ \
A^{\dagger}AA^{\dagger}=A^{\dagger},\ \ (AA^{\dagger})^{*}=AA^{\dagger},\ \
(A^{\dagger}A)^{*}=A^{\dagger}A,$ where $*$ denotes conjugate transpose. The
Moore-Penrose inverse exists for any arbitrary matrix [[6], Chapter 1], and
when a square matrix has a regular inverse, this inverse is its Moore-Penrose
inverse. A simple way to compute the Moore-Penrose is by using the singular
value decomposition. More on the theory of generalized inverses of matrices
can be found in [6], [5]. Klein and Radic introduced the notion of resistance
distance in undirected graphs [1]. Balaji, Bapat and Goel who introduced
resistance distance for digraphs in [2]. The resistance distance from the
vertex $i$ to the vertex $j$ of a digraph $D$ is denoted as $r_{ij}^{D}$. Then
the resistance distance matrix $R=(r_{ij}^{D})$ of the digraph $D$ is the
square matrix of order $n,$ where
$r_{ij}^{D}=l_{ii}^{\dagger}+l_{jj}^{\dagger}-2l_{ij}^{\dagger},$
$l_{jj}^{\dagger}$ is the $(i,j)$ entry of the Moore-Penrose inverse of the
Laplacian matrix $L.$ The study of resistance distance arose from the fact
that a simple, connected graph is a representation of an electrical network
with unit resistance placed on each of its edges.
The validity of Conjecture 1.3 given below has been verified to be true in
several examples.

######  Conjecture 1.3.

[3] For a strongly connected balanced digraph $D$, the resistance distance
$r_{ij}^{D}$ is upper bounded by $d_{ij}^{D}$ i.e., $r_{ij}^{D}\leq
d_{ij}^{D},$ where $d_{ij}^{D}$ is the length of a shortest directed path from
$i$ to $j$ in $D$.

Any connected balanced digraph is strongly connected. Hence the following
conjecture
( Conjecture 1.4 ) is equivalent to Conjecture 1.3.

######  Conjecture 1.4.

For a connected balanced digraph $D$, the resistance distance $r_{ij}^{D}$ is
upper bounded by $d_{ij}^{D}$ i.e., $r_{ij}^{D}\leq d_{ij}^{D},$ where
$d_{ij}^{D}$ is the length of a shortest directed path from $i$ to $j$ in $D$.

######  Definition 1.5.

A directed cactus is a strongly connected balanced digraph in which each edge
is contained in exactly one directed cycle.

Conjecture 1.3 is true for any directed cactus [3]. This was proved by using
combinatorial methods by counting the number of spanning forests satisfying
certain conditions. There is no proof showing that for a general connected,
balanced digraph $D$ which is not a directed cactus, which Conjecture 1.3 is
true. i.e. $r_{ij}^{D}\leq d_{ij}^{D}$ for all $i$ and $j$. In this paper, we
construct a new category $\mathcal{C}$ (which strictly contains the set of all
directed cactus) and prove the following theorem by using the method of
partitioning of matrices.

######  Theorem 1.6.

Let $\mathcal{C}$ be a collection of connected, balanced digraphs, each member
of which is a finite union of the form $D_{1}\cup D_{2}\cup....\cup D_{k}$
where each $D_{i}$ is a connected and balanced digraph with
$D_{i}\cap(D_{1}\cup D_{2}\cup....\cup D_{i-1})$ being a single vertex, for
all $i,$ $1<i\leq k.$ Then $r_{ij}^{D}\leq d_{ij}^{D}$ for all digraphs $D$ in
$\mathcal{C}$.

Note that $r_{ij}^{D}$ may be different from $r_{ij}^{D_{t}}$. (See Remark 2.8
below). Theorem 1.6 provides the proof of Conjecture 1.3 for all digraphs $D$
in $\mathcal{C}$. In this paper, as a corollary of Theorem 1.6, we deduce the
proof of Conjecture 1.3 for all directed cacti, which in fact is the main
result in [3].

######  Corollary 1.7 ([3], Theorem 3.5).

Let $D$ be a directed cactus. Then $r_{ij}^{D}\leq d_{ij}^{D}$ for all $i$ and
$j.$

######  Corollary 1.8.

Let $D_{1}$ and $D_{2}$ be two directed cacti with $D_{1}\cap D_{2}$ being a
single vertex. f Then $D_{1}\cup D_{2}$ also satisfies the condition that
$r_{ij}^{D}\leq d_{ij}^{D}$ for all $i$ and $j.$

##  2\. Preliminaries

We state some lemmas which will be used in the proof of our main theorem.
For a square matrix $A$ of order $N,$ let $A^{{}^{\prime}}$ be the transpose
of $A$. Let $S_{1}$ be a set of rows, $S_{2}$ be a set of columns of $A$ and
let $A[{S_{1}}^{c},{S_{2}}^{c}]$ be the matrix obtained by deleting the rows
of $S_{1}$ and columns of $S_{2}$. If $A$ is a square matrix with each row sum
and each column sum being zero, then all the cofactors of $A$ are the same. In
particular, if $\mathrm{rank}(A)=N-1,$ then
$\mathrm{det}(A[\\{i\\}^{c},\\{i\\}^{c}])$ are the same and also non-zero for
all $1\leq i\leq N$. Hence $A[\\{i\\}^{c},\\{i\\}^{c}]$ is non-singular.
A square matrix $A$ is called a $\mathbb{Z}$-matrix, if every off-diagonal
entry of $A$ is non- positive.

######  Lemma 2.1 ( [2], Lemma 3.1 ).

Let $L$ be a $\mathbb{Z}$-matrix of order $N$ such that
$L1=L^{{}^{\prime}}1=0$ and $\mathrm{rank}(L)=N-1$. Then $L$ can be
partitioned as $L=\begin{bmatrix}B&-Be\\\
-e^{{}^{\prime}}B&e^{{}^{\prime}}Be\end{bmatrix}$ and

$L^{\dagger}=\begin{bmatrix}B^{-1}-\frac{ee^{{}^{\prime}}B^{-1}}{N}-\frac{B^{-1}ee^{{}^{\prime}}}{N}&-\frac{B^{-1}e}{N}\\\
-\frac{e^{{}^{\prime}}B^{-1}}{N}&0\end{bmatrix}+\frac{e^{{}^{\prime}}B^{-1}e11^{{}^{\prime}}}{N^{2}},$

where $B$ is a square matrix of order $N-1$ and $e={\bf 1}_{N-1}.$

As an immediate application of the above lemma, the following theorem is
obtained in [2].

######  Theorem 2.2 ( [2], Theorem 3.1 ).

Let $D$ be a strongly connected, balanced digraph. The resistance distance
$r_{ij}^{D}$ satisfies
(i) $r_{ij}^{D}\geq 0,$ $\forall\ i$ and $j$, $r_{ij}^{D}=0\Leftrightarrow
i=j,$ (ii) Triangle inequality : $r_{ij}^{D}\leq r_{ik}^{D}+r_{kj}^{D}$ for
any $i,j$ and $k.$

The resistance distance is not a metric in general as it need not satisfy the
symmetry property.

Let $D=(V,E)$ be a connected, balanced digraph with vertex set $V$ and arc set
$E$. Let $\kappa(D,i)$ be the number of spanning trees of $D$ rooted at a
vertex $i$ of $D.$ By all minors matrix Theorem [7], it follows that
$\kappa(D,i)=\mathrm{det}(L[\\{i\\}^{c},\\{i\\}^{c}]).$ Since
$\mathrm{rank}(L)=|V|-1$ and $L1={L}^{{}^{\prime}}1=0$, all the cofactors of
$L$ are equal. Hence $\kappa(D,i)$ is independent of $i$ and we denote it by
$\kappa(D).$

######  Lemma 2.3 ([3], Lemma 3.1).

Let $D=(V,E)$ be a strongly connected, balanced digraph with vertex set $V$
and arc set $E$. Let $|V|=N$ and $i,j\in V$. If $(i,j)\in E$ or $(j,i)\in E,$
then $\mathrm{det}\left(L[\\{i,j\\}^{c},\\{i,j\\}^{c}]\right)\leq\kappa(D),$
where $L$ is the Laplacian of $D$ and $\kappa(D)$ is the number of spanning
trees of $D$ rooted at $i.$

######  Lemma 2.4.

Let $A^{\dagger}$ and $C^{\dagger}$ be the Moore-Penrose inverses of $A$ and
$C$ respectively. If $M$ is an $m\times n$ matrix partitioned with
$M=\left[\begin{array}[]{cc}A&0\\\ 0&C\end{array}\right]$ then
$M^{\dagger}=\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]$.

###### Proof.

By definition,
$A^{\dagger}AA^{\dagger}=A^{\dagger},AA^{\dagger}A=A,(AA^{\dagger})^{*}=AA^{\dagger},(A^{\dagger}A)^{*}=A^{\dagger}A$,
and
$C^{\dagger}CC^{\dagger}=C^{\dagger},CC^{\dagger}C=C,(CC^{\dagger})^{*}=CC^{\dagger},(C^{\dagger}C)^{*}=C^{\dagger}C$.
Now

$\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]\left[\begin{array}[]{cc}A&0\\\
0&C\end{array}\right]\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]=\left[\begin{array}[]{cc}A^{\dagger}AA^{\dagger}&0\\\
0&C^{\dagger}CC^{\dagger}\end{array}\right]=\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]$

$\left[\begin{array}[]{cc}A&0\\\
0&C\end{array}\right]\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]\left[\begin{array}[]{cc}A&0\\\
0&C\end{array}\right]=\left[\begin{array}[]{cc}AA^{\dagger}A&0\\\
0&CC^{\dagger}C\end{array}\right]=\left[\begin{array}[]{cc}A&0\\\
0&C\end{array}\right]$

$\left(\left[\begin{array}[]{cc}A&0\\\
0&C\end{array}\right]\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]\right)^{*}=\left[\begin{array}[]{cc}AA^{\dagger}&0\\\
0&CC^{\dagger}\end{array}\right]^{*}=\left[\begin{array}[]{cc}(AA^{\dagger})^{*}&0\\\
0&(CC^{\dagger})^{*}\end{array}\right]$
$=\left[\begin{array}[]{cc}AA^{\dagger}&0\\\
0&CC^{\dagger}\end{array}\right]=\left[\begin{array}[]{cc}A&0\\\
0&C\end{array}\right]\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]$

$\mathrm{Similarly}\left(\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]\left[\begin{array}[]{cc}A&0\\\
0&C\end{array}\right]\right)^{*}=\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]\left[\begin{array}[]{cc}A&0\\\
0&C\end{array}\right]$

Hence $M^{\dagger}=\left[\begin{array}[]{cc}A^{\dagger}&0\\\
0&C^{\dagger}\end{array}\right]$ by definition.

∎

######  Lemma 2.5.

Let $D=(V,E)$ be a strongly connected balanced digraph. Suppose $\forall$
$(i,j)\in E$, $r_{ij}^{D}\leq 1$, then Conjecture 1.3 is true for $D$.

###### Proof.

Suppose $i$ and $j$ are two distinct vertices of the digraph $D$. Let a
shortest path from $i$ to $j$ be given by $i=i_{0}\rightarrow
i_{1}\rightarrow.......\rightarrow i_{k-1}\rightarrow i_{k}=j$. The length of
the path is $k=d_{ij}^{D}$. We have $r_{i_{l-1}i_{l}}^{D}\leq 1\ \forall\ l=1\
\mathrm{to}\ k$. By repeatedly using the triangle inequality [Theorem 2.2,
(ii)], we get $r_{ij}^{D}\leq
r_{ii_{1}}^{D}+r_{i_{1}i_{2}}^{D}+.....+r_{i_{k-1}j}^{D}\leq 1+1+....+1$ (upto
$k$ times). Hence $r_{ij}^{D}\leq d_{ij}^{D}$. ∎

######  Lemma 2.6 ([3], Lemma 3.2, case(i)).

Let $D=(V,E)$ be a strongly connected, balanced digraph. Let $(i,j)\in E$. If
both $i$ and $j$ are of indegree one, then $r_{ij}^{D}\leq 1.$

######  Lemma 2.7 ([2], Theorem 5.2, (ii)).

Let $D$ be a strongly connected balanced digraph with vertex set
$\\{1,2,...,n\\},$ Laplacian matrix $L$ and Resistance matrix $R.$ Then for
each distinct pair $i,j\in\\{1,2,...,n\\},$

$r_{ij}^{D}+r_{ji}^{D}=2\frac{\mathrm{det}L[\\{i,j\\}^{c},\\{i,j\\}^{c}]}{\kappa(D)}.$

######  Remark 2.8.

Let $D$ be a strongly connected digraph and $D_{1},$ a strongly connected
subdigraph of $D$. Let $(i,j)$ be an arc in $D_{1}$. Then $r_{ij}^{D_{1}}$
need not be equal to $r_{ij}^{D}$.

######  Example 2.9.

Consider $D$ and $D_{1}$ as in Figures 4.1 and 4.2. We have
$r_{13}^{D}=0.8125+0.4375-0.625=0.625$ and
$r_{13}^{D_{1}}=0.6389+0.3056-0.2778=0.6667.$ Hence $r_{13}^{D}\neq
r_{13}^{D_{1}}$. Note that $r_{13}^{D}$ (resp. $r_{13}^{D_{1}}$) is evaluated
via the Moore-Penrose inverse of the Laplacian of $D$ (resp. $D_{1}$).

######  Example 2.10.

Consider the strongly connected graph $D$ as in Figure 4.4. We have
$r_{31}^{D}>d_{31}^{D}.$ This is a counterexample which shows that the
condition “balanced” in Conjecture 1.3 cannot be removed.

##  3\. Proof of Theorem 1.6

######  Lemma 3.1.

Let $D_{1},D_{2}$ be connected balanced arc-disjoint digraphs and let
$D_{1}\cap D_{2}$ be a single vertex. Suppose Conjecture 1.3 is true for both
$D_{1}$ and $D_{2}$, then it is true for $D=D_{1}\cup D_{2}$. In other words,
$r_{ij}^{D}\leq 1$ for all arcs $(i,j)\in E(D).$

###### Proof.

Let the vertex sets of $D_{1}$ and $D_{2}$ be $V(D_{1})=\\{1,2,....,n-1,n\\}$
and $V(D_{2})=\\{n,n+1,....,n+k\\}$. Let $D=D_{1}\cup D_{2}$. The vertex set
$V$ of $D=D_{1}\cup D_{2}$ is $\\{1,2,..,,n+k\\}$ and $V(D_{1})\cap
V(D_{2})=\\{n\\}$. Note that $|V_{1}|=n,|V_{2}|=k+1$. Let $N=n+k$. Then
$|V(D)|=N$. The digraphs $D_{1}$ and $D_{2}$ are both strongly connected and
balanced. Hence $D$ is also strongly connected and balanced. Let $(i,j)$ be an
arc. We have two cases. Case (i) $D_{1}\cap D_{2}=\\{i\\}\ \mathrm{or}\
\\{j\\}$, Case (ii) $D_{1}\cap D_{2}\neq\\{i\\}$ and $\neq\\{j\\}.$
Suppose Case (i) holds. Let $(i,j)$ be an arc and $i=n$ or $j=n$. Then either
$\\{i,j\\}\subseteq V(D_{1})\ \text{or}\ \\{i,j\\}\subseteq\ V(D_{2})$.
Without loss of generality, let $\\{i,j\\}\subseteq V(D_{1})$ and $i=1,$
$j=n$. The digraph $D$ is balanced and hence $L=L(D)$ satisfies the condition
that each row and each column adds up to zero and $\mathrm{rank}(L)=N-1$ and
$L$ is a $\mathbb{Z}$-matrix (see reference [3], section 2 (P7)). By Lemma
2.1,

$L^{\dagger}=\begin{bmatrix}B^{-1}-\frac{ee^{{}^{\prime}}B^{-1}}{N}-\frac{B^{-1}ee^{{}^{\prime}}}{N}&-\frac{B^{-1}e}{N}\\\
-\frac{e^{{}^{\prime}}B^{-1}}{N}&0\end{bmatrix}+\frac{e^{{}^{\prime}}B^{-1}e11^{{}^{\prime}}}{N^{2}},$

where $B=L[{\\{n\\}}^{c},{\\{n\\}^{c}}]$. Let $J$ be the $(N-1)\times(N-1)$
all $1$-matrix. $\mathrm{Set}\ B^{-1}=C=(c_{ij}),\\\
y=e^{{}^{\prime}}C=(y_{i}),\ x=Ce=(x_{i}),$
$\frac{e^{{}^{\prime}}B^{-1}e11^{{}^{\prime}}}{N^{2}}=x_{0}J,$ for some
rational number $x_{0}.$ We then have

$-\frac{ee^{{}^{\prime}}B^{-1}}{N}=-\frac{1}{N}\begin{bmatrix}y_{1}&y_{2}&\cdot&\cdot&\cdot&y_{N-1}\\\
y_{1}&y_{2}&\cdot&\cdot&\cdot&y_{N-1}\\\
\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\\
y_{1}&y_{2}&\cdot&\cdot&\cdot&y_{N-1}\end{bmatrix},\
-\frac{B^{-1}ee^{{}^{\prime}}}{N}=-\frac{1}{N}\begin{bmatrix}x_{1}&x_{1}&\cdot&\cdot&\cdot&x_{1}\\\
x_{2}&x_{2}&\cdot&\cdot&\cdot&x_{2}\\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\\
\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\\
x_{N-1}&x_{N-1}&\cdot&\cdot&\cdot&x_{N-1}\end{bmatrix},$

where $x_{i}=\sum_{l=1}^{N-1}c_{il},\ y_{i}=\sum_{l=1}^{N-1}c_{li},$ for all
$i=1$ to $N-1.$

Consider

$r_{1n}^{D}=l_{11}^{\dagger}+l_{nn}^{\dagger}-2l_{1n}^{\dagger}=c_{11}-\frac{y_{1}}{N}+x_{0}-\frac{x_{1}}{N}+x_{0}-(-\frac{2}{N}x_{1}+2x_{0})=c_{11}-\frac{y_{1}}{N}+\frac{x_{1}}{N}.$

Thus

$r_{1n}^{D}=c_{11}+\frac{(x_{1}-y_{1})}{N}.$ (3.1)

By Lemma 2.4, the Moore Penrose inverse of
$B=L[{\\{n\\}}^{c},{\\{n\\}^{c}}]=\begin{bmatrix}{L_{1}[{\\{n\\}}^{c},{\\{n\\}^{c}}]}&0\\\
0&{L_{2}[{\\{n\\}}^{c},{\\{n\\}^{c}}]}\end{bmatrix}$ is given by

$B^{-1}={L[{\\{n\\}}^{c},{\\{n\\}^{c}}]}^{-1}=\begin{bmatrix}{L_{1}[{\\{n\\}}^{c},{\\{n\\}^{c}}]}^{-1}&0\\\
0&{L_{2}[{\\{n\\}}^{c},{\\{n\\}^{c}}]}^{-1}\end{bmatrix}.$

By Lemma 2.1, we know that

$L_{1}^{\dagger}==\begin{bmatrix}B_{1}^{-1}-\frac{ee^{{}^{\prime}}B_{1}^{-1}}{n}-\frac{B_{1}^{-1}ee^{{}^{\prime}}}{n}&-\frac{B_{1}^{-1}e}{n}\\\
-\frac{e^{{}^{\prime}}B_{1}^{-1}}{n}&0\end{bmatrix}+\frac{e^{{}^{\prime}}B_{1}^{-1}e11^{{}^{\prime}}}{n^{2}},\mathrm{where}\
B_{1}=L_{1}[{\\{n\\}}^{c},{\\{n\\}^{c}}].$ $\mathrm{Set}\
B_{1}^{-1}=C^{*}=(c^{*}_{ij}),\ y^{*}=e^{{}^{\prime}}C^{*}=(y_{i}^{*}),\
x^{*}=C^{*}e=(x_{i}^{*}).\ \mathrm{We}\ \mathrm{get}\
r_{1n}^{D_{1}}=c^{*}_{11}+\frac{(x_{1}^{*}-y_{1}^{*})}{n_{1}}.$

From $B^{-1}=\begin{bmatrix}B_{1}^{-1}&0\\\
0&{L_{2}[{\\{n\\}}^{c},{\\{n\\}^{c}}]}^{-1}\end{bmatrix},$ we get
$c_{11}=c_{11}^{*},\ y_{1}=y_{1}^{*},\ x_{1}=x_{1}^{*}.$ Thus

$r_{1n}^{D_{1}}=c_{11}+\frac{(x_{1}-y_{1})}{n}.$ (3.2)

By combining equations 3.1 and 3.2, we get, as $N=n+k$,

$r_{1n}^{D}=c_{11}+\frac{n}{N}(r_{1n}^{D_{1}}-c_{11})=\frac{(nr_{1n}^{D_{1}}+kc_{11})}{n+k}.$
(3.3)

Now, by Lemma 2.3,

$c_{11}=\frac{\mathrm{det}L[\\{1,n\\}^{c},\\{1,n\\}^{c}]}{\kappa(D)}\leq 1.$
(3.4)

Conjecture 1.3 is true for $D_{1},$ so

$r_{1n}^{D_{1}}\leq 1.$ (3.5)

We conclude from equations 3.3, 3.4 and 3.5 that
$r_{1n}^{D}\leq\frac{n+k}{n+k}=1.$

Similarly, when $\\{i,j\\}\subseteq V(D_{1}),$ $(i,j)\in E(D_{1})$ and $j=1,$
$i=n,$ by using Lemma 2.3 we get $c_{11}\leq 1.$ Hence
$r_{n1}^{D}=\frac{(nr_{n1}^{D_{1}}+kc_{11})}{n+k}\leq 1.$ So $r_{ij}^{D}\leq
1$ if either $D_{1}\cap D_{2}=\\{i\\}\ \mathrm{or}\\{j\\}.$
Suppose Case (ii) holds. i.e. $D_{1}\cap D_{2}\neq\\{i\\}$ and $\neq\\{j\\}.$
Without loss of generality, let $\\{i,j\\}\subseteq V(D_{1})$. We have
$i,j\neq n$. Proceeding as before, we get

$r_{ij}^{D}=l_{ii}^{\dagger}+l_{jj}^{\dagger}-2l_{ij}^{\dagger}=c_{ii}+c_{jj}-2c_{ij}+\frac{(x_{i}-y_{i}+y_{j}-x_{j})}{N}$
(3.6)

and

$r_{ij}^{D_{1}}=l_{ii}^{\dagger}+l_{jj}^{\dagger}-2l_{ij}^{\dagger}=c_{ii}+c_{jj}-2c_{ij}+\frac{(x_{i}-y_{i}+y_{j}-x_{j})}{n}.$
(3.7)

By combining equations 3.1 and 3.2, we get, as $N=n+k$,

$r_{ij}^{D}=(c_{ii}+c_{jj}-2c_{ij})+\frac{n}{N}(r_{ij}^{D_{1}}-(c_{ii}+c_{jj}-2c_{ij}))=\frac{(nr_{ij}^{D_{1}}+k(c_{ii}+c_{jj}-2c_{ij}))}{n+k}$
(3.8)

and $r_{ij}^{D}+r_{ji}^{D}=2(c_{ii}+c_{jj}-c_{ij}-c_{ji})$. By Lemmas by 2.7
and 2.3 we thus have

$r_{ij}^{D}+r_{ji}^{D}=2\frac{\mathrm{det}L[\\{i,j\\}^{c},\\{i,j\\}^{c}]}{\kappa(D)}\leq
2.$

Hence $c_{ii}+c_{jj}-c_{ij}-c_{ji}\leq 1$. The determinant of a square matrix
is the same as the determinant of its transpose, we get

$c_{ij}=\frac{(-1)^{i+j}}{\kappa(D)}\mathrm{det}L[\\{i,n\\}^{c},\\{j,n\\}^{c}]=\frac{(-1)^{i+j}}{\kappa(D)}\mathrm{det}([L[\\{i,n\\}^{c},\\{j,n\\}^{c}]]^{{}^{\prime}})=c_{ji}.$

Hence

$c_{ii}+c_{jj}-2c_{ij}\leq 1.$ (3.9)

By equations 3.5, 3.8 and 3.9, we conclude that
$r_{ij}^{D}\leq\frac{n+k}{n+k}=1.$ ∎

We now present the proof of Theorem 1.6.

###### Proof.

Let $D=D_{1}\cup D_{2}\cup...\cup D_{k-1}\cup D_{k}$ be a digraph in
$\mathcal{C}$. We prove Theorem 1.6 by using induction on $k$, the number of
digraphs $D_{i}$. Note that the union of any finite number of strongly
connected and balanced digraphs is also strongly connected and balanced.
Without loss of generality, we can assume that $G=D_{1}\cup D_{2}\cup...\cup
D_{k-1}$ is connected and also $G$ and $D_{k}$ have a single vertex in common.
If $D$ is a union of two digraphs $D_{1}$ and $D_{2}$, then $r_{ij}^{D}\leq
d_{ij}^{D}$ by Lemma 3.1. The conjecture 1.3 is then true for $G=D_{1}\cup
D_{2}\cup...\cup D_{k-1}$ by induction. Hence Conjecture 1.3 is true for
$D=G\cup D_{k}$ by Lemma 3.1. ∎

######  Corollary 3.2 ([3], Theorem 3.5).

Let $D$ be a directed cactus. Then $r_{ij}^{D}\leq d_{ij}^{D}$ for all $i$ and
$j.$

###### Proof.

Let $D$ be a directed cactus. Then $D=D_{1}\cup D_{2}\cup.....\cup
D_{k},k\in\mathbb{N},$ where each $D_{i}$ is a balanced directed cycle and for
all $i,$ $1<i\leq k,$ $D_{i}\cap(D_{1}\cup D_{2}\cup...\cup D_{i-1})$ being a
single vertex. We know that Conjecture1.3 is true for $D_{i}$ by Lemma 2.6.
Hence $r_{ij}^{D}\leq d_{ij}^{D}$ by Theorem 1.6. ∎

##  4\. Examples

Figure 4.1. Strongly Connected and Balanced Digraph $D$ on $8$ vertices

v1v3v2v4v6v5v7v8

Figure 4.2 $D_{1}$ Figure 4.4 $D_{2}$

v1v3v2v4v6v5v6v7v8 $L=\left[\begin{array}[]{cccccccc}1&0&-1&0&0&0&0&0\\\
-1&2&-1&0&0&0&0&0\\\ 0&-1&2&-1&0&0&0&0\\\ 0&0&0&1&0&-1&0&0\\\
0&-1&0&0&1&0&0&0\\\ 0&0&0&0&-1&2&-1&0\\\ 0&0&0&0&0&0&1&-1\\\
0&0&0&0&0&-1&0&1\end{array}\right],\ $
$L_{1}=\left[\begin{array}[]{cccccc}1&0&-1&0&0&0\\\ -1&2&-1&0&0&0\\\
0&-1&2&-1&0&0\\\ 0&0&0&1&0&-1\\\ 0&-1&0&0&1&0\\\
0&0&0&0&-1&1\end{array}\right],\ L_{2}=\left[\begin{array}[]{ccc}1&-1&0\\\
0&1&-1\\\ -1&0&1\\\ \end{array}\right]$
$L^{\dagger}=\left[\begin{array}[]{cccccccc}0.8125&-0.0625&0.3125&0.1875&-0.3125&-0.1875&-0.3125&-0.4375\\\
0.3125&0.4375&0.3125&0.1875&-0.3125&-0.1875&-0.3125&-0.4375\\\
-0.0625&0.0625&0.4375&0.3125&-0.1875&-0.0625&-0.1875&-0.3125\\\
-0.3125&-0.1875&-0.3125&0.5625&0.0625&0.1875&0.0625&-0.0625\\\
0.1875&0.3125&0.1875&0.0625&0.5625&-0.3125&-0.4375&-0.5625\\\
-0.1875&-0.0625&-0.1875&-0.3125&0.1875&0.3125&0.1875&0.0625\\\
-0.4375&-0.3125&-0.4375&-0.5625&-0.0625&0.0625&0.9375&0.8125\\\
-0.3125&-0.1875&-0.3125&-0.4375&0.0625&0.1875&0.0625&0.9375\end{array}\right]\
\ $
$L_{1}^{\dagger}=\left[\begin{array}[]{cccccc}0.6389&-0.1944&0.1389&-0.0278&-0.3611&-0.1944\\\
0.1389&0.3056&0.1389&-0.0278&-0.3611&-0.1944\\\
-0.1944&-0.0278&0.3056&0.1389&-0.1944&-0.0278\\\
-0.3611&-0.1944&-0.3611&0.4722&0.1389&0.3056\\\
-0.0278&0.1389&-0.0278&-0.1944&0.4722&-0.3611\\\
-0.1944&-0.0278&-0.1944&-0.3611&0.3056&0.4722\end{array}\right],$
$L_{2}^{\dagger}=\left[\begin{array}[]{ccc}0.3333&0.3333&0.3333\\\
-0.1666&0.33333333&-0.1666\\\ -0.1666&-0.6666&-0.1666\end{array}\right].$

Figure 4.4. Strongly Connected Digraph $D$ on $4$ vertices

$v1$$v3$$v4$$v2$

The indegree at the vertex $v_{1}$ is $3$ and the outdegree at the vertex
$v_{1}$ is 2. Hence the above graph $D$ is not balanced. The degree matrix $D$
and the adjacency matrix $A$ are given by

$D=\left[\begin{array}[]{cccc}2&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\
0&0&0&0\end{array}\ \ \right],\ \ A=\left[\begin{array}[]{cccc}0&0&1&1\\\
1&0&0&0\\\ 1&0&0&0\\\ 1&1&0&0\end{array}\right]$

The Laplacian matrix $L(D)$ and the Moore-Penrose inverse of $L(D)$ are given
by

$L(D)=D-A=\left[\begin{array}[]{cccc}2&0&-1&-1\\\ -1&1&0&0\\\ -1&0&1&0\\\
-1&-1&0&2\end{array}\right],\ \
L(D)^{\dagger}=\left[\begin{array}[]{cccc}0.2&-0.275&-0.05&-0.025\\\
0&0.625&-0.25&-0.125\\\ -0.2&-0.475&0.5500&-0.225\\\
0&0.125&-0.25&0.375\end{array}\right]$ $\mathrm{We}\ \mathrm{have}\
r_{31}=l_{33}^{\dagger}+l_{11}^{\dagger}-2l_{31}^{\dagger}=0.2+0.55+0.4=1.15.$

Note $(3,1)$ is an arc. Hence $d_{31}=1.$ We have $r_{31}>d_{31}$.
Hence the graph $D$ is a counterexample which shows that the condition
“balanced” in Conjecture 1.3 cannot be removed.

###  4.1. Concluding Remark

The natural questions to ask are
(i) In Figure 4.2 the digraph $D_{1}=D\cap D^{{}^{\prime}},$ where the digraph
$D$ is a balanced triangle and the digraph $D^{{}^{\prime}}$ is a balanced
pentagon, numerically we have verified Conjecture 1.4 for $D_{1}.$ However an
abstract proof is not yet known. More precisely, If $D$ and $D^{{}^{\prime}}$
both are connected, balanced digraphs such that $D\cap D^{{}^{\prime}}$ have
only two vertices in common and Conjecture 1.4 is true for both $D$ and
$D^{{}^{\prime}}$ then whether it is true for the union $D\cup
D^{{}^{\prime}}$?
(ii) If $D_{1},D_{2},...,D_{k}$ are connected, balanced digraphs with
$D_{1}\cup D_{2}\cup....\cup D_{k}$ is connected, $D_{i}\cap D_{j}$ being at
most a single vertex, for all $i\neq j,$ $1\leq i,j\leq k$ and Conjecture 1.4
is true for all $D_{i}$, $i=1$ to $k$, then whether it is true for
$D=D_{1}\cup D_{2}\cup....\cup D_{k}?$ i.e., whether $D$ satisfies
$r_{ij}^{D}\leq d_{ij}^{D}$ for all $i$ and $j$? The methods in the proof of
our main theorem [Theorem 1.6] is not applicable to answer (i) and (ii). We
need alternative methods to answer these questions.

## Acknowledgement

We would like to thank Bharathidasan University, IISER, Thiruvananthapuram and
San Jose State University for providing the excellent working conditions. We
thank Ananth Narayanan for some helpful comments.

## References

  * [1] Klein, Douglas J and Randić, Milan. Resistance distance. Applied graph theory and discrete mathematics in chemistry. J. Math. Chem. 12, 1 (1993), 81–95.
  * [2] Balaji, R and Bapat, R.B and Goel, Shivani. Resistance matrices of balanced directed graphs. Linear and Multilinear Algebra. 70, 5 (2022), 787–808.
  * [3] Balaji, R and Bapat, R.B and Goel, Shivani, Resistance distance in directed cactus graphs. Electron. J. Linear Algebra. 36 (2020), 277–292.
  * [5] Campbell, Stephen L; Meyer, Carl D. Generalized inverses of linear transformations SIAM (2009).
  * [6] A. Ben-Israel, Adi; T.N. Greville, Generalized inverses: Theory and Applications. Springer Science and Business Media.15 (2003).
  * [7] S. Chaiken A combinatorial proof of the all minors matrix tree theorem SIAM. J. Algebraic Discrete Methods. 3 , 1 (1982), 319–329.


} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n-1})$ into
$\mathrm{PP}^{2M}(n\times n)$ then we will have
$\mathrm{Row}^{n}(\pi)=\mathrm{Tr}(\pi)$. Indeed, that essentially follows
from the reciprocity result, Theorem 5.7. It also can be shown using Theorem
5.7 that the _only_ $\pi\in\mathrm{PP}^{2M}(n\times n)$ with
$\mathrm{Row}^{n}(\pi)=\mathrm{Tr}(\pi)$ are in the image of this embedding.
But in fact, we can also establish that there are no other such $\pi$ via a
counting argument. Namely, Corollary 4.11 implies that

$\\#\\{\pi\in\mathrm{PP}^{2M}(n\times
n)\colon\mathrm{Tr}\cdot\mathrm{Row}^{n}(\pi)=\pi\\}=\mathrm{SymMac}(n,2M;q\coloneqq-1).$

Recall from Section 1 that

$\mathrm{SymMac}(n,2M;q\coloneqq-1)=\prod_{1\leq i\leq j\leq
n-1}\frac{i+j+2M}{i+j}.$

And it is known that $\\#\mathrm{PP}^{M}(\leavevmode\hbox to13.32pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 6.65831pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{-6.45831pt}{0.0pt}\pgfsys@lineto{6.45831pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{-6.45831pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n-1})=\prod_{1\leq
i\leq j\leq n-1}\frac{i+j+2M}{i+j}$; see, for instance, [56, Case “(CG)” of
Theorem 1]. This completes the proof of the lemma.

######  Remark 5.9.

If $m$ is odd, there are no $\pi\in\mathrm{PP}^{m}(n\times n)$ for which
$\mathrm{Tr}\cdot\mathrm{Row}^{n}(\pi)=\pi$. This can be seen either from the
Grinberg-Roby reciprocity result, Theorem 5.7, or from our cyclic sieving-like
result, Corollary 4.11. $\blacksquare$

######  Remark 5.10.

Recall the set $\mathrm{CY}(n,2M)$ defined in Section 2: this can be thought
of as the subset of $\mathrm{PP}^{2M}(\leavevmode\hbox to9.01pt{\vbox
to13.32pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-6.65831pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{0.0pt}{-6.45831pt}\pgfsys@lineto{0.0pt}{6.45831pt}\pgfsys@lineto{8.61108pt}{0.0pt}\pgfsys@lineto{0.0pt}{-6.45831pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n-1})$ with even
entries along the leftmost “file.” In Section 2 we explained how
$\mathrm{CY}(n,2M)$ is naturally in bijection with the set of plane partitions
$\pi\in\mathrm{PP}^{2M}(n\times n)$ for which
$\mathrm{Tr}\cdot\mathrm{Pro}(\pi)=\pi$. Meanwhile, we just explained in the
proof of Lemma 5.8 that $\mathrm{PP}^{M}(\leavevmode\hbox to13.32pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 6.65831pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{-6.45831pt}{0.0pt}\pgfsys@lineto{6.45831pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{-6.45831pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n-1})$ is naturally
in bijection with the set of plane partitions $\pi\in\mathrm{PP}^{2M}(n\times
n)$ for which $\mathrm{Tr}\cdot\mathrm{Row}^{n}(\pi)=\pi$. Then observe that

$\\#\mathrm{CY}(n,2M)=\prod_{1\leq i\leq j\leq
n-1}\frac{i+j+2M}{i+j}=\\#\mathrm{PP}^{M}(\leavevmode\hbox to13.32pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 6.65831pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{-6.45831pt}{0.0pt}\pgfsys@lineto{6.45831pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{-6.45831pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n-1}),$

as was proved for instance in the paper of Proctor [56]. However, it is not at
all a priori clear that $\mathrm{CY}(n,2M)$ and
$\mathrm{PP}^{M}(\leavevmode\hbox to13.32pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 6.65831pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{-6.45831pt}{0.0pt}\pgfsys@lineto{6.45831pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{-6.45831pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n-1})$ have the same
size, and constructing a bijection between these two sets is rather difficult
(a bijection appears for instance in [75]). Thus, by studying the way these
two operators interact with transposition, we uncovered another interesting
“duality” between promotion and rowmotion. $\blacksquare$

We can relate $\leavevmode\hbox to9.01pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{}{}}{} {{}{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{8.61108pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n}$ to the rectangle
by combining the previous two ideas.

######  Lemma 5.11.

There is a $\mathrm{Row}$-equivariant bijection between
$\mathrm{PP}^{M}(\leavevmode\hbox to9.01pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{}{}}{} {{}{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{8.61108pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n})$ and the subset
of $\pi\in\mathrm{PP}^{2M}(2n\times 2n)$ for which $\mathrm{Tr}(\pi)=\pi$ and
$\mathrm{Row}^{2n}(\pi)=\pi$.

This follows from combining the ideas in the proofs of Lemmas 5.6 and 5.8.
There is an obvious “transposition” symmetry of $\leavevmode\hbox
to13.32pt{\vbox to9.01pt{\pgfpicture\makeatletter\hbox{\hskip
6.65831pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{-6.45831pt}{0.0pt}\pgfsys@lineto{6.45831pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{-6.45831pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{2n-1}$ which
reflects the poset across the vertical line of symmetry. Let
$\mathrm{Tr}\colon\mathrm{PP}^{M}(\leavevmode\hbox to13.32pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 6.65831pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{-6.45831pt}{0.0pt}\pgfsys@lineto{6.45831pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{-6.45831pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{2n-1})\to\mathrm{PP}^{M}(\leavevmode\hbox
to13.32pt{\vbox to9.01pt{\pgfpicture\makeatletter\hbox{\hskip
6.65831pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{-6.45831pt}{0.0pt}\pgfsys@lineto{6.45831pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{-6.45831pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{2n-1})$ denote the
induced symmetry of $P$-partitions. Then, by the same argument as in the proof
of Lemma 5.6, $\mathrm{PP}^{M}(\leavevmode\hbox to9.01pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{}{}}{} {{}{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{8.61108pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n})$ is in
$\mathrm{Row}$-equivariant bijection with the
$\pi\in\mathrm{PP}^{M}(\leavevmode\hbox to13.32pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 6.65831pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}}{{}}{} {{}{}}{} {{}{}}{}
{{}{}}{}{}\pgfsys@moveto{-6.45831pt}{0.0pt}\pgfsys@lineto{6.45831pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{-6.45831pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{2n-1})$ with
$\mathrm{Tr}(\pi)=\pi$. Via the proof of Lemma 5.8 we can further embed
$\mathrm{PP}^{M}(\leavevmode\hbox to9.01pt{\vbox
to9.01pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{}{}}{} {{}{}}{}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{8.61108pt}{0.0pt}\pgfsys@lineto{0.0pt}{8.61108pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}_{n})$ into
$\mathrm{PP}^{2M}(2n\times 2n)$ in desired way.

The preceding lemmas about how to embed the triangular posets into the
rectangle allow us to reformulate Conjectures 5.1, 5.2 and 5.3, as follows:

######  Conjecture 5.12 (Reformulation of Conjecture 5.1 in light of Lemma
5.6).

For any $k\in\mathbb{Z}$ we have that

$\\#\\{\pi\in\mathrm{PP}^{m}(n\times
n)\colon\mathrm{Tr}(\pi)=\pi,\mathrm{Row}^{k}(\pi)=\pi\\}=F(q\coloneqq\zeta^{k}),$

where $\zeta\coloneqq e^{\pi i/n}$ is a primitive $(2n)$th root of unity and

$F(q)\coloneqq\prod_{1\leq i\leq j\leq
n}\frac{(1-q^{i+j+m-1})}{(1-q^{i+j-1})}.$

######  Conjecture 5.13 (Reformulation of Conjecture 5.2 in light of Lemma
5.8).

For any $k\in\mathbb{Z}$ we have that

$\\#\\{\pi\in\mathrm{PP}^{2M}(n\times
n)\colon\mathrm{Tr}\cdot\mathrm{Row}^{n}(\pi)=\pi,\mathrm{Row}^{k}(\pi)=\pi\\}=F(q\coloneqq\zeta^{k}),$

where $\zeta\coloneqq e^{\pi i/n}$ is a primitive $(2n)$th root of unity and

$F(q)\coloneqq\prod_{1\leq i\leq j\leq
n-1}\frac{(1-q^{i+j+2M})}{(1-q^{i+j})}.$

######  Conjecture 5.14 (Reformulation of Conjecture 5.3 in light of Lemma
5.11).

For any $k\in\mathbb{Z}$ we have that

$\\#\\{\pi\in\mathrm{PP}^{2M}(2n\times
2n)\colon\mathrm{Tr}(\pi)=\pi,\mathrm{Row}^{2n}(\pi)=\pi,\mathrm{Row}^{k}(\pi)=\pi\\}=F(q\coloneqq\zeta^{k}),$

where $\zeta\coloneqq e^{\pi i/2n}$ is a primitive $(4n)$th root of unity and

$F(q)\coloneqq\prod_{1\leq i,j\leq
n}\frac{(1-q^{2(i+j+M-1)})}{(1-q^{2(i+j-1)})}.$

######  Remark 5.15.

Conjecture 5.14 follows easily from Conjecture 5.13 or Conjecture 5.12 via the
same kind of argument as in [5, Proof of Proposition 2.4]. $\blacksquare$

Corollaries 4.3 and 4.11 from the previous section say that for any
$g\in\langle\mathrm{Row},\mathrm{Tr}\rangle$, the number of plane partitions
in $\mathrm{PP}^{m}(n\times n)$ fixed by $g$ is given by some kind of cyclic
sieving-like evaluation of a polynomial with a simple product formula as a
rational expression. In other words, for any cyclic subgroup
$H\subseteq\langle\mathrm{Row},\mathrm{Tr}\rangle$, the number of plane
partitions in $\mathrm{PP}^{m}(n\times n)$ fixed by $H$ is given by some kind
of cyclic sieving-like evaluation. Meanwhile, Conjectures 5.12, 5.13 and 5.14
assert that for various _noncyclic_ subgroups
$H\subseteq\langle\mathrm{Row},\mathrm{Tr}\rangle$, the number of plane
partitions in $\mathrm{PP}^{m}(n\times n)$ fixed by $H$ is given by some kind
of cyclic sieving-like evaluation. This leads us to wonder the following:

######  Question 5.16.

Is the number of plane partitions in $\mathrm{PP}^{m}(n\times n)$ fixed by
$H$, where $H$ is any subgroup of $\langle\mathrm{Row},\mathrm{Tr}\rangle$,
given by a cyclic sieving-like evaluation at a root of unity of a polynomial
with a simple product formula as a rational expression?

If Question 5.16 had a positive answer, it would be very similar to what
happens with the “classical” symmetries of plane partitions, where the 10
symmetry classes all have product formulas for their enumeration (again see
[78, 42]).

######  Remark 5.17.

The polynomial $F(q)$ appearing in Conjecture 5.1 is the principal
specialization of the character of the irreducible $SO(2n+1)$ representation
$V(m\omega_{n})$, where $\omega_{n}$ is the minuscule weight of Type $B_{n}$.
(Technically one might have to work with the simply connected double cover
$\widetilde{SO}(2n+1)$, i.e., the so-called “ _spin group_.”) Geometrically,
this representation is the dual of the $m$th homogeneous component of the
coordinate ring of the maximal orthogonal Grassmannian $\mathrm{OG}(n,2n+1)$.
Similarly, the polynomial $F(q)$ appearing in Conjecture 5.2 is (essentially)
the principal specialization of the character of the irreducible $Sp(2n)$
representation $V(m\omega_{n})$, where $\omega_{n}$ is the cominuscule weight
of Type $C_{n}$. Geometrically, this representation is the dual of the $m$th
homogeneous component of the coordinate ring of the Lagrangian Grassmannian
$\mathrm{LG}(n,2n)$. See Proctor [55, 56] or Stembridge [82] for more
information about these polynomials. At any rate, the fact that these
polynomials are more-or-less Lie group characters naturally suggests an
approach for resolving Conjectures 5.1 and 5.2: find a basis of the
corresponding representation indexed by the set of $P$-partitions in question
and such that an appropriate group element (e.g., the lift of a Coxeter
element) permutes the basis according to rowmotion (or, more likely, according
to a conjugate “promotion”-like action). In other words, extend Rhoades’s
approach [60] to other types. The problem with this approach is that the naive
bases like the standard monomial basis fail to behave in the appropriate way,
while the sophisticated bases like the dual canonical basis or the theta basis
are extremely hard to concretely get one’s hands on, and doubly so outside of
Type A. (We do not mean to suggest that it is _totally_ hopeless to work in
other types. For instance, the theory of plabic graphs [73, 53] is ultimately
the combinatorial underpinning of the Shen–Weng [76] proof of cyclic sieving,
and the work of Karpman [38, 36, 37] extends much of the theory of plabic
graphs to the Lagrangian Grassmannian.) Our results in this paper point the
way to an alternative but ultimately complementary approach to Conjectures 5.1
and 5.2: stay in the Type A world but impose symmetries. $\blacksquare$

##  Appendix A Plane partitions and semistandard tableaux

In this appendix we explain the correspondence between plane partitions and
semistandard tableaux of rectangular shape, and how the operators we are
interested in (e.g., promotion) behave under this correspondence.

A _partition_ $\lambda=(\lambda_{1}\geq\lambda_{2}\geq\cdots)$ is an infinite
nonincreasing sequence of integers for which $\lambda_{i}=0$ for all $i\gg 0$.
The nonzero $\lambda_{i}$ are called the _parts_ of $\lambda$. If we write a
partition as $\lambda=(\lambda_{1},\ldots,\lambda_{k})$ that means that
$\lambda_{i}=0$ for $i>k$. A particularly important family of partitions for
us will be the _rectangle_ partitions
$m^{a}\coloneqq(\overbrace{m,m,\ldots,m}^{a})$. We represent a partition
$\lambda$ via its _Young diagram_ , which is the collection of boxes in rows
with $\lambda_{i}$ boxes left-justified in row $i$. For example, the Young
diagram of $(4,3,1,1)$ is:

$\ydiagram{4,3,1,1}$

A _semistandard Young tableau_ of shape $\lambda$ is a filling of the boxes of
the Young diagram of $\lambda$ with positive integers that is weakly
increasing in rows and strictly increasing in columns. For example, the
following is a semistandard Young tableau of shape $(4,3,1,1)$:

$\ytableau 1&336\\\ 255\\\ 4\\\ 5$

We use $\mathrm{SSYT}(\lambda,k)$ to denote the set of semistandard Young
tableau of shape $\lambda$ whose entries belong to $\\{1,2,\ldots,k\\}$. Note
that this set is empty if $k$ is less than the number of parts of $\lambda$.

Now we define the _promotion_ operator $\rho$ acting on
$\mathrm{SSYT}(\lambda,k)$.222There is no consensus in the literature about
whether the operator $\rho$ or $\rho^{-1}$ is the one which should be called
“promotion.” We follow the convention of Rhoades [60] and Lam [44]; but for
instance Bloom, Pechenik, and Saracino [9] take the opposite convention. Of
course, ultimately these differences in convention are inconsequential.
Roughly speaking, promotion behaves as follows: first we delete all entries of
$k$ in our tableau, leaving holes in their places; then we slide the remaining
entries into the holes so that the holes occupy the upper-left of the Young
diagram; then we increment by one all entries in the tableau; and finally we
fill the holes in the upper-left with $1$’s. For example, with $k=6$, an
application of promotion might look like the following:

$\ytableau 1&33\\\ 246\\\ 45\\\ 66\xrightarrow{\textrm{delete $6$'s}}\ytableau
1&33\\\ 24\bullet\\\ 45\\\
\bullet\bullet\xrightarrow{\textrm{slide}}\ytableau\bullet&\bullet\bullet\\\
133\\\ 24\\\
45\xrightarrow{\textrm{increment}}\ytableau\bullet&\bullet\bullet\\\ 244\\\
35\\\ 56\xrightarrow{\textrm{fill in $1$'s}}\ytableau 1&11\\\ 244\\\ 35\\\ 56$

To formalize this definition would require more explanation of the sliding
procedure. A precise description is given in [60, §2]. In fact, these slides
are the “jeu de taquin” moves of Schützenberger [70, 71, 72] (see also the
presentation of Haiman [32]).

Another closely related operator acting on $\mathrm{SSYT}(\lambda,k)$ is
_evacuation_ $\varepsilon$. It can also be defined in terms of jeu de taquin
slides. Evacuation roughly behaves as follows: first we rotate the tableau
$180^{\circ}$; then we replace every entry by $k+1$ minus that entry; finally,
we slide the entries into the upper-left so that we get back to a Young
diagram shape. For example, with $k=6$, an application of evacuation might
look like the following:

$\ytableau 1&33\\\ 246\\\ 45\\\ 66\xrightarrow{\textrm{rotate
$180^{\circ}$}}\ytableau\none&66\\\ \none 54\\\ 642\\\
331\xrightarrow{i\mapsto k+1-i}\ytableau\none&11\\\ \none 23\\\ 135\\\
446\xrightarrow{\textrm{slide}}\ytableau 1&11\\\ 235\\\ 34\\\ 46$

Again, to formalize this definition of evacuation we would need to explain the
jeu de taquin slides in more detail; a precise description is given in [60,
§2].

However, rather than use jeu de taquin, we will instead work with different
but equivalent definitions of promotion and evacuation in terms of the so-
called “Bender–Knuth involutions” [7].

######  Definition A.1.

The $i$th _Bender–Knuth involution_
$\mathcal{BK}_{i}\colon\mathrm{SSYT}(\lambda,k)\to\mathrm{SSYT}(\lambda,k)$,
for $1\leq i<k$, is the operator which acts on a tableau
$T\in\mathrm{SSYT}(\lambda,k)$ as follows: first we “freeze” in place all
$i$’s directly above $(i+1)$’s, and all $(i+1)$’s directly below $i$’s; and
then, in each row, we change unfrozen $i$’s into $(i+1)$’s and unfrozen
$(i+1)$’s into $i$’s in the unique way which preserves the semistandardness
condition and so that the number of unfrozen $i$’s in that row in the
resulting tableau is the number of unfrozen $(i+1)$’s in that row in the
original tableau, and vice-versa.

######  Example A.2.

Let $T\in\mathrm{SSYT}((11,10,8,4,2),6)$ be the following tableau:

$T=\ytableau 1&1112223334\\\ 2233334445\\\ 34445555\\\ 5556\\\ 66$

Suppose we want to compute $\mathcal{BK}_{4}(T)$. First of all, we can
restrict our attention to only the $4$’s and $5$’s in the tableau, resulting
in a picture that looks like this:

$\ytableau\,&\,\,\,\,\,\,\,\,\,4\\\ \,\,\,\,\,\,4445\\\ \,4445555\\\ 555\,\\\
\,\,$

Then we “freeze” in place $4$’s directly above $5$’s and $5$’s directly below
$4$’s. In the picture below these frozen boxes have been shaded:

$\ytableau\,&\,\,\,\,\,\,\,\,\,4\\\
\,\,\,\,\,\,*(lightgray)4*(lightgray)445\\\
\,*(lightgray)4*(lightgray)4455*(lightgray)5*(lightgray)5\\\
5*(lightgray)5*(lightgray)5\,\\\ \,\,$

Then within each row we swap the number of unfrozen $4$’s and $5$’s, while
preserving the weakly decreasing requirement, resulting in the following:

$\ytableau\,&\,\,\,\,\,\,\,\,\,5\\\
\,\,\,\,\,\,*(lightgray)4*(lightgray)445\\\
\,*(lightgray)4*(lightgray)4445*(lightgray)5*(lightgray)5\\\
4*(lightgray)5*(lightgray)5\,\\\ \,\,$

Finally, to obtain $\mathcal{BK}_{4}(T)$, we put the entries which are not
$4$’s or $5$’s back in as they were in $T$:

$\mathcal{BK}_{4}(T)=\ytableau 1&1112223335\\\ 2233334445\\\ 34444555\\\
4556\\\ 66$

$\blacksquare$

It is clear that the $\mathcal{BK}_{i}$ are indeed involutions. We can define
promotion and evacuation as a composition of these involutions.

######  Definition A.3.

_Promotion_ $\rho\colon\mathrm{SSYT}(\lambda,k)\to\mathrm{SSYT}(\lambda,k)$ is
the following composition of Bender–Knuth involutions:

$\rho\coloneqq\mathcal{BK}_{1}\cdot\mathcal{BK}_{2}\cdots\mathcal{BK}_{k-2}\cdot\mathcal{BK}_{k-1}$

_Evacuation_
$\varepsilon\colon\mathrm{SSYT}(\lambda,k)\to\mathrm{SSYT}(\lambda,k)$ is:

$\varepsilon\coloneqq(\mathcal{BK}_{1})\cdot(\mathcal{BK}_{2}\cdot\mathcal{BK}_{1})\cdots(\mathcal{BK}_{k-2}\cdots\mathcal{BK}_{2}\cdot\mathcal{BK}_{1})\cdot(\mathcal{BK}_{k-1}\cdots\mathcal{BK}_{2}\cdot\mathcal{BK}_{1})$

_Dual evacuation_
$\varepsilon^{*}\colon\mathrm{SSYT}(\lambda,k)\to\mathrm{SSYT}(\lambda,k)$ is:

$\varepsilon^{*}\coloneqq(\mathcal{BK}_{k-1})\cdot(\mathcal{BK}_{k-2}\cdot\mathcal{BK}_{k-1})\cdots(\mathcal{BK}_{2}\cdots\mathcal{BK}_{k-2}\cdot\mathcal{BK}_{k-1})\cdot(\mathcal{BK}_{1}\cdots\mathcal{BK}_{k-2}\cdot\mathcal{BK}_{k-1})$

We did not discuss dual evacuation earlier but it turns out to be useful in
understanding the behavior of promotion and evacuation. It is a theorem of
Gansner [25] (see also [9]) that the definitions of promotion and evacuation
in terms of the Bender–Knuth involutions are the same as those in terms of
Schützenberger’s jeu de taquin moves.

As we will see in the next proposition, evacuation has a very simple behavior
on tableaux of rectangular shape. In order to record that behavior we need a
little notation. So for $T\in\mathrm{SSYT}(m^{a},k)$ we define
$T^{+}\in\mathrm{SSYT}(m^{a},k)$ to be the tableau obtained by rotating $T$
$180^{\circ}$ and replacing every entry by $k+1$ minus that entry.

The following proposition records some basic properties of promotion and
evacuation which are well known but are “folklore.” The best reference we have
for these results is the paper of Bloom-Pechenik-Saracino [9], who adapt the
arguments presented by Stanley [80] in the case of standard Young tableaux,
and also use the fundamental connection of promotion and evacuation to the
_Robinson-Schensted-Knuth correspondence_.

######  Proposition A.4 (See [9, Theorem 2.9]).

For any $\lambda$ and any $k$ we have the following relationship among the
operators
$\rho,\varepsilon,\varepsilon^{*}\colon\mathrm{SSYT}(\lambda,k)\to\mathrm{SSYT}(\lambda,k)$:

  * •

$\varepsilon^{2}=(\varepsilon^{*})^{2}=\mathrm{id}$ (the identity operator);

  * •

$\rho\varepsilon=\varepsilon\rho^{-1}$;

  * •

$\rho^{k}=\varepsilon\varepsilon^{*}$.

Furthermore, if $\lambda=m^{a}$ is a rectangle then
$\varepsilon(T)=\varepsilon^{*}(T)=T^{+}$ for all
$T\in\mathrm{SSYT}(m^{a},k)$. Consequently, $\rho^{k}=\mathrm{id}$ if
$\lambda=m^{a}$ is a rectangle.

Now we explain an equivalent, but very useful, way to think about semistandard
Young tableaux: namely, as _Gelfand-Tsetlin patterns_. In particular, Gelfand-
Tsetlin patterns will serve as the bridge between semistandard tableaux and
plane partitions. The usefulness of Gelfand-Tsetlin patterns for understanding
operations on semistandard tableaux in terms of piecewise-linear expressions
was especially emphasized in the papers of Berenstein and Kirillov [40] and
Berenstein and Zelevinsky [8].

######  Definition A.5.

Let $\lambda$ be a partition and $k$ an integer greater than or equal to the
number of parts of $\lambda$. A _Gelfand-Tsetlin pattern_ of shape $\lambda$
and length $k$ is a triangular array $\pi=(\pi_{i,j})_{1\leq i\leq j\leq k}$
of nonnegative integers $\pi_{i,j}\in\mathbb{N}$ such that:

  * •

$\pi$ is weakly decreasing in rows and columns (i.e.,
$\pi_{i,j}\geq\pi_{i+1,j}$, $\pi_{i,j}\geq\pi_{i,j+1}$ for all $i,j$);

  * •

the main diagonal $(\pi_{1,1},\pi_{2,2},\ldots,\pi_{k,k})$ of $\pi$ is equal
to the partition $\lambda$.

We denote the set of such Gelfand-Tsetlin patterns by
$\mathrm{GT}(\lambda,k)$.

There is a well-known bijection
$\Phi\colon\mathrm{GT}(\lambda,k)\to\mathrm{SSYT}(\lambda,k)$: for
$\pi\in\mathrm{GT}(\lambda,k)$, the tableau $T=\Phi(\pi)$ is the unique
semistandard tableau such that for all $1\leq i\leq k$ the diagonal
$(\pi_{i,1},\pi_{i+1,2},\ldots,\pi_{k,k+1-i})$ of $\pi$ is the shape of the
restriction of $T$ to the entries $\\{1,2,\ldots,k+1-i\\}$. To see that this
is really a bijection, observe that $\pi_{k,1}$ is the number of $1$’s in $T$,
and these must all go in the first row; similarly $\pi_{k-1,1}-\pi_{k,1}$ is
the number of $2$’s in the first row and $\pi_{k-1,2}$ is the number of $2$’s
in the second row; and so on. In this way we can clearly reconstruct a unique
tableau $T$ from $\pi$, and the inequalities imposed on the $\pi_{i,j}$
exactly correspond to the semistandardness condition.

######  Example A.6.

Let $\lambda=(3,2,1,1,0)$ and let $\pi\in\mathrm{GT}(\lambda,5)$ be the
following Gelfand-Tsetlin pattern:

$\pi=\begin{matrix}3&3&3&1&1\\\ &2&1&1&0\\\ &&1&1&0\\\ &&&1&0\\\
&&&&0\end{matrix}$

Then $T=\Phi(\pi)\in\mathrm{SSYT}(\lambda,5)$ is the semistandard tableau

$T=\ytableau 1&33\\\ 35\\\ 4\\\ 5$

$\blacksquare$

Naturally we want to understand how promotion behaves in terms of Gelfand-
Tsetlin patterns. This is where the piecewise-linear toggles come in. We
define the _piecewise-linear toggle_
$\tau_{i,j}\colon\mathrm{GT}(\lambda,k)\to\mathrm{GT}(\lambda,k)$ for $1\leq
i<j\leq k$ by

$(\tau_{i,j}\pi)_{p,q}\coloneqq\begin{cases}\pi_{p,q}&\textrm{if
$(p,q)\neq(i,j)$};\\\
\mathrm{min}(\pi_{i,j-1},\pi_{i-1,j})+\mathrm{max}(\pi_{i+1,j},\pi_{i,j+1})-\pi_{i,j}&\textrm{if
$(p,q)=(i,j)$},\\\ \end{cases}$

where we ignore $\pi_{i,j}$ with $i,j$ outside of the bounds of the triangle
(at least one term in each $\mathrm{max}$ and $\mathrm{min}$ will exist).
Observe that these are exactly the same as the $\tau_{i,j}$ defined in Section
1. We again define $\mathcal{F}_{l}\coloneqq\prod_{\begin{subarray}{c}1\leq
i\leq j\leq k,\\\ j-i=l\end{subarray}}\tau_{i,j}$ for $1\leq l\leq k-1$ to be
the composition of all the toggles along the “$l$th diagonal” of our array. As
Berenstein-Kirillov [40] explained, these diagonal toggles are the same as the
Bender–Knuth involutions:333Hence one may view $\mathcal{BK}$ as honoring
either Bender and Knuth or Berenstein and Kirillov.

######  Proposition A.7 ([40, Proposition 2.2]).

Viewing the Bender–Knuth involutions as operators on $\mathrm{GT}(\lambda,k)$
via the bijection $\Phi$, we have $\mathcal{BK}_{i}=\mathcal{F}_{k-i}$ for
$1\leq i\leq k-1$.

So $\rho$ and $\varepsilon$ can be described in terms of piecewise-linear
dynamics on $\mathrm{GT}(\lambda,k)$.

Finally, let us concentrate on the rectangular case and the correspondence
with plane partitions. So suppose that $\lambda=m^{a}$, and let us take
$k=a+b$ to match our indexing of plane partitions. Consider what a Gelfand-
Tsetlin pattern $\pi\in\mathrm{GT}(m^{a},a+b)$ looks like. In the upper-left,
$\pi$ has a length $a$ triangle of entries which must all be $m$’s; in the
lower-right, $\pi$ has a length $b$ triangle of entries which must all be
$0$’s; and the other entries in $\pi$, whose values are not forced, form an
$a\times b$ rectangle. For example, with $a=3$, $b=2$, and $m=5$, we have

$\pi=\begin{matrix}5&5&5&*&*\\\ &5&5&*&*\\\ &&5&*&*\\\ &&&0&0\\\
&&&&0\end{matrix}$

where the asterisks denote the entries whose values are not forced. What
condition is placed on these asterisk entries? Well, they certainly must be
weakly decreasing in rows and columns, and they must all be integers between
$0$ and $m$. In other words, they exactly form a plane partition in
$\mathrm{PP}^{m}(a\times b)$. And clearly any such plane partition can be
placed in the asterisk entries.

In this way we obtain a bijection $\Psi\colon\mathrm{PP}^{m}(a\times
b)\to\mathrm{SSYT}(m^{a},a+b)$: we extend a plane partition
$\pi\in\mathrm{PP}^{m}(a\times b)$ to a Gelfand-Tsetlin pattern in
$\mathrm{GT}(m^{a},a+b)$ by appending a length $a$ triangle of $m$’s to its
left and a length $b$ triangle of $0$’s below it; and then we map that
Gelfand-Tsetlin pattern to a semistandard tableau in
$\mathrm{SSYT}(m^{a},a+b)$ via $\Phi$. This is depicted in the following
example for a plane partition $\pi\in\mathrm{PP}^{4}(2\times 2)$:

$\pi=\ytableau 2&2\\\ 10\;\;\mapsto\;\;\begin{matrix}4&4&2&2\\\ &4&1&0\\\
&&0&0\\\ &&&0\\\ \end{matrix}\;\;\mapsto\;\;\ytableau 1&133\\\ 3444=\Psi(\pi)$

This construction is discussed, very briefly, in [16, pp. 516-517].

######  Remark A.8.

There is a very naive way to obtain a semistandard Young tableau of
rectangular shape from a plane partition $\pi\in\mathrm{PP}^{m}(a\times b)$:
rotate $\pi$ $180^{\circ}$, and then add $i$ to all entries in the $i$th row.
The bijection $\Psi$ is not this naive procedure. Indeed, this naive procedure
produces a tableau in $\mathrm{SSYT}(b^{a},m+a)$, which is not the same set of
tableau that $\Psi$ maps into. $\blacksquare$

Let us describe another way to view the bijection $\Psi$, which is also
useful. We start with the case $m=1$. Note that a single column tableau
$T\in\mathrm{SSYT}(1^{a},a+b)$ is exactly the same as a subset
$I\subseteq\\{1,2,\ldots,a+b\\}$ of size $a$. So in this case $\Psi$ is some
bijection $\Psi\colon\mathrm{PP}^{1}(a\times
b)\xrightarrow{\sim}\\{I\subseteq\\{1,\ldots,a+b\\}\textrm{ of size $a$}\\}$.
In fact, this bijection is a correspondence between Young diagrams that fit in
an $a\times b$ rectangle and size $a$ subsets of $\\{1,2,\ldots,a+b\\}$ which
is ubiquitous in algebraic combinatorics, as we now explain. Let
$\pi\in\mathrm{PP}^{1}(a\times b)$. The boundary between the entries of $1$
and $0$ in $\pi$ determines a lattice path of down and left steps from the
upper-right corner of the $a\times b$ grid to the lower-left corner. Writing
this lattice path as a word in the alphabet $\\{D,L\\}$ with $a$ $D$’s and $b$
$L$’s (where $D$’s correspond to down steps and $L$’s to left steps), the
subset $\Psi(\pi)\subseteq\\{1,2,\ldots,a+b\\}$ is the set of positions of
$D$’s in this word. This is depicted in the following example with $a=4$ and
$b=5$:

$\pi=$ 1 & 1 1 1 0
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
$\mapsto\textrm{L\text@underline{D}LL\text@underline{DD}LL\text@underline{D}}\mapsto\\{2,5,6,9\\}=$
2
5
6
9 $=\Psi(\pi)$

Now we extend the construction from the previous paragraph to greater values
of $m$. For $\pi,\pi^{\prime}\in\mathrm{PP}^{m}(a\times b)$ we write
$\pi\geq\pi^{\prime}$ to mean that $\pi$ is entrywise greater than or equal to
$\pi^{\prime}$; and we define
$\pi+\pi^{\prime}\in\mathrm{PP}^{m+m^{\prime}}(a\times b)$ for
$\pi\in\mathrm{PP}^{m}(a\times b)$,
$\pi^{\prime}\in\mathrm{PP}^{m^{\prime}}(a\times b)$ to be their entrywise
sum. Let $\pi\in\mathrm{PP}^{m}(a\times b)$. There are unique plane partitions
$\pi^{1},\pi^{2},\ldots,\pi^{m}\in\mathrm{PP}^{1}(a\times b)$ for which
$\pi=\pi^{1}+\pi^{2}+\cdots+\pi^{m}$ and
$\pi^{1}\geq\pi^{2}\geq\cdots\geq\pi^{m}$; explicitly, we have

$(\pi^{k})_{i,j}=\begin{cases}1&\textrm{ if $\pi_{i,j}\geq k$};\\\
0&\textrm{otherwise},\end{cases}$

for all $1\leq k\leq m$. Then $\Psi(\pi)\in\mathrm{SSYT}(m^{a},a+b)$ is the
tableau whose columns are the subsets
$\Psi(\pi^{1}),\Psi(\pi^{2}),\ldots,\Psi(\pi^{m})$ in order. This is easily
proven inductively: the condition $\pi^{m-1}\geq\pi^{m}$ means that placing
the column $\Psi(\pi^{m})$ to the right of the column $\Psi(\pi^{m-1})$ will
preserve the tableau’s semistandardness; conversely, appending the column
$\Psi(\pi^{m})$ changes the entries in the Gelfand-Tsetlin pattern of the
tableau in exactly the way that corresponds to adding $\pi^{m}$. This
description of $\Psi$ is depicted in the following example for a plane
partition $\pi\in\mathrm{PP}^{4}(2\times 2)$:

$\pi=$ 2 & 2
1 0 $=$ 1 & 1
1 0 $+$ 1 & 1
0 0 $+$ 0 & 0
0 0 $+$ 0 & 0
0 0  $\Psi(\pi)=$ 1
3 $+$ 1
4 $+$ 3
4 $+$ 3
4 $=$ 1 & 1 3 3
3 4 4 4

We end this section by describing how the operators $\mathrm{Pro}$,
$\mathrm{Co}$, and $\mathrm{Tr}$ on plane partitions defined in Section 1
behave when viewed as operators on semistandard tableaux via the bijection
$\Psi$. Unsurprisingly, $\mathrm{Pro}$ behaves as $\rho$ (thus justifying the
name promotion), while $\mathrm{Co}$ behaves as evacuation. In order to record
the behavior of transposition we need a little notation. So for
$T\in\mathrm{SSYT}(m^{n},2n)$ we define
$T^{\dagger}\in\mathrm{SSYT}(m^{n},2n)$ to be the tableau obtained from $T$ by
first replacing each entry by $2n+1$ minus that entry, and then replacing each
column $I$ by its set-theoretic complement $\\{1,2,\ldots,2n\\}\setminus I$.

######  Proposition A.9.

Via the bijection $\Psi\colon\mathrm{PP}^{m}(a\times
b)\to\mathrm{SSYT}(m^{a},a+b)$, view $\mathrm{Pro}$ and $\mathrm{Co}$, and, if
$a=b=n$, also $\mathrm{Tr}$, as operators on $\mathrm{SSYT}(m^{a},a+b)$. Then:

  * •

$\mathrm{Pro}(T)=\rho(T)$ for all $T\in\mathrm{SSYT}(m^{a},a+b)$;

  * •

$\mathrm{Co}(T)=\varepsilon(T)=\varepsilon^{*}(T)=T^{+}$ for all
$T\in\mathrm{SSYT}(m^{a},a+b)$;

  * •

(if $a=b=n$) $\mathrm{Tr}(T)=T^{\dagger}$ for all
$T\in\mathrm{SSYT}(m^{n},2n)$.

The first bulleted item is immediate from the original description of $\Psi$
in terms of Gelfand-Tsetlin patterns, together with the description of the
Bender–Knuth involutions as compositions of toggles which appears in
Proposition A.7 above.

The second and third bulleted items are easier to see from the alternate
description of $\Psi$. (Of course, with the second bulleted item we are
implicitly applying the folklore Proposition A.4.) It is easily checked that
the behaviors of $\mathrm{Co}$ and $\mathrm{Tr}$ are as claimed for single
column tableau. Furthermore, for $T\in\mathrm{SSYT}(m^{a},a+b)$, if the
columns of $T$ are $I_{1},\ldots,I_{m}$ then the columns of $T^{+}$ will be
$I_{m}^{+},\ldots,I_{1}^{+}$; and for $T\in\mathrm{SSYT}(m^{n},2n)$, if the
columns of $T$ are $I_{1},\ldots,I_{m}$ then the columns of $T^{\dagger}$ will
be $I_{1}^{\dagger},\ldots,I_{m}^{\dagger}$. Finally, for
$\pi,\pi^{\prime}\in\mathrm{PP}^{1}(a\times b)$ we have
$\pi\geq\pi^{\prime}\Leftrightarrow\mathrm{Co}(\pi^{\prime})\geq\mathrm{Co}(\pi)$;
and for $\pi,\pi^{\prime}\in\mathrm{PP}^{1}(n\times n)$ we have
$\pi\geq\pi^{\prime}\Leftrightarrow\mathrm{Tr}(\pi)\geq\mathrm{Tr}(\pi^{\prime})$.
These observations, together with the alternate description of $\Psi$, imply
the second and third bulleted items.

## References

  * [1] Omar Abuzzahab, Matthew Korson, Martin Li Man Chun, and Seth Meyer.  Cyclic and dihedral sieving phenomenon for plane partitions.  REU report, http://www-users.math.umn.edu/~reiner/REU/PlanePartitionReport.pdf, 2005\.
  * [2] Per Alexandersson, Svante Linusson, and Samu Potka.  The cyclic sieving phenomenon on circular Dyck paths.  Electron. J. Combin., 26(4):Paper 4.16, 32, 2019.
  * [3] George E. Andrews.  Plane partitions. II. The equivalence of the Bender-Knuth and MacMahon conjectures.  Pacific J. Math., 72(2):283–291, 1977.
  * [4] George E. Andrews.  Plane partitions. I. The MacMahon conjecture.  In Studies in foundations and combinatorics, volume 1 of Adv. in Math. Suppl. Stud., pages 131–150. Academic Press, New York-London, 1978\.
  * [5] Drew Armstrong, Christian Stump, and Hugh Thomas.  A uniform bijection between nonnesting and noncrossing partitions.  Trans. Amer. Math. Soc., 365(8):4121–4151, 2013.
  * [6] Hélène Barcelo, Victor Reiner, and Dennis Stanton.  Bimahonian distributions.  J. Lond. Math. Soc. (2), 77(3):627–646, 2008.
  * [7] Edward A. Bender and Donald E. Knuth.  Enumeration of plane partitions.  J. Combinatorial Theory Ser. A, 13:40–54, 1972.
  * [8] Arkady Berenstein and Andrei Zelevinsky.  Canonical bases for the quantum group of type $A_{r}$ and piecewise-linear combinatorics.  Duke Math. J., 82(3):473–502, 1996.
  * [9] Jonathan Bloom, Oliver Pechenik, and Dan Saracino.  Proofs and generalizations of a homomesy conjecture of Propp and Roby.  Discrete Math., 339(1):194–206, 2016.
  * [10] A. E. Brouwer and A. Schrijver.  On the period of an operator, defined on antichains.  Mathematisch Centrum, Amsterdam, 1974.  Mathematisch Centrum Afdeling Zuivere Wiskunde ZW 24/74.
  * [11] Jonathan Brundan.  Dual canonical bases and Kazhdan-Lusztig polynomials.  J. Algebra, 306(1):17–46, 2006.
  * [12] P. J. Cameron and D. G. Fon-Der-Flaass.  Orbits of antichains revisited.  European J. Combin., 16(6):545–554, 1995.
  * [13] Jie Du.  Canonical bases for irreducible representations of quantum ${\rm GL}_{n}$.  Bull. London Math. Soc., 24(4):325–334, 1992.
  * [14] Jie Du.  Canonical bases for irreducible representations of quantum ${\rm GL}_{n}$. II.  J. London Math. Soc. (2), 51(3):461–470, 1995.
  * [15] David Einstein and James Propp.  Combinatorial, piecewise-linear, and birational homomesy for products of two chains.  arXiv:1310.5294, 2013.
  * [16] David Einstein and James Propp.  Piecewise-linear and birational toggling.  In 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), Discrete Math. Theor. Comput. Sci. Proc., AT, pages 513–524. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2014.
  * [17] Vladimir V. Fock and Alexander B. Goncharov.  Cluster ensembles, quantization and the dilogarithm.  Ann. Sci. Éc. Norm. Supér. (4), 42(6):865–930, 2009.
  * [18] D. G. Fon-Der-Flaass.  Orbits of antichains in ranked posets.  European J. Combin., 14(1):17–22, 1993.
  * [19] Chris Fraser.  Braid group symmetries of Grassmannian cluster algebras.  Selecta Math. (N.S.), 26(2):Paper No. 17, 2020.
  * [20] Gabriel Frieden.  Affine type $A$ geometric crystal on the Grassmannian.  J. Combin. Theory Ser. A, 167:499–563, 2019.
  * [21] Jürgen Fuchs, Urmie Ray, and Christoph Schweigert.  Some automorphisms of generalized Kac-Moody algebras.  J. Algebra, 191(2):518–540, 1997.
  * [22] Jürgen Fuchs, Bert Schellekens, and Christoph Schweigert.  From Dynkin diagram symmetries to fixed point structures.  Comm. Math. Phys., 180(1):39–97, 1996.
  * [23] William Fulton and Joe Harris.  Representation theory, volume 129 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1991.  A first course, Readings in Mathematics.
  * [24] Pavel Galashin and Pavlo Pylyavskyy.  $R$-systems.  Selecta Math. (N.S.), 25(2):Art. 22, 63, 2019.
  * [25] Emden R. Gansner.  On the equality of two plane partition correspondences.  Discrete Math., 30(2):121–132, 1980.
  * [26] Alexander Garver, Rebecca Patrias, and Hugh Thomas.  Minuscule reverse plane partitions via quiver representations.  arXiv:1812.08345, 2018.
  * [27] Basil Gordon.  A proof of the Bender-Knuth conjecture.  Pacific J. Math., 108(1):99–113, 1983.
  * [28] Darij Grinberg and Tom Roby.  Iterative properties of birational rowmotion II: rectangles and triangles.  Electron. J. Combin., 22(3):Paper 3.40, 49, 2015.
  * [29] Darij Grinberg and Tom Roby.  Iterative properties of birational rowmotion I: generalities and skeletal posets.  Electron. J. Combin., 23(1):Paper 1.33, 40, 2016.
  * [30] I. Grojnowski and G. Lusztig.  A comparison of bases of quantized enveloping algebras.  In Linear algebraic groups and their representations (Los Angeles, CA, 1992), volume 153 of Contemp. Math., pages 11–19. Amer. Math. Soc., Providence, RI, 1993.
  * [31] Mark Gross, Paul Hacking, Sean Keel, and Maxim Kontsevich.  Canonical bases for cluster algebras.  J. Amer. Math. Soc., 31(2):497–608, 2018.
  * [32] Mark D. Haiman.  Dual equivalence with applications, including a conjecture of Proctor.  Discrete Math., 99(1-3):79–113, 1992.
  * [33] Sam Hopkins.  Minuscule doppelgängers, the coincidental down-degree expectations property, and rowmotion.  Experimental Mathematics, 2020.  Forthcoming; available online at https://doi.org/10.1080/10586458.2020.1731881.
  * [34] Jens Carsten Jantzen.  Darstellungen halbeinfacher algebraischer Gruppen und zugeordnete kontravariante Formen.  Bonn. Math. Schr., (67):v+124, 1973.
  * [35] Steven N. Karp.  Moment curves and cyclic symmetry for positive Grassmannians.  Bull. Lond. Math. Soc., 51(5):900–916, 2019.
  * [36] Rachel Karpman.  Total positivity for the Lagrangian Grassmannian.  Adv. in Appl. Math., 98:25–76, 2018.
  * [37] Rachel Karpman.  The purity conjecture in Type C.  arXiv:1907.08275, 2019.
  * [38] Rachel Karpman and Yi Su.  Combinatorics of symmetric plabic graphs.  J. Comb., 9(2):259–278, 2018.
  * [39] Masaki Kashiwara.  Global crystal bases of quantum groups.  Duke Math. J., 69(2):455–485, 1993.
  * [40] A. N. Kirillov and A. D. Berenstein.  Groups generated by involutions, Gel’fand-Tsetlin patterns, and combinatorics of Young tableaux.  Algebra i Analiz, 7(1):92–152, 1995.
  * [41] Harold Knight and Andrei Zelevinsky.  Representations of quivers of type $A$ and the multisegment duality.  Adv. Math., 117(2):273–293, 1996.
  * [42] C. Krattenthaler.  Plane partitions in the work of Richard Stanley and his school.  In The mathematical legacy of Richard P. Stanley, pages 231–261. Amer. Math. Soc., Providence, RI, 2016.
  * [43] Greg Kuperberg.  Self-complementary plane partitions by Proctor’s minuscule method.  European J. Combin., 15(6):545–553, 1994.
  * [44] Thomas Lam.  Cyclic Demazure modules and positroid varieties.  Electron. J. Combin., 26(2):P2.28, 20, 2019.
  * [45] Cristian Lenart.  On the combinatorics of crystal graphs. I. Lusztig’s involution.  Adv. Math., 211(1):204–243, 2007.
  * [46] G. Lusztig.  Canonical bases arising from quantized enveloping algebras.  J. Amer. Math. Soc., 3(2):447–498, 1990.
  * [47] George Lusztig.  Introduction to quantum groups, volume 110 of Progress in Mathematics.  Birkhäuser Boston, Inc., Boston, MA, 1993.
  * [48] I. G. Macdonald.  Symmetric functions and Hall polynomials.  The Clarendon Press, Oxford University Press, New York, 1979.  Oxford Mathematical Monographs.
  * [49] Percy A. MacMahon.  Combinatory analysis. Vol. I, II (bound in one volume).  Dover Phoenix Editions. Dover Publications, Inc., Mineola, NY, 2004.  Reprint of _An introduction to combinatory analysis_ (1920) and _Combinatory analysis. Vol. I, II_ (1915, 1916).
  * [50] Percy Alexander MacMahon.  Partitions of numbers whose graphs possess symmetry.  Trans. Cambridge Philos. Soc., 17:149–170, 1899.
  * [51] Gregg Musiker and Tom Roby.  Paths to understanding birational rowmotion on products of two chains.  Algebr. Comb., 2(2):275–304, 2019.
  * [52] Dmitri I. Panyushev.  On orbits of antichains of positive roots.  European J. Combin., 30(2):586–594, 2009.
  * [53] Alexander Postnikov.  Total positivity, Grassmannians, and networks.  arXiv:math/0609764, 2006.
  * [54] Robert A. Proctor.  Shifted plane partitions of trapezoidal shape.  Proc. Amer. Math. Soc., 89(3):553–559, 1983.
  * [55] Robert A. Proctor.  Bruhat lattices, plane partition generating functions, and minuscule representations.  European J. Combin., 5(4):331–350, 1984.
  * [56] Robert A. Proctor.  New symmetric plane partition identities from invariant theory work of De Concini and Procesi.  European J. Combin., 11(3):289–300, 1990.
  * [57] Sujit Rao and Joe Suk.  Dihedral sieving phenomena.  Discrete Math., 343(6):111849, 2020.
  * [58] V. Reiner, D. Stanton, and D. White.  The cyclic sieving phenomenon.  J. Combin. Theory Ser. A, 108(1):17–50, 2004.
  * [59] Victor Reiner, Dennis Stanton, and Dennis White.  What is …cyclic sieving?  Notices Amer. Math. Soc., 61(2):169–171, 2014.
  * [60] Brendon Rhoades.  Cyclic sieving, promotion, and representation theory.  J. Combin. Theory Ser. A, 117(1):38–76, 2010.
  * [61] Brendon Rhoades and Mark Skandera.  Kazhdan-Lusztig immanants and products of matrix minors.  J. Algebra, 304(2):793–811, 2006.
  * [62] Brendon Rhoades and Mark Skandera.  Kazhdan-Lusztig immanants and products of matrix minors. II.  Linear Multilinear Algebra, 58(1-2):137–150, 2010.
  * [63] K. Rietsch and L. Williams.  Newton-Okounkov bodies, cluster duality, and mirror symmetry for Grassmannians.  Duke Math. J., 168(18):3437–3527, 2019.
  * [64] Tom Roby.  Dynamical algebraic combinatorics and the homomesy phenomenon.  In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pages 619–652. Springer, [Cham], 2016.
  * [65] David B. Rush.  Restriction of global bases and Rhoades’s theorem.  arXiv:2001.00743, 2020.
  * [66] David B. Rush and XiaoLin Shi.  On orbits of order ideals of minuscule posets.  J. Algebraic Combin., 37(3):545–569, 2013.
  * [67] Bruce E. Sagan.  The cyclic sieving phenomenon: a survey.  In Surveys in combinatorics 2011, volume 392 of London Math. Soc. Lecture Note Ser., pages 183–233. Cambridge Univ. Press, Cambridge, 2011.
  * [68] The Sage-Combinat community.  Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2019.  http://combinat.sagemath.org.
  * [69] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 8.4), 2019.  http://www.sagemath.org.
  * [70] M. P. Schützenberger.  Quelques remarques sur une construction de Schensted.  Math. Scand., 12:117--128, 1963.
  * [71] M. P. Schützenberger.  Promotion des morphismes d’ensembles ordonnés.  Discrete Math., 2:73--94, 1972.
  * [72] M.-P. Schützenberger.  La correspondance de Robinson.  In Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976), pages 59--113. Lecture Notes in Math., Vol. 579. Springer, Berlin, 1977.
  * [73] J.S. Scott.  Grassmannians and cluster algebras.  Proc. London Math. Soc. (3), 92(2):345--380, 2006.
  * [74] C. S. Seshadri.  Introduction to the theory of standard monomials, volume 46 of Texts and Readings in Mathematics.  Hindustan Book Agency, New Delhi, second edition, 2014.
  * [75] Jeffrey T. Sheats.  A symplectic jeu de taquin bijection between the tableaux of King and of De Concini.  Trans. Amer. Math. Soc., 351(9):3569--3607, 1999.
  * [76] Linhui Shen and Daping Weng.  Cyclic sieving and cluster duality for Grassmannian.  arXiv:1803.06901, 2018.
  * [77] Mark Skandera.  On the dual canonical and Kazhdan-Lusztig bases and 3412-, 4231-avoiding permutations.  J. Pure Appl. Algebra, 212(5):1086--1104, 2008.
  * [78] Richard P. Stanley.  Symmetries of plane partitions.  J. Combin. Theory Ser. A, 43(1):103--113, 1986.
  * [79] Richard P. Stanley.  Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1999.
  * [80] Richard P. Stanley.  Promotion and evacuation.  Electron. J. Combin., 16(2, Special volume in honor of Anders Björner):Research Paper 9, 24, 2009.
  * [81] Richard P. Stanley.  Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, second edition, 2012.
  * [82] John R. Stembridge.  On minuscule representations, plane partitions and involutions in complex Lie groups.  Duke Math. J., 73(2):469--490, 1994.
  * [83] John R. Stembridge.  Some hidden relations involving the ten symmetry classes of plane partitions.  J. Combin. Theory Ser. A, 68(2):372--409, 1994.
  * [84] John R. Stembridge.  Canonical bases and self-evacuating tableaux.  Duke Math. J., 82(3):585--606, 1996.
  * [85] Jessica Striker and Nathan Williams.  Promotion and rowmotion.  European J. Combin., 33(8):1919--1942, 2012.