\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, June 07, 2017 02:48:20}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%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}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\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 ``Approche Duale des repr\'esentations...''}
\ohead{\today}
\begin{document}

\begin{center}
\textbf{\href{http://user.math.uzh.ch/feray/Peccot/ApprocheDualeVFeray.pdf}{\textbf{Approche
Duale des repr\'{e}sentations du groupe sym\'{e}trique}}}

\textit{Valentin F\'{e}ray}

\texttt{feray - approche duale des Rep Sn - version 29 aug 2016.pdf}

version of 29 August 2016

\textbf{Errata and addenda by Darij Grinberg}

\bigskip
\end{center}

I will refer to the results appearing in the book \textquotedblleft Approche
Duale des repr\'{e}sentations du groupe sym\'{e}trique\textquotedblright\ by
the numbers under which they appear in this book (specifically, in its version
of 29 August 2016).

Most of my corrections are written in English, as I don't speak French well enough.

\setcounter{section}{8}

\section{Errata}

\begin{itemize}
\item \textbf{Page 2, Exemple 1.5:} The words \textquotedblleft permutation de
$\mathcal{S}_{n}$\textquotedblright\ are ambiguous: do you mean a permutation
\textbf{in} the set $\mathcal{S}_{n}$ (of which there are $n!$), or a
permutation \textbf{of} the set $\mathcal{S}_{n}$ (of which there are $\left(
n!\right)  !$) ? I know you mean the former, but maybe not every reader does.

\item \textbf{Pages 1--13:} Somewhere here you should introduce a few more
notations that you are using. Namely:

\begin{itemize}
\item If $\left(  V,\rho\right)  $ is a representation of a group $G$, and if
$u$ is any element of the group ring $\mathbb{C}\left[  G\right]  $, then the
endomorphism $\rho\left(  u\right)  $ of $V$ is defined as follows: Write $u$
in the form $u=\sum_{g\in G}\alpha_{g}e_{g}$ (with $\alpha_{g}\in\mathbb{C}$),
and set $\rho\left(  u\right)  =\sum_{g\in G}\alpha_{g}\rho\left(  g\right)
$. (You are using this notation, e.g., in the formulas (a) and (b) on page
13.) Notice that $\rho\left(  u\right)  $ depends $\mathbb{C}$-linearly on
$u$, and that we have $\rho\left(  e_{g}\right)  =\rho\left(  g\right)  $ for
each $g\in G$. Thus, the values $\rho\left(  u\right)  $ for $u\in
\mathbb{C}\left[  G\right]  $ encode exactly the same information as the
original homomorphism $\rho:G\rightarrow\operatorname*{GL}\left(  V\right)  $.

\item If $G$ is a group, if $\chi:G\rightarrow\mathbb{C}$ is any map, and if
$u$ is any element of the group ring $\mathbb{C}\left[  G\right]  $, then the
complex number $\chi\left(  u\right)  $ is defined as follows: Write $u$ in
the form $u=\sum_{g\in G}\alpha_{g}e_{g}$ (with $\alpha_{g}\in\mathbb{C}$),
and set $\chi\left(  u\right)  =\sum_{g\in G}\alpha_{g}\chi\left(  g\right)
$. (You are using this notation, e.g., in Lemme 3.4 on page 39.) Notice that
$\chi\left(  u\right)  $ depends $\mathbb{C}$-linearly on $u$, and that we
have $\chi\left(  e_{g}\right)  =\chi\left(  g\right)  $ for each $g\in G$.
Thus, the values $\chi\left(  u\right)  $ for $u\in\mathbb{C}\left[  G\right]
$ encode exactly the same information as the original map $\chi:G\rightarrow
\mathbb{C}$.
\end{itemize}

\item \textbf{Page 3, D\'{e}finition 1.7:} Replace \textquotedblleft Une
repr\'{e}sentation est dite \textbf{irr\'{e}ductible}\textquotedblright\ by
\textquotedblleft Une repr\'{e}sentation $\left(  V,\rho\right)  $ est dite
\textbf{irr\'{e}ductible}\textquotedblright\ (since you later refer to both
$V$ and $\rho$ in this sentence).

\item \textbf{Page 3, D\'{e}finition 1.7:} Both in the definition of
\textquotedblleft ind\'{e}composable\textquotedblright\ and in the definition
of \textquotedblleft irr\'{e}ductible\textquotedblright, a requirement that
$V\neq0$ should be added.

\item \textbf{Page 3, Remarque 1.8:} You probably want to replace the word
\textquotedblleft irr\'{e}ductibles\textquotedblright\ by \textquotedblleft
ind\'{e}composables\textquotedblright. (They are, of course, equivalent, but
only the version with \textquotedblleft ind\'{e}composables\textquotedblright%
\ really follows directly from the definitions).

\item \textbf{Page 3, Th\'{e}or\`{e}me 1.9:} When you say \textquotedblleft un
nombre fini\textquotedblright, it might be useful to point out that you are
counting irreducible representations \textbf{up to isomorphism}.

\item \textbf{Page 4, D\'{e}monstration de Corollaire 1.15:} Replace
\textquotedblleft$\chi_{V_{N}}$\textquotedblright\ by \textquotedblleft%
$\chi^{V_{N}}$\textquotedblright.

\item \textbf{Page 5, \S 1.2:} When you define the \textquotedblleft%
\textbf{type cyclique}\textquotedblright, it would be worthwhile pointing out
that cycles of size $1$ (that is, cycles corresponding to fixed points of
$\sigma$) are included in the decomposition. (Many authors, particularly those
of introductory algebra texts, tend to omit them.)

\item \textbf{Page 6:} In \textquotedblleft et donc de repr\'{e}sentations
irr\'{e}ductibles de $S_{n}$\textquotedblright, replace \textquotedblleft%
$S_{n}$\textquotedblright\ by \textquotedblleft$\mathcal{S}_{n}$%
\textquotedblright.

\item \textbf{Page 8, D\'{e}monstration de Lemme 1.23:} In \textquotedblleft
d'un seul param\`{e}tre $\alpha_{\operatorname*{id}}$\textquotedblright,
replace \textquotedblleft$\operatorname*{id}$\textquotedblright\ by
\textquotedblleft$\operatorname*{Id}$\textquotedblright.

\item \textbf{Page 8, D\'{e}monstration de Lemme 1.23:} You write:
\textquotedblleft Il n'est pas difficile de v\'{e}rifier la CNS
suivante\textquotedblright.

From a sufficiently experienced point of view, this CNS is really not hard to
verify. However, I don't think that omitting this proof is appropriate when
you are targeting an undergraduate readership. The proof is somewhat similar
to the proof of Lemme 1.31, and more difficult if anything; it is strange that
you present the latter in all its detail while leaving the former entirely to
the reader. At the very least, it's reasonable to give some references for the
proof of your CNS (more precisely: of the fact that $\pi\in\mathcal{S}_{n}$
can be written in the form $\sigma\tau$ with $\sigma\in\operatorname*{RS}%
\left(  T\right)  $ and $\tau\in\operatorname*{CS}\left(  T\right)  $ if and
only if the condition (P) is satisfied):

\begin{itemize}
\item The fact that you are claiming (or, more precisely, the sufficiency of
your condition (P)) is implicit in the proof of Lemma 4.40 in:

\href{https://arxiv.org/abs/0901.0827v5}{Pavel Etingof, Oleg Golberg,
Sebastian Hensel, Tiankai Liu, Alex Schwendner, Dmitry Vaintrob, Elena
Yudovina, \textit{Introduction to representation theory}, arXiv:0901.0827v5}.

\item The same fact is a particular case of Lemma 3 (b) in:

\href{http://www.math.toronto.edu/murnaghan/courses/mat445/Symmetric.pdf}{Graham
Gill, \textit{Representation theory of the symmetric group: basic elements},
16 January 2006}.

\item It is also a consequence of the Lemma in \S 2.3 of:

\href{http://www1.mat.uniroma1.it/people/procesi/tensor.pdf}{Claudio Procesi,
\textit{Chapter 9: Tensor symmetry}, 28 November 2005}.

\item It also follows from Lemma (2.6) in:

\href{http://math.cmu.edu/~cnewstea/notes/reptheory.pdf}{Stuart Martin,
\textit{Part III Representation Theory, Lent Term 2013 (notes by Clive
Newstead)}, 26 April 2013}

(applied to $\mu=\lambda$, $t_{\lambda}=\pi^{-1}\left(  T\right)  $ and
$t_{\mu}=T$).

\item It also follows from Lemma 2 in \S 2 of:

\href{https://www1.maths.leeds.ac.uk/~pmtwc/repinv.pdf}{William
Crawley-Boevey, \textit{Lectures on representation theory and invariant
theory}, 1999}

(or, rather, is proven by a similar argument).
\end{itemize}

(I have only listed references freely available online; of course, there are
many others as well.)

\item \textbf{Page 9, D\'{e}monstration de Lemme 1.23:} In \textquotedblleft
ne v\'{e}rifiant pas $\left(  P\right)  $\textquotedblright, replace the
\textquotedblleft$\left(  P\right)  $\textquotedblright\ by a textmode
\textquotedblleft(P)\textquotedblright.

\item \textbf{Page 10, Exemple 1.26:} On the last line of this example,
replace \newline\textquotedblleft$\operatorname*{Vect}\left(  \left(
u_{1}+\cdots+u_{n}\right)  \right)  $\textquotedblright\ by \textquotedblleft%
$\operatorname*{Vect}\left(  \left(  e_{1}+\cdots+e_{n}\right)  \right)
$\textquotedblright.

\item \textbf{Page 11, D\'{e}monstration de Proposition 1.27:} Let me suggest
a different proof of Proposition 1.27 -- one that does not apply the (somewhat
obscure) Lemme 1.19, but instead makes use of Proposition 1.28. (This is not
circular reasoning, because the proof of Proposition 1.28 does not rely on
Proposition 1.27 anywhere.)

\textit{Second proof of Proposition 1.27.} We want to prove that $V_{\lambda}$
is irreducible. Since \textquotedblleft irreducible\textquotedblright\ is
equivalent to \textquotedblleft indecomposable\textquotedblright\ (for a
representation of a finite group), it suffices to show that $V_{\lambda}$ is
indecomposable. Thus, let us prove this. Since $C_{\lambda}\neq0$, we have
$V_{\lambda}\neq\left\{  0\right\}  $. Thus, it remains to show that
$V_{\lambda}$ cannot be written in the form $\left(  V_{1}\oplus V_{2}%
,\rho_{1}\oplus\rho_{2}\right)  $ for two nonzero subspaces $V_{1}$ and
$V_{2}$.

Assume the contrary. Thus, $V_{\lambda}=\left(  V_{1}\oplus V_{2},\rho
_{1}\oplus\rho_{2}\right)  $ for two nonzero subspaces $V_{1}$ and $V_{2}$.
Thus, both subspaces $V_{1}$ and $V_{2}$ are stable under the action of
$\mathcal{S}_{n}$. We have $V_{\lambda}=V_{1}\oplus V_{2}$ and thus
$\dim\left(  V_{\lambda}\right)  =\dim\left(  V_{1}\oplus V_{2}\right)
=\dim\left(  V_{1}\right)  +\underbrace{\dim\left(  V_{2}\right)
}_{\substack{>0\\\text{(since }V_{2}\text{ is nonzero)}}}>\dim\left(
V_{1}\right)  $. Hence, $V_{\lambda}\not \subseteq V_{1}$.

Let $n_{1}$ and $n_{2}$ be as in Proposition 1.28. Then, Proposition 1.28
yields $n_{1}n_{2}\mid n!$, so that $n_{1}n_{2}\neq0$ and thus $n_{2}\neq0$.
Now, $C_{\lambda}^{2}=n_{2}C_{\lambda}\neq0$ (since $n_{2}\neq0$ and
$C_{\lambda}\neq0$).

We have $C_{\lambda}\in\mathbb{C}\left[  \mathcal{S}_{n}\right]  C_{\lambda
}=V_{\lambda}=V_{1}\oplus V_{2}$. Hence, there exist some $v_{1}\in V_{1}$ and
$v_{2}\in V_{2}$ such that $C_{\lambda}=v_{1}+v_{2}$. Consider these $v_{1}$
and $v_{2}$.

If we had $C_{\lambda}\in V_{1}$, then we would have $V_{\lambda}%
=\mathbb{C}\left[  \mathcal{S}_{n}\right]  \underbrace{C_{\lambda}}_{\in
V_{1}}\subseteq\mathbb{C}\left[  \mathcal{S}_{n}\right]  V_{1}\subseteq V_{1}$
(since $V_{\lambda}$ is stable under the action of $\mathcal{S}_{n}$), which
would contradict $V_{\lambda}\not \subseteq V_{1}$. Hence, we cannot have
$C_{\lambda}\in V_{1}$. In other words, we have $C_{\lambda}\notin V_{1}$.

We have $v_{1}\in V_{1}\subseteq V_{\lambda}=\mathbb{C}\left[  \mathcal{S}%
_{n}\right]  C_{\lambda}$. In other words, there exists some $w_{1}%
\in\mathbb{C}\left[  \mathcal{S}_{n}\right]  $ satisfying $v_{1}%
=w_{1}C_{\lambda}$. Consider this $w_{1}$.

The element $x=C_{\lambda}w_{1}C_{\lambda}$ satisfies the equalities (1) and
(2) from the proof of Lemme 1.23 (because of (1.3) and (1.4)). Hence, $x$ is a
scalar multiple of $C_{\lambda}$ (as follows from Lemme 1.23). In other words,
$C_{\lambda}w_{1}C_{\lambda}=\alpha C_{\lambda}$ for some $\alpha\in
\mathbb{C}$. Consider this $\alpha$. We have $\alpha C_{\lambda}=C_{\lambda
}\underbrace{w_{1}C_{\lambda}}_{=v_{1}\in V_{1}}\in C_{\lambda}V_{1}\subseteq
V_{1}$ (since $V_{\lambda}$ is stable under the action of $\mathcal{S}_{n}$).
If $\alpha$ was nonzero, then we would have $C_{\lambda}=\dfrac{1}{\alpha
}\underbrace{C_{\lambda}}_{\in V_{1}}\in\dfrac{1}{\alpha}V_{1}\subseteq V_{1}%
$, which would contradict $C_{\lambda}\notin V_{1}$. Hence, $\alpha$ cannot be
nonzero. Thus, $\alpha=0$. Hence, $C_{\lambda}w_{1}C_{\lambda}%
=\underbrace{\alpha}_{=0}C_{\lambda}=0$. Thus, $C_{\lambda}\underbrace{v_{1}%
}_{=w_{1}C_{\lambda}}=C_{\lambda}w_{1}C_{\lambda}=0$. Similarly, $C_{\lambda
}v_{2}=0$. Now,
\[
C_{\lambda}^{2}=C_{\lambda}\underbrace{C_{\lambda}}_{=v_{1}+v_{2}}=C_{\lambda
}\left(  v_{1}+v_{2}\right)  =\underbrace{C_{\lambda}v_{1}}_{=0}%
+\underbrace{C_{\lambda}v_{2}}_{=0}=0.
\]
This contradicts $C_{\lambda}^{2}\neq0$. This contradiction shows that our
assumption was false. Hence, $V_{\lambda}$ cannot be written in the form
$\left(  V_{1}\oplus V_{2},\rho_{1}\oplus\rho_{2}\right)  $ for two nonzero
subspaces $V_{1}$ and $V_{2}$. Thus, the representation $V_{\lambda}$ is
indecomposable (since $V_{\lambda}\neq\left\{  0\right\}  $), and therefore
irreducible (since Maschke's theorem tells us that \textquotedblleft
irreducible\textquotedblright\ and \textquotedblleft
indecomposable\textquotedblright\ is the same thing). This proves Proposition
1.27 again. $\square$

\item \textbf{Page 12, D\'{e}monstration de Proposition 1.28:} Replace
\textquotedblleft$\operatorname*{id}$\textquotedblright\ by \textquotedblleft%
$\operatorname*{Id}$\textquotedblright\ twice in this proof. (Maybe it is
easier to just root out these errors by a find-replace? Or do you use
$\operatorname*{Id}$ and $\operatorname*{id}$ for two different things at some point?)

\item \textbf{Page 18, D\'{e}monstration de Lemma 2.2:} On the second line of
this proof, the words \textquotedblleft dans ce cas\textquotedblright\ sound
somewhat inappropriate to me (you aren't really focussing on a case). Maybe
something like \textquotedblleft for this reason\textquotedblright\ would be better.

\item \textbf{Page 18:} The last equality sign in the equality%
\begin{align*}
\chi^{\lambda}\left(  \pi\right)   &  :=\operatorname*{Tr}\left(  \rho\left(
\pi\right)  \right)  =\operatorname*{Tr}\left(  \varphi_{\lambda,\pi}\right)
\\
&  =\dfrac{\dim\left(  V_{\lambda}\right)  }{n!}\sum_{\substack{\sigma
\in\mathcal{S}_{n}\\\sigma\in\operatorname*{RS}\left(  T\right)  }%
}\sum_{\substack{\tau\in\mathcal{S}_{n}\\\tau\in\operatorname*{CS}\left(
T\right)  }}\varepsilon\left(  \tau\right)  \operatorname*{Tr}\left(  x\mapsto
e_{\pi}\cdot x\cdot e_{\sigma}\cdot e_{\tau}\right)
\end{align*}
requires some work to verify; maybe it's better to add some explanation such
as \textquotedblleft because the definition of $\varphi_{\lambda,\pi}$
becomes
\begin{align*}
\varphi_{\lambda,\pi}  &  =\dfrac{\dim\left(  V_{\lambda}\right)  }{n!}\left(
x\mapsto e_{\pi}\cdot x\cdot C_{\lambda}\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{by the definition of }p_{\lambda}\right) \\
&  =\dfrac{\dim\left(  V_{\lambda}\right)  }{n!}\sum_{\substack{\sigma
\in\mathcal{S}_{n}\\\sigma\in\operatorname*{RS}\left(  T\right)  }%
}\sum_{\substack{\tau\in\mathcal{S}_{n}\\\tau\in\operatorname*{CS}\left(
T\right)  }}\varepsilon\left(  \tau\right)  \left(  x\mapsto e_{\pi}\cdot
x\cdot e_{\sigma}\cdot e_{\tau}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }C_{\lambda}\right)
.
\end{align*}
\textquotedblright.

\item \textbf{Page 18:} Before \textquotedblleft Nous allons
manipuler\textquotedblright, I'd suggest adding something like
\textquotedblleft Therefore,%
\begin{align*}
\dfrac{n!\chi^{\lambda}\left(  \pi\right)  }{\dim\left(  V_{\lambda}\right)
}  &  =\sum_{\substack{\sigma\in\mathcal{S}_{n}\\\sigma\in\operatorname*{RS}%
\left(  T\right)  }}\sum_{\substack{\tau\in\mathcal{S}_{n}\\\tau
\in\operatorname*{CS}\left(  T\right)  }}\varepsilon\left(  \tau\right)
\operatorname*{Card}\left\{  g\in\mathcal{S}_{n}\ \mid\ g=\pi\cdot
g\cdot\sigma\cdot\tau\right\} \\
&  =\sum_{\substack{\sigma\in\mathcal{S}_{n}\\\sigma\in\operatorname*{RS}%
\left(  T\right)  }}\sum_{\substack{\tau\in\mathcal{S}_{n}\\\tau
\in\operatorname*{CS}\left(  T\right)  }}\varepsilon\left(  \tau\right)
\sum_{g\in\mathcal{S}_{n}}\delta_{g,\pi\cdot g\cdot\sigma\cdot\tau}=\sum
_{g\in\mathcal{S}_{n}}\sum_{\substack{\sigma\in\operatorname*{RS}\left(
T\right)  \\\tau\in\operatorname*{CS}\left(  T\right)  }}\varepsilon\left(
\tau\right)  \delta_{g,\pi\cdot g\cdot\sigma\cdot\tau}.
\end{align*}
\textquotedblright.\ This would help bridge the gap to the computations on
page 19 (which otherwise seem to come out of the blue).

\item \textbf{Page 19:} Replace \textquotedblleft$\delta_{\pi=\tau^{\prime
}\sigma^{\prime}}$\textquotedblright\ by \textquotedblleft$\delta_{\pi
,\tau^{\prime}\sigma^{\prime}}$\textquotedblright.

\item \textbf{Page 19:} Replace \textquotedblleft$\delta_{\pi=\tau\sigma}%
$\textquotedblright\ by \textquotedblleft$\delta_{\pi,\tau\sigma}%
$\textquotedblright.

\item \textbf{Page 19:} Replace \textquotedblleft$CS\left(  T\right)
$\textquotedblright\ by \textquotedblleft$\operatorname*{CS}\left(  T\right)
$\textquotedblright\ (twice on this page).

Also, replace \textquotedblleft$RS\left(  T\right)  $\textquotedblright\ by
\textquotedblleft$\operatorname*{RS}\left(  T\right)  $\textquotedblright.

(Again, this kind of mistake might be susceptible to an automated search.)

\item \textbf{Page 20, Remarque 2.6:} Replace \textquotedblleft$CS\left(
T\right)  $\textquotedblright\ by \textquotedblleft$\operatorname*{CS}\left(
T\right)  $\textquotedblright.

Also, replace \textquotedblleft$RS\left(  T\right)  $\textquotedblright\ by
\textquotedblleft$\operatorname*{RS}\left(  T\right)  $\textquotedblright.

\item \textbf{Page 21, D\'{e}monstration de Proposition 2.7:} Replace
\textquotedblleft de la d\'{e}finition (2.5)\textquotedblright\ by
\textquotedblleft de la D\'{e}finition 2.5\textquotedblright. (You are citing
a definition, not a formula.)

\item \textbf{Page 22, D\'{e}monstration de Proposition 2.7:} Replace
\textquotedblleft sont dans la m\^{e}me case\textquotedblright\ by
\textquotedblleft sont la m\^{e}me case\textquotedblright.

\item \textbf{Page 22, D\'{e}monstration de Proposition 2.7:} In the last
equation in this proof, replace the \textquotedblleft$\varepsilon\left(
\tau\right)  $\textquotedblright\ (on the right hand side) by an
\textquotedblleft$\varepsilon\left(  \check{\tau}\right)  $\textquotedblright%
\ (and maybe add a justification, such as \textquotedblleft because
$\varepsilon\left(  \tau_{\mid\left\{  1,\ldots,k\right\}  }\right)
=\varepsilon\left(  \tau\right)  $\textquotedblright).

\item \textbf{Page 22, Exemple 2.9:} Replace \textquotedblleft$\in S_{2}%
$\textquotedblright\ by \textquotedblleft$\in\mathcal{S}_{2}$%
\textquotedblright.

\item \textbf{Page 23, Exemple 2.9:} Replace \textquotedblleft Le
th\'{e}or\`{e}me nous donne\textquotedblright\ by \textquotedblleft
Proposition 2.7 nous donne\textquotedblright.

\item \textbf{Page 24, D\'{e}monstration de Th\'{e}or\`{e}me 2.13:} In this
proof, you are using the notation $\delta_{\mathcal{A}}$ for $%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true;}\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
$ when $\mathcal{A}$ is any logical statement. It might be worth defining this notation.

\item \textbf{Page 26, Corollaire 2.16:} Replace \textquotedblleft$\dim\left(
V^{p\times q}\right)  $\textquotedblright\ by \textquotedblleft$\dim\left(
V_{p\times q}\right)  $\textquotedblright.

\item \textbf{Page 26, Remarque 2.17:} Replace \textquotedblleft$\dim\left(
V^{p\times q}\right)  $\textquotedblright\ by \textquotedblleft$\dim\left(
V_{p\times q}\right)  $\textquotedblright.

\item \textbf{Page 27, Corollaire 2.22:} I'd clarify here that $\lambda$ is
considered fixed.

\item \textbf{Page 27, Exemple 2.24:} These aren't all the possible graphs;
you are missing the ones where one of $V_{\circ}\left(  G\right)  $ and
$V_{\bullet}\left(  G\right)  $ is empty :)

\item \textbf{Page 27, Exemple 2.24:} I don't think you have ever defined the
notation $\ell\left(  \lambda\right)  $ for the length of a partition
$\lambda$.

\item \textbf{Page 27, Remarque 2.25:} I know it looks totally obvious, but it
wouldn't hurt to explain what the \textquotedblleft sommets
blancs\textquotedblright\ of a bipartite graph $G$ are (namely, the elements
of $V_{\circ}\left(  G\right)  $), and what the \textquotedblleft sommets
noirs\textquotedblright\ of a bipartite graph $G$ are (namely, the elements of
$V_{\bullet}\left(  G\right)  $).

\item \textbf{Page 29, Proposition 2.31:} The sum on the right hand side has
many undefined addends. You should either replace \textquotedblleft%
$\varphi:V_{G}\rightarrow\mathbb{N}^{\ast}$\textquotedblright\ by
\textquotedblleft$\varphi:V_{G}\rightarrow\left\{  1,2,\ldots,m\right\}
$\textquotedblright\ under the summation sign (saying that $m$ is the size of
$\mathbf{p}$), or define the values $p_{i}$ and $q_{i}$ to be $0$ for $i>m$.

\item \textbf{Page 29, D\'{e}monstration de Proposition 2.31:} You write:
\textquotedblleft On part du lemme 2.19\textquotedblright, but the setting of
Proposition 2.31 is more general than the setting of Lemme 2.19 (for example,
the bipartite graph $G$ in Proposition 2.31 may have isolated vertices, which
can never happen for a bipartite graph of the form $G_{\sigma,\tau}$). You
probably want to refer to D\'{e}finition 2.23 instead. Furthermore, whenever
you refer to \textquotedblleft$\left(  \star\right)  _{h}$\textquotedblright,
you mean the third condition in D\'{e}finition 2.23.

\item \textbf{Page 29, D\'{e}monstration de Proposition 2.31:} Replace
\textquotedblleft$\varphi\left(  v\right)  =j$ si $q_{1}+\cdots+q_{j-1}%
<h_{c}\left(  v\right)  \leq q_{1}+\cdots+q_{j}$\textquotedblright\ by
\textquotedblleft$\varphi\left(  v\right)  =j$ si $q_{j+1}+\cdots+q_{m}%
<h_{c}\left(  v\right)  \leq q_{j}+\cdots+q_{m}$\textquotedblright.

\item \textbf{Page 31, Proposition 2.39:} The graphs in this bijection should
not be allowed to have isolated vertices.

\item \textbf{Page 35, Notes et r\'{e}f\'{e}rences:} You seem to write (my bad
grasp of French might be misleading me here) that Young symmetrizers have
(surprisingly) not been previously used to compute characters of
$\mathcal{S}_{n}$. This doesn't seem true to me. In \S 36--\S 38 of Daniel
Edwin Rutherford's \textit{Substitutional Analysis}, these characters are
computed using the material previously studied in the book, which includes
both Young symmetrizers and Young's seminormal form; this is more complicated
than your argument, but still doesn't use symmetric functions.

\item \textbf{Page 37:} After \textquotedblleft et l'appellerons le
\textbf{caract\`{e}re normalis\'{e}}\textquotedblright, add a period.

\item \textbf{Page 38, \S 2.1:} You say that \textquotedblleft$\Lambda$ est
une alg\`{e}bre\textquotedblright, and that this follows from Proposition 3.3.
Maybe it is worth pointing out one more step in this argument: Namely, the
function $\operatorname*{Ch}\nolimits_{\varnothing}$ (corresponding to the
partition $\varnothing$ of $0$) sends every partition $\lambda$ to%
\begin{align*}
\underbrace{\left\vert \lambda\right\vert \left(  \left\vert \lambda
\right\vert -1\right)  \cdots\left(  \left\vert \lambda\right\vert
-0+1\right)  }_{=\left(  \text{empty product}\right)  =1}%
\underbrace{\widehat{\chi}^{\lambda}\left(  \operatorname*{Id}\right)
}_{=\dfrac{\chi^{\lambda}\left(  \operatorname*{Id}\right)  }{\dim\left(
V_{\lambda}\right)  }}  &  =\dfrac{\chi^{\lambda}\left(  \operatorname*{Id}%
\right)  }{\dim\left(  V_{\lambda}\right)  }=\dfrac{1}{\dim\left(  V_{\lambda
}\right)  }\underbrace{\chi^{\lambda}\left(  \operatorname*{Id}\right)
}_{\substack{=\operatorname*{Tr}\left(  \rho^{\lambda}\left(
\operatorname*{id}\right)  \right)  \\=\dim\left(  V_{\lambda}\right)  }}\\
&  =\dfrac{1}{\dim\left(  V_{\lambda}\right)  }\dim\left(  V_{\lambda}\right)
=1.
\end{align*}
Hence, $\operatorname*{Ch}\nolimits_{\varnothing}$ is the unity of the algebra
of all functions on the set of all Young diagrams. Therefore, the latter unity
belongs to $\Lambda$. Hence, in order to prove that $\Lambda$ is an algebra,
it suffices to prove Proposition 3.3.

\item \textbf{Page 39, Lemme 3.4:} It is not necessary to relegate the proof
of Lemme 3.4 to [Sag 01]. Here is a simple proof using nothing but the results
shown in Chapter 1 of your book:

\textit{Proof of Lemme 3.4.} Assume that $x\in\mathbb{C}\left[  \mathcal{S}%
_{n}\right]  $ is central.

The element $x$ of $\mathbb{C}\left[  \mathcal{S}_{n}\right]  $ is central. In
other words, $x$ lies in the center of the ring $\mathbb{C}\left[
\mathcal{S}_{n}\right]  $. Hence, $xC_{\lambda}=C_{\lambda}x$. Hence, every
$\sigma\in\operatorname*{RS}\left(  T\right)  $ satisfies%
\begin{equation}
e_{\sigma}\cdot\underbrace{xC_{\lambda}}_{=C_{\lambda}x}=\underbrace{e_{\sigma
}\cdot C_{\lambda}}_{\substack{=C_{\lambda}\\\text{(by (1.3))}}}x=C_{\lambda
}x=xC_{\lambda}. \label{p39.l3.4.pf.1}%
\end{equation}
Moreover, every $\tau\in\operatorname*{CS}\left(  T\right)  $ satisfies%
\begin{equation}
x\underbrace{C_{\lambda}\cdot e_{\tau}}_{\substack{=\varepsilon\left(
\tau\right)  C_{\lambda}\\\text{(by (1.4))}}}=\varepsilon\left(  \tau\right)
xC_{\lambda}. \label{p39.l3.4.pf.2}%
\end{equation}


But Lemme 1.23 shows that if some element $y\in\mathbb{C}\left[
\mathcal{S}_{n}\right]  $ satisfies%
\[
\left(  e_{\sigma}\cdot y=y\ \ \ \ \ \ \ \ \ \ \text{for every }\sigma
\in\operatorname*{RS}\left(  T\right)  \right)
\]
and%
\[
\left(  y\cdot e_{\tau}=\varepsilon\left(  \tau\right)
y\ \ \ \ \ \ \ \ \ \ \text{for every }\tau\in\operatorname*{CS}\left(
T\right)  \right)  ,
\]
then $y$ is a scalar multiple of $C_{\lambda}$. Applying this to
$y=xC_{\lambda}$, we conclude that $xC_{\lambda}$ is a scalar multiple of
$C_{\lambda}$ (since we have (\ref{p39.l3.4.pf.1}) for every $\sigma
\in\operatorname*{RS}\left(  T\right)  $, and since we have
(\ref{p39.l3.4.pf.2}) for every $\tau\in\operatorname*{CS}\left(  T\right)
$). In other words, there exists some scalar $\gamma\in\mathbb{C}$ such that
$xC_{\lambda}=\gamma C_{\lambda}$. Consider this $\gamma$.

Now, let $w\in V_{\lambda}$. Then, $w\in V_{\lambda}=\mathbb{C}\left[
\mathcal{S}_{n}\right]  C_{\lambda}$. In other words, there exists some
$u\in\mathbb{C}\left[  \mathcal{S}_{n}\right]  $ such that $w=uC_{\lambda}$.
Consider this $u$. We have $xu=ux$ (since $x$ lies in the center of the ring
$\mathbb{C}\left[  \mathcal{S}_{n}\right]  $). Now,
\[
\left(  \rho^{\lambda}\left(  x\right)  \right)  \left(  w\right)
=x\underbrace{w}_{=uC_{\lambda}}=\underbrace{xu}_{=ux}C_{\lambda
}=u\underbrace{xC_{\lambda}}_{=\gamma C_{\lambda}}=\gamma
\underbrace{uC_{\lambda}}_{=w}=\gamma w=\left(  \gamma\operatorname*{Id}%
\nolimits_{V_{\lambda}}\right)  \left(  w\right)  .
\]


Now, forget that we fixed $w$. We thus have shown that $\left(  \rho^{\lambda
}\left(  x\right)  \right)  \left(  w\right)  =\left(  \gamma
\operatorname*{Id}\nolimits_{V_{\lambda}}\right)  \left(  w\right)  $ for each
$w\in V_{\lambda}$. In other words, $\rho^{\lambda}\left(  x\right)
=\gamma\operatorname*{Id}\nolimits_{V_{\lambda}}$. But the definition of the
character $\chi^{\lambda}$ yields
\[
\chi^{\lambda}\left(  x\right)  =\operatorname*{Tr}\left(  \underbrace{\rho
^{\lambda}\left(  x\right)  }_{=\gamma\operatorname*{Id}\nolimits_{V_{\lambda
}}}\right)  =\operatorname*{Tr}\left(  \gamma\operatorname*{Id}%
\nolimits_{V_{\lambda}}\right)  =\gamma\underbrace{\operatorname*{Tr}\left(
\operatorname*{Id}\nolimits_{V_{\lambda}}\right)  }_{=\dim\left(  V_{\lambda
}\right)  }=\gamma\dim\left(  V_{\lambda}\right)  .
\]
Now, the definition of $\widehat{\chi}^{\lambda}$ yields $\widehat{\chi
}^{\lambda}\left(  x\right)  =\dfrac{\chi^{\lambda}\left(  x\right)  }%
{\dim\left(  V_{\lambda}\right)  }=\gamma$ (since $\chi^{\lambda}\left(
x\right)  =\gamma\dim\left(  V_{\lambda}\right)  $). Now,%
\[
\rho^{\lambda}\left(  x\right)  =\underbrace{\gamma}_{=\widehat{\chi}%
^{\lambda}\left(  x\right)  }\operatorname*{Id}\nolimits_{V_{\lambda}%
}=\widehat{\chi}^{\lambda}\left(  x\right)  \operatorname*{Id}%
\nolimits_{V_{\lambda}}.
\]
This proves Lemme 3.4. $\square$

\item \textbf{Page 40, D\'{e}monstration de Proposition 3.3:} After the word
\textquotedblleft Ainsi\textquotedblright, replace \textquotedblleft%
$\operatorname*{Ch}\nolimits_{\left(  2,1\right)  }\left(  \lambda\right)
$\textquotedblright\ by \textquotedblleft$\operatorname*{Ch}\nolimits_{\left(
2\right)  }\left(  \lambda\right)  \cdot\operatorname*{Ch}\nolimits_{\left(
2\right)  }\left(  \lambda\right)  $\textquotedblright.

\item \textbf{Page 41:} How exactly do you mean the word \textquotedblleft
planaire\textquotedblright\ in \textquotedblleft$\left\{  M\in\mathcal{M}%
_{k},\ M\text{ planaire}\right\}  $\textquotedblright? Do you mean that the
underlying graph is planar, or does there have to be a planar embedding under
which the \textquotedblleft syst\`{e}me de rotation\textquotedblright\ goes
counterclockwise around each vertex?

(This asked, you don't seem to use this characterization of $\mathcal{T}_{k}$
anywhere; thus, maybe it is better left to some footnote, where it is less
likely to trip up readers?)

\item \textbf{Page 41:} Replace \textquotedblleft Cette famille correspond aux
factorisations $\sigma\tau=\zeta_{k}$\textquotedblright\ by \textquotedblleft
Cette famille correspond aux factorisations $\tau\sigma=\zeta_{k}%
$\textquotedblright.

\item \textbf{Page 41, D\'{e}finition 3.8:} Remove the first option
(\textquotedblleft soit un sommet noir seul $\bullet$,\textquotedblright).
Indeed, a node with no children is already covered by the second option (since
the \textquotedblleft liste ordonn\'{e}e d'arbres plans
enracin\'{e}s\textquotedblright\ can be an empty list). That said, of course,
it's worth pointing out that the list is allowed to be empty, which allows you
to construct \textquotedblleft the first rooted plane tree\textquotedblright%
\ out of nothing.

\item \textbf{Pages 41--42, D\'{e}monstration de Lemme 3.10:} I find this
somewhat too brief. Maybe it is worth at least pointing out why the map
constructed is unicellular (intuitively, walking along the edges starting from
the chosen edge performs something like a left-to-right depth-first traversal
of the tree; I am not sure about the details myself).

\item \textbf{Page 42:} Maybe replace \textquotedblleft en restreignant dans
$\operatorname*{Ch}\nolimits_{\left(  l-1\right)  }$\textquotedblright\ by
\textquotedblleft en restreignant dans $\operatorname*{Ch}\nolimits_{\left(
l-1\right)  }=\left(  -1\right)  ^{l-1}\sum_{M\in\mathcal{M}_{l-1}}\left(
-1\right)  ^{\left\vert V_{\bullet}\left(  M\right)  \right\vert }N_{G\left(
M\right)  }$\textquotedblright. (Otherwise it is not clear where there is a
sum in $\operatorname*{Ch}\nolimits_{\left(  l-1\right)  }$; after all, the
definition $\operatorname*{Ch}\nolimits_{\left(  l-1\right)  }$ involves no summations.)

\item \textbf{Page 42, D\'{e}finition 3.12:} I would replace \textquotedblleft%
$\sum_{\substack{T\text{ arbre plan enracin\'{e}}\\\text{\`{a} }l\text{
sommets}\\\text{(}l-1\text{ ar\^{e}tes)}}}$\textquotedblright\ by
\textquotedblleft$\sum_{T\in\mathcal{T}_{l-1}}$\textquotedblright. (In writing
\textquotedblleft$\sum_{\substack{T\text{ arbre plan enracin\'{e}}%
\\\text{\`{a} }l\text{ sommets}\\\text{(}l-1\text{ ar\^{e}tes)}}}\left(
-1\right)  ^{\left\vert V_{\bullet}\left(  T\right)  \right\vert }N_{G\left(
T\right)  }$\textquotedblright, you are tacitly using the bijection from Lemme
3.10 to identify plane binary trees with elements of $\mathcal{T}_{k}$. I
don't think this is a good idea, seeing that your proof of Lemme 3.10 is
rather sketchy and that the identification creates fertile ground for
confusion, as you point out yourself in Remarque 3.11. My suggested
replacement avoids this identification. As far as I understand, you don't
really use the \textquotedblleft arbres plans enracin\'{e}s\textquotedblright%
\ anywhere outside Lemme 3.10; therefore it seems unreasonable to invoke them
in D\'{e}finition 3.12.)

\item \textbf{Page 42, Proposition 3.14:} I would replace \textquotedblleft%
$\operatorname*{vect}\left(  \operatorname*{Ch}\nolimits_{\mu}\right)
$\textquotedblright\ by \textquotedblleft$\operatorname*{vect}\left(
\operatorname*{Ch}\nolimits_{\mu}\right)  =\Lambda$\textquotedblright, so that
the reader won't have to wonder why you are suddenly circumscribing $\Lambda$.

\item \textbf{Page 42, Proposition 3.14:} Is this obvious, or are you
intending to prove this later, or are you omitting the proof? Maybe a few
words could clear this up.

\item \textbf{Page 61, Lemme 4.17:} Instead of \textquotedblleft$\tau_{i}$ et
$\sigma_{i}$ permutent les m\^{e}mes \'{e}l\'{e}ments que $\pi_{i}%
$\textquotedblright, I would suggest \textquotedblleft$\tau_{i}$ et
$\sigma_{i}$ sont des permutations de l'ensemble des \'{e}l\'{e}ments du cycle
$\pi_{i}$\textquotedblright\ (or whatever is the closest correct French
sentence to this). Your formulation falsely suggests that $\tau_{i}$ and
$\sigma_{i}$ actually have to nontrivially permute the elements of $\pi_{i}$
(i.e., cannot leave any of them fixed).

\item \textbf{Page 61, Remarque 4.18:} I would add the extra observation
(between the first observation and the second observation) that%
\[
C\left(  \sigma\right)  =\bigsqcup_{i=1}^{s}C\left(  \sigma_{i}\right)
\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ C\left(  \tau\right)
=\bigsqcup_{i=1}^{s}C\left(  \tau_{i}\right)
\]
(since the permutations $\sigma_{1},\sigma_{2},\ldots,\sigma_{s}$ act on
disjoint sets, and so do the permutations $\tau_{1},\tau_{2},\ldots,\tau_{s}%
$). This is a useful step towards the second observation you make (about
decomposing the graph $G_{\sigma,\tau}$ as a disjoint union).
\end{itemize}

\section{An approach to Proposition 3.38}

Here is something more speculative. I am just as vexed as you seem to be about
the fact that no elementary proof of Proposition 3.38 is known. To me, it says
that we are missing some insights about matchings in bipartite graphs that
perhaps could shed a new light on matching theory. (You don't actually mention
matchings, but transport polytopes are closely related to them, and the
\textquotedblleft expanseur\textquotedblright\ condition has a well-known
interpretation in terms of existence of matchings at least in the particular
case where each $v\in V_{\circ}$ satisfies $h\left(  \circ\right)  =2$.) I
have been trying for a while to find the missing insights (independently from
your [DF\'{S} 10] paper because I don't speak the language of polytopes), and
I have something that looks like a partial result. Maybe you see a way to
complete it?

I call a decorated graph $\left(  G,h\right)  $ a \textit{semi-expander} if
each subset $V$ of $V_{\circ}$ satisfies $\left\vert \overline{\mathcal{V}%
\left(  V\right)  }\right\vert \geq\sum_{\circ\in V}h\left(  \circ\right)  $.
Thus, expanders\footnote{I have taken the liberty to translate your
\textquotedblleft graph expanseur\textquotedblright\ as \textquotedblleft
expander\textquotedblright. I don't know whether this is reasonable...} are
always semi-expanders, but not vice versa.

If $V_{\circ}$ and $V_{\bullet}$ are two finite sets, and if $k$ is a
nonnegative integer, then I introduce the following notations:

\begin{itemize}
\item A map $\varphi:V_{\circ}\sqcup V_{\bullet}\rightarrow\mathbb{N}^{\ast}$
is $k$\textit{-packed} if $\varphi\left(  V_{\circ}\right)  =\varphi\left(
V_{\bullet}\right)  =\left\{  1,2,\ldots,k\right\}  $. (Notice that a
$k$-packed map $\varphi:V_{\circ}\sqcup V_{\bullet}\rightarrow\mathbb{N}%
^{\ast}$ can exist only if $\left\vert V_{\circ}\right\vert \geq k$ and
$\left\vert V_{\bullet}\right\vert \geq k$.)

\item Now, let $h:V_{\circ}\rightarrow\left\{  2,3,4,\ldots\right\}  $ be a
map. A map $\varphi:V_{\circ}\sqcup V_{\bullet}\rightarrow\mathbb{N}^{\ast}$
is said to be $h$\textit{-equitable} if each $i\in\mathbb{N}^{\ast}$ satisfies
$\left\vert \varphi^{-1}\left(  i\right)  \right\vert =\sum_{\substack{\circ
\in V_{\circ};\\\varphi\left(  \circ\right)  =i}}h\left(  \circ\right)  $.
\end{itemize}

\begin{noncompile}
If $V_{\circ}$ and $V_{\bullet}$ are two finite sets, and if $k$ is a
nonnegative integer, then I introduce the following notations:

\begin{itemize}
\item A $k$\textit{-biflag} of $\left(  V_{\circ},V_{\bullet}\right)  $ means
a pair $\left(  \left(  I_{0},I_{1},\ldots,I_{k}\right)  ,\left(  J_{0}%
,J_{1},\ldots,J_{k}\right)  \right)  $ of two $\left(  k+1\right)  $-tuples of
subsets of $V$ such that%
\begin{align*}
\varnothing &  =I_{0}\subseteq I_{1}\subseteq\cdots\subseteq I_{k}=V_{\circ
}\ \ \ \ \ \ \ \ \ \ \text{and}\\
\varnothing &  =J_{0}\subseteq J_{1}\subseteq\cdots\subseteq J_{k}=V_{\bullet
}.
\end{align*}


A $k$-biflag $\left(  \left(  I_{0},I_{1},\ldots,I_{k}\right)  ,\left(
J_{0},J_{1},\ldots,J_{k}\right)  \right)  $ is said to be \textit{proper} if
each $i\in\left\{  1,2,\ldots,k\right\}  $ satisfies $I_{i-1}\subsetneq I_{i}$
and $J_{i-1}\subsetneq J_{i}$. (Notice that a proper $k$-biflag can only exist
if $k\leq\left\vert V_{\circ}\right\vert $ and $k\leq\left\vert V_{\bullet
}\right\vert $.)

Now, let $h:V_{\circ}\rightarrow\left\{  2,3,4,\ldots\right\}  $ be a map. A
$k$-biflag $\left(  \left(  I_{0},I_{1},\ldots,I_{k}\right)  ,\left(
J_{0},J_{1},\ldots,J_{k}\right)  \right)  $ is said to be $h$%
\textit{-equitable} if each $i\in\left\{  0,1,\ldots,k\right\}  $ satisfies
$\left\vert J_{i}\right\vert =\sum_{\circ\in I_{i}}\left(  h\left(
\circ\right)  -1\right)  $.
\end{itemize}

If $\left(  G,h\right)  $ is a decorated graph, and if $U$ is a subset of
$V_{\circ}$, then $\mathcal{V}\left(  U\right)  $ shall mean the set of all
vertices of $G$ that have at least one neighbor in $U$. This $\mathcal{V}%
\left(  U\right)  $ is a subset of $V_{\bullet}$.

[Previously, the sum was $\sum_{k\geq0}\left(  -1\right)  ^{k}\sum
_{\substack{\left(  \left(  I_{0},I_{1},\ldots,I_{k}\right)  ,\left(
J_{0},J_{1},\ldots,J_{k}\right)  \right)  \text{ is an}\\h\text{-equitable
proper }k\text{-biflag of }\left(  V_{\circ},V_{\bullet}\right)  }}\left[
\mathcal{V}\left(  I_{j}\right)  \subseteq J_{j}\text{ for all }j\in\left\{
0,1,\ldots,k\right\}  \right]  $.]
\end{noncompile}

I can prove the following fact:

\begin{proposition}
\label{prop.semi-exp-form}Let $\left(  G,h\right)  $ be a decorated graph that
is a semi-expander. Then,%
\begin{align*}
&  \sum_{k\geq0}\left(  -1\right)  ^{k}\sum_{\substack{\varphi:V_{\circ}\sqcup
V_{\bullet}\rightarrow\mathbb{N}^{\ast}\text{ is }k\text{-packed}\\\text{and
}h\text{-equitable}}}\left[  \varphi\text{ is increasing on }G\right] \\
&  =\left(  -1\right)  ^{\operatorname*{Con}\left(  G\right)  }\left[  \left(
G,h\right)  \text{ is an expander}\right]  .
\end{align*}
(Here, as usual, the Iverson bracket notation $\left[  \mathcal{A}\right]  $
for the truth value of a statement $\mathcal{A}$ is used; you seem to call it
$\delta_{\mathcal{A}}$.)
\end{proposition}

How does this proposition help?

It lets us deduce your Proposition 3.38 easily from a variant of your
Proposition 3.19\footnote{Here is the variant I am talking about:
\par
Let us use the notation of your Proposition 3.19. Let $\varphi:V_{\circ}\sqcup
V_{\bullet}\rightarrow\mathbb{N}^{\ast}$ be any map. Then,%
\[
\sum_{E^{\prime}\subseteq E_{\overrightarrow{C}}}\left(  -1\right)
^{\left\vert E^{\prime}\right\vert }\left[  \varphi\text{ is increasing on
}G\setminus E^{\prime}\right]  =0.
\]
(Of course, the proof of this is similar to the proof of your Proposition
3.19.)} \textbf{under the extra assumption that all the }$\left(  G\setminus
E^{\prime},h\right)  $ \textbf{involved are semi-expanders}. This obnoxious
assumption is what stands between this approach and a self-contained proof of
your Proposition 3.38.\footnote{Moreover, if we can somehow get this
assumption lifted, then we might also be able to simplify your argument: Your
approach is to prove Proposition 3.38 and then use it to define a linear
functional $I_{\nu}$ (on the space of all polynomials in the variables
$p_{1},p_{2},p_{3},\ldots,q_{1},q_{2},q_{3},\ldots$) that satisfies
\begin{equation}
I_{\nu}\left(  N_{G}\right)  =I_{\nu}\left(  G\right)
\ \ \ \ \ \ \ \ \ \ \text{for each bipartite graph }G.\label{eq.approach.1}%
\end{equation}
I believe that this detour is unnecessary: We should instead be able to define
the linear functional $I_{\nu}$ directly, and then use it to prove Proposition
3.38. Thus, the problem is shifted to defining $I_{\nu}$. Again, this could be
done if not for the \textquotedblleft semi-expander\textquotedblright%
\ assumption in Proposition \ref{prop.semi-exp-form}.}

\begin{noncompile}
Well, let $P$ be the space of all polynomials in the variables $p_{1}%
,p_{2},p_{3},\ldots,q_{1},q_{2},q_{3},\ldots$. Monomials in $P$ have the form
$\mathbf{p}^{a}\mathbf{q}^{b}$, where $a=\left(  a_{1},a_{2},a_{3}%
,\ldots\right)  $ and $b=\left(  b_{1},b_{2},b_{3},\ldots\right)  $ are
finitely supported sequences of nonnegative integers, and where $\mathbf{p}%
^{a}=p_{1}^{a_{1}}p_{2}^{a_{2}}p_{3}^{a_{3}}\cdots$ and $\mathbf{q}^{b}%
=q_{1}^{b_{1}}q_{2}^{b_{2}}q_{3}^{b_{3}}\cdots$. We can try to define a linear
functional $I_{\nu}$ on this vector space $P$ as follows: For any monomial
$\mathbf{p}^{a}\mathbf{q}^{b}\in P$, we fix some $\left(  a_{1}+a_{2}%
+a_{3}+\cdots\right)  $-element set $V_{\circ}$ and some $\left(  b_{1}%
+b_{2}+b_{3}+\cdots\right)  $-element set $V_{\bullet}$, and we set
\[
I_{\nu}\left(  \mathbf{p}^{a}\mathbf{q}^{b}\right)  =\sum
_{\substack{h:V_{\circ}\rightarrow\left\{  2,3,4,\ldots\right\}  ;\\h\text{
has type }\nu}}\sum_{k\geq0}\left(  -1\right)  ^{k}\sum_{\substack{\varphi
:V_{\circ}\sqcup V_{\bullet}\rightarrow\mathbb{N}^{\ast}\text{ is
}k\text{-packed}\\\text{and }h\text{-equitable}}}\left[  \mathbf{p}%
^{a}\mathbf{q}^{b}=\prod_{\circ\in V_{\circ}}p_{\varphi\left(  \circ\right)
}\prod_{\bullet\in V_{\bullet}}q_{\varphi\left(  \bullet\right)  }\right]  .
\]
(Here, the \textit{type} of a map $h:V_{\circ}\rightarrow\left\{
2,3,4,\ldots\right\}  $ means the partition obtained by sorting the multiset
$h\left(  V_{\circ}\right)  $.)

This map $I_{\nu}$ has the property that every semi-expander $\left(
G,h\right)  $ satisfie... Wait, not quite. This is not quite correct.
\end{noncompile}

My questions thus are the following:

\begin{itemize}
\item \textbf{Question 1:} Can we find a formula similar to Proposition
\ref{prop.semi-exp-form} but without requiring $\left(  G,h\right)  $ to be a
semi-expander? This formula would represent $\left(  -1\right)
^{\operatorname*{Con}\left(  G\right)  }\left[  \left(  G,h\right)  \text{ is
an expander}\right]  $ as a linear combination of terms of the form $\left[
\varphi\text{ is increasing on }G\right]  $ for varying $\varphi:V_{\circ
}\sqcup V_{\bullet}\rightarrow\mathbb{N}^{\ast}$ (with coefficients dependent
on $h$ but independent of $G$). Thus, roughly speaking, we want to tell if
$\left(  G,h\right)  $ is an expander (and whether it has an even or an odd
number of connected components) by probing lots of maps $\varphi:V_{\circ
}\sqcup V_{\bullet}\rightarrow\mathbb{N}^{\ast}$ for their increasingness on
$G$.

\item \textbf{Question 2:} My proof of Proposition \ref{prop.semi-exp-form} is
not as simple as I'd prefer it to be. It starts by showing that the set of all
subsets $V$ of $V_{\circ}$ satisfying $\left\vert \overline{\mathcal{V}\left(
V\right)  }\right\vert =\sum_{\circ\in V}h\left(  \circ\right)  $ is a
sublattice of the Boolean lattice of all subsets of $V_{\circ}$%
\ \ \ \ \footnote{This is actually a particular case of a known fact about
cuts in networks: See, e.g., Exercise 7 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/hw5s.pdf}{UMN Math 5707
Spring 2017 homework set \#5}.}. Then, it proceeds by observing that this
sublattice is a Boolean lattice of rank $\operatorname*{Con}\left(  G\right)
$ if $\left(  G,h\right)  $ is an expander, and otherwise has some
behavior\footnote{Specifically: It is a bounded lattice that is not
complemented.} which quickly dooms it to having M\"{o}bius function $0$;
therefore, its M\"{o}bius function is always $\left(  -1\right)
^{\operatorname*{Con}\left(  G\right)  }\left[  \left(  G,h\right)  \text{ is
an expander}\right]  $. Finally, Proposition \ref{prop.semi-exp-form} is
obtained from this by comparing this with another evaluation of the M\"{o}bius
function, viz. Philip Hall's theorem (Proposition 3.8.5 in
\href{http://www-math.mit.edu/~rstan/ec/ec1/}{Stanley's \textit{Enumerative
Combinatorics volume 1}}), and re-encoding it via decreasing maps.

I suspect that there should be an easier proof, using a sign-reversing
involution with few fixed points (the way such identities are usually proven
in combinatorics). The involution should probably act on the set
\[
\bigsqcup_{k\geq0}\left\{  h\text{-equitable }k\text{-packed maps }%
\varphi:V_{\circ}\sqcup V_{\bullet}\rightarrow\mathbb{N}^{\ast}\text{ that are
increasing on }G\right\}  .
\]
I furthermore would not be surprised if the involution uses what
\href{https://arxiv.org/abs/1410.5023v4}{Benedetti and Sagan
(arXiv:1410.5023v4)} call the \textquotedblleft split-merge
technique\textquotedblright: i.e.,

\begin{itemize}
\item under some conditions (the \textquotedblleft splitting
case\textquotedblright), the involution maps a $k$-packed map $\varphi$ to a
$\left(  k+1\right)  $-packed map $\varphi^{\prime}$ given by
\[
\varphi^{\prime}\left(  v\right)  =%
\begin{cases}
\varphi\left(  v\right)  , & \text{if }\varphi\left(  v\right)  <i\text{;}\\
i, & \text{if }\varphi\left(  v\right)  =i\text{ and }\mathcal{C}\left(
v\right)  \text{ holds;}\\
i+1, & \text{if }\varphi\left(  v\right)  =i\text{ and }\mathcal{C}\left(
v\right)  \text{ does not hold;}\\
\varphi\left(  v\right)  +1, & \text{if }\varphi\left(  v\right)  >i
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }v\in V_{\circ}\sqcup V_{\bullet}%
\]
where $i$ is some number and $\mathcal{C}$ is some predicate;

\item under some other conditions (the \textquotedblleft merging
case\textquotedblright), the involution maps a $k$-packed map $\varphi$ to a
$\left(  k-1\right)  $-packed map $\varphi^{\prime}$ given by
\[
\varphi^{\prime}\left(  v\right)  =%
\begin{cases}
\varphi\left(  v\right)  , & \text{if }\varphi\left(  v\right)  <i\text{;}\\
i, & \text{if }\varphi\left(  v\right)  \in\left\{  i,i+1\right\}  \text{;}\\
\varphi\left(  v\right)  -1, & \text{if }\varphi\left(  v\right)  >i+1
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }v\in V_{\circ}\sqcup V_{\bullet}%
\]
where $i$ is some number;

\item in the remaining (rare) cases, the involution sends $\varphi$ to
$\varphi$.
\end{itemize}

If we are lucky, then this involution might generalize to an answer to
Question 1 as well.
\end{itemize}


\end{document}