\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=Saturday, April 28, 2018 17:17:36}
%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
\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 [corrected
version]}

due date: Wednesday 25 April 2018 at the beginning of class, or before that by
email or moodle

Please solve \textbf{at most 4} of the 7 exercises!
\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}

Usually, we don't care about the \textquotedblleft
identities\textquotedblright\ of the edges of a multigraph. Thus, we specify a
multigraph by saying what its vertices are, and how many edges join each pair
of its vertices. Whether we ca
\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{, 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*}


Recall that a\textit{ matching} of a graph $G$ means a set $M$ 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}
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}

\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}

\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}
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}

\subsection{Your friends have more friends than you}

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}


[\textbf{Hint:} It helps to use the inequality $\dfrac{x}{y}+\dfrac{y}{x}%
\geq2$, which holds for any two positive reals $x$ and $y$ (it is a
consequence of $\dfrac{x}{y}+\dfrac{y}{x}-2=\dfrac{\left(  x-y\right)  ^{2}%
}{xy}\geq0$).]
\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.

\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}

\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 check.

\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}

\begin{exercise}
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<n$, you
can extend $A$ to a Latin $\left(  r+1\right)  \times n$-rectangle by
appending one extra row. You can use Hall's marriage theorem without proof
here, even though we have not shown it in class.]
\end{exercise}

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.

\subsection{Latin squares and signs}

\begin{exercise}
\label{exe.latin.signs}Let $n\in\mathbb{N}$. Let $A$ be a Latin square of size
$n$. Recall Definition \ref{def.matrix.Aij}.

For each $i\in\left[  n\right]  $, let $r_{i}$ be the permutation of $\left[
n\right]  $ whose one-line notation is the $i$-th row of $A$ (that is, which
satisfies $r_{i}\left(  j\right)  =A_{i,j}$ for each $j\in\left[  n\right]  $).

For each $j\in\left[  n\right]  $, let $c_{j}$ be the permutation of $\left[
n\right]  $ whose one-line notation is the $j$-th column of $A$ (that is,
which satisfies $c_{j}\left(  i\right)  =A_{i,j}$ for each $i\in\left[
n\right]  $).

For each $k\in\left[  n\right]  $, let $z_{k}$ be the permutation of $\left[
n\right]  $ such that for each $i\in\left[  n\right]  $, we have
$A_{i,z_{k}\left(  i\right)  }=k$. (Thus, the permutation $z_{k}$ sends each
$i\in\left[  n\right]  $ to the position of the entry $k$ in the $i$-th row of
$A$. This is indeed a permutation, as follows easily from the definition of a
Latin square and from the pigeonhole principle.)

Prove that%
\[
\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)  ^{n\left(  n-1\right)  /2}.
\]

\end{exercise}

\begin{example}
For this example, let $n=4$ and $A=\left(
\begin{array}
[c]{cccc}%
4 & 3 & 1 & 2\\
1 & 2 & 4 & 3\\
3 & 4 & 2 & 1\\
2 & 1 & 3 & 4
\end{array}
\right)  $. Then, $A$ is a Latin square of size $4$. The permutations
$r_{i},c_{j},z_{k}$ of Exercise \ref{exe.latin.signs} then look as follows in
one-line notation:%
\begin{align*}
r_{1}  &  =\left[  4,3,1,2\right]  ,\ \ \ \ \ \ \ \ \ \ r_{2}=\left[
1,2,4,3\right]  ,\ \ \ \ \ \ \ \ \ \ r_{3}=\left[  3,4,2,1\right]
,\ \ \ \ \ \ \ \ \ \ r_{4}=\left[  2,1,3,4\right]  ;\\
c_{1}  &  =\left[  4,1,3,2\right]  ,\ \ \ \ \ \ \ \ \ \ c_{2}=\left[
3,2,4,1\right]  ,\ \ \ \ \ \ \ \ \ \ c_{3}=\left[  1,4,2,3\right]
,\ \ \ \ \ \ \ \ \ \ c_{4}=\left[  2,3,1,4\right]  ;\\
z_{1}  &  =\left[  3,1,4,2\right]  ,\ \ \ \ \ \ \ \ \ \ z_{2}=\left[
4,2,3,1\right]  ,\ \ \ \ \ \ \ \ \ \ z_{3}=\left[  2,4,1,3\right]
,\ \ \ \ \ \ \ \ \ \ z_{4}=\left[  1,3,2,4\right]  .
\end{align*}

