\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{mathtools}
\usepackage{float}
\usepackage{enumerate}
\usepackage{hyperref}
\usepackage{comment}

\setlength{\parindent}{0pt}

\usepackage{amsthm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{corollary}{Corollary}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{claim}{Claim}[section]
\newtheorem{axiom}{Axiom}[section]

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]

\theoremstyle{remark}
\newtheorem{remark}{Remark}[section]
\newtheorem{example}{Example}[section]
\newtheorem{observation}{Observation}[section]

\let\originalleft\left
\let\originalright\right
\renewcommand{\left}{\mathopen{}\mathclose\bgroup\originalleft}
\renewcommand{\right}{\aftergroup\egroup\originalright}
\newcommand{\laplace}[1]{\mathcal{L}\left\{#1\right\}}
\newcommand{\pset}[1]{\mathcal{P}\left(#1\right)}
\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\inprod}[1]{\left\langle#1\right\rangle}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\val}{val}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\charac}{char}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\intemb}{int}
\DeclareMathOperator{\com}{com}
\DeclareMathOperator{\vecspan}{span}
\DeclareMathOperator{\defequiv}{\mkern4mu :\mkern-8mu \iff}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\lcm}{lcm}

\newcommand{\ind}[1]{\mathbf{1}_{\left\{#1\right\}}}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\hateq}{\mathrel{\widehat{=}}}

\makeatletter
\newcommand{\axcirc}[1]{\mathbin{\mathpalette\make@circled#1}}
\newcommand{\make@circled}[2]{%
	\ooalign{$\m@th#1\largecirc{#1}$\cr\hidewidth$\m@th#1#2$\hidewidth\cr}%
}
\newcommand{\largecirc}[1]{%
	\vcenter{\hbox{\scalebox{1.5}{$\m@th#1\bigcirc$}}}%
}
\makeatother

\newcommand{\letprob}{Let $(S, \Sigma, P)$ be a probability space. {}}
\let\letprobalways\letprob

% (un)comment to remove useless fluff
\renewcommand{\letprob}{}

\let\tilde\widetilde
\let\hat\widehat

\title{Discrete Mathematics II}
\author{Koen Oostveen}

\begin{document}
	\maketitle
	\section{Integers, primes, Euclidean algorithm}
	\begin{theorem}[Properties of $\Z, \N$]~
		\begin{itemize}
			\item $Z_{\geq 0} := \N$ is \textbf{well-ordered}, that is, any subset has a least element by $\leq$. More formally, if $S \subseteq \N$, then there exists a unique $m \in S$ such that for all $x \in S$, $m \leq x$.
			\item $(Z, \cdot)$ has no zero divisors, that is, for all $a, b \in \Z$, if $ab = 0$, then $a = 0$ or $b = 0$.
		\end{itemize}
	\end{theorem}
	\begin{corollary}
		If $a, x, y \in \Z$ and $a \neq 0$, as well as $ax = ay$, then $x = y$. That is, the map $x \mapsto ax$ is injective for all $a \neq 0$.\\
		The proof is very elementary:
		\[ ax = ay \implies ax - ay = 0 \implies a(x - y) = 0 \implies a = 0 \lor x - y = 0 \stackrel{a \neq 0}{\implies} x - y = 0 \implies x = y  \]
	\end{corollary}
	\begin{definition}
		Let $a, b \in \Z$. We say that $a$ \textbf{divides} $b$ if there exists an $n \in \Z$ such that $b = na$. We define
		\[ a \mid b \defequiv a \text{ divides } b \]
	\end{definition}
	\begin{theorem}[Properties of $\mid$]~
		\begin{itemize}
			\item If $a \mid b$, then for all $x \in \Z$, $a \mid bx$.
			\item If $x = y + z$ and some $a$ exists that divides two of $x, y, z \in \Z$, then it divides all.
			\item If $a \mid b$ and $a \mid c$ then for all $x, y \in \Z$, $a\mid bx + cy$
		\end{itemize}
	\end{theorem}
	\begin{theorem}
		Let $a, b \in \Z$, let $b > 0$, then there exist unique $q, r \in \Z$ with $0 \leq r < b$ such that
		\[ a = qb + r \]
	\end{theorem}
	\begin{proof}
		Let $r$ be chosen in the equivalence class of $a$ modulo $b$, with the particular unique representatitive that satisfies $0 \leq r < b$, which exists uniquely. We have $a - r = qb$ for some unique $q \in \Z$. From this clearly follows $a = qb + r$. To show that these particular choices for $q, r$ are unique, let $\tilde q, \tilde r \in \Z$ such that $a = \tilde q b + \tilde r$. Clearly we still must have that $r \equiv \tilde r \pmod{b}$, so that $r - \tilde r = nb$ for some $n \in \Z$. Then $0 = b(q - \tilde q) + r - \tilde r = b(q - \tilde q + n)$ so that $\tilde q - q = n$. But then if $n \neq 0$ we get that $\tilde q = q + n \geq n$, which is a contradiction, so $n = 0$, whence $\tilde q = q$, which gives $0 = r - \tilde r$, so that $r = \tilde r$.
	\end{proof}
	\begin{definition}[GCD]
		Let $a, b \in \Z$. The largest $x \in \Z$ by $\leq$ such that $x \mid a$ and $x \mid b$ defines $\gcd(a, b) := x$.\\
		This definition is sound, because the set of $x \in \Z$ for which this holds is nonempty and bounded above; consider that $1 \mid a$ and $1 \mid b$, so the set is nonempty, and the bound from above can be realized by the fact that if $x \mid a$ and $x \mid b$, then $x \leq a$ and $x \leq b$ (because $x > 0$ wlog), so in particular we have the upper bound $\min\{a, b\}$.\\
		Note that additionally this set is finite, so in particular the maximum is attained and is unique. In this analysis above, we clearly ignore the cases for $a = 0$ or $b = 0$.
	\end{definition}
	\begin{theorem}
		Let $a, b \in \Z^*$, then
		\[ \gcd(a, b) = \min \underbrace{\{ ax + by > 0 \mid x, y \in \Z \}}_{=: S} \]
	\end{theorem}
	\begin{proof}
		From $\gcd(a, b) \mid a$ and $\gcd(a, b) \mid b$ it follows that there exist $p, q \in \Z$ such that $a = p\gcd(a, b)$ and $b = q\gcd(a, b)$. Clearly, $\operatorname{gcd}(a, b) \mid s$ for all $s \in S$, which also gives $s \geq \gcd(a, b)$, so the gcd is a lower bound of $S$. Now it thus suffices to show it lies in $S$. This involves ugly calculations I won't do.
	\end{proof}
	\begin{corollary}
		Let $d$ be any divisor of $a$ and $b$, then $d \mid \gcd(a, b)$
	\end{corollary}
	\begin{definition}
		Let $\operatorname{gcd}(a, b) = ax + by$, we say that these $x, y \in \Z$ are Bézout coefficients of $a, b$.
	\end{definition}
	\begin{definition}
		$a, b \in \Z$ are said to be \textbf{coprime} if $\gcd(a, b) = 1$.
	\end{definition}
	\begin{lemma}
		Let $a, b \in \Z$, $n \in \N$, such that $nb \leq a$. Then $\gcd(a, b) = \gcd(a - nb, b)$.
	\end{lemma}
	\begin{corollary}[Euclidean algorithm]
		Let $q, r \in \Z$ be according to a previous theorem such that $a = qb + r$. Then $\gcd(a, b) = \gcd(r, b)$, whence we have a sequence of remainders $(r_n)_{n \in \N}$ such that $r_0 = a$, $r_1 = b$, and then $r_{n + 2} = r_n \mod r_{n+1}$ for all $n \in \N$, which eventually reaches $0$, the last nonzero term then clearly equals $\operatorname{gcd}(a, b)$.
	\end{corollary}
	\begin{definition}[GCD]
		Let $a, b \in \Z$. The smallest $x \in \Z$ by $\leq$ such that $a \mid x$ and $b \mid x$ defines $\lcm(a, b) := x$.
	\end{definition}
	\begin{theorem}
		For all $a, b \in \Z$,
		\[ ab = \gcd(a, b) \lcm(a, b) \]
	\end{theorem}
	\begin{definition}
		Let $p \in \N^*$, then $p$ is called \textbf{prime} if for all $x \in \Z$, $x \mid p$ implies $x = 1$ or $x = p$, whence for all $q \in \N$ with $q \neq p$ we have $\gcd(p, q) = 1$.
	\end{definition}
	\begin{lemma}
		For all $n \in \N^*$, there exists a prime $p$ such that $p \mid n$.
	\end{lemma}
	\begin{proof}
		If $n$ is prime, we are done, great. Otherwise, there exists $1 < m < p$ such that $m \mid n$, so that there exists $q \in \Z$ with $n = qm$. By doing a hidden induction we know there exists a prime $p$ such that $p \mid m$, whence $p \mid n$.
	\end{proof}
	\begin{lemma}
		If $p \mid ab$ then $p \mid a$ or $p \mid b$ for prime $p$.
	\end{lemma}
	\newpage
	\section{Graph theory}
	\begin{definition}
		Let $V$ be any set. Let $E \in \pset{V \times V}$. We say that $(V, E)$ is a (directed) \textbf{graph}. If for all $(v, w) \in E$ we also have $(w, v) \in E$, $(V, E)$ is called \textbf{undirected}. We also identify $E$ with the set
		\[ \{ \{v, w\} \mid (v, w) \in E \} \]
		for such an undirected graph, just for convenience. The remainder of this section deals only with undirected graphs.
	\end{definition}
	\begin{definition}
		Let $G = (V, E)$ be an undirected graph. Let $v \in V$ (called a \textbf{vertex}), let $e \in E$ (called an \textbf{edge}), then vertex $v$ is called \textbf{incident} with edge $e$ if $v \in e$.\\
		Two vertices $v, w \in V$ are called \textbf{adjacent} if $\{v, w\} \in E$. We also define the following sets
		\[ N(v) := \{ w \in V \mid w \neq v \land \{v, w\} \in E \} \]
		\[ \delta(v) := \{ e \in E \mid v \in e \} \]
		respectively called the \textbf{neighborhood} and \textbf{incident edges} of $v$. We say that the \textbf{degree} of $v$, denoted by $d(v) := |N(v)| = |\delta(v)|$.
	\end{definition}
	\begin{definition}
		Let $G = (V, E)$ be a graph. We say that a graph $\tilde G = (\tilde V, \tilde E)$ is a \textbf{subgraph} of $G$ if $\tilde V \subseteq V$, $\tilde E \subseteq E$, and of course because $\tilde G$ is a graph, also $\tilde E \subseteq \tilde V \times \tilde V$.
	\end{definition}
	\begin{definition}
		Let $G = (V, E)$ be a graph. We say that a subgraph $\tilde G = (\tilde V, \tilde E)$ is \textbf{induced} by $\tilde V$, if $\tilde E$ is the \textbf{largest subset} of $E$ such that $\tilde G$ is a graph. Explicitely, this set is
		\[ \tilde E := \{ \{v, w\} \in E \mid v \in \tilde V \land w \in \tilde V \} \]
	\end{definition}
	\begin{definition}
		Let $G = (V, E)$ be a graph. A \textbf{walk} of $G$ is a finite sequence $v_1, \ldots, v_n \in V$ such that for all $1 \leq i < n$ we have $\{v_i, v_{i+1}\} \in E$.\\
		A \textbf{closed walk} of $G$ is a walk $v_1, \ldots, v_n$ such that $v_1 = v_n$.\\
		A \textbf{trail} of $G$ is a walk of $G$ such that every edge $\{v_i, v_{i+1}\}$ occurs as most once. A \textbf{circuit} of $G$ is a closed walk of $G$ that is also a trail.\\
		A \textbf{path} of $G$ is a walk of $G$ such that every vertex $v_i$ occurs at most once. A \textbf{cycle} of $G$ is a path of $G$ that is also a closed walk of $G$.
	\end{definition}
	\begin{lemma}
		The number of vertices with odd degree is even.
	\end{lemma}
	\begin{definition}
		Let $G = (V, E)$ be a graph. $G$ is said to be \textbf{connected} if for any two $v, w \in V$, there exists a path starting at $v$ and ending in $w$. That is, a path $v_1, \ldots, v_n$ such that $v_1 = v$, $v_n = w$.
	\end{definition}
	\begin{lemma}
		Any graph $G = (V, E)$ can be written as the disjoint union of at most $|V|$ connected subgraphs. This decomposition is unique, we call these connected subgraphs the \textbf{connected components} of $G$.
	\end{lemma}
	\begin{definition}
		An edge $e \in E$ in a graph $G = (V, E)$ is called a \textbf{bridge} if $(V, E \setminus \{e\})$ has more connected components than $G$.
	\end{definition}
	\begin{lemma}
		If $G = (V, E)$ is connected, then $|V| \leq |E| + 1$.
	\end{lemma}
	\begin{definition}
		An undirected graph $G$ is called a \textbf{forest} if $G$ has no cycles, that is, for any closed walk of the graph, said walk is not a cycle. A forest $G$ is called a \textbf{tree} if it is connected.
	\end{definition}
	\begin{theorem}
		For an undirected graph $G = (V, E)$ tfae
		\begin{itemize}
			\item $G$ is a tree.
			\item $G$ is a forest with $|E| = |V| - 1$.
			\item $G$ is connected with $|E| = |V| - 1$.
			\item There exists a unique path between any two vertices
			\item $G$ is a forest, and introducing one $e \in \pset{V \times V} \setminus E$ into $G$, that is, constructing $\tilde G := (V, E \cup \{e\})$, gives $\tilde G$ exactly one cycle.
		\end{itemize}
	\end{theorem}
	\subsection{Euler graphs}
	\begin{definition}
		A graph is called \textbf{Eulerian} if there exists a closed walk (circuit) that visits every edge exactly once. Said walk is called an \textbf{Euler walk} or \textbf{Euler tour}.
	\end{definition}
	\begin{theorem}
		A graph is Eulerian if and only if it is connected and every vertex has even degree.
	\end{theorem}
	\subsection{Shortest path}
	Let $G = (V, E)$ be a \textbf{directed graph}. Note that undirected graphs are also allowed, because essentially they form a subset of the directed graphs, the identity is an inclusion, unless $E$ was chosen to be a subset of all doublett sets of $V$, in which case we have the injection
	\[ E \mapsto \{ (v, w) \mid \{v, w\} \in E \} \cup \{ (w, v) \mid \{v, w\} \in E \} \]
	We are also given a \textbf{cost function} $c : E \to \R$, and two vertices $s, t$. The goal is to find a path $P$ (if it exists) consisting of vertices $v_1, \ldots, v_n$ such that $v_1 = s$, $v_n = t$, and
	\[ \sum_{i=1}^{n-1} c(v_i, v_{i+1}) =: c(P) \]
	is minimized. Such a path is called a \text{shortest path} from $s$ to $t$.\\
	If we fix $s \in V$, then we can define the metric $\operatorname{dist} : V \to \R$ on $V$ with
	\[ v \mapsto \inf \{ c(P) \in \R \mid P \text{ is a walk from } s \text{ to } v \} \]
	which gives rise to a type of triangle inequality, if $(u, v) \in E$ is an edge, then
	\[ \operatorname{dist}(v) \leq \operatorname{dist}(u) + c(u, v) \]
	and if this equality is achieved, we call $(u, v)$ \textbf{tight}. This equality is obviously achieved if $u=s$. Remember that `$\inf \varnothing := \infty$', so we need to be a bit careful, this inequality holds whenever the distances are real and defined.\\
	\begin{lemma}
		A subpath of a shortest path is also a shortest path. A subpath, by the way, is just a subsequence of the path, which provably is still a path.
	\end{lemma}
	So, as we can see, having this distance metric gives us a triangle inequality. It turns out that any labelling $d : V \to \R$ that \textbf{overestimates} $\operatorname{dist}$, that is, for any $v \in V$, $d(v) \geq \operatorname{dist}(v)$, if it satisfies this triangle inequality, we get that $d = \operatorname{dist}$. This follows easily by `walking the path' through the triangle inequality, i.e. if we have a shortest path $s = v_1, \dots, v_n = t$, then
	\[ d(t) \leq d(v_{n-1}) + c(v_{n-1}, v_n) \leq d(v_{n-2}) + c(v_{n-2}, v_{n-1}) \leq \ldots \leq d(s) + c(P) = c(P) = \operatorname{dist}(t) \]
	and because $d(t) \geq \operatorname{dist}(t)$ we are done.\\
	This way, we can solve shortest path, by starting with a distance metric $d : V \to \R$ with $d(s) = 0$, $d(v) = \infty$ for all $v \in V \setminus \{s\}$, and then `fixing' triangle inequalities as we go. If we detect that no more inequalities can be fixed, we have found a labelling from which we can infer the shortest path. If we choose the labelling $d$ cleverly, we can also get the distances.\\
	In practice this means the following: if we have a labelling $d$, we can `fix' the inequality for an edge $(u, v)$ if $d(v) > d(u) + c(u, v)$, by making the above an equality in a new labelling $\tilde d$. The procedure that does this in-place is called \texttt{relax}.
	
	\subsubsection{Bellman-Ford}
	Call \texttt{relax} on every edge $|V| - 1$ times, which guarantees that at the end, $d = \operatorname{dist}$. Why? Let $s = v_1, \ldots, t = v_n$ be a shortest path. At every iteration $i$ of the algorithm, we have the invariant that $d(v_i) = \operatorname{dist}(v_i)$, the weights kind of `propagate' throughout the graph. Obviously this relaxation then won't update $d$ any more if $i > n$, but $n \leq |V| - 1$, so that is how many iterations we need at most. This obviously \textbf{only works if there are no negative cycles in the graph}.
	\subsubsection{Dijkstra's algorithm}
	We can skip a lot of the work by performing the \texttt{relax} procedure in a certain order. Namely, we can relax those edges outgoing from vertices that we order by the smallest tentative label $d$. We can keep track of all vertices that we still need to process, and then store in a priority queue the tentative total distance of a vertex. Any time we remove the smallest element $v$ from the queue and relax all of its outgoing edges, we have the invariant that $d(v) = \operatorname{dist}(v)$, so the algorithm is correct. This does assume that \textbf{all weights are nonnegative}.
	
	\newpage
	
	\section{Max-flow min-cut}
%	\begin{definition}
%		Let $(V, E)$ be a directed graph, let $v \in V$ be a vertex. The incoming and outgoing edge sets are defined, respectively
%		\[ \delta^{\text{in}}(v) := \{ (a, b) \in E \mid b = v \} \]
%		\[ \delta^{\text{out}}(v) := \{ (a, b) \in E \mid a = v \} \]
%	\end{definition}
	\begin{definition}
		Let $G = (V, E)$ be a connected directed graph, let $c : E \to \N$, let $s, t \in V$. A function $f : E \to \R$ is called an $(s, t)$-flow of $G$ if
		\begin{itemize}
			\item For all $e \in E$, $0 \leq f(e) \leq c(e)$.
			\item For all $u \in V \setminus \{s, t\}$,
			\[ \sum_{v\mid(u, v) \in E} f(u, v) = \sum_{v\mid(v, u) \in E} f(v, u) \]
			Intuitively, the outgoing flow must equal the incoming flow.
		\end{itemize}
		We define the \textbf{value} of the flow $f$, $\operatorname{val}(f)$, through
		\[ \operatorname{val}(f) := \sum_{v\mid(s, v) \in E} f(s, v) - \sum_{v\mid(v, s) \in E} f(v, s) \]
		i.e. how much flows out of $s$, which also equals how much flows into $t$ due to the conservation property.
	\end{definition}
	\begin{definition}
		The max-flow problem is the following: given $G = (V, E)$ a connected directed graph, $c : E \to \N$ a capacity function, and $s, t \in V$ vertices, find a flow $f$ that maximizes $\operatorname{val}(f)$. It is useful to pack this data into a tuple, so we call $(G, c, s, t)$ a max-flow problem.
	\end{definition}
	\begin{definition}
		Let  $(G, c, s, t)$ be a max-flow problem. Let $f$ be a valid flow for this problem. The \textbf{residual capacity} with respect to $f$, $r_f : E \to \R$, is defined by first studying the simplified flow $f$. We can simplify $f$ by `cancelling' flow, if $f(u, v) > 0$ and $f(v, u) > 0$, we keep the greater edge, subtract, and delete the smaller edge (i.e. set its flow to $0$). Then, for any edge $(u, v) \in E$, define
		\[ r_f(u, v) := \begin{cases*}
			c(u, v) - f(u, v) & if $f(u, v) > 0$ \\
			f(v, u) + c(u, v) & otherwise
		\end{cases*} \]
		Intuitively, this gives a notion of `how much flow we can still send through, or back'.\\
		We define the \textbf{residual graph}, $G_f$, with respect to $f$, by $G_f := (V, E_f)$, where
		\[ E_f := \{ e \in V \times V \mid r_f(e) > 0 \} \]
		We define the \textbf{residual max-flow problem} to be $(G_f, r_f, s, t)$.
	\end{definition}
	\begin{lemma}
		Let $f$ be a flow in $(G, c, s, t)$ and let $g$ be a flow in $(G_f, r_f, s, t)$. Then the pointwise sum $h := f + g$, is a flow in $(G, c, s, t)$, where $\operatorname{val}(h) = \operatorname{val}(f) + \operatorname{val}(g)$.
	\end{lemma}
	\begin{definition}
		An \textbf{augmenting path} for the flow $f$ is an $(s, t)$-path $P$ (a path from $s$ to $t$) in the residual graph $G_f$. Define the \textbf{residual capacity} of the path $P$ through
		\[ r_f(P) := \min \{ r_f(e) \mid e \in P \} \]
	\end{definition}
	\begin{lemma}
		Let $f$ be a flow in $(G, c, s, t)$, let $P$ be an augmenting path, we define the \textbf{augmented flow} $\tilde f : E \to \R$ by
		\[ \tilde f(e) := \begin{cases*}
			f(e) + r_f(P) & if $e \in P$ \\
			f(e) & otherwise
		\end{cases*} \]
		Then $\tilde f$ is a flow in $(G, c, s, t)$.
	\end{lemma}
	\begin{proof}
		$\tilde f = f + g$ where $g := r_f(P) \mathbf{1}_P$, and $g$ is a flow in the residual problem.
	\end{proof}
	\begin{theorem}
		A flow $f$ solves the max-flow problem $(G, c, s, t)$ if and only if it has no augmenting paths.
	\end{theorem}
	\subsection{Ford-Fulkerson algorithm}
	Very simple, choose an augmenting path, augment the graph, repeat until no more augmenting graphs exist. Note that the trivial flow defined pointwisely by $f := 0$ yields a flow on any graph.\\
	A result from linear optimization says
	\begin{theorem}
		If $c : E \to \R$ are integers, that is, for all $e \in E$, $c(e) \in \N$, then the maximum flow $f : E \to \R$ also is integer-valued, that is, for all $e \in E$, $f(e) \in \N$.
	\end{theorem}
	\subsection{Edmonds-Karp algorithm}
	Essentially the same as before, but instead of selecting \textbf{any} augmenting path, we select the shortest, where the shortest path is defined by the amount of edges in the path. This can be found by way of breadth-first search.
	
	\subsection{Cuts}
	\begin{definition}
		Let $(V, E, c, s, t)$ be a max-flow problem. A \textbf{cut} $(S, T)$ is a partition $V = S \sqcup T$, such that $s \in S$, $t \in T$. The \textbf{edges} of the cut $(S, T)$ are those that do not lie in the subgraphs of $V$ when restricting to either $S$ or $T$, that must be in-edges in $S$ and out-edges in $T$. That is, they are the set
		\[ \{ (u, v) \in E \mid u \in S \land v \in T \} = (S \times T) \cap E \]
		We say that the \textbf{capacity of the cut} $(S, T)$, $c(S, T)$, is the sum of the capacities of these edges.\\
		We say that the cut $(S, T)$ is a min-cut if it minimizes the capacity.
	\end{definition}
	\begin{theorem}
		For any flow $f$ and cut $(S, T)$ of $(V, E, c, s, t)$, we have that
		\[ \operatorname{val}(f) \leq c(S, T) \]
	\end{theorem}
	\begin{theorem}
		For any max-flow problem $(V, E, c, s, t)$, there exists a max-flow $f$ and a min-cut $(S, T)$, such that
		\[ \operatorname{val}(f) = c(S, T) \]
	\end{theorem}
	
	\newpage
	
	\section{Stable matchings}
	\begin{definition}
		Let $G = (V, E)$ be an undirected graph. We say that a subset $M \subseteq E$ is a \textbf{matching} of $G$ if every vertex is incident to at most one edge in $M$. If every vertex is incident to exactly one edge in $M$, we call the matching \textbf{perfect}.
	\end{definition}
	\begin{lemma}
		Given a perfect matching $M$, there exists a unique function $p_M : V \to V$ that is an involution (self-inverse), such that for all $v \in V$, we have that $\{v, p_M(v)\} \in M$. This function we call the \textbf{partner function} on $M$.
	\end{lemma}
	\begin{definition}
		A graph $G = (V, E)$ is called \textbf{bipartite} if there exists a decomposition $V = V_M \sqcup V_W$ such that every edge is indicent to exactly one vertex in $V_M$ and exactly one in $V_W$.
	\end{definition}
	\begin{definition}
%		A graph $(V, E)$ is called \textbf{complete} if $E \supseteq V \times V \setminus \{ (v, v) \mid v \in V \}$.
		A bipartite graph $(V_M \sqcup V_W, E)$ is called \textbf{bipartite complete} if for all $m \in V_M$ and $w \in V_W$, $\{m, w\} \in E$.
	\end{definition}
	\begin{definition}
		Let $(V_M \sqcup V_W, E)$ be a bipartite graph. Suppose that for every $v \in V_*$ (the asterisk is a placeholder), there exists a strict total order $<_v$ on $V \setminus V_*$. These are, in a sense, \textbf{preference lists} for matchings. A pair $(m, w) \in V_M \times V_W$ is said to be \textbf{unstable} with respect to a matching $M \subseteq V$ if both $p(m) <_m w$ and $p(w) <_w m$.
	\end{definition}
	\begin{definition}
		A perfect matching $M$ on a bipartite graph $(V_M \sqcup V_W, E)$ is said to be \textbf{stable} if no unstable pairs exist, that is, there do not exist $m \in V_M$ and $w \in V_W$ such that $(m, w)$ is unstable. The \textbf{stable matching problem} is concerned with whether, given a bipartite (complete) graph, a stable matching exists. We study the case where $|V_M| = |V_W|$.
	\end{definition}
	\subsection{Gale-Shapley algorithm}
	A solution to this problem is simple: add the `best possible pair' $(m, w)$ if both $m$ and $w$ are not matched yet, replace (when encountered) unstable pairs with stable ones. Rinse and repeat until every $v \in V$ is matched. The `best possible pair' is decided by either the preference of $m$ or $w$. This always yields a perfect stable matching.\\
	Problem: a stable matching is definitely not unique. In particular, when one decides by preference of $w$ rather than $m$ for example, we probably get a different stable matching. One matching, in this setup, is not better than the other in any sense, so long as they are stable. Individual $v \in V$ with their preference lists may prefer one matching over the other, though. The Gale-Shapley algorithm favors the `proposing side', that is, the part of the graph (either $V_M$ or $V_W$) whose preference is considered first.
	\begin{theorem}
		The Gale-Shapley algorithm is proposing-optimal, that is, if the preference of $V_*$ is considered first, every element of $V_*$ will be matched up with the best possible element of $V \setminus V_*$.\\
		The Gale-Shapley algorithm is proposee-pessimal, that is, if the preference of $V_*$ is considered last (not first), every element of $V_*$ will be matched up with the worst possible element of $V \setminus V_*$.
	\end{theorem}
	\newpage
	\section{Recurrence relations}
	\begin{definition}
		A \textbf{recurrence relation} of order $k$ is given by a function $g : \R^k \to \R$, numbers $a_0, \ldots, a_{k-1} \in \R$, such that a sequence $a : \N \to \R$ satisfies the following: for all $n \in \N$, if $n < k$ we have $a(n) = a_n$, otherwise: $a(n) = g(a_{n-1}, \ldots, a_{n-k})$. If this is the case for $a$ it is called a \textbf{solution to the recurrence relation}. We can pack the numbers $a_0, \ldots, a_{k-1}$ in a vector $b \in \R^k$, so we can represent the recurrence relation as a tuple $(k, g, b)$. Informally, we simply write: given $a_0, \ldots, a_{k-1}$, we have
		\[ a_n = g(a_{n-1}, \ldots, a_{n-k}), \quad \forall n \geq k \]
	\end{definition}
	\begin{theorem}
		Every recurrence relation has a unique solution.
	\end{theorem}
	\begin{proof}
		Kind of trivial, the unique solution is the function defined by the recurrence relation. The difficulty, of course, is finding a representation of the function $a$ independent of $g$.
	\end{proof}
	\begin{example}
		Consider the relation $a_n = C a_{n-1}$ for all $n \geq 1$, $a_0 \in \R$ and $C \in \R$ are given. The unique solution is given by $a_n = a_0 C^n$ for all $n \in \N$, which we can show: if $n = 0$ then $a_0 = a_0 \cdot C^0 = a_0$. If $n \geq 1$ we consider that
		\[ a_0 C^n = a_n = Ca_{n-1} = C a_0 C^{-1} = a_0 C^n \]
	\end{example}
%	\begin{proof}
%		Existence is sort of clear, depending on your axiom system this is already a sound definition. Now we deal with uniqueness, suppose two sequences $a, b : \N \to \R$ are solutions. Let $n \in \N$. If we can show that $a(n) = b(n)$ we are done. We do proceed by cases. If $n < k$ then $a(n) = b(n) = a_n$, this case is boring. If $n \geq k$, then 
%		We prove existence first. We do this by induction on $k$. First we deal with the order $0$ recurrence relation, which has a function $g : \{*\} \to \R$, which is a constant $c \in \R$, whence $a : \N \to \R$ given by $n \mapsto c$ is a solution. Now we suppose that every recurrence relation of order $k$ has a solution.
%	\end{proof}
	\begin{remark}
		This previous example is that of a linear first-order recurrence relation. Those are quite boring, for the rest of the lecture we deal with linear second-order recurrence relations of the form
		\[ a_{n+2} + C_1 a_{n+1} + C_2 a_n = f(n), \quad \forall n \in \N \]
		with $C_1, C_2 \in \R^*$ and given $a_0, a_1 \in \R$.
	\end{remark}
	\begin{remark}
		We can identify a $k$-th order linear recurrence relation with just the function $f$, the coefficients $v \in \R^k$ and the initial sequence $a_0, \ldots, a_{k-1} \in \R$ with a vector $b$.
	\end{remark}
	\begin{definition}
		A linear $k$th-order recurrence relation $a_{n+k} + C_1 a_{n+k-1} + \ldots + C_k a_n = f(n)$ is called \textbf{homogeneous} if $f = 0$ pointwisely.
	\end{definition}
	\begin{theorem}
		Let $k \in \N$. Let $\mathcal{A}_k$ be the set of all solutions to homogeneous linear $k$-th order recurrence relations (which are functions $a : \N \to \R$) with \textbf{the same coefficients}. Then $\mathcal{A}_k$ can be equipped with a vector space structure over $\R$ with pointwise addition and scalar multiplication in $\R$. Furthermore, $\dim \mathcal{A}_k = k$.
	\end{theorem}
	\begin{proof}
		The vector space structure with $+(a, b) \mapsto a+b$ defined by $a + b:  \N \to \R$ with $(a + b)(n) := a(n) + b(n)$ for all $n \in \N$ and $a, b : \N \to \R$ as well as $\cdot(\lambda, a) \mapsto \lambda a$ defined by $\lambda a : \N \to \R$ with $(\lambda a)(n) := \lambda a(n)$ for all $n \in \N$ and $a : \N \to \R$ is clear. It suffices to show that $a + b$ also lies in $\mathcal{A}_k$. Let \[a_{n+k} + C_1 a_{n+k-1} + \ldots + C_k a_n = 0\] and \[b_{n+k} + C_1 b_{n+k-1} + \ldots + C_k b_n = 0\] be the recurrence relations of $a$ and $b$, respectively. Then $a_0 + b_0, \ldots, a_{k-1} + b_{k-1} \in \R$ are the initial values of $a+b$ (clearly), and 
		\begin{align*}
			(a + b)_{n+k} + C_1 (a + b)_{n+k-1} + \ldots + C_k (a + b)_n &= a_{n+k} + C_1 a_{n+k-1} + \ldots + C_k a_n\\ &+ b_{n+k} + C_1 b_{n+k-1} + \ldots + C_k b_n \\
			&= 0 + 0 = 0
		\end{align*}
		Scalar multiplication is also trivial. To show that $\dim \mathcal{A}_k = k$, we define the map $\pi : \mathcal{A}_k \to \R^k$ by $a \mapsto (a_0, \ldots, a_{k-1})$ and show it is an isomorphism of vector spaces. It is easily linear. Bijectivity is also clear.
	\end{proof}
	\begin{remark}
		Now then to solve a linear homogeneous recurrence relation, all we need is to find a basis for $\mathcal{A}_k$ (in terms of $C_1, \ldots, C_K$), and then take a linear combination to arrive at any solution, which linear combination to take is essentially a linear system. Namely, suppose we have a basis $a^1, \ldots, a^k$, and we want to find $c_1, \ldots, c_k$ such that $a$ has solution $a_n = c_1 a^1_n + \ldots + c_k a^k_n$, then all we need is for this to hold for $n < k$, which gives rise to a linear map $A : \R^k \to \R^k$ such that $A(e_i) = \pi(a^i)$ in the canonical basis. The solution coefficients $c = (A^*)^{-1}(a_0, \ldots, a_{k-1})$. Why? Let's consider the situation componentwise. Let $i < k$.
		\[ a_i = c_1 a^1_i + \ldots + c_k a^k_i \]
		and
		\[ \inprod{c, a_i} = \inprod{c, A^* e_i} = \inprod{Ac, e_i} = (Ac)^i = A^i_j c^j = \sum_j \pi(a^j)^i c^j = \sum_j a^j_i c^j \]
		which are equal, so this choice of $A$ leads to the right linear system.\\
		Solving now amounts to finding a basis, which we can do if we find linearly independent solutions (note that these do not depend on the initial conditions).
	\end{remark}
	\begin{theorem}
		Let $a_{n+k} + C_1 a_{n+k-1} + \ldots + C_k a_n = 0$ be a linear homogeneous recurrence relation. Then the sequence $a : \N \to \R$ defined by $a_n := \lambda^n$ is a solution if and only if $\lambda \in \R$ satisfies $\lambda^k + C_1 \lambda^{k-1} + \ldots + C_k = 0$ (this polynomial on the left in called the \textbf{characteristic polynomial}).
	\end{theorem}
	\begin{proof}
		We first prove `if': suppose $\lambda$ satisfies the characteristic polynomial equation. We compute
		\begin{align*}
			a_{n+k} + C_1 a_{n+k-1} + \ldots + C_k a_n &= \lambda^{n+k} + C_1 \lambda^{n+k-1} + \ldots + C_k \lambda^n \\
			&= \lambda^n \left(\lambda^k + C_1 \lambda^{k-1} + \ldots + C_k \right) = 0
		\end{align*}
		The initial conditions that we need are simply $a_i := \lambda^i$, $i < k$, which is satisfied by $a$ as well.\\
		What about only if? This is essentially the same logic which we can also do by contraposition.
	\end{proof}
	\begin{example}
		Fibonacci thyme. Let $F_0 := 0$, $F_1 := 1$ and
		\[ F_{n + 2} := F_{n+1} + F_{n} \iff F_{n+2} - F_{n+1} - F_{n} = 0 \]
		Then the roots of the characteristic polynomial are $\phi$ and $\phi^*$, the golden ratio and its complement. Proof:
		\[ \lambda^2 - \lambda - 1 = 0 \iff \lambda = \frac{1 \pm \sqrt{1 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2} \]
		So $a^1(n) := \phi^n$ and $a^2(n) := (\phi^*)^n$ are basic solutions. We let $F := c_1 a^1 + c_2 a^2$. We need to solve:
		\[ \bmat{
			1 & 1 \\
			\phi & \phi^*
		} \bmat{c_1 \\ c_2} = \bmat{0 \\ 1} \]
		so $c_1 = -c_2$ and $c_1 = 1/(\phi - \phi^*) = \frac{1}{\sqrt{5}}$, whence
		\[ F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n  \right) \]
	\end{example}
	\begin{example}
		$a_0 := 1$, $a_1 := 2$, and
		\[ a_{n+2} - 2a_{n+1} + 2a_n = 0 \]
		The characteristic polynomial:
		\[ \lambda^2 - 2\lambda + 2 = 0 \iff \lambda = \frac{2 \pm 2i}{2} = 1 \pm i \]
		Note that we have basic solutions
		\[ (a^1)_n := \lambda^n, \quad (a^2)_n := \overline{\lambda^n} \]
		which do give a valid solution, but we can find a real basis from this, to get real solutions. Consider that $z + \bar{z} = 2 \Re z$ and $z - \bar{z} = 2i \Im z$. And indeed, these are linearly independent, so in principle we can take
		\[ (\tilde a^1)_n := \Re \lambda^n, \quad (\tilde a^2)_n := \Im \lambda^n \]
		How do we find these? Find the polar form of $\lambda = r\exp(i\theta)$, then $\lambda^n = r^n \exp(in\theta)$. Finally:
		\[ (\tilde a^1)_n = \Re \lambda^n = \Re r^n \exp(in\theta) = r^n \cos(n \theta), \quad (\tilde a^2)_n = r^n \sin(n \theta) \]
		The polar form is clearly $1 + i = \sqrt{2} \exp(i \pi / 4)$
	\end{example}
	\begin{example}
		Consider the recurrence relation
		\[ a_{n+2} - 2\lambda a_{n+1} + \lambda^2 a_{n} = 0 \]
		Note that its characteristic polynomial has only the root $\lambda$ with multiplicity $2$, it doesn't generate two linearly independent solutions. But in this case, we can get another: $n \mapsto n\lambda^n$
		\[ (n+2)\lambda^{n+2} - 2\lambda (n+1) \lambda^{n+1} + \lambda^2 n \lambda^n = \lambda^{n+2}\left(n+2 - 2n - 2 + n\right) = 0 \]
	\end{example}
	\newpage
	\section{RSA}
	
	\begin{definition}
		Let $G$ be a set, and let $\cdot : G \times G \to G$ be a binary operation on $G$. The pair $(G, \cdot)$ is called a \textbf{group} if:
		\begin{itemize}
			\item For all $x, y, z \in G$, we have that
			\[ (x \cdot y) \cdot z = x \cdot (y \cdot z) \]
			\item There exists a $e \in G$ such that for all $x \in G$, we have that $e \cdot x = x \cdot e = x$. Note that this element is unique: let $\tilde e \in G$ be another satisfying this axiom, then
			\[ \tilde e = \tilde e \cdot e = e \cdot \tilde e = e \]
			whence $\tilde e = e$.
			\item For all $x \in G$, there exists an $x^{-1} \in G$, such that $x \cdot x^{-1} = x^{-1} \cdot x = e$. Note that for all particular $x \in G$ this element is unique, let $\tilde x^{-1}$ be another, then
			\[ \tilde x^{-1} = \tilde x^{-1} \cdot e = \tilde x^{-1} \cdot (x \cdot x^{-1}) = (\tilde x^{-1} \cdot x) \cdot x^{-1} = e \cdot x^{-1} = x^{-1} \]
			whence $\tilde x^{-1} = x^{-1}$.
		\end{itemize}
	\end{definition}
	\begin{definition}
		Let $(G, \cdot)$ be a group. Let $n \in \N$. Let $x \in G$. We define the map $m_x : G \to G$ through $y \mapsto x \cdot y$. Then we define the following symbol:
		\[ x^n := (m_x)^n(e) = \underbrace{x \cdot x \cdot \ldots x}_{n \text{ times}} \]
		We additionally define (to extend to $n \in \Z$) $x^{-n} := (x^n)^{-1}$. Note that this notation is consistent with our existing $x^{-1}$ notation, as well as: $x^0 = (m_x)^0(e) = \id_G(e) = e$.
	\end{definition}
	\begin{lemma}
		Let $j, k \in \Z$, let $x \in G$, then
		\[ (x^j)^k = x^{jk}, \qquad x^j \cdot x^k = x^{j + k} \]
	\end{lemma}
	\begin{definition}
		Let $(G, \cdot)$ be a group. A \textbf{subgroup} of $G$ is a group $(F, \cdot|_F)$ where $F \subseteq G$ and the group relation is inherited. Note that $G$ is then a subgroup of $G$.
	\end{definition}
	\begin{definition}
		Let $(G, \cdot)$ be a group. Let $a \in G$. Then we define the following set
		\[ \inprod{a} := \{ a^k \mid k \in \Z \} \]
		We equip it with $\cdot$, which makes $(\inprod{a}, \cdot|_{\inprod{a}})$ a group, called the \textbf{subgroup of} $G$ \textbf{generated by} $a$.
	\end{definition}
	\begin{definition}
		A group $(G, \cdot)$ is called \textbf{cyclic} if there exists an $x \in G$ such that $G = \inprod{x}$.
	\end{definition}
	\begin{theorem}
		If the subgroup $\inprod{x}$ generated by $x \in G$ is finite, there exists $n \in \N$ such that
		\[ \inprod{x} = \left\{ x, x^2, \ldots, x^{n-1}, x^n = e \right\} \]
	\end{theorem}
	\begin{theorem}
		Let $(G, \cdot)$ be a finite cyclic group of size $n \in \N^*$ with generator $a$. Then for all $k \in \N^*$, $a^k$ is also a generator for $G$ if and only if $\gcd(k, n) = 1$.
	\end{theorem}
	\begin{corollary}
		Every finite subgroup of the same size has the same amount of generators. The function $\phi : \N^* \to \N^*$ that counts the amount of generators $\phi(n)$ for a finite cyclic group of size $n$ is called the \textbf{Euler totient function}.
	\end{corollary}
	\begin{lemma}
		If $a, b \in \N^*$ are coprime, then $\phi(ab) = \phi(a)\phi(b)$.
	\end{lemma}
%	\begin{proof}
%		$a, b$ coprime iff $\gcd(a, b) = 1$, i.e. they share no prime divisors. Let $1 \leq a_1, \ldots, a_m < a$ be the numbers such that $\gcd(a_i, a) = 1$ with of course $m = \phi(a)$ and let $1 \leq b_1, \ldots, b_n < b$ be the numbers such that $\gcd(b_i, b) = 1$ with of course $n = \phi(b)$. Let $1 \leq i \leq m$ and $1 \leq j \leq n$. It suffices to show that $\gcd(a_i b_j, ab) = 1$, because that achieves a lower bound on $\phi(ab) \geq \phi(a)\phi(b)$, the upper bound is trivial.
%		\[ \gcd(a_i b_j, ab) = \gcd(a_i b_j, a) \gcd(a_i b_j, b) = \gcd(b_j, a) \gcd(a_i, b) \]
%	\end{proof}
	\begin{lemma}
		Let $p > 1$ be prime and let $e \in \N^*$, then $\phi(p^e) = p^e - p^{e-1}$.
	\end{lemma}
	\begin{theorem}
		Let $p_1, \ldots, p_k$ be all prime divisors of $n \in \N^*$, then
		\[ \phi(n) = n \prod_{i=1}^k \left( 1 - 1/p_i \right) \] 
	\end{theorem}
	\begin{proof}
		Let $n = p_1^{e_1} \cdot \ldots \cdot p_k^{e_k}$ be the prime factorisation of $n$. Then
		\begin{align*}
			\phi(n) &= \phi\left(p_1^{e_1} \cdot \ldots \cdot p_k^{e_k}\right) \\
			&= \phi(p_1^{e_1}) \cdot \ldots \cdot \phi(p_k^{e_k}) \\
			&= \prod_{i=1}^k p_i^{e_i} \left(1 - 1/p_i\right) \\
			&= \prod_{i=1}^k p_i^{e_i} \prod_{i=1}^k \left(1 - 1/p_i\right) \\
			&= n \prod_{i=1}^k \left(1 - 1/p_i\right)
		\end{align*}
	\end{proof}
	\begin{definition}
		Let $n \in \N$ with $n \geq 2$, define the following set
		\[ U_n := \{ a \in \Z/n\Z \mid \forall x \in \Z/n\Z : ax = 1 \} = \{ a \in \Z/n\Z \mid \gcd(a, n) = 1 \} \]
		This is a subgroup of $\Z/n\Z$. Its size (order) is $\phi(n)$ (trivially).
	\end{definition}
	\begin{theorem}[Lagrange]
		Let $(G, \cdot)$ be a finite group. Let $(H, \cdot|_H)$ be a subgroup of $G$. Then $|H|$ divides $|G|$.
	\end{theorem}
	\begin{corollary}
		If a finite subgroup has prime $|G|$, then $G$ is cyclic.
	\end{corollary}
	\begin{corollary}
		Let $a \in G$, then $a^{|G|} = e$.
	\end{corollary}
	\begin{proof}
		Let $H := \inprod{a}$, then $|H|$ divides $|G|$, so that there exists $k \in \N$ such that $|G| = k|H|$. Notice that
		\[ a^{|G|} = a^{k|H|} = (a^|H|)^k = e^k = e \]
		since $a^{|H|} = e$ because of the subgroup property.
	\end{proof}
	\begin{theorem}
		Let $n > 1$, $M \in \Z$. If $\gcd(M, n) = 1$, then
		\[ M^{\phi(n)} \equiv 1 \pmod{1} \]
	\end{theorem}
\end{document}