\documentclass[12pt,final,notitlepage,onecolumn,german]{article}%
\usepackage[all,cmtip]{xy}
\usepackage{lscape}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{color}
\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
%TCIDATA{Created=Sat Mar 27 17:33:36 2004}
%TCIDATA{LastRevised=Saturday, November 16, 2013 22:12:54}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcommand{\id}{\operatorname*{id}}
\definecolor{violet}{RGB}{143,0,255}
\definecolor{forestgreen}{RGB}{34, 100, 34}
\voffset=-1.5cm
\hoffset=-2cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\begin{document}
\begin{center}
\textbf{Combinatorial Markov chains on linear extensions}
\textit{Arvind Ayyer, Steven Klee, Anne Schilling}
version 3, arXiv:1205.7074v3
\texttt{\href{http://arxiv.org/abs/1205.7074v3}{\texttt{http://arxiv.org/abs/1205.7074v3}%
}}
\textbf{Errata and comments - I}
\bigskip
\end{center}
\begin{itemize}
\item \textbf{Page 3, \S 2.1:} In "are labeled by integers in $\left[
n\right] :=\left\{ 1,2,...,n\right\} $", replace "integers" by "the
integers", since otherwise it sounds as if one has the freedom to skip some of
the integers or use them twice.
\item \textbf{Page 3, \S 2.1:} In my opinion, the idea to label the vertices
of $P$ by the integers in $\left[ n\right] $ is a fundamentally bad one. In
the few parts of the paper where it is used (like Lemma 5.5 and all statements
about poset derangements), it can be introduced locally. In all the rest of
the paper, it is fully expendable and only confuses the reader by giving the
integers $1,2,...,n$ a double role (once as the labels of the vertices of $P$,
and again as the ordinal numbers of these vertices in a linear extension).
Here are two examples of places where this leads to ambiguity:
-- In part (2) of the definition of promotion on page 4, does "labels covering
$i$" mean "labels covering the vertex $i$" or "labels covering the vertex
labelled $i$" ? I know it means the latter, but this is not really obvious
from the wording. If you wouldn't label the vertices of $P$ by $1,2,...,n$ by
default, there would only be one possible meaning (namely, the correct one).
-- In the definition of $P_{j}$, I think you got yourself confused, because
the definition that you give does not make (2.3) valid (I think). See below
for how to correct this.
As I said, in my opinion there is no reason to assume globally that the
elements of $P$ are labeled by the integers in $\left[ n\right] $. I think
the paper would become way more readable if you remove this assumption. Of
course, with this change, linear extensions of $P$ are no longer elements of
$S_{n}$ but are now bijections $\left[ n\right] \rightarrow P$%
\ \ \ \ \footnote{But this is okay, since you never multiply or invert them.
And if you ask me, it is a good thing as it saves me the hassle of remembering
whether the label of a vertex $i$ is $\pi_{i}$ or $\pi_{i}^{-1}$: when the
vertices of $P$ are not identified with integers, only one of these two
possibilities makes any sense.}. "One-line notation" for elements $\pi$ of
$S_{n}$ now means the obvious thing (just writing the images of $1,2,...,n$
under $\pi$ in one line). The maps $\partial_{j}$ and $\tau_{j}$ are still
indexed by elements of $\left[ n\right] $, but the maps $\widehat{\partial
}_{j}$ are now indexed by elements of $P$ (I believe this makes the difference
between them clearer). The uniform transposition and the uniform promotion
Markov chains still have their edge weights defined in the polynomial ring
$\mathbb{Q}\left[ x_{1},x_{2},...,x_{n}\right] $, but the transposition and
promotion Markov chains now have their edge weights defined in the polynomial
ring $\mathbb{Q}\left[ x_{p}\ \mid\ p\in P\right] $. In Theorem 4.5, the
product $\prod\limits_{i=1}^{n}\dfrac{x_{1}+\cdots+x_{i}}{x_{\pi_{1}}%
+\cdots+x_{\pi_{i}}}$ no longer makes sense because $x_{1}+\cdots+x_{i}$ is
not defined; but you can just replace it by the simpler product $\prod
\limits_{i=1}^{n}\dfrac{1}{x_{\pi_{1}}+\cdots+x_{\pi_{i}}}$, which differs
from it just by a factor independent on $\pi$ (of course, you lose the
$w\left( e\right) =1$ property this way, but this is expected since you
don't have a distinguished linear extension $e$ anymore). Funnily, this
simplifies both the proof of Theorem 4.5 (because the normalization you use
there is precisely $\prod\limits_{i=1}^{n}\dfrac{1}{x_{\pi_{1}}+\cdots
+x_{\pi_{i}}}$) and the formulation of Theorem 5.1 (because now (5.1) gets
replaced by the simple equality $Z_{P}=\prod\limits_{i\in P}x_{\preceq i}$).
Also, Theorem 4.7 needs to be adjusted (terms like $x_{\pi_{i}}^{i-\pi_{i}}$
make no sense anymore no matter if $i$ is an element of $P$ or of $\left[
n\right] $), but again this adjustment actually makes it simpler (you can
replace (4.7) by $w\left( \pi\right) =\prod\limits_{i=1}^{n}x_{\pi_{i}}^{i}%
$, forgetting about $w\left( e\right) =1$ since there is no $e$ anymore).
\item \textbf{Page 4:} You define $P_{j}$ as "the natural (induced) subposet
of $P$ consisting of elements $k$ such that $j\preceq k$". First of all, I
don't think this is the definition you want to make. In order to make (2.3)
true, it should be "the natural (induced) subposet of $P$ consisting of
elements $k$ such that the element of $P$ labelled $j$ in $\pi$ is $\preceq
k$" (note that this depends on the choice of a linear extension $\pi$ of $P$).
But anyway, I don't see why you define $P_{j}$ at all. You only ever use
$P_{j}$ in the definition of extended promotion $\partial_{j}$, where it is
almost a red hering. I think that extended promotion is best defined along
these lines: "Given a linear extension $\pi=\pi_{1}\pi_{2}...\pi_{n}$ of $P$,
apply promotion to the linear extension $\pi_{j}\pi_{j+1}...\pi_{n}$ of the
subposet $\left\{ \pi_{j},\pi_{j+1},...,\pi_{n}\right\} $ of $P$. Denoting
the resulting linear extension by $\sigma_{j}\sigma_{j+1}...\sigma_{n}$, we
then see that $\pi_{1}\pi_{2}...\pi_{j-1}\sigma_{j}\sigma_{j+1}...\sigma_{n}$
is a new linear extension of $P$, which we denote by $\pi\partial_{j}$."
\item \textbf{Page 4, Example 2.1:} In my opinion, "namely $3$ is in position
$5$ in $\pi^{\prime}$ " is a bit ambiguous, because $\pi^{\prime}$ can mean
both a labelling of vertices of $P$ and a word. It is best to say "namely $3$
is in position $5$ in the word $\pi^{\prime}$ ".
\item \textbf{Page 5:} I know that you refer to Stanley's papers for
notations, but I am not sure if every reader will follow the reference. For
those who don't, it would help to point out that all maps of the form
$\tau_{j}$, $\partial_{j}$, $\widehat{\partial}_{j}$ and $\partial$ act on the
right, and consequently their composition (as in (2.3)) is to be understood as
"perform the leftmost map first, then the next one etc.".
(It probably wouldn't harm to have an example for $\partial_{j}$, too.)
\item \textbf{Page 6, Figure 2:} Replace "$\partial\pi$" by "$\pi\partial$"
(one of you apparently doesn't like Stanley's notations very much -- my sympathies).
\item \textbf{Page 6, Lemma 2.3:} "each operator" $\rightarrow$ "the operator"
(since $j$ is already fixed).
\item \textbf{Page 7:} Remove the comma before "define a directed graph".
\item \textbf{Page 12, proof of Proposition 4.1:} I think the words "and label
$1$ is at position $k$ of $P$" can be just removed, since you never use $k$.
\item \textbf{Page 12, proof of Proposition 4.1:} At the very end, I believe
"from Lemma 2.3" should be "from (2.3)".
\item \textbf{Page 15, proof of Theorem 4.5:} Replace "hence (4.3) yields" by
"hence the right hand side of (4.3) becomes".
\item \textbf{Page 15, proof of Theorem 4.5:} Remove the word "set" from "In
the first case, set $\widetilde{\pi}=\pi$".
\item \textbf{Page 16, \S 5.1:} This is one of my trademark nitpicks: Add
"disjoint" before "union" in "A \textbf{rooted forest} is a union of rooted trees."
\item \textbf{Page 17, proof of Theorem 5.1:} Replace "of the sums over $i$"
by "of the addends of the sum over $i$".
\item \textbf{Page 19, Lemma 5.5:} It might be useful to point out explicitly
that $P$ is to be labeled consecutively within chains (as in Theorem 5.3).
\item \textbf{Page 19, proof of Lemma 5.5:} In "define $N_{i}=n_{1}%
+\cdots+n_{i-1}$ for all $2\leq i\leq k$", replace the "$k$" by "$k+1$" (since
you do use $N_{k+1}$ in the very next sentence).
\item \textbf{Page 21, proof of Lemma 5.5:} Replace "$w_{N_{i}+j}^{\prime}$"
by "$w_{N_{i}^{\prime}+j}^{\prime}$" on the first line of this page.
\item \textbf{Page 23, Lemma 6.5:} It might help to point out that
"reordering" means "reordering in such a way that the result is a linear extension".
\item \textbf{Page 23, proof of Lemma 6.5:} I think the "$\widehat{\partial
}_{\pi_{i}^{-1}}$" and the "$\widehat{\partial}_{k}$" on the second line of
this proof should be "$\partial_{\pi_{i}^{-1}}$" and "$\partial_{k}$", respectively.
\item \textbf{Page 23, Example 6.6:} The "12345" at the very end should be in
mathmode, not in textmode.
\item \textbf{Page 24, proof of Lemma 6.7:} You write: "we hence must have
$\widehat{\partial}_{\alpha_{j}}x=x$ for all $1\leq j\leq m$". Why?
\item \textbf{Page 24, proof of Lemma 6.7:} I don't see why "we have
$\operatorname*{Rfactor}\left( x\right) \subsetneq\operatorname*{Rfactor}%
\left( x\widehat{\partial}_{\alpha_{j}}\right) $" either...
\item Have you ever tried considering eigenvalues of the promotion and
transposition chains for a Young diagram poset? I think an analogue of Theorem
5.2 has chances to hold in this case, and would be a very interesting result
if it does.
Let me explain what I mean by "analogue" first. It is not true that
$\det\left( M-\lambda\right) $ factors into linear terms if $P$ is the
$\left[ 2\right] \times\left[ 2\right] $-rectangle poset and $M$ is the
transition matrix of the promotion graph of Section 3.4. Hence, Theorem 5.2
doesn't directly hold for Young tableaux. But I conjecture the following:
\textbf{Conjecture.} Let $\cdots,y_{-2},y_{-1},y_{0},y_{1},y_{2},\cdots$ be a
set of commuting indeterminates. If $P$ is the northwest-oriented poset of a
Young diagram $\lambda$ (that is, the poset whose elements are the cells of
$\lambda$ and whose order is given by $\left( c\leq d\right)
\Longleftrightarrow\left( d\text{ lies weakly north and weakly west of
}c\right) $), then $\det\left( \widetilde{M}-\lambda\right) $ factors into
linear terms, where $\widetilde{M}$ is the result of substituting
$y_{\operatorname*{cont}c}$ for each $x_{c}$ in the transition matrix of the
promotion graph of Section 3.4. Here, $\operatorname*{cont}p$ denotes the
content of the cell $p$ (that is, its row coordinate minus its column
coordinate). Note that (as explained above) I am not identifying the elements
of $P$ with positive integers, so the variables $x_{c}$ in the transition
matrix of the promotion graph are indexed by cells of the Young diagram; thus,
substituting $y_{\operatorname*{cont}c}$ for $x_{c}$ makes sense.
I have done some computations in Sage, checking that this conjecture holds
whenever $\left\vert \lambda\right\vert \leq6$. For example, when
$\lambda=\left( 3,3\right) $, the eigenvalues are $y_{0},0,y_{0}+y_{1}%
,y_{0}+y_{-1},2y_{0}+2y_{1}+y_{2}+y_{-1}$ if this tells you anything. There
are counterexamples if $\lambda$ is allowed to be a skew partition (for
$\lambda=\left( 3,3\right) \diagup\left( 2\right) $, for instance). I can
send you the code, but it is very hacky (the nice part is in patch \#15428)
and I don't have any hopes of running it for $\left\vert \lambda\right\vert
=7$ in reasonable time (multivariate polynomial factorization in high degrees
isn't fun). It is not true that specializing one $y_{i}$ to $1$ and all the
other $y_{i}$'s to $0$ yields matrices which pairwise commute, so at least
from this viewpoint the conjecture is not trivial.
The idea that a polynomial identity depending on a forest can be made into a
polynomial identity depending on a Young diagram by substituting
$y_{\operatorname*{cont}c}$ for $x_{c}$ might appear mysterious at first
sight, and I think it \textbf{is} mysterious. All I can say is that I have got
this idea from a hook-length formula by Alex Postnikov which is very similar
to your Theorem 5.1 in the same way as my above conjecture is to your Theorem
5.2. In some more detail:
Theorem 5.1 in your paper can be rewritten as follows: If $P$ is a rooted
forest, and $x_{p}$ is a variable for every $p\in P$ (these variables should
all commute), then%
\[
\sum\limits_{\pi\in\mathcal{L}\left( P\right) }\prod\limits_{i=1}%
^{\left\vert P\right\vert }\dfrac{1}{x_{\pi_{1}}+x_{\pi_{2}}+\cdots+x_{\pi
_{i}}}=\prod\limits_{p\in P}\dfrac{1}{\sum\limits_{q\in P;\ q\preceq p}x_{q}}.
\]
This formula can be regarded as a kind of hook-length formula if you consider
$\left\{ q\in P\ \mid\ q\preceq p\right\} $ to be a "hook" of $p$ in the
forest (and setting all $x_{p}$ to $1$ actually yields the well-known
hook-length formula for forests). There is a little-known analogue of this
formula which was told to me by Alexander Postnikov: If $\lambda$ is a Young
diagram (not skew this time) and $P$ is the northwest-oriented poset of
$\lambda$, then%
\[
\sum\limits_{\pi\in\mathcal{L}\left( P\right) }\prod\limits_{i=1}%
^{\left\vert P\right\vert }\dfrac{1}{y_{\operatorname*{cont}\left( \pi
_{1}\right) }+y_{\operatorname*{cont}\left( \pi_{2}\right) }+\cdots
+y_{\operatorname*{cont}\left( \pi_{i}\right) }}=\prod\limits_{p\in P}%
\dfrac{1}{\sum\limits_{q\in\operatorname*{hook}p}y_{\operatorname*{cont}q}}.
\]
Postnikov proved this using polyhedral combinatorics (I am trying to convince
him to write up his proof); it specializes to the classical hook-length
formula again by specializing all $y_{i}$ to $1$. It seems, however, that none
of the proofs of the classical hook-length formula easily extend to this
generalization (as far as I can tell). I have been told that this formula
follows from Corollary 7.2 in Kento Nakada, \textit{Colored hook formula for a
generalized Young diagram}, Osaka J. Math. 45 (2008), but I don't understand
root systems well enough to tell whether it does or just looks similar.
I don't know in how far $\mathcal{R}$-trivial monoids (or maybe a variant of
them where $\mathcal{R}$-classes are somehow bounded rather than having
cardinality $1$) are useful to handle the conjecture. But there are weird
things going on. The conjecture involves a matrix labelled by linear
extensions of a Young diagram poset (i. e., by standard Young tableaux) whose
eigenvalues are conjectured to be integer combinations of $y_{i}$'s. This is
reminiscent of the Reiner-Saliola-Welker conjecture (Conjecture 1.2 in
arXiv:1102.2460v2) which involves certain operators on $\mathbb{Q}\left[
S_{n}\right] $ which are suspected to have integer eigenvalues, but these
operators break down into operators acting on every irreducible representation
of $S_{n}$, and this means matrices labelled by standard Young tableaux. Of
course, there is no guarantee of a connection, but I suspect at least some of
the same methods can be used.
\end{itemize}
\end{document}