\end{example}

[\textbf{Hint to Exercise \ref{exe.latin.signs}:} Let $S$ be the set of all
triples $\left(  i,j,A_{i,j}\right)  \in\left[  n\right]  ^{3}$ for
$i\in\left[  n\right]  $ and $j\in\left[  n\right]  $. Notice that you can
visualize the set $\left[  n\right]  ^{3}$ as an $n\times n\times n$-cube
built out of $1\times1\times1$-blocks -- like a Rubik's cube --, and then $S$
is a set of $n^{2}$ blocks of this cube such that each strip parallel to one
of the three coordinate axes contains exactly one block from $S$. In other
words, if you fix two entries of a triple $\left(  i,j,k\right)  \in\left[
n\right]  ^{3}$, then there exists exactly one value for the third entry that
causes the triple to belong to $S$. (Notice that this rule characterizes sets
$S\subseteq\left[  n\right]  ^{3}$ that come from Latin squares; thus, it can
be viewed as a more symmetric definition of a Latin square.)

Now, whenever $\alpha$, $\beta$ and $\gamma$ are three binary relations on the
set $\left[  n\right]  $ (for example, $\alpha$ can be any of the relations
$=$, $<$, $>$ 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
\ x<x^{\prime}\text{ and }y>y^{\prime}\text{ and }z=z^{\prime}\right\}  .
\]


Now, you can follow the following roadmap:

\textbf{(a)} Prove that
\begin{align*}
\left\vert N\left(  <,<,>\right)  \right\vert  &  =\left\vert N\left(
>,>,<\right)  \right\vert \ \ \ \ \ \ \ \ \ \ \text{and}\\
\left\vert N\left(  <,>,<\right)  \right\vert  &  =\left\vert N\left(
>,<,>\right)  \right\vert \ \ \ \ \ \ \ \ \ \ \text{and}\\
\left\vert N\left(  >,<,<\right)  \right\vert  &  =\left\vert N\left(
<,>,>\right)  \right\vert .
\end{align*}


\textbf{(b)} Let $\ast$ be the binary relation on $\left[  n\right]  ^{2}$
such that \textbf{every} pair $\left(  i,j\right)  $ satisfies $a\ast b$. (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}\\
\left\vert N\left(  <,>,\ast\right)  \right\vert  &  =\left(  n\left(
n-1\right)  /2\right)  ^{2}\ \ \ \ \ \ \ \ \ \ \text{and}\\
\left\vert N\left(  >,\ast,<\right)  \right\vert  &  =\left(  n\left(
n-1\right)  /2\right)  ^{2}.
\end{align*}


\textbf{(c)} Prove that%
\[
\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 .
\]
Add this equality with two similar ones, and derive that%
\[
\left\vert N\left(  =,<,>\right)  \right\vert +\left\vert N\left(
<,>,=\right)  \right\vert +\left\vert N\left(  >,=,<\right)  \right\vert
\equiv3\left(  n\left(  n-1\right)  /2\right)  ^{2}\equiv n\left(  n-1\right)
/2\operatorname{mod}2.
\]


\textbf{(d)} Prove that%
\begin{align*}
\prod_{i=1}^{n}\left(  -1\right)  ^{r_{i}}  &  =\left(  -1\right)
^{\left\vert N\left(  =,<,>\right)  \right\vert }%
\ \ \ \ \ \ \ \ \ \ \text{and}\\
\prod_{j=1}^{n}\left(  -1\right)  ^{c_{j}}  &  =\left(  -1\right)
^{\left\vert N\left(  >,=,<\right)  \right\vert }%
\ \ \ \ \ \ \ \ \ \ \text{and}\\
\prod_{k=1}^{n}\left(  -1\right)  ^{z_{k}}  &  =\left(  -1\right)
^{\left\vert N\left(  <,>,=\right)  \right\vert }.
\end{align*}


\textbf{(e)} Derive the claim of Exercise \ref{exe.latin.signs}.]


\end{document}