\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}{\protect\rule{.1in}{.1in}} %EndMSIPreambleData \theoremstyle{definition} \newtheorem{theo}{Theorem}[section] \newenvironment{theorem}[] {\begin{theo}[#1]\begin{leftbar}} {\end{leftbar}\end{theo}} \newtheorem{lem}[theo]{Lemma} \newenvironment{lemma}[] {\begin{lem}[#1]\begin{leftbar}} {\end{leftbar}\end{lem}} \newtheorem{prop}[theo]{Proposition} \newenvironment{proposition}[] {\begin{prop}[#1]\begin{leftbar}} {\end{leftbar}\end{prop}} \newtheorem{defi}[theo]{Definition} \newenvironment{definition}[] {\begin{defi}[#1]\begin{leftbar}} {\end{leftbar}\end{defi}} \newtheorem{remk}[theo]{Remark} \newenvironment{remark}[] {\begin{remk}[#1]\begin{leftbar}} {\end{leftbar}\end{remk}} \newtheorem{coro}[theo]{Corollary} \newenvironment{corollary}[] {\begin{coro}[#1]\begin{leftbar}} {\end{leftbar}\end{coro}} \newtheorem{conv}[theo]{Convention} \newenvironment{condition}[] {\begin{conv}[#1]\begin{leftbar}} {\end{leftbar}\end{conv}} \newtheorem{quest}[theo]{Question} \newenvironment{algorithm}[] {\begin{quest}[#1]\begin{leftbar}} {\end{leftbar}\end{quest}} \newtheorem{warn}[theo]{Warning} \newenvironment{conclusion}[] {\begin{warn}[#1]\begin{leftbar}} {\end{leftbar}\end{warn}} \newtheorem{conj}[theo]{Conjecture} \newenvironment{conjecture}[] {\begin{conj}[#1]\begin{leftbar}} {\end{leftbar}\end{conj}} \newtheorem{exmp}[theo]{Example} \newenvironment{example}[] {\begin{exmp}[#1]\begin{leftbar}} {\end{leftbar}\end{exmp}} \newenvironment{proof2}[] {\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}