\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{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, December 04, 2017 10:39:13}
%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}}
\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{\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]}
\ihead{Math 4707 Fall 2017 (Darij Grinberg): midterm 3}
\ohead{page \thepage}
\cfoot{}
\begin{document}
\begin{center}
\textbf{Math 4707 Fall 2017 (Darij Grinberg): midterm 3}
due date: Monday 11 December 2017 at the beginning of class, or before that by
email or moodle
Please solve \textbf{at most 4} of the 10 exercises!
\end{center}
\subsection{One last binomial sum}
\begin{exercise}
\label{exe.sum-2choosek}Let $n\in\mathbb{N}$. Prove that%
\[
\sum_{k=0}^{n}\dbinom{-2}{k}=\left( -1\right) ^{n}\left\lfloor \dfrac
{n+2}{2}\right\rfloor .
\]
\end{exercise}
\subsection{The Cartesian product of two permutations}
We have defined the sign of a permutation of $\left[ n\right] $ for an
$n\in\mathbb{N}$. But we can, more generally, define the sign of a permutation
of \textbf{any} finite set. This would be difficult to define directly;
instead, we define it by reducing it to a permutation of $\left[ n\right] $
as follows:
\begin{definition}
\label{def.permX.sign}Let $X$ be a finite set. We want to define the sign of
any permutation of $X$.
Fix a bijection $\phi:X\rightarrow\left[ n\right] $ for some $n\in
\mathbb{N}$. (Such a bijection always exists.) For every permutation $\sigma$
of $X$, set%
\[
\left( -1\right) _{\phi}^{\sigma}=\left( -1\right) ^{\phi\circ\sigma
\circ\phi^{-1}}.
\]
Here, the right hand side is well-defined because $\phi\circ\sigma\circ
\phi^{-1}$ is a permutation of $\left[ n\right] $.
It is not hard to check (see \cite[Exercise 5.12 \textbf{(a)}]{detnotes}) that
$\left( -1\right) _{\phi}^{\sigma}$ depends only on the permutation $\sigma$
of $X$, but not on the bijection $\phi$. (In other words, for a given $\sigma
$, any two different choices of $\phi$ will lead to the same $\left(
-1\right) _{\phi}^{\sigma}$.)
This allows us to define the \textit{sign} of the permutation $\sigma$ to be
$\left( -1\right) _{\phi}^{\sigma}$ for any choice of bijection
$\phi:X\rightarrow\left[ n\right] $. We denote this sign simply by $\left(
-1\right) ^{\sigma}$. (When $X=\left[ n\right] $, then this sign is clearly
the same as the sign $\left( -1\right) ^{\sigma}$ we defined before, because
we can pick the bijection $\phi=\operatorname*{id}$.)
\end{definition}
(In contrast, we could \textbf{not} define the length $\ell\left(
\sigma\right) $ of a permutation $\sigma$ of $X$, because different
bijections $\phi$ can lead to different values of $\ell\left( \phi\circ
\sigma\circ\phi^{-1}\right) $.)
The sign of a permutation $\sigma$ of a finite set $X$ has the following
properties (see \cite[Exercise 5.12]{detnotes}):
\begin{itemize}
\item The permutation $\operatorname*{id}:X\rightarrow X$ satisfies $\left(
-1\right) ^{\operatorname*{id}}=1$.
\item We have $\left( -1\right) ^{\sigma\circ\tau}=\left( -1\right)
^{\sigma}\cdot\left( -1\right) ^{\tau}$ for any two permutations $\sigma$
and $\tau$ of $X$.
\end{itemize}
\begin{exercise}
\label{exeadd.perm.sigmacrosstau}Let $U$ and $V$ be two finite sets. Let
$\sigma$ be a permutation of $U$. Let $\tau$ be a permutation of $V$. We
define a permutation $\sigma\times\tau$ of the set $U\times V$ by setting%
\[
\left( \sigma\times\tau\right) \left( a,b\right) =\left( \sigma\left(
a\right) ,\tau\left( b\right) \right) \ \ \ \ \ \ \ \ \ \ \text{for every
}\left( a,b\right) \in U\times V.
\]
\textbf{(a)} Prove that $\sigma\times\tau$ is a well-defined permutation.
\textbf{(b)} Prove that $\sigma\times\tau=\left( \sigma\times
\operatorname*{id}\right) \circ\left( \operatorname*{id}\times\tau\right) $.
\textbf{(c)} Prove that $\left( -1\right) ^{\sigma\times\tau}=\left(
\left( -1\right) ^{\sigma}\right) ^{\left\vert V\right\vert }\left(
\left( -1\right) ^{\tau}\right) ^{\left\vert U\right\vert }$. (All the
signs here are well-defined due to Definition \ref{def.permX.sign}.)
\end{exercise}
(Can you find a slick proof for part \textbf{(c)} that involves no endless
stream of trivial lemmas?)
\subsection{Non-cut vertices I}
See \href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/hw2s.pdf}{solutions
to Spring 2017 Math 5707 homework set \#2} (specifically, Section 0.1) for
definitions of simple graphs, multigraphs, digraphs and multidigraphs. Note,
in particular, that all of these are assumed to be finite (i.e., they have
finitely many vertices and finitely many edges).
Recall that a \textit{multigraph} is defined to be a triple $\left(
V,E,\varphi\right) $, where $V$ and $E$ are two finite sets and $\varphi$ is
a map $E\rightarrow\mathcal{P}_{2}\left( V\right) $ (sending each
\textquotedblleft edge\textquotedblright\ $e\in E$ to an unordered pair of two
distinct \textquotedblleft vertices\textquotedblright). The elements of $V$
are called the \textit{vertices} of the multigraph; the elements of $E$ are
called its \textit{edges}.
\begin{definition}
Let $G=\left( V,E,\varphi\right) $ and $G^{\prime}=\left( V^{\prime
},E^{\prime},\varphi^{\prime}\right) $ be two multigraphs. We say that
$G^{\prime}$ is a \textit{subgraph} of $G$ if and only if $V^{\prime}\subseteq
V$, $E^{\prime}\subseteq E$ and $\left( \varphi^{\prime}\left( e\right)
=\varphi\left( e\right) \text{ for each }e\in E^{\prime}\right) $.
\end{definition}
Thus, a subgraph of a multigraph $G$ is simply a multigraph obtained from $G$
by removing some vertices and some edges\footnote{\textquotedblleft
Some\textquotedblright\ may mean \textquotedblleft none\textquotedblright, and
may also mean \textquotedblleft all\textquotedblright\ (as well as anything
inbetween).}, provided that for each vertex we remove, all edges containing
that vertex are also removed. For example, the $2$-vertex graph $\xymatrix{
1 \are[r] & 2
}$ has $5$ subgraphs: itself; the subgraph obtained by removing the edge (but
leaving both vertices intact); the two subgraphs obtained by removing one
vertex (along with the edge); and finally the subgraph obtained by removing everything.
\begin{definition}
Let $G=\left( V,E,\varphi\right) $ be a multigraph. Let $v\in V$ be a
vertex. Then, $G\setminus v$ shall denote the subgraph $\left( V\setminus
\left\{ v\right\} ,E^{\prime},\varphi\mid_{E^{\prime}}\right) $ of $G$,
where $E^{\prime}$ is the set of all edges $e\in E$ that don't contain the
vertex $v$. In other words, $G\setminus v$ is the subgraph of $G$ obtained by
removing the vertex $v$ and all edges containing $v$.
\end{definition}
For example, if $G$ is the $3$-vertex graph $\xymatrix{
1 \are[r] & 2 \are[r] & 3
}$, then $G\setminus1$ is the $2$-vertex graph $\xymatrix{
2 \are[r] & 3
}$, whereas $G\setminus2$ is the $2$-vertex graph $\xymatrix{
1 & 3
}$.
\begin{definition}
Let $G=\left( V,E,\varphi\right) $ be a multigraph. A vertex $v\in V$ is
said to be \textit{non-cut} if the multigraph $G\setminus v$ is connected or
has no vertices.
\end{definition}
For example, if $G$ is the $3$-vertex graph $\xymatrix{
1 \are[r] & 2 \are[r] & 3
}$, then the non-cut vertices of $G$ are $1$ and $3$.
\begin{definition}
Let $G$ be a multigraph. Let $\left( v_{0},e_{1},v_{1},e_{2},v_{2}%
,\ldots,v_{k-1},e_{k},v_{k}\right) $ be a walk in $G$. Then, the
\textit{length} of this walk is defined to be $k$ (that is, the number of edges).
\end{definition}
\begin{definition}
Let $G=\left( V,E,\varphi\right) $ be a connected multigraph. Let $v\in V$
and $w\in V$ be two vertices. Then, $d\left( v,w\right) $ (the
\textit{distance} between $v$ and $w$) is defined as the smallest length of a
path from $v$ to $w$. (This is also the smallest length of a walk from $v$ to
$w$, because every walk from $v$ to $w$ can be trimmed down to a path of the
same or smaller length.)
\end{definition}
\begin{exercise}
\label{exe.graph.non-cut.1}Let $G=\left( V,E,\varphi\right) $ be a connected
multigraph. Let $v\in V$ be any vertex.
\textbf{(a)} Pick any $w\in V$ such that $d\left( v,w\right) $ is maximum
(among all $w\in V$). Prove that $w$ is a non-cut vertex of $G$.
\textbf{(b)} Let $n=\left\vert V\right\vert $. Prove that $\sum_{u\in
V}d\left( v,u\right) \leq\dbinom{n}{2}$.
\end{exercise}
Exercise \ref{exe.graph.non-cut.1} \textbf{(a)} is particularly important, as
it guarantees that any connected multigraph with at least one vertex has a
non-cut vertex. This allows proving properties of connected multigraphs by
induction on the number of vertices.
Note that the inequality in Exercise \ref{exe.graph.non-cut.1} \textbf{(b)} is
sharp (i.e., equality can hold): If $V$ is the $n$-vertex graph $\xymatrix{
1 \are[r] & 2 \are[r] & 3 \are[r] & \cdots \are[r] & n
}$ and if $v=1$, then $\sum_{u\in V}\underbrace{d\left( v,u\right) }%
_{=u-1}=0+1+\cdots+\left( n-1\right) =\dbinom{n}{2}$.
\subsection{Non-cut vertices II: subgraphs}
\begin{exercise}
\label{exe.graph.non-cut.2}Let $G$ be a connected multigraph. Let $H$ be a
connected subgraph of $G$. Prove that the number of non-cut vertices of $H$ is
$\leq$ to the number of non-cut vertices of $G$.
\end{exercise}
\subsection{When do transpositions generate all permutations?}
\begin{exercise}
\label{exe.graph.transpositions-gen}Let $G=\left( V,E,\varphi\right) $ be a
connected multigraph.
For each $e=\left\{ u,v\right\} \in\mathcal{P}_{2}\left( V\right) $, we
let $t_{e}$ be the permutation of $V$ that switches $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}
[You are allowed to use the result of Exercise \ref{exe.graph.non-cut.1}
\textbf{(a)} here even if you have not solved that exercise.]
Note that Exercise \ref{exe.graph.transpositions-gen} generalizes Exercise 3
on \href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw7os.pdf}{Math 4990
homework set \#7}, because the simple graph $\left( \left[ n\right]
,\left\{ \left\{ 1,2\right\} ,\left\{ 1,3\right\} ,\ldots,\left\{
1,n\right\} \right\} \right) $ (for $n > 0$) is connected.
Exercise \ref{exe.graph.transpositions-gen} also generalizes the fact that
every permutation of $\left[ n\right] $ can be written as a composition of
simple transpositions $s_{i}=t_{i,i+1}$, because the simple graph $\left(
\left[ n\right] ,\left\{ \left\{ 1,2\right\} ,\left\{ 2,3\right\}
,\ldots,\left\{ n-1,n\right\} \right\} \right) $ (for $n > 0$) is connected.
Exercise \ref{exe.graph.transpositions-gen} also has a converse: If $G=\left(
V,E,\varphi\right) $ is a multigraph 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{Watersheds in digraphs}
\Needspace{25cm}
\begin{example}
Consider the following digraph:%
\begin{equation}
\xymatrix{ & 1 \ar[dl] \ar[dr] \\ 2 \ar[dd] \ar[dr] & & 4 \ar[dd] \ar[dl] \\ & 3 \ar[dl] \ar[dr] \\ 6 \ar[d] & & 5 \\ 7 }.
\label{eq.exa.confluence.1}%
\end{equation}
Imagine a game chip placed initially at the vertex $1$. The chip is allowed to
move along the arcs of the digraph (from source to target). For example, the
chip can first move along the arc $\left( 1,2\right) $ to $2$, then along
the arc $\left( 2,3\right) $ to $3$, then along the arc $\left( 3,5\right)
$ to $5$. Once it arrives at $5$, it can no longer move, because there are no
arcs with source $5$. We say that $5$ is a \textit{sink} for this reason (see
Exercise \ref{exe.confluence.diamond} below for the precise definition).
Alternatively, the chip could have moved along the arc $\left( 1,2\right) $
to $2$, then along the arc $\left( 2,6\right) $ to $6$, then along the arc
$\left( 6,7\right) $ to $7$. At this point it would again be stuck, since
$7$ is a sink.
Thus, the chip can get stuck in \textbf{two different sinks}, depending on the
path it takes. (It will always get stuck in \textbf{some} sink, because our
digraph has no cycles.)
Now, consider the following digraph:%
\begin{equation}
\xymatrix{ 7 \ar[d] \\ 6 \ar[dd] \ar[dr] & & 5 \ar[dd] \ar[dl] & 8 \ar[d] & 10 \ar[dl] \\ & 3 \ar[dr] \ar[dl] & & 9 \\ 2 \ar[dr] & & 4 \ar[dl] \\ & 1 }.
\label{eq.exa.confluence.2}%
\end{equation}
This time, any chip starting at any given vertex will necessarily get stuck at
\textbf{the same sink} no matter what path it takes (either the sink $1$, if
it started at one of the vertices $1,2,3,4,5,6,7$; or the sink $9$, if it
started at one of the vertices $8,9,10$). How can we show this without
checking all possible paths?
One criterion, which is clearly necessary, is that there are no
\textquotedblleft watershed vertices\textquotedblright: i.e., there is no
vertex $u$ from which the chip can take two different arcs $\left(
u,v\right) $ and $\left( u,w\right) $ such that $v$ and $w$
\textquotedblleft never meet again\textquotedblright\ (i.e., there exists no
vertex reachable both from $v$ and from $w$). For example, the digraph
(\ref{eq.exa.confluence.1}) has a \textquotedblleft watershed
vertex\textquotedblright\ (namely, $3$, because the arcs $\left( 3,5\right)
$ and $\left( 3,6\right) $ lead to the vertices $5$ and $6$ which
\textquotedblleft never meet again\textquotedblright).
The next exercise claims that this condition is also sufficient (as long as
our digraph has no cycles). That is, if there are no \textquotedblleft
watershed vertices\textquotedblright\ and no cycles, then the sink at which a
chip gets stuck is uniquely determined by the vertex it started at (rather
than by the path it took).
\end{example}
\begin{exercise}
\label{exe.confluence.diamond}Let $D$ be a multidigraph having no cycles. A
vertex $v$ of $D$ is said to be a \textit{sink} if there is no arc of $D$ with
source $v$.
If $u$ and $v$ are any two vertices of $D$, then:
\begin{itemize}
\item we write $u\longrightarrow v$ if and only if $D$ has an \textbf{arc}
with source $u$ and target $v$;
\item we write $u\overset{\ast}{\longrightarrow}v$ if and only if $D$ has a
\textbf{path} from $u$ to $v$.
\end{itemize}
The so-called \textit{no-watershed condition} says that for any three vertices
$u$, $v$ and $w$ of $D$ satisfying $u\longrightarrow v$ and $u\longrightarrow
w$, there exists a vertex $t$ of $D$ such that $v\overset{\ast
}{\longrightarrow}t$ and $w\overset{\ast}{\longrightarrow}t$.
Assume that the no-watershed condition holds. Prove that for each vertex $p$
of $D$, there exists a \textbf{unique} sink $q$ of $D$ such that
$p\overset{\ast}{\longrightarrow}q$.
[\textbf{Hint:} Induction on the ``height'' of $p$ (that is, the length of a
longest path starting at $p$).]
\end{exercise}
\subsection{Acyclic orientations and source pushing}
Roughly speaking, an \textit{orientation} of a multigraph $G$ is a way to
assign to each edge of $G$ a direction (thus making it an arc). If the
resulting \textbf{multidigraph} has no cycles, then this orientation will be
called \textit{acyclic}. A rigorous way to state this definition is the following:
\begin{definition}
\label{def.aco.aco} Let $G = \left( V, E, \psi\right) $ be a multigraph.
\textbf{(a)} An \textit{orientation} of $G$ is a map $\phi: E \to V \times V$
such that each $e \in E$ has the following property: If we write $\phi\left(
e \right) $ in the form $\phi\left( e \right) = \left( u, v \right) $,
then $\psi\left( e \right) = \left\{ u, v \right\} $.
\textbf{(b)} An orientation $\phi$ of $G$ is said to be \textit{acyclic} if
and only if the multidigraph $\left( V, E, \phi\right) $ has no cycles.
\end{definition}
\begin{example}
Let $G = \left( V, E, \psi\right) $ be the following multigraph:
\[
\xymatrix{
& 2 \are[dl]^a \are@/_2pc/[dl]_b \are[dr]^c \\
1 \are[rr]_d & & 3
}
\]
Then, the following four maps $\phi$ are orientations of $G$:
\begin{itemize}
\item the map sending $a$ to $\left( 1, 2 \right) $, sending $b$ to $\left(
1, 2 \right) $, sending $c$ to $\left( 3, 2 \right) $, and sending $d$ to
$\left( 1, 3 \right) $;
\item the map sending $a$ to $\left( 2, 1 \right) $, sending $b$ to $\left(
1, 2 \right) $, sending $c$ to $\left( 3, 2 \right) $, and sending $d$ to
$\left( 3, 1 \right) $;
\item the map sending $a$ to $\left( 1, 2 \right) $, sending $b$ to $\left(
1, 2 \right) $, sending $c$ to $\left( 2, 3 \right) $, and sending $d$ to
$\left( 1, 3 \right) $;
\item the map sending $a$ to $\left( 1, 2 \right) $, sending $b$ to $\left(
1, 2 \right) $, sending $c$ to $\left( 2, 3 \right) $, and sending $d$ to
$\left( 3, 1 \right) $.
\end{itemize}
Here are the multidigraphs $\left( V,E,\phi\right) $ corresponding to these
four maps (in the order mentioned):
\[%
\begin{tabular}
[c]{|c|c|c|c|}%
\xymatrix{ & 2 \ar@{<-}[dl]^a \ar@{<-}@/_2pc/[dl]_b \ar@{<-}[dr]^c \\ 1 \ar[rr]_d & & 3 } &
\xymatrix{ & 2 \ar[dl]^a \ar@{<-}@/_2pc/[dl]_b \ar@{<-}[dr]^c \\ 1 \ar@{<-}[rr]_d & & 3 } &
\xymatrix{ & 2 \ar@{<-}[dl]^a \ar@{<-}@/_2pc/[dl]_b \ar[dr]^c \\ 1 \ar[rr]_d & & 3 } &
\xymatrix{ & 2 \ar@{<-}[dl]^a \ar@{<-}@/_2pc/[dl]_b \ar[dr]^c \\ 1 \ar@{<-}[rr]_d & & 3 }
\end{tabular}
\
\]
Only the first and the third of these orientations $\phi$ are acyclic (since
only the first and the third of these multidigraphs have no cycles).
\end{example}
\begin{definition}
Let $G = \left( V, E, \psi\right) $ be a multigraph.
Let $\phi$ be an orientation of $G$.
A vertex $v\in V$ is said to be a \textit{source} of $\phi$ if no arc of the
multidigraph $\left( V,E,\phi\right) $ has target $v$. Exercise 6
\textbf{(a)} on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/hw5s.pdf}{Math 5707
(Spring 2017) homework set \#5} shows that if $\phi$ is acyclic and if
$V\neq\varnothing$, then there exists a source of $\phi$.
If $v$ is a source of $\phi$, then we can define a new orientation
$\phi^{\prime}$ of $G$ as follows:
\begin{itemize}
\item For each $e \in E$ satisfying $v \in\psi\left( e \right) $, we set
$\phi^{\prime}\left( e \right) = \left( u, v \right) $, where $u$ is
chosen such that $\phi\left( e \right) = \left( v, u \right) $.
\item For all other $e \in E$, we set $\phi^{\prime}\left( e \right) =
\phi\left( e \right) $.
\end{itemize}
(Roughly speaking, this simply means that $\phi^{\prime}$ is obtained by
$\phi$ by reversing the directions of all edges that contain $v$.) We say that
this new orientation $\phi^{\prime}$ is obtained from $\phi$ by
\textit{pushing the source $v$}.
\end{definition}
\Needspace{25cm}
\begin{example}
Let $G = \left( V, E, \psi\right) $ be the following multigraph:
\[
\xymatrix{
& 2 \are[dl]_a \are[dr]^b \\
1 \are[d]_c & & 3 \are[d]^d \\
4 \are@/^/[rr]^e \are@/_/[rr]_f & & 5
} .
\]
Consider the orientation $\phi$ of $G$ for which the multidigraph $\left( V,
E, \phi\right) $ looks as follows:
\[
\xymatrix{
& 2 \ar@{<-}[dl]_a \ar@{<-}[dr]^b \\
1 \ar[d]_c & & 3 \ar[d]^d \\
4 \ar@/^/[rr]^e \ar@{<-}@/_/[rr]_f & & 5
} .
\]
(Formally speaking, this is the orientation $\phi$ that sends the edges $a, b,
c, d, e, f$ to the pairs $\left( 1, 2 \right) , \left( 3, 2 \right) ,
\left( 1, 4 \right) , \left( 3, 5 \right) , \left( 4, 5 \right) ,
\left( 5, 4 \right) $, respectively.)
This orientation $\phi$ has two sources $1$ and $3$. We can transform this
orientation by pushing the source $1$; this results in the following
orientation $\phi^{\prime}$ (shown here by drawing the multidigraph $\left(
V, E, \phi^{\prime}\right) $):
\[
\xymatrix{
& 2 \ar[dl]_a \ar@{<-}[dr]^b \\
1 \ar@{<-}[d]_c & & 3 \ar[d]^d \\
4 \ar@/^/[rr]^e \ar@{<-}@/_/[rr]_f & & 5
} .
\]
This new orientation $\phi^{\prime}$ has a single source, $3$. If we push this
source, we obtain a new orientation $\phi^{\prime\prime}$, which looks as
follows (again, represented by the multidigraph $\left( V, E, \phi
^{\prime\prime}\right) $):
\[
\xymatrix{
& 2 \ar[dl]_a \ar[dr]^b \\
1 \ar@{<-}[d]_c & & 3 \ar@{<-}[d]^d \\
4 \ar@/^/[rr]^e \ar@{<-}@/_/[rr]_f & & 5
} .
\]
This orientation $\phi^{\prime\prime}$, in turn, has a single source, $2$. If
we push this source, we obtain a new orientation $\phi^{\prime\prime\prime}$,
which looks as follows (again, represented by the multidigraph $\left( V, E,
\phi^{\prime\prime\prime}\right) $):
\[
\xymatrix{
& 2 \ar@{<-}[dl]_a \ar@{<-}[dr]^b \\
1 \ar@{<-}[d]_c & & 3 \ar@{<-}[d]^d \\
4 \ar@/^/[rr]^e \ar@{<-}@/_/[rr]_f & & 5
} .
\]
This orientation $\phi^{\prime\prime\prime}$ has no sources, and thus cannot
be transformed any further by pushing sources.
\end{example}
The preceding example suggests some questions: For example, given an
orientation of a multigraph, can we keep pushing sources indefinitely, or will
we eventually end up at an orientation that has no more sources? The following
is easy to see:
\begin{proposition}
Let $\phi$ be an acyclic orientation of a multigraph $G = \left( V, E,
\psi\right) $. Let $v$ be a source of $\phi$. Then, the orientation obtained
from $\phi$ by pushing the source $v$ is again acyclic.
\end{proposition}
This proposition shows that if we start with an acyclic orientation of a
multigraph (with at least one vertex), then we can keep pushing sources
indefinitely (since the orientation always remains acyclic, and thus there
always will be sources to push). The next exercise (specifically,
Exercise~\ref{exe.aco.source-push.finite} \textbf{(c)}) yields a converse (for
connected multigraphs): If we can keep pushing sources indefinitely (or, even,
if we can keep pushing sources for more than $\dbinom{n}{2}$ times in a row),
then our orientation must have been acyclic.
\begin{exercise}
\label{exe.aco.source-push.finite} Let $G=\left( V,E,\psi\right) $ be a
connected multigraph. Set $n=\left\vert V\right\vert $.
Let $\left( \phi_{0}, \phi_{1}, \ldots, \phi_{k} \right) $ be a sequence of
orientations of $G$, and let $\left( v_{1}, v_{2}, \ldots, v_{k} \right) $
be a sequence of vertices of $G$ such that for each $i \in\left\{ 1, 2,
\ldots, k \right\} $, the orientation $\phi_{i}$ is obtained from $\phi
_{i-1}$ by pushing the source $v_{i}$ (in particular, this is saying that
$v_{i}$ is a source of $\phi_{i-1}$).
\textbf{(a)} Prove that if $u$ and $w$ are two mutually adjacent vertices of
$G$, then between any two consecutive appearances of $u$ in the sequence
$\left( v_{1},v_{2},\ldots,v_{k}\right) $, the vertex $w$ must appear at
least once.
Now, assume that $k>\dbinom{n}{2}$.
\textbf{(b)} Prove that each vertex of $G$ appears at least once in the
sequence $\left( v_{1},v_{2},\ldots,v_{k}\right) $.
\textbf{(c)} Prove that the orientations $\phi_{0},\phi_{1},\ldots,\phi_{k}$
are acyclic.
[\textbf{Hint:} For part \textbf{(b)}, assume that some vertex $v$ does not
appear in the sequence $\left( v_{1},v_{2},\ldots,v_{k}\right) $. Then,
argue that any vertex $u\in V$ appears at most $d\left( v,u\right) $ times
in this sequence, using part \textbf{(a)}. Then apply Exercise
\ref{exe.graph.non-cut.1} \textbf{(b)}. For part \textbf{(c)}, first argue
that any cycle existing in \textbf{one} of the orientations $\phi_{0},\phi
_{1},\ldots,\phi_{k}$ would automatically exist in \textbf{all} of these orientations.]
\end{exercise}
[You may use Exercise \ref{exe.graph.non-cut.1} \textbf{(b)} even if you have
not solved this exercise.]
\begin{exercise}
\label{exe.aco.source-push.confluent}Let $G=\left( V,E,\psi\right) $ be a
connected multigraph.
Fix a vertex $v\in V$.
If $\phi$ and $\phi^{\prime}$ are two orientations of $G$, then we write
$\phi\overset{v}{\longrightarrow}\phi^{\prime}$ if and only if $\phi^{\prime}$
is obtained from $\phi$ by repeatedly pushing sources without ever pushing the
source $v$. (More rigorously: We write $\phi\overset{v}{\longrightarrow}%
\phi^{\prime}$ if and only if there exist a sequence $\left( \phi_{0}%
,\phi_{1},\ldots,\phi_{k}\right) $ of orientations of $G$ and a sequence
$\left( v_{1},v_{2},\ldots,v_{k}\right) $ of vertices of $G$ distinct from
$v$ such that for each $i\in\left\{ 1,2,\ldots,k\right\} $, the orientation
$\phi_{i}$ is obtained from $\phi_{i-1}$ by pushing the source $v_{i}$ (in
particular, this is saying that $v_{i}$ is a source of $\phi_{i-1}$), and such
that $\phi_{0}=\phi$ and $\phi_{k}=\phi^{\prime}$.)
If $\phi$ is an orientation of $G$, then we say that $\phi$ is $v$%
\textit{-fleeing} if $\phi$ has no source other than $v$. (Note that $\phi$
may or may not have $v$ as a source.)
For any orientation $\phi$ of $G$, prove that there is a \textbf{unique}
$v$-fleeing orientation $\phi^{\prime}$ such that $\phi
\overset{v}{\longrightarrow}\phi^{\prime}$.
[\textbf{Hint:} Consider a new multidigraph $O_{v}$ whose vertices are the
orientations of $G$, and which has an arc from an orientation $\phi$ to an
orientation $\phi^{\prime}$ if and only if $\phi^{\prime}$ can be obtained
from $\phi$ by pushing a source different from $v$. Use Exercise
\ref{exe.aco.source-push.finite} \textbf{(b)} to argue that this multidigraph
$O_{v}$ has no cycles, and then use Exercise \ref{exe.confluence.diamond}.]
\end{exercise}
[You may use both exercises mentioned in the hint without solving them.]
\subsection{On network flows}
The following two exercises are probably best approached after reading
\cite{5707lec16}.
\begin{exercise}
\label{exe.flows.multi}State and prove the analogues of all definitions and
results from \cite[\S 1.1--\S 1.8]{5707lec16} for networks in which the
digraph is replaced by a multidigraph (so the arcs are no longer just pairs of
vertices, but rather arbitrary objects that map to pairs of vertices).
[\textbf{Hint:} You don't have to give the whole proofs, as long as you
explain what needs to be modified and how. For example, what would $a^{-1}$ be
if $a$ is an arc of a multidigraph? Alternatively, you can deduce the
analogues from the results proven in \cite{5707lec16}.]
\end{exercise}
\begin{definition}
Let $G$ be a multigraph. A \textit{spanning subgraph} of $G$ means a subgraph
$H$ of $G$ such that each vertex of $G$ is a vertex of $H$.
\end{definition}
Thus, a spanning subgraph of a multigraph $G$ is obtained from $G$ by removing
some edges\footnote{\textquotedblleft Some\textquotedblright\ includes the
options \textquotedblleft none\textquotedblright\ and \textquotedblleft
all\textquotedblright.}, but not removing any vertices.
\begin{definition}
Let $H=\left( V,E,\varphi\right) $ be a multigraph. The \textit{degree
function} of $H$ means the function $\deg:V\rightarrow\mathbb{N}$ that sends
each vertex $v\in V$ of $H$ to its degree $\deg v$.
\end{definition}
\begin{exercise}
\label{exe.ore-ryser}Let $\left( G;X,Y\right) $ be a bipartite graph, where
$G=\left( V,E,\varphi\right) $ is a multigraph. Let $\gamma:V\rightarrow
\mathbb{N}$ be a function such that each $y\in Y$ satisfies $\gamma\left(
y\right) \leq\deg y$. Prove that the following two statements are equivalent:
\begin{statement}
\textit{Statement 1:} There exists a spanning subgraph of $G$ with degree
function $\gamma$. (In other words, there exists a spanning subgraph of $G$
such that each vertex $v\in V$ is contained in exactly $\gamma\left(
v\right) $ edges of this subgraph.)
\end{statement}
\begin{statement}
\textit{Statement 2:} Every subset $S$ of $X$ satisfies%
\[
\sum\limits_{s\in S}\gamma\left( s\right) \leq\sum\limits_{y\in Y}%
\min\left\{ \gamma\left( b\right) ,\deg b\right\} ,
\]
and this inequality becomes an equality for $S=X$ (but not necessarily only
for $S=X$).
\end{statement}
\end{exercise}
\begin{thebibliography}{99999999} %
\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[Grinbe17]{5707lec16}Darij Grinberg, \textit{UMN, Spring 2017, Math
5707: Lecture 16 (flows and cuts in networks)}, \newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/t/17s/5707lec16.pdf} .
\end{thebibliography}
\end{document}