\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, December 10, 2020 23:10:24}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\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{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\lf}[2]{{#1}^{\underline{#2}}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand\staircasepath[4]{
\fill[cyan!25] (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
-- ++(0,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\draw[dashed] (#1) -- +(#2,#2);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\coordinate (dep) at (0,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\delannoypath[4]{
\fill[cyan!25] (#1) rectangle +(#2,#3);
\fill[fill=lime]
(#1)
\foreach \dir in {#4}{
\ifnum\dir=1
-- ++(1,0)
\else
\ifnum\dir=0
-- ++(0,1)
\else
-- ++(1,1)
\fi
\fi
} |- (#1);
\draw[help lines] (#1) grid +(#2,#3);
\coordinate (prev) at (#1);
\foreach \dir in {#4}{
\ifnum\dir=1
\coordinate (dep) at (1,0);
\else
\ifnum\dir=0
\coordinate (dep) at (0,1);
\else
\coordinate (dep) at (1,1);
\fi
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\newcommand\dyckpath[3]{
\fill[fill=lime]
(#1)
\foreach \dir in {#3}{
\ifnum\dir=1
-- ++(1,-1)
\else
-- ++(1,1)
\fi
} |- (#1);
\draw[help lines] (#1) grid +(2*#2, #2);
\coordinate (prev) at (#1);
\foreach \dir in {#3}{
\ifnum\dir=1
\coordinate (dep) at (1,-1);
\else
\coordinate (dep) at (1,1);
\fi
\draw[line width=2pt,-stealth] (prev) -- ++(dep) coordinate (prev);
};
}
\ihead{Math 4707 Spring 2018 (Darij Grinberg): homework set 5}
\ohead{page \thepage}
\cfoot{}
\begin{document}
\begin{center}
\textbf{Math 4707 Spring 2018 (Darij Grinberg): homework set 5 with solutions
[preliminary version]}
\end{center}
%
%TCIMACRO{\TeXButton{tableofcontents}{\tableofcontents}}%
%BeginExpansion
\tableofcontents
%EndExpansion
\bigskip
\begin{noncompile}
Recall the following:
\begin{itemize}
\item If $S$ is a set, and if $k\in\mathbb{N}$, then $\mathcal{P}_{k}\left(
S\right) $ denotes the set of all $k$-element subsets of $S$.
\item A \textit{graph} (or \textit{multigraph}) is a triple $\left(
V,E,\varphi\right) $, where $V$ and $E$ are two finite sets, and where
$\varphi$ is a map from $E$ to $\mathcal{P}_{2}\left( V\right) $. If
$G=\left( V,E,\varphi\right) $ is a graph, then
\begin{itemize}
\item the elements of $V$ are called the \textit{vertices} of $G$;
\item the elements of $E$ are called the \textit{edges} of $G$;
\item the \textit{endpoints} of an edge $e\in E$ are defined to be the two
elements of $\varphi\left( e\right) $;
\item we say that an edge $e\in E$ \textit{joins} the two endpoints of $e$.
\end{itemize}
\item We visualize a graph $G$ as follows:
\begin{itemize}
\item For each vertex $v$ of $G$, choose some point that will represent $v$.
Mark this point with a $v$ (and possibly with a circle).
\item For each edge $e$ of $G$, draw a curve connecting the points
representing the two endpoints of $e$. Label this curve with an $e$.
\end{itemize}
Often, we omit the markings of the points and the labelings of the edges, as
we often don't care about the precise identities of the vertices and edges of
$G$.
\item A \textit{simple graph} is a pair $\left( V,E\right) $, where $V$ is a
finite set, and where $E$ is a subset of $\mathcal{P}_{2}\left( V\right) $.
If $G=\left( V,E\right) $ is a simple graph, then we identify $G$ with the
multigraph $\left( V,E,\iota\right) $, where $\iota:E\rightarrow
\mathcal{P}_{2}\left( V\right) $ is the map sending each $e\in E$ to $e$
(this would be the identity map, if not for the fact that $E\neq
\mathcal{P}_{2}\left( V\right) $ usually).
\end{itemize}
\end{noncompile}
For the notations that we will use, we refer to
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/hw2s.pdf}{Spring 2017 Math
5707 Homework set \#2} and to classwork. The word \textquotedblleft
graph\textquotedblright\ means \textquotedblleft multigraph\textquotedblright%
\ unless it appears as part of \textquotedblleft simple
graph\textquotedblright. Here are the notations that I did not introduce in class:
\begin{itemize}
\item A two-element set $\left\{ u,v\right\} $ will be denoted by $uv$ when
no confusion can arise. This will be mostly used for two-element sets that
appear as edges in simple graphs (or as images of edges in multigraphs). For
example, the simple graph%
\[%
%TCIMACRO{\TeXButton{TeX field}{\xymatrix{
%1 \are[r] \are[rd] & 4 \are[rd] \are[r] & 5 \\
%& 3 \are[r] & 6
%}}}%
%BeginExpansion
\xymatrix{
1 \are[r] \are[rd] & 4 \are[rd] \are[r] & 5 \\
& 3 \are[r] & 6
}%
%EndExpansion
\]
has edges $13,14,36,45,46$.
\item The set of all vertices of a graph $G$ is called the \textit{vertex set}
of $G$, and is denoted by $\operatorname*{V}\left( G\right) $.
The set of all edges of a graph $G$ is called the \textit{edge set} of $G$,
and is denoted by $\operatorname*{E}\left( G\right) $.
\item If $v$ is a vertex and $e$ is an edge of a graph $\left( V,E,\varphi
\right) $, then we say that $v$ \textit{belongs to} $e$ (or, equivalently,
$e$ \textit{contains }$v$) if $v$ is an endpoint of $e$ (that is, $v\in
\varphi\left( e\right) $).
\end{itemize}
\subsection{Perfect matchings of a $2\times n$ grid}
\begin{definition}
\label{def.graphs.path-graph}Let $n\in\mathbb{N}$. Then, the \textit{path
graph} $P_{n}$ is defined to be the simple graph whose vertices are the $n$
numbers $1,2,\ldots,n$, and whose edges are $\left\{ 1,2\right\} ,\left\{
2,3\right\} ,\ldots,\left\{ n-1,n\right\} $. Here is how it looks like:%
\[%
%TCIMACRO{\TeXButton{TeX field}{\xymatrix{
%1 \are[r] & 2 \are[r] & \cdots\are[r] & n
%}}}%
%BeginExpansion
\xymatrix{
1 \are[r] & 2 \are[r] & \cdots\are[r] & n
}%
%EndExpansion
\]
\end{definition}
\begin{definition}
Let $G$ and $H$ be two simple graphs. The \textit{Cartesian product} of $G$
and $H$ is a new simple graph, denoted $G\times H$, which is defined as follows:
\begin{itemize}
\item The vertex set $\operatorname{V}\left( G\times H\right) $ of $G\times
H$ is the Cartesian product $\operatorname{V}\left( G\right) \times
\operatorname{V}\left( H\right) $. (So the vertices of $G\times H$ are all
pairs of the form $\left( v,w\right) $, where $v$ is a vertex of $G$ and $w$
is a vertex of $H$.)
\item A vertex $\left( g,h\right) $ of $G\times H$ is adjacent to a vertex
$\left( g^{\prime},h^{\prime}\right) $ of $G\times H$ if and only if we have%
\[
\text{\textbf{either} }\left( g=g^{\prime}\text{ and }hh^{\prime}%
\in\operatorname*{E}\left( H\right) \right) \text{\textbf{ or }}\left(
h=h^{\prime}\text{ and }gg^{\prime}\in\operatorname*{E}\left( G\right)
\right) .
\]
(In particular, exactly one of the two equalities $g=g^{\prime}$ and
$h=h^{\prime}$ has to hold when $\left( g,h\right) $ is adjacent to $\left(
g^{\prime},h^{\prime}\right) $.)
\end{itemize}
\end{definition}
\begin{definition}
Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. The \textit{grid graph} $G_{n,m}$
is defined to be the Cartesian product $P_{n}\times P_{m}$.
\end{definition}
Here is how the grid graph $G_{3,4}$ looks like:%
\[%
%TCIMACRO{\TeXButton{grid graph 3,4}{\xymatrix{
%\tup{1,1} \are[r] \are[d] & \tup{1,2} \are[r] \are[d] & \tup{1,3} \are
%[r] \are[d] & \tup{1,4} \are[d] \\
%\tup{2,1} \are[r] \are[d] & \tup{2,2} \are[r] \are[d] & \tup{2,3} \are
%[r] \are[d] & \tup{2,4} \are[d] \\
%\tup{3,1} \are[r] & \tup{3,2} \are[r] & \tup{3,3} \are[r] & \tup{3,4}
%}}}%
%BeginExpansion
\xymatrix{
\tup{1,1} \are[r] \are[d] & \tup{1,2} \are[r] \are[d] & \tup{1,3} \are
[r] \are[d] & \tup{1,4} \are[d] \\
\tup{2,1} \are[r] \are[d] & \tup{2,2} \are[r] \are[d] & \tup{2,3} \are
[r] \are[d] & \tup{2,4} \are[d] \\
\tup{3,1} \are[r] & \tup{3,2} \are[r] & \tup{3,3} \are[r] & \tup{3,4}
}%
%EndExpansion
\]
(Check that you understand how the definition of a Cartesian product of two
graphs causes it to look like this.) For arbitrary $n,m\in\mathbb{N}$, the
grid graph $G_{n,m}$ is the simple graph whose vertex set is $\left[
n\right] \times\left[ m\right] $, and whose edges have the form%
\begin{align*}
\left( i,j\right) \left( i+1,j\right) \ \ \ \ \ \ \ \ \ \ \text{for }i &
\in\left[ n-1\right] \text{ and }j\in\left[ m\right] \text{,}%
\ \ \ \ \ \ \ \ \ \ \text{and}\\
\left( i,j\right) \left( i,j+1\right) \ \ \ \ \ \ \ \ \ \ \text{for }i &
\in\left[ n\right] \text{ and }j\in\left[ m-1\right] .
\end{align*}
Two edges of a graph $G$ are said to be \textit{disjoint} if they have no
common endpoint. A\textit{ matching} of a graph $G$ means a set of disjoint
edges of $G$. A \textit{perfect matching} of a graph $G$ means a matching $M$
of $G$ such that each vertex of $G$ belongs to exactly one edge in $M$. For
example,%
\[
\left\{ \left( 1,1\right) \left( 1,2\right) ,\ \ \left( 1,3\right)
\left( 1,4\right) ,\ \ \left( 2,1\right) \left( 3,1\right) ,\ \ \left(
2,2\right) \left( 2,3\right) ,\ \ \left( 3,2\right) \left( 3,3\right)
,\ \ \left( 2,4\right) \left( 3,4\right) \right\}
\]
is a perfect matching of the grid graph $G_{3,4}$ shown above; let me
visualize this matching by drawing only the edges of this matching (omitting
all the other edges):%
\[%
%TCIMACRO{\TeXButton{grid graph 3,4}{\xymatrix{
%\tup{1,1} \are[r] & \tup{1,2} & \tup{1,3} \are[r] & \tup{1,4} \\
%\tup{2,1} \are[d] & \tup{2,2} \are[r] & \tup{2,3} & \tup{2,4} \are[d] \\
%\tup{3,1} & \tup{3,2} \are[r] & \tup{3,3} & \tup{3,4}
%}}}%
%BeginExpansion
\xymatrix{
\tup{1,1} \are[r] & \tup{1,2} & \tup{1,3} \are[r] & \tup{1,4} \\
\tup{2,1} \are[d] & \tup{2,2} \are[r] & \tup{2,3} & \tup{2,4} \are[d] \\
\tup{3,1} & \tup{3,2} \are[r] & \tup{3,3} & \tup{3,4}
}%
%EndExpansion
\]
\begin{exercise}
\label{exe.graph.perfect-matchings.grid}Let $n\in\mathbb{N}$. How many perfect
matchings does the grid graph $G_{2,n}$ have?
[\textbf{Hint:} This is something you know in disguise.]
\end{exercise}
\begin{proof}
[Hints to Exercise \ref{exe.graph.perfect-matchings.grid}.]We shall use the
notations of Exercise 5 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/hw1s.pdf}{homework set \#1}.
In particular, we recall that $R_{n,2}$ denotes the set $\left[ n\right]
\times\left[ 2\right] $, regarded as a rectangle of width $n$ and height
$2$. We know from class that the number of domino tilings of $R_{n,2}$ is the
Fibonacci number $f_{n+1}$.
But there is a bijection%
\[
\left\{ \text{perfect matchings of }G_{2,n}\right\} \rightarrow\left\{
\text{domino tilings of }R_{n,2}\right\} .
\]
(This bijection acts by replacing each edge $\left( i,j\right) \left(
u,v\right) $ by the domino $\left\{ \left( j,i\right) ,\left( v,u\right)
\right\} $. For example, for $n=5$, it maps the perfect matching%
\[%
%TCIMACRO{\TeXButton{grid graph 2,5 with PM}{\xymatrix{
%\tup{1,1} \are[d] & \tup{1,2} \are[r] & \tup{1,3} & \tup{1,4} \are
%[d] & \tup{1,5} \are[d] \\
%\tup{2,1} & \tup{2,2} \are[r] & \tup{2,3} & \tup{2,4} & \tup{2,5}
%}}}%
%BeginExpansion
\xymatrix{
\tup{1,1} \are[d] & \tup{1,2} \are[r] & \tup{1,3} & \tup{1,4} \are
[d] & \tup{1,5} \are[d] \\
\tup{2,1} & \tup{2,2} \are[r] & \tup{2,3} & \tup{2,4} & \tup{2,5}
}%
%EndExpansion
\]
to the domino tiling
\[%
%TCIMACRO{\TeXButton{tabular}{\begin{tabular}{ | c | c | c | c | c | }
%\hline\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a}
%& \phantom{a} & \phantom{a} \\ \cline{2-3}
%\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a} & \phantom{a}
%& \phantom{a}
%\\ \hline\end{tabular}}}%
%BeginExpansion
\begin{tabular}{ | c | c | c | c | c | }
\hline\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a}
& \phantom{a} & \phantom{a} \\ \cline{2-3}
\phantom{a} & \multicolumn{1}{ c}{\phantom{a}} & \phantom{a} & \phantom{a}
& \phantom{a}
\\ \hline\end{tabular}%
%EndExpansion
\ \ \ \ \ \ \ \ \ \ \text{.)}%
\]
This bijection shows that the number of perfect matchings of $G_{2,n}$ is the
number of domino tilings of $R_{n,2}$. But the latter number is the Fibonacci
number $f_{n+1}$. Hence, the number of perfect matchings of $G_{2,n}$ is
$f_{n+1}$.
\end{proof}
\subsection{Eulerian circuits of a windmill}
The concept of a circuit in a graph is somewhat ambiguous: In the graph%
\begin{equation}
\xymatrix{ 1 \are[r]^{a} \are[dr]_{c} \are[d]_{d} & 2 \are[d]^b \\ 4 & 3 },
\label{eq.circuit.ambig.ex1}%
\end{equation}
do you consider $\left( 1,a,2,b,3,c,1\right) $ and $\left(
2,b,3,c,1,a,2\right) $ as the same circuit? What about $\left(
1,a,2,b,3,c,1\right) $ and $\left( 1,c,3,b,2,a,1\right) $ ? According to
our definition of a circuit (we defined it as a specific kind of walk), the
answer is \textquotedblleft no\textquotedblright\ in both cases:%
\[
\left( 2,b,3,c,1,a,2\right) \neq\left( 1,a,2,b,3,c,1\right) \neq\left(
1,c,3,b,2,a,1\right) .
\]
But most people would like to equate $\left( 1,a,2,b,3,c,1\right) $ with
$\left( 2,b,3,c,1,a,2\right) $, at the very least, since these are
\textquotedblleft the same circuit with different starting
points\textquotedblright. So they say \textquotedblleft
circuit\textquotedblright\ but really mean \textquotedblleft equivalence class
of circuits with respect to cyclic rotation (and perhaps mirror
reflection)\textquotedblright. This is all irrelevant as long as we just
discuss the \textbf{existence} of circuits; but when we start
\textbf{counting} circuits, it becomes important. Depending on how circuits
are defined, the graph (\ref{eq.circuit.ambig.ex1}) has either $6$ or $3$ or
$2$ or $1$ cycles (which, as you remember, are circuits satisfying some
conditions). According to our definition (which I don't want to change), it
has $6$ cycles.
\begin{definition}
Let $G$ be a graph.
\textbf{(a)} A walk $\left( v_{0},e_{1},v_{1},e_{2},v_{2},\ldots
,v_{k-1},e_{k},v_{k}\right) $ of $G$ is said to be \textit{Eulerian} if each
edge of $G$ appears exactly once among the $k$ edges $e_{1},e_{2},\ldots
,e_{k}$.
\textbf{(b)} Let $\mathbf{w}=\left( v_{0},e_{1},v_{1},e_{2},v_{2}%
,\ldots,v_{k-1},e_{k},v_{k}\right) $ be a walk of $G$. Then, $k$ is called
the \textit{length} of $\mathbf{w}$. If $k>0$, then $e_{1}$ is called the
\textit{starting edge} of $\mathbf{w}$.
\end{definition}
Counting all Eulerian circuits of a graph is usually difficult. For example,
the number of Eulerian circuits in a complete graph $K_{n}$ grows very fast
with $n$ and doesn't have a known expression (see
\href{https://oeis.org/A007082}{sequence A007082 in the OEIS} for the values
when $n$ is odd; of course, the values when $n$ is even are $0$).
\Needspace{8cm}
\begin{exercise}
\label{exe.eulerian-circuits.count.windmill}Let $g$ be a positive integer. Let
$G$ be the simple graph whose vertices are the $2g+1$ integers $-g,-g+1,\ldots
,g-1,g$, and whose edges are
\begin{align*}
& \left\{ 0,i\right\} \qquad\text{ for all }i\in\left\{ 1,2,\ldots
,g\right\} ;\\
& \left\{ 0,-i\right\} \qquad\text{ for all }i\in\left\{ 1,2,\ldots
,g\right\} ;\\
& \left\{ i,-i\right\} \qquad\text{ for all }i\in\left\{ 1,2,\ldots
,g\right\}
\end{align*}
(these are $3g$ edges in total).
[Here is how $G$ looks like in the case when $g=4$:
\begin{equation}
\xymatrix{ & 1 \are[ddr] \are[rr] & & -1 \are[ddl] \\ -4 \are[dd] \are[drr] & & & & 2 \are[dd] \\ & & 0 \are[urr] \are[drr] \are[dll] \are[ddl] \are[ddr] \\ 4 & & & & -2 \\ & -3 \are[rr] & & 3 }
\label{eq.exe.eulerian-circuits.count.windmill.g=4}%
\end{equation}
]
\textbf{(a)} Find the number of Eulerian circuits of $G$ whose starting point
is $0$ and whose starting edge is $\left\{ 0,1\right\} $.
\textbf{(b)} Find the number of Eulerian circuits of $G$ whose starting point
is $0$.
\end{exercise}
\begin{proof}
[Hints to Exercise \ref{exe.eulerian-circuits.count.windmill}.]We shall refer
to the $g$ sets $\left\{ 0,1,-1\right\} $, $\left\{ 0,2,-2\right\} $,
$\ldots$, $\left\{ 0,g,-g\right\} $ as the \textit{triangles}.
\textbf{(b)} An Eulerian circuit of $G$ whose starting point is $0$ must have
the following form: Start at $0$, traverse some triangle, come back to $0$,
traverse another triangle, come back to $0$, traverse another triangle, and so
on, until each triangle has been traversed exactly once. (No other Eulerian
circuits are possible, because there is no way to \textquotedblleft
escape\textquotedblright\ a triangle short of fully traversing it.)
Thus, in order to construct an Eulerian circuit of $G$ whose starting point is
$0$, we need to decide in what order it should traverse the $g$ triangles, and
moreover, for each triangle $\left\{ 0,i,-i\right\} $, we need to decide
whether it shall traverse it \textquotedblleft clockwise\textquotedblright%
\ (that is, $0\rightarrow i\rightarrow-i\rightarrow0$) or \textquotedblleft
counterclockwise\textquotedblright\ (that is, $0\rightarrow-i\rightarrow
i\rightarrow0$). The first of these decisions can be made in $g!$ many ways;
the second in $2^{g}$ many ways (since there are two choices for each of the
$g$ triangles). Thus, the number of Eulerian circuits of $G$ whose starting
point is $0$ is $g!\cdot2^{g}$.
\textbf{(a)} The number of Eulerian circuits of $G$ whose starting point is
$0$ and whose starting edge is $\left\{ 0,1\right\} $ is $\left(
g-1\right) !\cdot2^{g-1}$. Indeed, the same argument as used for part
\textbf{(b)} applies here, except that we are somewhat restricted in our
decision, since our circuit must begin with the triangle $\left\{
0,1,-1\right\} $ and it must traverse this triangle \textquotedblleft
clockwise\textquotedblright.
\end{proof}
\subsection{Counting walks in a graph}
A graph always has a finite number of paths (since a path can never have more
vertices than the graph has), but usually has an infinite number of walks
(indeed, if the graph has a cycle, then you can build arbitrarily long walks
by walking along this cycle over and over). Nevertheless, walks are much
easier to count than paths. The next exercise states a formula for the number
of walks of a given length between two given vertices in terms of the
\textit{adjacency matrix} of a graph. This matrix is an important
representation of a graph.
\begin{definition}
\label{def.matrix.Aij}Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$. Let $A$ be an
$n\times m$-matrix. Let $i\in\left[ n\right] $ and $j\in\left[ m\right] $.
Then, $A_{i,j}$ will denote the $\left( i,j\right) $-th entry of $A$.
\end{definition}
\begin{definition}
Let $G=\left( V,E,\varphi\right) $ be a graph. Assume that $V=\left[
n\right] $ for some $n\in\mathbb{N}$. Then, the \textit{adjacency matrix} of
$G$ is defined as the $n\times n$-matrix whose $\left( i,j\right) $-th entry
(for each $i\in\left[ n\right] $ and $j\in\left[ n\right] $) is the number
of edges whose endpoints are $i$ and $j$.
\end{definition}
For example, the graph%
\begin{equation}
\xymatrix{ 1 \are[dr] \are@/^/[r] \are@/_/[r] & 2 \are[d] \are[r] & 4 \\ & 3 }
\label{eq.adjmat.ex1.G}%
\end{equation}
has adjacency matrix%
\[
\left(
\begin{array}
[c]{cccc}%
0 & 2 & 1 & 0\\
2 & 0 & 1 & 1\\
1 & 1 & 0 & 0\\
0 & 1 & 0 & 0
\end{array}
\right) .
\]
Clearly, the adjacency matrix of a graph $G=\left( V,E,\varphi\right) $ with
$V=\left[ n\right] $ is symmetric. Furthermore, this adjacency matrix
\textquotedblleft encodes\textquotedblright\ the whole structure of $G$ apart
from the identities of the edges.
\begin{exercise}
\label{exe.graph.count-walks}Let $G=\left( V,E,\varphi\right) $ be a graph.
Assume that $V=\left[ n\right] $ for some $n\in\mathbb{N}$. Let $A$ be the
adjacency matrix of $G$. Let $i\in\left[ n\right] $ and $j\in\left[
n\right] $ and $k\in\mathbb{N}$. Prove that $\left( A^{k}\right) _{i,j}$ is
the number of walks from $i$ to $j$ that have length $k$.
\end{exercise}
Exercise \ref{exe.graph.count-walks} is a fundamental result. For example, it
appears in \cite[Theorem 1.1]{Stanle13}. The simplest proof uses induction:
\begin{proof}
[Solution to Exercise \ref{exe.graph.count-walks} (sketched).]Forget that we
fixed $i$, $j$ and $k$. We want to prove the following claim:
\begin{statement}
\textit{Claim 1:} Let $i\in\left[ n\right] $ and $j\in\left[ n\right] $
and $k\in\mathbb{N}$. Then,%
\[
\left( A^{k}\right) _{i,j}=\left( \text{the number of walks from }i\text{
to }j\text{ that have length }k\right) .
\]
\end{statement}
Before we prove this claim, let us recall that $A$ is the adjacency matrix of
$G$. Thus, for each $i\in\left[ n\right] $ and $j\in\left[ n\right] $, we
have%
\[
A_{i,j}=\left( \text{the number of edges whose endpoints are }i\text{ and
}j\right)
\]
(by the definition of the adjacency matrix). Renaming $i$ as $w$ in this
statement, we obtain the following: For each $w\in\left[ n\right] $ and
$j\in\left[ n\right] $, we have%
\begin{equation}
A_{w,j}=\left( \text{the number of edges whose endpoints are }w\text{ and
}j\right) . \label{sol.graph.count-walks.Aij=}%
\end{equation}
Let us also recall that any two $n\times n$-matrices $B$ and $C$ satisfy
\begin{equation}
\left( BC\right) _{i,j}=\sum_{w=1}^{n}B_{i,w}C_{w,j}
\label{sol.graph.count-walks.mmult}%
\end{equation}
for any $i\in\left[ n\right] $ and $j\in\left[ n\right] $. (Indeed, this
is just the rule for how matrices are multiplied.)
We can now prove Claim 1:
[\textit{Proof of Claim 1:} We shall prove Claim 1 by induction on $k$:
\textit{Induction base:} We shall first prove Claim 1 for $k=0$.
Indeed, let $i\in\left[ n\right] $ and $j\in\left[ n\right] $. For any two
objects $u$ and $v$, we let $\delta_{u,v}=\left[ u=v\right] $ (where we are
using the Iverson bracket notation). Then, the $n\times n$ identity matrix
$I_{n}$ satisfies $\left( I_{n}\right) _{i,j}=\delta_{i,j}$ (by the
definition of the identity matrix). Hence, $\left( I_{n}\right)
_{i,j}=\delta_{i,j}=\left[ i=j\right] $ (by the definition of $\delta_{i,j}%
$). But the $0$-th power of any $n\times n$-matrix is defined to be the
$n\times n$ identity matrix $I_{n}$; thus, $A^{0}=I_{n}$. Hence, $\left(
A^{0}\right) _{i,j}=\left( I_{n}\right) _{i,j}=\left[ i=j\right] $.
On the other hand, how many walks from $i$ to $j$ have length $0$ ? A walk
that has length $0$ must consist of a single vertex, which is simultaneously
the starting point and the ending point of this walk. Thus, a walk from $i$ to
$j$ that has length $0$ exists only when $i=j$, and in this case there is
exactly one such walk (namely, the walk $\left( i\right) $). Hence,%
\[
\left( \text{the number of walks from }i\text{ to }j\text{ that have length
}0\right) =%
\begin{cases}
1, & \text{if }i=j;\\
0, & \text{if }i\neq j
\end{cases}
=\left[ i=j\right] .
\]
Comparing this with the equality $\left( A^{0}\right) _{i,j}=\left[
i=j\right] $, we conclude that%
\begin{equation}
\left( A^{0}\right) _{i,j}=\left( \text{the number of walks from }i\text{
to }j\text{ that have length }0\right) .
\label{sol.graph.count-walks.goal.IB.1}%
\end{equation}
Now, forget that we fixed $i$ and $j$. We thus have proven
(\ref{sol.graph.count-walks.goal.IB.1}) for any $i\in\left[ n\right] $ and
$j\in\left[ n\right] $. In other words, Claim 1 holds for $k=0$. Thus, the
induction base is complete.
\textit{Induction step:} Let $g$ be a positive integer. Assume that Claim 1
holds for $k=g-1$. We must show that Claim 1 holds for $k=g$ as well.
We have assumed that Claim 1 holds for $k=g-1$. In other words, for any
$i\in\left[ n\right] $ and $j\in\left[ n\right] $, we have%
\[
\left( A^{g-1}\right) _{i,j}=\left( \text{the number of walks from }i\text{
to }j\text{ that have length }g-1\right) .
\]
Renaming $j$ as $w$ in this statement, we obtain the following: For any
$i\in\left[ n\right] $ and $w\in\left[ n\right] $, we have%
\begin{equation}
\left( A^{g-1}\right) _{i,w}=\left( \text{the number of walks from }i\text{
to }w\text{ that have length }g-1\right) .
\label{sol.graph.count-walks.goal.IH}%
\end{equation}
Each walk from $i$ to $j$ that has length $g$ has the form $\left(
v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{g-1},v_{g-1},e_{g},v_{g}\right) $ for
some vertices $v_{0},v_{1},\ldots,v_{g}$ of $G$ and some edges $e_{1}%
,e_{2},\ldots,e_{g}$ of $G$ satisfying $v_{0}=i$, $v_{g}=j$ and $\left(
\varphi\left( e_{h}\right) =\left\{ v_{h-1},v_{h}\right\} \text{ for all
}h\in\left[ g\right] \right) $. Thus, each such walk can be constructed by
the following algorithm:
\begin{itemize}
\item First, we choose a vertex $w$ of $G$ to serve as the vertex $v_{g-1}$
(that is, as the penultimate vertex of the walk). This vertex $w$ must belong
to $V=\left[ n\right] $.
\item Now, we choose the vertices $v_{0},v_{1},\ldots,v_{g-1}$ (that is, all
vertices of our walk except for the last one) and the edges $e_{1}%
,e_{2},\ldots,e_{g-1}$ (that is, all edges of our walk except for the last
one) in such a way that $v_{g-1}=w$. This is tantamount to choosing a walk
$\left( v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{g-1},v_{g-1}\right) $ from
$i$ to $w$ that has length $g-1$. This choice can be made in $\left(
A^{g-1}\right) _{i,w}$ many ways (because
(\ref{sol.graph.count-walks.goal.IH}) shows that the number of walks from $i$
to $w$ that have length $g-1$ is $\left( A^{g-1}\right) _{i,w}$).
\item We have now determined all but the last vertex and all but the last edge
of our walk $\left( v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{g},v_{g}\right)
$. We set the last vertex $v_{g}$ of our walk to be $j$. (This is the only
possible option, since our walk $\left( v_{0},e_{1},v_{1},e_{2},v_{2}%
,\ldots,e_{g-1},v_{g-1},e_{g},v_{g}\right) $ has to be a walk from $i$ to $j$.)
\item We choose the last edge $e_{g}$ of our walk. This edge $e_{g}$ must have
endpoints $v_{g-1}$ and $v_{g}$; in other words, it must have endpoints $w$
and $j$ (since $v_{g-1}=w$ and $v_{g}=j$). Thus, we need to choose an edge
whose endpoints are $w$ and $j$. This choice can be made in $A_{w,j}$ many
ways (because (\ref{sol.graph.count-walks.Aij=}) shows that the number of
edges whose endpoints are $w$ and $j$ is $A_{w,j}$).
\end{itemize}
Conversely, of course, this algorithm always constructs a walk from $i$ to $j$
that has length $g$, and different choices in the algorithm lead to distinct
walks. Thus, the total number of walks from $i$ to $j$ that have length $g$
equals the total number of choices in the algorithm. But the latter number is
$\sum_{w\in\left[ n\right] }\left( A^{g-1}\right) _{i,w}A_{w,j}$ (since
the algorithm first chooses a $w\in\left[ n\right] $, then involves a step
with $\left( A^{g-1}\right) _{i,w}$ choices, and then involves a step with
$A_{w,j}$ choices). Hence, the total number of walks from $i$ to $j$ that have
length $g$ is $\sum_{w\in\left[ n\right] }\left( A^{g-1}\right)
_{i,w}A_{w,j}$. In other words,%
\[
\left( \text{the number of walks from }i\text{ to }j\text{ that have length
}g\right) =\sum_{w\in\left[ n\right] }\left( A^{g-1}\right) _{i,w}%
A_{w,j}.
\]
Comparing this with%
\begin{align*}
\left( \underbrace{A^{g}}_{=A^{g-1}A}\right) _{i,j} & =\left(
A^{g-1}A\right) _{i,j}=\sum_{w=1}^{n}\left( A^{g-1}\right) _{i,w}A_{w,j}\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{by (\ref{sol.graph.count-walks.mmult})
(applied to }B=A^{g-1}\text{ and }C=A\text{)}\right) \\
& =\sum_{w\in\left[ n\right] }\left( A^{g-1}\right) _{i,w}A_{w,j},
\end{align*}
we obtain%
\begin{equation}
\left( A^{g}\right) _{i,j}=\left( \text{the number of walks from }i\text{
to }j\text{ that have length }g\right) .
\label{sol.graph.count-walks.goal.IG}%
\end{equation}
Now, forget that we fixed $i$ and $j$. We thus have proven
(\ref{sol.graph.count-walks.goal.IG}) for any $i\in\left[ n\right] $ and
$j\in\left[ n\right] $. In other words, Claim 1 holds for $k=g$. Thus, the
induction step is complete. Hence, Claim 1 is proven by induction.]
Exercise \ref{exe.graph.count-walks} follows immediately from Claim 1.
\end{proof}
\begin{remark}
There is an analogue of Exercise \ref{exe.graph.count-walks} for
multidigraphs. If $D$ is a multidigraph with vertices $1,2,\ldots,n$, then the
\textit{adjacency matrix} $A$ of $D$ is defined to be the $n\times n$-matrix
whose $\left( i,j\right) $-th entry (for each $i\in\left[ n\right] $ and
$j\in\left[ n\right] $) is the number of arcs with source $i$ and target
$j$. In general, this adjacency matrix $A$ is not symmetric. Now, if
$D=\left( V,A,\phi\right) $ is a multidigraph with $V=\left[ n\right] $
for some $n\in\mathbb{N}$ and with adjacency matrix $A$, and if $i\in\left[
n\right] $ and $j\in\left[ n\right] $ and $k\in\mathbb{N}$ are arbitrary,
then $\left( A^{k}\right) _{i,j}$ is the number of walks from $i$ to $j$
that have length $k$. The proof of this is completely analogous to the
solution of Exercise \ref{exe.graph.count-walks}.
\end{remark}
\subsection{Your friends have more friends than you (the \textquotedblleft
friendship paradox\textquotedblright)}
If $G$ is a graph, and if $v$ is a vertex of $G$, then $\deg v$ denotes the
degree of $v$ (that is, the number of edges of $G$ that contain $v$).
\begin{exercise}
\label{exe.friends-neighbors}Let $G=\left( V,E,\varphi\right) $ be a graph.
If $v\in V$ and $e\in E$ are such that $v\in\varphi\left( e\right) $ (that
is, the edge $e$ contains the vertex $v$), then we let $e/v$ denote the
endpoint of $e$ distinct from $v$. For each $v\in V$, we define a rational
number $q_{v}$ by
\[
q_{v}=\sum_{\substack{e\in E;\\v\in\varphi\left( e\right) }}\dfrac
{\deg\left( e/v\right) }{\deg v}.
\]
(Note that the denominator $\deg v$ on the right hand side is nonzero whenever
the sum is nonempty!)
[Roughly speaking, $q_{v}$ is the average degree of the neighbors of $v$. But
to be more precise, this is an average over all \textbf{edges} containing $v$,
not just over all \textbf{neighbors} of $v$; the degree of a neighbor of $v$
will factor in the stronger the more edges join this neighbor to $v$. When $v$
is an isolated vertex -- i.e., when $\deg v=0$ --, the number $q_{v}$ is $0$.]
Prove that%
\begin{equation}
\sum_{v\in V}q_{v}\geq\sum_{v\in V}\deg v.
\label{eq.exe.friends-neighbors.claim}%
\end{equation}
\end{exercise}
If the graph $G$ is a social network (vertices being people, and edges being
friendships), then the inequality (\ref{eq.exe.friends-neighbors.claim}) (when
divided by $\left\vert V\right\vert $) can be construed as saying
\textquotedblleft the average person is unpopular\textquotedblright, where
being \textquotedblleft unpopular\textquotedblright\ means that your average
friend has at least as many friends as you do. This is a slippery statement
(involving an average within an average) and needs to be interpreted
correctly: For example, in the graph
(\ref{eq.exe.eulerian-circuits.count.windmill.g=4}), the vertex $0$ has degree
$8$, while all other vertices have degree $2$; the corresponding numbers
$q_{v}$ are $q_{0}=2$ and $q_{v}=5$ (for $v\neq0$), respectively. Thus,
(\ref{eq.exe.friends-neighbors.claim}) says that%
\[
2+5+5+5+5+5+5+5+5\geq8+2+2+2+2+2+2+2+2,
\]
which indeed holds (fairly strongly). The vertex $0$, of course, is popular
(having $\deg0=8$ friends, whereas its average friend has $q_{0}=2$ friends),
but this is balanced out by the unpopularity of all the other vertices.
Note that (\ref{eq.exe.friends-neighbors.claim}) does \textbf{not} mean that
most vertices are unpopular. For example, if $G$ is the simple graph with $5$
vertices $1,2,3,4,5$ and all the $\dbinom{5}{2}=10$ possible edges between
them except for the edge $\left\{ 4,5\right\} $, then the vertices $1,2,3$
of $G$ are popular (a majority), while the vertices $4,5$ are unpopular.
Nevertheless, (\ref{eq.exe.friends-neighbors.claim}) holds here, since the
popularity of $1,2,3$ \textquotedblleft outweighs\textquotedblright\ the
unpopularity of $4,5$ when the appropriate averages are added. See
\href{https://en.wikipedia.org/wiki/Friendship_paradox}{the Wikipedia page for
the friendship paradox} for further discussion.
The solution to Exercise \ref{exe.friends-neighbors} relies on the following
basic inequality:
\begin{lemma}
\label{lem.ineq.x/y+y/x}Let $x$ and $y$ be two positive reals. Then,
$\dfrac{x}{y}+\dfrac{y}{x}\geq2$.
\end{lemma}
\begin{proof}
[Proof of Lemma \ref{lem.ineq.x/y+y/x}.]Straightforward computations reveal
that $\dfrac{x}{y}+\dfrac{y}{x}-2=\dfrac{\left( x-y\right) ^{2}}{xy}$. But
$\left( x-y\right) ^{2}\geq0$ (since the square of a real number is always
$\geq0$), and thus $\dfrac{\left( x-y\right) ^{2}}{xy}\geq0$ (since $x$ and
$y$ are positive). Thus, $\dfrac{x}{y}+\dfrac{y}{x}-2=\dfrac{\left(
x-y\right) ^{2}}{xy}\geq0$, so that $\dfrac{x}{y}+\dfrac{y}{x}\geq2$. This
proves Lemma \ref{lem.ineq.x/y+y/x}.
\end{proof}
\begin{proof}
[Solution to Exercise \ref{exe.friends-neighbors} (sketched).]We first observe
that every $e\in E$ satisfies%
\begin{equation}
\sum_{v\in\varphi\left( e\right) }\dfrac{\deg\left( e/v\right) }{\deg
v}\geq2. \label{sol.friends-neighbors.1}%
\end{equation}
[\textit{Proof of (\ref{sol.friends-neighbors.1}):} Let $e\in E$. Recall that
$\varphi\left( e\right) $ is a $2$-element subset of $V$. Thus, we can write
$\varphi\left( e\right) $ in the form $\varphi\left( e\right) =\left\{
p,q\right\} $ for two distinct elements $p$ and $q$ of $V$. Consider these
$p$ and $q$. Thus, $p$ and $q$ are the endpoints of the edge $e$. Hence,
$e/p=q$ (due to how we defined $e/p$) and $e/q=p$ (similarly). Also, the
vertex $p$ of $V$ belongs to at least one edge (namely, to the edge $e$);
thus, its degree is $\geq1$. In other words, $\deg p\geq1>0$. Similarly, $\deg
q>0$. Thus, Lemma \ref{lem.ineq.x/y+y/x} (applied to $x=\deg q$ and $y=\deg
p$) yields $\dfrac{\deg q}{\deg p}+\dfrac{\deg p}{\deg q}\geq2$.
But recall that $\varphi\left( e\right) =\left\{ p,q\right\} $, with $p$
and $q$ being distinct. Hence,
\begin{align*}
\sum_{v\in\varphi\left( e\right) }\dfrac{\deg\left( e/v\right) }{\deg v}
& =\dfrac{\deg\left( e/p\right) }{\deg p}+\dfrac{\deg\left( e/q\right)
}{\deg q}\\
& =\dfrac{\deg q}{\deg p}+\dfrac{\deg p}{\deg q}\ \ \ \ \ \ \ \ \ \ \left(
\text{since }e/p=q\text{ and }e/q=p\right) \\
& \geq2.
\end{align*}
This proves (\ref{sol.friends-neighbors.1}).]
On the other hand, the handshaking lemma (Proposition 6.3 in
\href{http://www.cip.ifi.lmu.de/~grinberg/t/18s/4707-2018apr2.pdf}{the
classwork from April 2nd}) yields
\begin{equation}
\sum_{v\in V}\deg v=2\left\vert E\right\vert .
\label{sol.friends-neighbors.hslem}%
\end{equation}
Now,%
\begin{align*}
\sum_{v\in V}\underbrace{q_{v}}_{\substack{=\sum_{\substack{e\in
E;\\v\in\varphi\left( e\right) }}\dfrac{\deg\left( e/v\right) }{\deg
v}\\\text{(by the definition of }q_{v}\text{)}}} & =\underbrace{\sum_{v\in
V}\sum_{\substack{e\in E;\\v\in\varphi\left( e\right) }}}_{=\sum_{e\in
E}\sum_{\substack{v\in V;\\v\in\varphi\left( e\right) }}}\dfrac{\deg\left(
e/v\right) }{\deg v}=\sum_{e\in E}\underbrace{\sum_{\substack{v\in
V;\\v\in\varphi\left( e\right) }}}_{\substack{=\sum_{v\in\varphi\left(
e\right) }\\\text{(since }\varphi\left( e\right) \text{ is}\\\text{a subset
of }V\text{)}}}\dfrac{\deg\left( e/v\right) }{\deg v}\\
& =\sum_{e\in E}\underbrace{\sum_{v\in\varphi\left( e\right) }\dfrac
{\deg\left( e/v\right) }{\deg v}}_{\substack{\geq2\\\text{(by
(\ref{sol.friends-neighbors.1}))}}}\geq\sum_{e\in E}2=\left\vert E\right\vert
\cdot2=2\left\vert E\right\vert =\sum_{v\in V}\deg v
\end{align*}
(by (\ref{sol.friends-neighbors.hslem})). This solves Exercise
\ref{exe.friends-neighbors}.
\end{proof}
\subsection{When do transpositions generate all permutations?}
\begin{exercise}
\label{exe.graph.transpositions-gen}Let $G=\left( V,E,\varphi\right) $ be a
connected graph.
For each $e=\left\{ u,v\right\} \in\mathcal{P}_{2}\left( V\right) $, we
let $t_{e}$ be the permutation of $V$ that swaps $u$ with $v$ while leaving
all other elements of $V$ unchanged.
An $E$\textit{-transposition} shall mean a permutation of the form $t_{e}$ for
some $e\in\varphi\left( E\right) $.
Prove that every permutation of $V$ can be written as a composition of some
$E$-transpositions.
\end{exercise}
\Needspace{10cm}
\begin{remark}
In Exercise \ref{exe.graph.transpositions-gen}, we can WLOG assume (by
relabeling the vertices) that $V=\left[ n\right] $ for some $n\in\mathbb{N}%
$. Thus, Exercise \ref{exe.graph.transpositions-gen} makes a statement about
permutations of $\left[ n\right] $.
For instance, if we apply Exercise \ref{exe.graph.transpositions-gen} to the
connected simple graph $P_{n}=\left( \left[ n\right] ,\left\{ \left\{
1,2\right\} ,\left\{ 2,3\right\} ,\ldots,\left\{ n-1,n\right\} \right\}
\right) $ (for some $n>0$), then we obtain the well-known fact that every
permutation of $\left[ n\right] $ can be written as a composition of some
simple transpositions (because the $E$-transpositions in this case are
precisely the simple transpositions $s_{1},s_{2},\ldots,s_{n-1}$).
For another example, we can apply Exercise \ref{exe.graph.transpositions-gen}
to the connected simple graph $\left( \left[ n\right] ,\left\{ \left\{
1,2\right\} ,\left\{ 1,3\right\} ,\ldots,\left\{ 1,n\right\} \right\}
\right) $ (for some $n>0$); this graph is called a \textquotedblleft
star\textquotedblright, because here is how it looks like for $n=7$:%
\[%
%TCIMACRO{\TeXButton{star with 7 vertices}{\xymatrix{
%& 3 \are[dr] & & 4 \are[dl] \\
%2 \are[rr] & & 1 \are[rr] & & 5 \\
%& 6 \are[ur] & & 7 \are[ul]
%}}}%
%BeginExpansion
\xymatrix{
& 3 \are[dr] & & 4 \are[dl] \\
2 \are[rr] & & 1 \are[rr] & & 5 \\
& 6 \are[ur] & & 7 \are[ul]
}%
%EndExpansion
\]
Thus, Exercise \ref{exe.graph.transpositions-gen} shows that every permutation
of $\left[ n\right] $ can be written as a composition of some
transpositions, each of which swaps $1$ with one of the numbers $2,3,\ldots
,n$. (This fact was Exercise 3 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw7os.pdf}{Fall 2017 Math 4990
homework set \#7}.)
\end{remark}
Exercise \ref{exe.graph.transpositions-gen} also has a converse: If $G=\left(
V,E,\varphi\right) $ is a graph such that every permutation of $V$ can be
written as a composition of some $E$-transpositions, then $G$ is connected or
$V$ is empty. This is not hard to prove\footnote{\textit{Hint:} Show that if a
composition of some $E$-transpositions maps a vertex $u\in V$ to a vertex
$v\in V$, then there exists a walk from $u$ to $v$ in $G$.}.
Our solution of Exercise \ref{exe.graph.transpositions-gen} relies on the
following notation:
\begin{definition}
Let $V$ be any set. Let $u$ and $v$ be two distinct elements of $V$. Then,
$t_{u,v}$ shall denote the permutation of $V$ that swaps $u$ with $v$ while
leaving all other elements of $V$ unchanged. This permutation $t_{u,v}$ is
called a \textit{transposition} of $V$.
\end{definition}
\begin{lemma}
\label{lem.perm.tiq-through-tip}Let $V$ be a set. Let $i$, $p$ and $q$ be
three distinct elements of $V$. Then,%
\[
t_{i,q}=t_{p,q}\circ t_{i,p}\circ t_{p,q}.
\]
\end{lemma}
\begin{proof}
[Proof of Lemma \ref{lem.perm.tiq-through-tip} (sketched).]This is
straightforward: We just need to show that $t_{i,q}\left( x\right) =\left(
t_{p,q}\circ t_{i,p}\circ t_{p,q}\right) \left( x\right) $ for each $x\in
V$. This can be shown by considering the cases $x=i$, $x=p$, $x=q$ and
$x\notin\left\{ i,p,q\right\} $ separately; in the first three cases, the
verification is a straightforward computation, whereas in the fourth case, the
claim follows from $t_{i,q}\left( x\right) =x$ and $\left( t_{p,q}\circ
t_{i,p}\circ t_{p,q}\right) \left( x\right) =x$.
\end{proof}
\begin{proof}
[Solution to Exercise \ref{exe.graph.transpositions-gen} (sketched).]Recall
that every permutation of $V$ is a composition of transpositions\footnote{This
is proven, e.g., in \cite[Exercise 5.15 \textbf{(b)}]{detnotes} (but also
follows easily from what we have done in class).}. We now focus on proving the
following fact:
\begin{statement}
\textit{Statement 1:} Let $i$ and $j$ be two distinct elements of $V$. Then,
the transposition $t_{i,j}$ of $V$ can be written as a composition of some $E$-transpositions.
\end{statement}
[\textit{Proof of Statement 1:} Since $G$ is connected, there is a path
$\left( k_{0},e_{1},k_{1},\ldots,e_{p},k_{p}\right) $ from $i$ to $j$ in $G$
(with $k_{0}=i$ and $k_{p}=j$). Consider such a path. For each $r\in\left[
p\right] $, the transposition $t_{k_{r-1},k_{r}}$ is an $E$-transposition
(since it can be written as $t_{e_{r}}$). Thus, in particular, $t_{k_{0}%
,k_{1}}$ is an $E$-transposition. Note that the path $\left( k_{0}%
,e_{1},k_{1},\ldots,e_{p},k_{p}\right) $ has length $>0$ (since $i\neq j$).
In other words, $p>0$. Hence, $p\in\left[ p\right] $.
We \textit{claim} that $t_{i,k_{r}}$ is a composition of some $E$%
-transpositions for each $r\in\left\{ 1,2,\ldots,p\right\} $. Indeed, this
can be proven by induction on $r$: The base case ($r=1$) is clear, since
$t_{i,k_{1}}=t_{k_{0},k_{1}}$ is itself an $E$-transposition. For the
induction step, let $r\in\left\{ 1,2,\ldots,p\right\} $ be such that $r>1$,
and assume that $t_{i,k_{r-1}}$ is a composition of some $E$-transpositions;
we must show that $t_{i,k_{r}}$ is a composition of some $E$-transpositions.
But the vertices $k_{0},k_{r-1},k_{r}$ of $V$ are distinct (since they are
three different vertices of the path $\left( k_{0},e_{1},k_{1},\ldots
,e_{p},k_{p}\right) $). In other words, the vertices $i,k_{r-1},k_{r}$ of $V$
are distinct (since $k_{0}=i$). Hence, Lemma \ref{lem.perm.tiq-through-tip}
(applied to $k_{r-1}$ and $k_{r}$ instead of $p$ and $q$) yields $t_{i,k_{r}%
}=t_{k_{r-1},k_{r}}\circ t_{i,k_{r-1}}\circ t_{k_{r-1},k_{r}}$. But the right
hand side of this equality is a composition of some $E$-transpositions (since
$t_{i,k_{r-1}}$ is a composition of some $E$-transpositions, whereas
$t_{k_{r-1},k_{r}}$ is itself an $E$-transposition). Hence, so is the left
hand side. In other words, $t_{i,k_{r}}$ is a composition of some
$E$-transpositions. That completes the induction. Now, applying our claim to
$r=p$, we conclude that $t_{i,k_{p}}$ is a composition of some $E$%
-transpositions. Since $k_{p}=j$, this means that $t_{i,j}$ is a composition
of some $E$-transpositions. This proves Statement 1.]
Statement 1 shows that each transposition of $V$ can be written as a
composition of some $E$-transpositions. We thus know that every permutation of
$V$ is a composition of transpositions, each of which can in turn be written
as a composition of some $E$-transpositions. Hence, every permutation of $V$
is a composition of compositions of $E$-transpositions. But this means that
every permutation of $V$ can be written as a composition of $E$%
-transpositions. This solves Exercise \ref{exe.graph.transpositions-gen}.
\end{proof}
\subsection{Latin rectangles and squares}
\begin{definition}
Let $n\in\mathbb{N}$ and $r\in\mathbb{N}$. A \textit{Latin }$r\times
n$\textit{-rectangle} is an $r\times n$-matrix with the following properties:
\begin{itemize}
\item Each row contains the integers $1,2,\ldots,n$ in some order.
\item No number appears more than once in a column.
\end{itemize}
\end{definition}
For example, $\left(
\begin{array}
[c]{cccc}%
1 & 4 & 2 & 3\\
2 & 1 & 3 & 4
\end{array}
\right) $ is a Latin $2\times4$-rectangle, and $\left(
\begin{array}
[c]{ccccc}%
4 & 3 & 1 & 5 & 2\\
1 & 2 & 5 & 4 & 3\\
3 & 5 & 2 & 1 & 4
\end{array}
\right) $ is a Latin $3\times5$-rectangle, whereas $\left(
\begin{array}
[c]{cccc}%
1 & 4 & 2 & 3\\
1 & 2 & 3 & 4
\end{array}
\right) $ is not a Latin $2\times4$-rectangle (as the number $1$ appears
twice in the first column) and $\left(
\begin{array}
[c]{ccc}%
1 & 3 & 2\\
2 & 2 & 3\\
3 & 1 & 2
\end{array}
\right) $ is not a Latin $3\times3$-rectangle (since the second row is
$2,2,3$, which is not a rearrangement of $1,2,3$).
Clearly, a Latin $r\times n$-rectangle can only exist if $r\leq n$.
\begin{definition}
Let $n\in\mathbb{N}$. A \textit{Latin square of size }$n$ means a Latin
$n\times n$-rectangle.
\end{definition}
Latin squares are another classical combinatorial object whose number has not
been expressed to a reasonable standard; see
\href{https://en.wikipedia.org/wiki/Latin_square}{the Wikipedia page} for what
is known and why people care.
\begin{exercise}
\label{exe.latin.complete}Let $r\in\mathbb{N}$ and $n\in\mathbb{N}$ be such
that $r\leq n$. Let $A$ be a Latin $r\times n$-rectangle. Show that $A$ can be
extended to a Latin square of size $n$ by appending $n-r$ extra rows.
[\textbf{Hint:} By induction, it suffices to show that, as long as $r$ and $\neq$, and so can be $\beta$ and $\gamma$), we define the
set $N\left( \alpha,\beta,\gamma\right) $ by%
\[
N\left( \alpha,\beta,\gamma\right) =\left\{ \left( \left( x,y,z\right)
,\left( x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times
S\ \mid\ x\alpha x^{\prime}\text{ and }y\beta y^{\prime}\text{ and }z\gamma
z^{\prime}\right\} .
\]
For example,%
\[
N\left( <,>,=\right) =\left\{ \left( \left( x,y,z\right) ,\left(
x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid
\ xy^{\prime}\text{ and }z=z^{\prime}\right\}
\]
and%
\[
N\left( >,=,=\right) =\left\{ \left( \left( x,y,z\right) ,\left(
x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid
\ x>x^{\prime}\text{ and }y=y^{\prime}\text{ and }z=z^{\prime}\right\} .
\]
\textit{Step 2:} We have
\begin{align}
\left\vert N\left( <,<,>\right) \right\vert & =\left\vert N\left(
>,>,<\right) \right\vert \ \ \ \ \ \ \ \ \ \ \text{and}%
\label{sol.latin.signs.a.1}\\
\left\vert N\left( <,>,<\right) \right\vert & =\left\vert N\left(
>,<,>\right) \right\vert \ \ \ \ \ \ \ \ \ \ \text{and}%
\label{sol.latin.signs.a.2}\\
\left\vert N\left( >,<,<\right) \right\vert & =\left\vert N\left(
<,>,>\right) \right\vert . \label{sol.latin.signs.a.3}%
\end{align}
[\textit{Proof:} The map
\begin{align*}
N\left( <,<,>\right) & \rightarrow N\left( >,>,<\right) ,\\
\left( \left( x,y,z\right) ,\left( x^{\prime},y^{\prime},z^{\prime
}\right) \right) & \mapsto\left( \left( x^{\prime},y^{\prime},z^{\prime
}\right) ,\left( x,y,z\right) \right)
\end{align*}
is a bijection. Thus, $\left\vert N\left( <,<,>\right) \right\vert
=\left\vert N\left( >,>,<\right) \right\vert $. Similarly, $\left\vert
N\left( <,>,<\right) \right\vert =\left\vert N\left( >,<,>\right)
\right\vert $ and $\left\vert N\left( >,<,<\right) \right\vert =\left\vert
N\left( <,>,>\right) \right\vert $.]
\textit{Step 3:} Let $\ast$ be the binary relation on $\left[ n\right] $
such that \textbf{every} pair $\left( i,j\right) $ satisfies $i\ast j$. (The
\textquotedblleft joker relation\textquotedblright.) Show that%
\begin{align}
\left\vert N\left( \ast,<,>\right) \right\vert & =\left( n\left(
n-1\right) /2\right) ^{2}\ \ \ \ \ \ \ \ \ \ \text{and}%
\label{sol.latin.signs.b.1}\\
\left\vert N\left( <,>,\ast\right) \right\vert & =\left( n\left(
n-1\right) /2\right) ^{2}\ \ \ \ \ \ \ \ \ \ \text{and}%
\label{sol.latin.signs.b.2}\\
\left\vert N\left( >,\ast,<\right) \right\vert & =\left( n\left(
n-1\right) /2\right) ^{2}. \label{sol.latin.signs.b.3}%
\end{align}
[\textit{Proof:} The definition of $N\left( \ast,<,>\right) $ yields%
\begin{align}
& N\left( \ast,<,>\right) \nonumber\\
& =\left\{ \left( \left( x,y,z\right) ,\left( x^{\prime},y^{\prime
},z^{\prime}\right) \right) \in S\times S\ \mid\ \underbrace{x\ast
x^{\prime}}_{\substack{\text{this always}\\\text{holds}}}\text{ and
}yz^{\prime}\right\} \nonumber\\
& =\left\{ \left( \left( x,y,z\right) ,\left( x^{\prime},y^{\prime
},z^{\prime}\right) \right) \in S\times S\ \mid\ yz^{\prime}\right\} . \label{sol.latin.signs.b.1.pf.1}%
\end{align}
Thus, the elements of $N\left( \ast,<,>\right) $ are simply the pairs
$\left( \left( x,y,z\right) ,\left( x^{\prime},y^{\prime},z^{\prime
}\right) \right) \in S\times S$ satisfying $yz^{\prime}%
$. We can construct any such pair by the following algorithm:
\begin{itemize}
\item Choose two elements $y,y^{\prime}\in\left[ n\right] $ satisfying
$yz^{\prime
}$. Again, there are $\dbinom{n}{2}=n\left( n-1\right) /2$ ways to do this.
\item Find the unique $x\in\left[ n\right] $ such that $\left(
x,y,z\right) \in S$. (This is indeed unique, because for each pair $\left(
j,k\right) \in\left[ n\right] ^{2}$, there is exactly one $i\in\left[
n\right] $ such that $\left( i,j,k\right) \in S$.)
\item Find the unique $x^{\prime}\in\left[ n\right] $ such that $\left(
x^{\prime},y^{\prime},z^{\prime}\right) \in S$. (Again, this is unique for
the same reason.)
\end{itemize}
Hence, altogether, there are $\left( n\left( n-1\right) /2\right) ^{2}$
such pairs (because we had $n\left( n-1\right) /2$ choices in the first step
of the above algorithm, and then again $n\left( n-1\right) /2$ choices in
the second step, and no further choices). Thus,%
\[
\left\vert \left\{ \left( \left( x,y,z\right) ,\left( x^{\prime
},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid\ yz^{\prime}\right\} \right\vert =\left( n\left( n-1\right)
/2\right) ^{2}.
\]
In view of (\ref{sol.latin.signs.b.1.pf.1}), this rewrites as $\left\vert
N\left( \ast,<,>\right) \right\vert =\left( n\left( n-1\right) /2\right)
^{2}$. This proves (\ref{sol.latin.signs.b.1}). Similarly,
(\ref{sol.latin.signs.b.2}) and (\ref{sol.latin.signs.b.3}) can be shown.]
\textit{Step 4:} We have%
\begin{align}
\left\vert N\left( =,<,>\right) \right\vert +\left\vert N\left(
<,<,>\right) \right\vert +\left\vert N\left( >,<,>\right) \right\vert &
=\left\vert N\left( \ast,<,>\right) \right\vert ;\label{sol.latin.signs.c.1}%
\\
\left\vert N\left( >,=,<\right) \right\vert +\left\vert N\left(
>,<,<\right) \right\vert +\left\vert N\left( >,>,<\right) \right\vert &
=\left\vert N\left( >,\ast,<\right) \right\vert ;\label{sol.latin.signs.c.2}%
\\
\left\vert N\left( <,>,=\right) \right\vert +\left\vert N\left(
<,>,<\right) \right\vert +\left\vert N\left( <,>,>\right) \right\vert &
=\left\vert N\left( <,>,\ast\right) \right\vert .
\label{sol.latin.signs.c.3}%
\end{align}
[\textit{Proof:} The definition of $N\left( \ast,<,>\right) $ yields%
\begin{align*}
& N\left( \ast,<,>\right) \\
& =\left\{ \left( \left( x,y,z\right) ,\left( x^{\prime},y^{\prime
},z^{\prime}\right) \right) \in S\times S\ \mid\ \underbrace{x\ast
x^{\prime}}_{\substack{\text{this always}\\\text{holds}}}\text{ and
}yz^{\prime}\right\} \\
& =\left\{ \left( \left( x,y,z\right) ,\left( x^{\prime},y^{\prime
},z^{\prime}\right) \right) \in S\times S\ \mid\ yz^{\prime}\right\} .
\end{align*}
Clearly, each element $\left( \left( x,y,z\right) ,\left( x^{\prime
},y^{\prime},z^{\prime}\right) \right) $ of $N\left( \ast,<,>\right) $
satisfies either $x=x^{\prime}$ or $xx^{\prime}$ (but not
more than one of these relations); and, correspondingly, it belongs to either
$N\left( =,<,>\right) $ or $N\left( <,<,>\right) $ or $N\left(
>,<,>\right) $. Thus, the set $N\left( \ast,<,>\right) $ is the union of
its three disjoint subsets $N\left( =,<,>\right) $, $N\left( <,<,>\right)
$ and $N\left( >,<,>\right) $. Hence,%
\[
\left\vert N\left( \ast,<,>\right) \right\vert =\left\vert N\left(
=,<,>\right) \right\vert +\left\vert N\left( <,<,>\right) \right\vert
+\left\vert N\left( >,<,>\right) \right\vert .
\]
This proves (\ref{sol.latin.signs.c.1}). Analogous arguments prove
(\ref{sol.latin.signs.c.2}) and (\ref{sol.latin.signs.c.3}).]
\textit{Step 5:} Adding the equalities (\ref{sol.latin.signs.c.1}),
(\ref{sol.latin.signs.c.2}) and (\ref{sol.latin.signs.c.3}) together, we
obtain%
\begin{align*}
& \left\vert N\left( =,<,>\right) \right\vert +\left\vert N\left(
<,<,>\right) \right\vert +\left\vert N\left( >,<,>\right) \right\vert \\
& \ \ \ \ \ \ \ \ \ \ +\left\vert N\left( >,=,<\right) \right\vert
+\left\vert N\left( >,<,<\right) \right\vert +\left\vert N\left(
>,>,<\right) \right\vert \\
& \ \ \ \ \ \ \ \ \ \ +\left\vert N\left( <,>,=\right) \right\vert
+\left\vert N\left( <,>,<\right) \right\vert +\left\vert N\left(
<,>,>\right) \right\vert \\
& =\underbrace{\left\vert N\left( \ast,<,>\right) \right\vert
}_{\substack{=\left( n\left( n-1\right) /2\right) ^{2}\\\text{(by
(\ref{sol.latin.signs.b.1}))}}}+\underbrace{\left\vert N\left( >,\ast
,<\right) \right\vert }_{\substack{=\left( n\left( n-1\right) /2\right)
^{2}\\\text{(by (\ref{sol.latin.signs.b.3}))}}}+\underbrace{\left\vert
N\left( <,>,\ast\right) \right\vert }_{\substack{=\left( n\left(
n-1\right) /2\right) ^{2}\\\text{(by (\ref{sol.latin.signs.b.2}))}}}\\
& =\left( n\left( n-1\right) /2\right) ^{2}+\left( n\left( n-1\right)
/2\right) ^{2}+\left( n\left( n-1\right) /2\right) ^{2}\\
& =3\left( n\left( n-1\right) /2\right) ^{2}\equiv\left( n\left(
n-1\right) /2\right) ^{2}\equiv n\left( n-1\right) /2\operatorname{mod}2
\end{align*}
(since $m^{2}\equiv m\operatorname{mod}2$ for each integer $m$ (because
$\dfrac{m^{2}-m}{2}=\dbinom{m}{2}$ is an integer)). Comparing this with%
\begin{align*}
& \left\vert N\left( =,<,>\right) \right\vert +\underbrace{\left\vert
N\left( <,<,>\right) \right\vert }_{\substack{=\left\vert N\left(
>,>,<\right) \right\vert \\\text{(by (\ref{sol.latin.signs.a.1}))}%
}}+\left\vert N\left( >,<,>\right) \right\vert \\
& \ \ \ \ \ \ \ \ \ \ +\left\vert N\left( >,=,<\right) \right\vert
+\underbrace{\left\vert N\left( >,<,<\right) \right\vert }%
_{\substack{=\left\vert N\left( <,>,>\right) \right\vert \\\text{(by
(\ref{sol.latin.signs.a.3}))}}}+\left\vert N\left( >,>,<\right) \right\vert
\\
& \ \ \ \ \ \ \ \ \ \ +\left\vert N\left( <,>,=\right) \right\vert
+\underbrace{\left\vert N\left( <,>,<\right) \right\vert }%
_{\substack{=\left\vert N\left( >,<,>\right) \right\vert \\\text{(by
(\ref{sol.latin.signs.a.2}))}}}+\left\vert N\left( <,>,>\right) \right\vert
\\
& =\left\vert N\left( =,<,>\right) \right\vert +\left\vert N\left(
>,>,<\right) \right\vert +\left\vert N\left( >,<,>\right) \right\vert \\
& \ \ \ \ \ \ \ \ \ \ +\left\vert N\left( >,=,<\right) \right\vert
+\left\vert N\left( <,>,>\right) \right\vert +\left\vert N\left(
>,>,<\right) \right\vert \\
& \ \ \ \ \ \ \ \ \ \ +\left\vert N\left( <,>,=\right) \right\vert
+\left\vert N\left( >,<,>\right) \right\vert +\left\vert N\left(
<,>,>\right) \right\vert \\
& =\left\vert N\left( =,<,>\right) \right\vert +\left\vert N\left(
<,>,=\right) \right\vert +\left\vert N\left( >,=,<\right) \right\vert \\
& \ \ \ \ \ \ \ \ \ \ +2\left( \left\vert N\left( >,>,<\right) \right\vert
+\left\vert N\left( >,<,>\right) \right\vert +\left\vert N\left(
<,>,>\right) \right\vert \right) \\
& \equiv\left\vert N\left( =,<,>\right) \right\vert +\left\vert N\left(
<,>,=\right) \right\vert +\left\vert N\left( >,=,<\right) \right\vert
\operatorname{mod}2,
\end{align*}
we obtain%
\begin{align}
& \left\vert N\left( =,<,>\right) \right\vert +\left\vert N\left(
<,>,=\right) \right\vert +\left\vert N\left( >,=,<\right) \right\vert
\nonumber\\
& \equiv n\left( n-1\right) /2\operatorname{mod}2.
\label{sol.latin.signs.c.res}%
\end{align}
\textit{Step 6:} We have%
\begin{align}
\prod_{i=1}^{n}\left( -1\right) ^{r_{i}} & =\left( -1\right)
^{\left\vert N\left( =,<,>\right) \right\vert }%
\ \ \ \ \ \ \ \ \ \ \text{and}\label{sol.latin.signs.d.1}\\
\prod_{j=1}^{n}\left( -1\right) ^{c_{j}} & =\left( -1\right)
^{\left\vert N\left( >,=,<\right) \right\vert }%
\ \ \ \ \ \ \ \ \ \ \text{and}\label{sol.latin.signs.d.2}\\
\prod_{k=1}^{n}\left( -1\right) ^{z_{k}} & =\left( -1\right)
^{\left\vert N\left( <,>,=\right) \right\vert }. \label{sol.latin.signs.d.3}%
\end{align}
[\textit{Proof:} We begin by proving (\ref{sol.latin.signs.d.1}). For each
$i\in\left[ n\right] $, the length $\ell\left( r_{i}\right) $ of the
permutation $r_{i}\in S_{n}$ is given by%
\begin{align}
\ell\left( r_{i}\right) & =\left( \text{the number of inversions of
}r_{i}\right) \nonumber\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of the length of a
permutation}\right) \nonumber\\
& =\left( \text{the number of all }\left( u,v\right) \in\left[ n\right]
^{2}\text{ satisfying }ur_{i}\left(
v\right) \right) \nonumber\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of an inversion}\right)
\nonumber\\
& =\left\vert \left\{ \left( u,v\right) \in\left[ n\right] ^{2}%
\ \mid\ ur_{i}\left( v\right)
\right\} \right\vert \nonumber\\
& =\left\vert \left\{ \left( y,y^{\prime}\right) \in\left[ n\right]
^{2}\ \mid\ yr_{i}\left(
y^{\prime}\right) \right\} \right\vert \label{sol.latin.signs.d.1.pf.1}%
\end{align}
(here, we have renamed the index $\left( u,v\right) $ as $\left(
y,y^{\prime}\right) $).
But%
\[
N\left( =,<,>\right) =\left\{ \left( \left( x,y,z\right) ,\left(
x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid
\ x=x^{\prime}\text{ and }yz^{\prime}\right\}
\]
and thus%
\begin{align}
& \left\vert N\left( =,<,>\right) \right\vert \nonumber\\
& =\left\vert \left\{ \left( \left( x,y,z\right) ,\left( x^{\prime
},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid\ x=x^{\prime
}\text{ and }yz^{\prime}\right\} \right\vert
\nonumber\\
& =\sum_{i\in\left[ n\right] }\left\vert \left\{ \left( \left(
x,y,z\right) ,\left( x^{\prime},y^{\prime},z^{\prime}\right) \right) \in
S\times S\ \mid\ x=x^{\prime}=i\text{ and }yz^{\prime}\right\} \right\vert .\nonumber\\
& \label{sol.latin.signs.d.1.pf.2}%
\end{align}
But each $i\in\left[ n\right] $ satisfies%
\begin{align*}
& \left\vert \left\{ \left( \left( x,y,z\right) ,\left( x^{\prime
},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid\ x=x^{\prime
}=i\text{ and }yz^{\prime}\right\} \right\vert \\
& =\left\vert \left\{ \left( y,z,y^{\prime},z^{\prime}\right) \in\left[
n\right] ^{4}\ \mid\ \underbrace{\left( i,y,z\right) \in S}%
_{\substack{\Longleftrightarrow\ \left( A_{i,y}=z\right) \\\text{(by the
definition of }S\text{)}}}\text{ and }\underbrace{\left( i,y^{\prime
},z^{\prime}\right) \in S}_{\substack{\Longleftrightarrow\ \left(
A_{i,y^{\prime}}=z^{\prime}\right) \\\text{(by the definition of }S\text{)}%
}}\text{ and }yz^{\prime}\right\} \right\vert \\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because the }\left( \left( x,y,z\right) ,\left( x^{\prime}%
,y^{\prime},z^{\prime}\right) \right) \in S\times S\text{ satisfying
}x=x^{\prime}=i\text{ are}\\
\text{uniquely determined by their coordinates }y,z,y^{\prime},z^{\prime}%
\end{array}
\right) \\
& =\left\vert \left\{ \left( y,z,y^{\prime},z^{\prime}\right) \in\left[
n\right] ^{4}\ \mid\ \underbrace{A_{i,y}}_{\substack{=r_{i}\left( y\right)
\\\text{(by the definition}\\\text{of }r_{i}\text{)}}}=z\text{ and
}\underbrace{A_{i,y^{\prime}}}_{\substack{=r_{i}\left( y^{\prime}\right)
\\\text{(by the definition}\\\text{of }r_{i}\text{)}}}=z^{\prime}\text{ and
}yz^{\prime}\right\} \right\vert \\
& =\left\vert \left\{ \left( y,z,y^{\prime},z^{\prime}\right) \in\left[
n\right] ^{4}\ \mid\ r_{i}\left( y\right) =z\text{ and }r_{i}\left(
y^{\prime}\right) =z^{\prime}\text{ and }yz^{\prime
}\right\} \right\vert \\
& =\left\vert \left\{ \left( y,y^{\prime}\right) \in\left[ n\right]
^{2}\ \mid\ yr_{i}\left(
y^{\prime}\right) \right\} \right\vert \\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the }4\text{-tuples }\left( y,z,y^{\prime},z^{\prime}\right)
\in\left[ n\right] ^{4}\text{ satisfying }r_{i}\left( y\right) =z\text{
and }r_{i}\left( y^{\prime}\right) =z^{\prime}\\
\text{are uniquely determined by their coordinates }y\text{ and }y^{\prime}%
\end{array}
\right) \\
& =\ell\left( r_{i}\right) \ \ \ \ \ \ \ \ \ \ \left( \text{by
(\ref{sol.latin.signs.d.1.pf.1})}\right) .
\end{align*}
Thus, (\ref{sol.latin.signs.d.1.pf.2}) becomes%
\begin{align*}
\left\vert N\left( =,<,>\right) \right\vert & =\sum_{i\in\left[ n\right]
}\underbrace{\left\vert \left\{ \left( \left( x,y,z\right) ,\left(
x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid
\ x=x^{\prime}=i\text{ and }yz^{\prime}\right\}
\right\vert }_{=\ell\left( r_{i}\right) }\\
& =\sum_{i\in\left[ n\right] }\ell\left( r_{i}\right) =\sum_{i=1}^{n}%
\ell\left( r_{i}\right) .
\end{align*}
Thus,
\[
\left( -1\right) ^{\left\vert N\left( =,<,>\right) \right\vert }=\left(
-1\right) ^{\sum_{i=1}^{n}\ell\left( r_{i}\right) }=\prod_{i=1}%
^{n}\underbrace{\left( -1\right) ^{\ell\left( r_{i}\right) }%
}_{\substack{=\left( -1\right) ^{r_{i}}\\\text{(since }\left( -1\right)
^{r_{i}}=\left( -1\right) ^{\ell\left( r_{i}\right) }\\\text{(by the
definition of }\left( -1\right) ^{r_{i}}\text{))}}}=\prod_{i=1}^{n}\left(
-1\right) ^{r_{i}}.
\]
This proves (\ref{sol.latin.signs.d.1}).
Next, we will prove (\ref{sol.latin.signs.d.2}). This proof is similar, but
differs in some details, so we give it in full. For each $j\in\left[
n\right] $, the length $\ell\left( c_{j}\right) $ of the permutation
$c_{j}\in S_{n}$ is given by%
\begin{align}
\ell\left( c_{j}\right) & =\left( \text{the number of inversions of
}c_{j}\right) \nonumber\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of the length of a
permutation}\right) \nonumber\\
& =\left( \text{the number of all }\left( u,v\right) \in\left[ n\right]
^{2}\text{ satisfying }uc_{j}\left(
v\right) \right) \nonumber\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of an inversion}\right)
\nonumber\\
& =\left\vert \left\{ \left( u,v\right) \in\left[ n\right] ^{2}%
\ \mid\ uc_{j}\left( v\right)
\right\} \right\vert \nonumber\\
& =\left\vert \left\{ \left( u,v\right) \in\left[ n\right] ^{2}%
\ \mid\ \underbrace{vv\right) }\text{ and
}\underbrace{c_{j}\left( v\right) >c_{j}\left( u\right) }%
_{\Longleftrightarrow\ \left( c_{j}\left( u\right) v\text{ and }c_{j}\left( u\right) x^{\prime}\text{ and }c_{j}\left( x\right) ,=,<\right) =\left\{ \left( \left( x,y,z\right) ,\left(
x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid
\ x>x^{\prime}\text{ and }y=y^{\prime}\text{ and }z,=,<\right) \right\vert \nonumber\\
& =\left\vert \left\{ \left( \left( x,y,z\right) ,\left( x^{\prime
},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid\ x>x^{\prime
}\text{ and }y=y^{\prime}\text{ and }zx^{\prime}\text{ and }y=y^{\prime}=j\text{ and }%
zx^{\prime
}\text{ and }y=y^{\prime}=j\text{ and }zx^{\prime}\text{ and }zx^{\prime}\text{ and }zx^{\prime}\text{ and }zx^{\prime}\text{ and }c_{j}\left( x\right) ,=,<\right) \right\vert & =\sum_{j\in\left[ n\right]
}\underbrace{\left\vert \left\{ \left( \left( x,y,z\right) ,\left(
x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid
\ x>x^{\prime}\text{ and }y=y^{\prime}=j\text{ and }z,=,<\right) \right\vert }=\left(
-1\right) ^{\sum_{j=1}^{n}\ell\left( c_{j}\right) }=\prod_{j=1}%
^{n}\underbrace{\left( -1\right) ^{\ell\left( c_{j}\right) }%
}_{\substack{=\left( -1\right) ^{c_{j}}\\\text{(since }\left( -1\right)
^{c_{j}}=\left( -1\right) ^{\ell\left( c_{j}\right) }\\\text{(by the
definition of }\left( -1\right) ^{c_{j}}\text{))}}}=\prod_{j=1}^{n}\left(
-1\right) ^{c_{j}}.
\]
This proves (\ref{sol.latin.signs.d.2}).
Finally, we need to prove (\ref{sol.latin.signs.d.3}). For each $k\in\left[
n\right] $, the length $\ell\left( z_{k}\right) $ of the permutation
$z_{k}\in S_{n}$ is given by%
\begin{align}
\ell\left( z_{k}\right) & =\left( \text{the number of inversions of
}z_{k}\right) \nonumber\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of the length of a
permutation}\right) \nonumber\\
& =\left( \text{the number of all }\left( u,v\right) \in\left[ n\right]
^{2}\text{ satisfying }uz_{k}\left(
v\right) \right) \nonumber\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of an inversion}\right)
\nonumber\\
& =\left\vert \left\{ \left( u,v\right) \in\left[ n\right] ^{2}%
\ \mid\ uz_{k}\left( v\right)
\right\} \right\vert \nonumber\\
& =\left\vert \left\{ \left( x,x^{\prime}\right) \in\left[ n\right]
^{2}\ \mid\ xz_{k}\left(
x^{\prime}\right) \right\} \right\vert \label{sol.latin.signs.d.3.pf.1}%
\end{align}
(here, we have renamed the index $\left( u,v\right) $ as $\left(
x,x^{\prime}\right) $).
But%
\[
N\left( <,>,=\right) =\left\{ \left( \left( x,y,z\right) ,\left(
x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid
\ xy^{\prime}\text{ and }z=z^{\prime}\right\}
\]
and thus%
\begin{align}
& \left\vert N\left( <,>,=\right) \right\vert \nonumber\\
& =\left\vert \left\{ \left( \left( x,y,z\right) ,\left( x^{\prime
},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid\ xy^{\prime}\text{ and }z=z^{\prime}\right\} \right\vert
\nonumber\\
& =\sum_{k\in\left[ n\right] }\left\vert \left\{ \left( \left(
x,y,z\right) ,\left( x^{\prime},y^{\prime},z^{\prime}\right) \right) \in
S\times S\ \mid\ xy^{\prime}\text{ and }z=z^{\prime
}=k\right\} \right\vert .\nonumber\\
& \label{sol.latin.signs.d.3.pf.2}%
\end{align}
But each $k\in\left[ n\right] $ satisfies%
\begin{align*}
& \left\vert \left\{ \left( \left( x,y,z\right) ,\left( x^{\prime
},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid\ xy^{\prime}\text{ and }z=z^{\prime}=k\right\} \right\vert \\
& =\left\vert \left\{ \left( x,y,x^{\prime},y^{\prime}\right) \in\left[
n\right] ^{4}\ \mid\ \underbrace{\left( x,y,k\right) \in S}%
_{\substack{\Longleftrightarrow\ \left( A_{x,y}=k\right) \\\text{(by the
definition of }S\text{)}}}\text{ and }\underbrace{\left( x^{\prime}%
,y^{\prime},k\right) \in S}_{\substack{\Longleftrightarrow\ \left(
A_{x^{\prime},y^{\prime}}=k\right) \\\text{(by the definition of }S\text{)}%
}}\text{ and }xy^{\prime}\right\} \right\vert \\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{because the }\left( \left( x,y,z\right) ,\left( x^{\prime}%
,y^{\prime},z^{\prime}\right) \right) \in S\times S\text{ satisfying
}z=z^{\prime}=k\text{ are}\\
\text{uniquely determined by their coordinates }x,y,x^{\prime},y^{\prime}%
\end{array}
\right) \\
& =\left\vert \left\{ \left( x,y,x^{\prime},y^{\prime}\right) \in\left[
n\right] ^{4}\ \mid\ \underbrace{A_{x,y}=k}_{\substack{\Longleftrightarrow
\ \left( y=z_{k}\left( x\right) \right) \\\text{(by the definition}%
\\\text{of }z_{k}\text{)}}}\text{ and }\underbrace{A_{x^{\prime},y^{\prime}%
}=k}_{\substack{\Longleftrightarrow\ \left( y^{\prime}=z_{k}\left(
x^{\prime}\right) \right) \\\text{(by the definition}\\\text{of }%
z_{k}\text{)}}}\text{ and }xy^{\prime}\right\}
\right\vert \\
& =\left\vert \left\{ \left( x,y,x^{\prime},y^{\prime}\right) \in\left[
n\right] ^{4}\ \mid\ y=z_{k}\left( x\right) \text{ and }y^{\prime}%
=z_{k}\left( x^{\prime}\right) \text{ and }xy^{\prime}\right\} \right\vert \\
& =\left\vert \left\{ \left( x,x^{\prime}\right) \in\left[ n\right]
^{2}\ \mid\ xz_{k}\left(
x^{\prime}\right) \right\} \right\vert \\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the }4\text{-tuples }\left( x,y,x^{\prime},y^{\prime}\right)
\in\left[ n\right] ^{4}\text{ satisfying }y=z_{k}\left( x\right) \text{
and }y^{\prime}=z_{k}\left( x^{\prime}\right) \\
\text{are uniquely determined by their coordinates }x\text{ and }x^{\prime}%
\end{array}
\right) \\
& =\ell\left( z_{k}\right) \ \ \ \ \ \ \ \ \ \ \left( \text{by
(\ref{sol.latin.signs.d.3.pf.1})}\right) .
\end{align*}
Thus, (\ref{sol.latin.signs.d.3.pf.2}) becomes%
\begin{align*}
\left\vert N\left( <,>,=\right) \right\vert & =\sum_{k\in\left[ n\right]
}\underbrace{\left\vert \left\{ \left( \left( x,y,z\right) ,\left(
x^{\prime},y^{\prime},z^{\prime}\right) \right) \in S\times S\ \mid
\ xy^{\prime}\text{ and }z=z^{\prime}=k\right\}
\right\vert }_{=\ell\left( z_{k}\right) }\\
& =\sum_{k\in\left[ n\right] }\ell\left( z_{k}\right) =\sum_{k=1}^{n}%
\ell\left( z_{k}\right) .
\end{align*}
Thus,
\[
\left( -1\right) ^{\left\vert N\left( <,>,=\right) \right\vert }=\left(
-1\right) ^{\sum_{k=1}^{n}\ell\left( z_{k}\right) }=\prod_{k=1}%
^{n}\underbrace{\left( -1\right) ^{\ell\left( z_{k}\right) }%
}_{\substack{=\left( -1\right) ^{z_{k}}\\\text{(since }\left( -1\right)
^{z_{k}}=\left( -1\right) ^{\ell\left( z_{k}\right) }\\\text{(by the
definition of }\left( -1\right) ^{z_{k}}\text{))}}}=\prod_{k=1}^{n}\left(
-1\right) ^{z_{k}}.
\]
This proves (\ref{sol.latin.signs.d.3}).]
\textit{Step 7:} Multiplying the three equalities (\ref{sol.latin.signs.d.1}),
(\ref{sol.latin.signs.d.2}) and (\ref{sol.latin.signs.d.3}), we obtain%
\begin{align*}
& \left( \prod_{i=1}^{n}\left( -1\right) ^{r_{i}}\right) \left(
\prod_{j=1}^{n}\left( -1\right) ^{c_{j}}\right) \left( \prod_{k=1}%
^{n}\left( -1\right) ^{z_{k}}\right) \\
& =\left( -1\right) ^{\left\vert N\left( =,<,>\right) \right\vert
}\left( -1\right) ^{\left\vert N\left( >,=,<\right) \right\vert }\left(
-1\right) ^{\left\vert N\left( <,>,=\right) \right\vert }\\
& =\left( -1\right) ^{\left\vert N\left( =,<,>\right) \right\vert
}\left( -1\right) ^{\left\vert N\left( <,>,=\right) \right\vert }\left(
-1\right) ^{\left\vert N\left( >,=,<\right) \right\vert }\\
& =\left( -1\right) ^{\left\vert N\left( =,<,>\right) \right\vert
+\left\vert N\left( <,>,=\right) \right\vert +\left\vert N\left(
>,=,<\right) \right\vert }=\left( -1\right) ^{n\left( n-1\right) /2}%
\end{align*}
(by (\ref{sol.latin.signs.c.res})). This solves Exercise \ref{exe.latin.signs}.
\end{proof}
\begin{thebibliography}{99999999} %
\bibitem[Bartle12]{Bartle12}%
\href{http://web.math.ucsb.edu/~padraic/mathcamp_2012/mathcamp_2012.html}{Padraic
Bartlett, \textit{Notes from the 2012 Canada/USA Mathcamp}}.\newline\url{http://web.math.ucsb.edu/~padraic/mathcamp_2012/mathcamp_2012.html}
\bibitem[Bernds12]{Bernds12}%
\href{http://repository.tue.nl/fc05ed79-5969-47ce-adaa-bf2d59a3cecc}{Jochem
Berndsen, \textit{Three problems in algebraic combinatorics}, master's thesis,
Eindhoven 2012}.\newline\url{http://repository.tue.nl/fc05ed79-5969-47ce-adaa-bf2d59a3cecc}
\bibitem[Glynn10]{Glynn10}\href{https://doi.org/10.1137/090773751}{David G.
Glynn, \textit{The conjectures of Alon-Tarsi and Rota in dimension prime minus
one}, SIAM J. Discrete Math., Vol. 24, No. 2, pp. 394--399.}\newline\url{https://doi.org/10.1137/090773751}
\bibitem[Grinbe16]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} \newline The
numbering of theorems and formulas in this link might shift when the project
gets updated; for a \textquotedblleft frozen\textquotedblright\ version whose
numbering is guaranteed to match that in the citations above, see
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} .
\bibitem[Hall45]{Hall45}%
\href{https://projecteuclid.org/euclid.bams/1183506980}{Marshall Hall,
\textit{An existence theorem for Latin squares}, Bull. Amer. Math. Soc.,
Volume 51, Number 6, Part 1 (1945), pp. 387--388.}
\bibitem[HilVau11]{HilVau11}\href{https://arxiv.org/abs/1107.2639v1}{A. J. W.
Hilton, E. R. Vaughan, \textit{Hall's Condition for Partial Latin Squares},
arXiv:1107.2639v1}.
\bibitem[Jansse95]{Jansse95}%
\href{https://doi.org/10.1016/0097-3165(95)90115-9}{Jeannette C. M. Janssen,
\textit{On even and odd latin squares}, Journal of Combinatorial Theory,
Series A, Volume 69, Issue 1, January 1995, pp. 173--181}.\newline\url{https://doi.org/10.1016/0097-3165(95)90115-9}
\bibitem[Stanle13]{Stanle13}Richard Stanley, \textit{Algebraic Combinatorics:
Walks, Trees, Tableaux, and More}, Springer 2013.\newline See
\url{http://www-math.mit.edu/~rstan/algcomb/} for a draft version.
\end{thebibliography}
\end{document}