\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Wednesday, February 22, 2017 04:28:37}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{proof2}[1][]
{\begin{proof}[#1]}{\end{proof}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand{\NN}{\mathbb{N}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{Errata to ``Algebraic Combinatorics''}
\ohead{\today}
\begin{document}
\begin{center}
\textbf{Algebraic Combinatorics: Walks, Trees, Tableaux, and
More\footnote{alternative title: \textbf{Topics in Algebraic Combinatorics}}}
\textit{Richard P. Stanley}
Springer 2013
\url{http://www-math.mit.edu/~rstan/algcomb/}
---------------------------------------------------------------------------------------
\textbf{List of additional errata and questions}
Darij Grinberg,
%TCIMACRO{\TeXButton{TeX field}{\today}}%
%BeginExpansion
\today
%EndExpansion
\bigskip
\end{center}
I shall give two page numbers for each of the following comments: The first
page number refers to the page in the published version of the book
(\textquotedblleft Algebraic Combinatorics: Walks, Trees, Tableaux, and
More\textquotedblright, Springer, 2013), whereas the second page number refers
to the page in the online draft of the book (\textquotedblleft Topics in
Algebraic Combinatorics\textquotedblright, version of 1 February 2013, \url{http://www-math.mit.edu/~rstan/algcomb/algcomb.pdf}).
\begin{itemize}
\item \textbf{page 22 in the published version (= page 34 in the online
draft), proof of Theorem 3.2:} You are using the word \textquotedblleft
connected\textquotedblright\ here, but you don't define the notion of a
\textquotedblleft connected graph\textquotedblright\ until Chapter 9. It makes
sense to move the definition of \textquotedblleft connected
graph\textquotedblright\ to the beginning of Chapter 3 (if not earlier).
The definition of \textquotedblleft connected graph\textquotedblright\ in
Chapter 9 is also wrong on a little technical issue: It should require the
graph to have at least one vertex. (Allowing the graph with $0$ vertices to be
connected would break results such as Corollary 9.10 and the notion of
\textquotedblleft connected component\textquotedblright.)
Similarly, Proposition 9.1 should require $p$ to be $\geq1$, since otherwise
the graph with $0$ vertices would satisfy condition (d) but not condition (c).
\item \textbf{page 151 in the published version (= page 189 in the online
draft):} You have not defined what a \textquotedblleft connected
digraph\textquotedblright\ is. This is a tricky point that should not be left
to the reader, since there are two reasonable options:
\begin{itemize}
\item A digraph $D=\left( V,E,\varphi\right) $ is said to be
\textit{strongly connected} if and only if $V$ is nonempty and for every two
vertices $u\in V$ and $v\in V$, there exists at least one walk from $u$ to $v$
in $D$.
\item A digraph $D=\left( V,E,\varphi\right) $ is said to be \textit{weakly
connected} if and only if the undirected graph obtained from $D$ by
\textquotedblleft forgetting the arrows\textquotedblright\ (i.e., replacing
each edge from $u\in V$ to $v\in V$ by an undirected edge connecting $u$ with
$v$) is connected (as an undirected graph).
\end{itemize}
I suspect that you want the word \textquotedblleft connected\textquotedblright%
\ (when speaking of a directed graph) to mean \textquotedblleft weakly
connected\textquotedblright.
\item \textbf{page 151 in the published version (= page 189 in the online
draft):} After \textquotedblleft We then call $u$ the \textit{initial vertex}
and $v$ the \textit{final vertex} of $e$\textquotedblright, add
\textquotedblleft(and denote them by $\operatorname*{init}\left( e\right) $
and $\operatorname*{fin}\left( e\right) $, respectively)\textquotedblright.
\item \textbf{page 152 in the published version (= page 191 in the online
draft):} You write: \textquotedblleft An \textit{oriented tree} with root $v$
is a (finite) digraph $T$ with $v$ as one of its vertices, such that there is
a unique directed path from any vertex $u$ to $v$\textquotedblright.
Here, the word \textquotedblleft path\textquotedblright\ should be replaced by
\textquotedblleft walk\textquotedblright. (Otherwise, the digraph $%
%TCIMACRO{\TeXButton{x}{\xymatrix{
%1 \ar@/^/[r] & 2 \ar@/^/[l] \ar[r] & 3
%}}}%
%BeginExpansion
\xymatrix{
1 \ar@/^/[r] & 2 \ar@/^/[l] \ar[r] & 3
}%
%EndExpansion
$ would count as an oriented tree with root $3$, which is definitely unintended.)
\item \textbf{page 152 in the published version (= page 191 in the online
draft):} After \textquotedblleft such that (a) $\operatorname*{init}\left(
e_{1}\right) =u$, (b) $\operatorname*{fin}\left( e_{r}\right) =v$, and (c)
$\operatorname*{fin}\left( e_{i}\right) =\operatorname*{init}\left(
e_{i+1}\right) $ for $1\leq i\leq r-1$.\textquotedblright, add
\textquotedblleft(All three of these conditions are understood to be vacuously
true if the sequence $e_{1},\ldots,e_{r}$ is empty.)\textquotedblright.
\item \textbf{page 152 in the published version (= page 191 in the online
draft):} Somewhere before Theorem 10.2, it is probably worthwhile to say
explicitly that \textquotedblleft From now on, \textquotedblleft oriented
subtree of $D$\textquotedblright\ will always mean \textquotedblleft
subdigraph of $D$ that is an oriented tree with vertex set $V$%
\textquotedblright.\textquotedblright. Just putting the word \textquotedblleft
spanning\textquotedblright\ in parentheses in Theorem 10.2 might not be very clear.
\item \textbf{page 153 in the published version (= page 191 in the online
draft), proof of Theorem 10.2:} In the first line of the proof, after
\textquotedblleft be an Eulerian tour $\mathcal{E}$ in $D$\textquotedblright,
add \textquotedblleft beginning with the edge $e$\textquotedblright. (If it
was just some Eulerian tour, then there would be no guarantee that $e\left(
u\right) $ is defined for all $u\neq v$, since there would be no guarantee
that the tour would end at $u$.)
\item \textbf{page 153 in the published version (= page 192 in the online
draft), proof of Theorem 10.2:} In item (c) in the proof of Claim \#1, you
write: \textquotedblleft Thus when we enter $u$ \textit{via} $f$, we must exit
$u$. We can't exit $u$ \textit{via }$f^{\prime}$ since $f$ occurs after
$f^{\prime}$ in $\mathcal{E}$. Hence $f^{\prime}$ is not the last exit from
$u$, contradicting the definition of $T$.\textquotedblright
I am a bit confused by this argument, and I would find the following clearer
instead: \textquotedblleft The edge $f^{\prime}$ is an edge of $T$; hence, it
is the last exit from $u$ in the Eulerian tour $\mathcal{E}$ (by the
definition of $T$). But the edge $f$ occurs after all the other edges of $C$
in the Eulerian tour $\mathcal{E}$. In particular, $f$ occurs after the edge
$f^{\prime}$, which is the last exit from $u$. Hence, the Eulerian tour
$\mathcal{E}$ cannot exit $u$ after $f$. Hence, $u=v$, which contradicts
$u\neq v$.\textquotedblright.
\item \textbf{page 155 in the published version (= page 193 in the online
draft), proof of Theorem 10.4:} Your use of the induction hypothesis is
slightly illegitimate, since you only stated Theorem 10.4 for connected
digraphs, but either of the digraphs $D_{1}$ and $D_{2}$ (or even both of
them) can fail to be connected. Maybe the best way to fill in this hole is to
extend Theorem 10.4 to arbitrary (not necessarily connected) digraphs having
at least one vertex. If I am not mistaken, this requires no other changes to
the statement of Theorem 10.4. The proof, however, will need some extra
considerations. Namely, the case when $D$ is not connected needs to be treated
separately\footnote{This case is not hard to treat:
\par
Let $\underline{D}$ be the undirected graph obtained from $D$ by
\textquotedblleft forgetting the arrows\textquotedblright. Let $S$ be the set
of all vertices of $D$ from which there exists no walk to $v_{p}$ in the
undirected graph $\underline{D}$. Clearly, $v_{p}\notin S$. Let $\mathbf{s}$
be the column vector of size $p-1$ whose $i$-th coordinate (for each
$i\in\left\{ 1,2,\ldots,p-1\right\} $) is $%
\begin{cases}
1, & \text{if }i\in S;\\
0, & \text{if }i\notin S
\end{cases}
$. It is easy to see that $\mathbf{L}_{0}\mathbf{s}=0$, so that $\mathbf{s}%
\in\operatorname*{Ker}\left( \mathbf{L}_{0}\right) $.
\par
Now, Assume that $D$ is not connected. Then, $S\neq\varnothing$. Hence,
$\mathbf{s}\neq0$. Therefore, $\operatorname*{Ker}\left( \mathbf{L}%
_{0}\right) \neq0$ (since $\mathbf{s}\in\operatorname*{Ker}\left(
\mathbf{L}_{0}\right) $). Consequently, $\det\left( \mathbf{L}_{0}\right)
=0$. Comparing this with $\tau\left( D,v_{p}\right) =0$ (which is clear
because of the non-connectedness of $D$), we obtain $\det\left(
\mathbf{L}_{0}\right) =\tau\left( D,v_{p}\right) $. Thus, Theorem 10.4 is
proven in the case when $D$ is not connected.}.
\item \textbf{page 156 in the published version (= page 196 in the online
draft), Example 10.8:} You define edges of $D_{n}$ to be pairs of vertices.
This works fine when $n\geq2$, but in the case $n=1$ it results in having only
$1$ edge, which is not what you want (you want to be $2$ edges). I find the
following definition cleaner: The edges of $D_{n}$ are binary sequences of
length $n$, and each such edge $a_{1}a_{2}\cdots a_{n}$ has initial vertex
$a_{1}a_{2}\cdots a_{n-1}$ and final vertex $a_{2}a_{3}\cdots a_{n}$. (Your
definition of digraph allows for multiple edges, and this is very fortunate here.)
\item \textbf{page 157 in the published version (= page 197 in the online
draft):} \textquotedblleft we need to compute $\det\mathbf{L}\left(
D_{n}\right) $\textquotedblright\ $\rightarrow$ \textquotedblleft we need to
compute $\det\mathbf{L}_{0}\left( D_{n}\right) $\textquotedblright. (The
determinant of $\mathbf{L}\left( D_{n}\right) $ is $0$.)
\item \textbf{page 157 in the published version (= page 197 in the online
draft), proof of Lemma 10.9:} \textquotedblleft path\textquotedblright\ should
be \textquotedblleft walk\textquotedblright.
\item \textbf{page 158 in the published version (= page 197 in the online
draft), proof of Theorem 10.10:} The definition of $\mathbf{A}$ is not
properly tailored to the case of $n=1$ (in which case $D_{n}$ has multiple
edges). Not a big deal, of course...
\end{itemize}
\end{document}