Reorder, expand graph theory digest

1 files changed, 51 insertions, 38 deletions

diff --git a/content/graph_theory.tex b/content/graph_theory.tex
index 50b28dd..8975109 100644
--- a/content/graph_theory.tex
+++ b/content/graph_theory.tex
@@ -12,7 +12,6 @@ A \emph{hypergraph} $H$ is a tuple $(X,E)$ where $X$ is a finite set and $E \sub
 
 i.e. edges may join any number of vertices.
 
-
 \subsection*{Notation of special graphs}
 
 $K_n$ is the complete graph on $n$ vertices.
@@ -57,6 +56,12 @@ $\text{diam}(G) := \displaystyle\max_{u,v \in V(G)} d(u,v)$ is the \emph{diamete
 
 $\text{rad}(G) := \displaystyle\min_{u \in V(G)} \max_{v \in V(G)} d(u,v)$ is the \emph{radius} of $G$.
 
+\subsection*{Handshake Lemma}
+
+$$2|E| = \sum_{v \in V} d(v)$$
+
+Furthermore the sum of all degrees is even and thus \#vertices with odd degree is also even.
+
 \subsection*{Induced Subgraphs}
 
 Subgraph $H \subset G$ is \emph{induced} if:
@@ -65,15 +70,19 @@ $\forall u, v \in V(H) : uv \in E(H) \iff uv \in E(G)$
 
 i.e. every induced subgraph may be generated by deleting vertices and their incident edges from $G$.
 
-\subsection*{Handshake Lemma}
+\subsection*{Bipartite Charaterization}
 
-$$2|E| = \sum_{v \in V} d(v)$$
+$G$ is \emph{bipartite} iff it has no cycles of odd length.
 
-Furthermore the sum of all degrees is even and thus \#vertices with odd degree is also even.
+\subsection*{Hamiltonian Cycles}
 
-\subsection*{Bipartite Charaterization}
+A \emph{Hamiltonian cycle} is a cycle that visits each vertex of $G$ exactly once.
 
-$G$ is \emph{bipartite} iff it has no cycles of odd length.
+Correspondingly a \emph{Hamiltonian path} is a path that visits each vertex of $G$ exactly once.
+
+\subsubsection*{Dirac Theorem}
+
+Every graph $G$ with $|V(G)| \geq 3$ and $\delta(G) \geq \frac{n}{2}$ has a Hamiltonian cycle.
 
 \subsection*{Eulerian Tour Condition}
 
@@ -111,21 +120,20 @@ $\delta(G) \geq (1-\frac{1}{k})n$ for $k | n \implies G$ has a $K_k$-factor.
 
 \section*{Connectivity}
 
-Let $\kappa(G)$ be the connectivity of $G$ i.e. the maximum $k$ for which $G$ is $k$-connected.
+Let $\kappa(G)$ be the \emph{connectivity} of $G$
 
-$G$ is $k$-connected if $k-1$ vertices can be removed without disconnecting.
+i.e. the maximum $k$ for which $G$ is \emph{$k$-connected}.
 
-Let $\kappa'(G)$ be the edge-connectivity of $G$.
+$G$ is $k$-connected if $k-1$ vertices can be removed without disconnecting.
 
-For any non-trivial connected $G$:
+Let $\kappa'(G)$ be the edge-connectivity of $G$:
 
+\vspace*{-3mm}
 $$\kappa(G) \leq \kappa'(G) \leq \delta(G)$$
 
 \subsection*{Menger's Theorem}
 
-For graph $G$ and vertex sets $A,B \subseteq V(G)$ the minimum number of vertices separting $A$ and $B$ equals the maximum number of disjoint $A$-$B$-paths.
-
-\spacing
+For $A,B \subseteq V(G)$ the min \#vertices separating $A, B$ equals the max number of disjoint $A$-$B$-paths.
 
 For $a, b \in V(G)$ s.t. $\{a,b\} \notin E(G)$ the minimum number of $v \in V(G)\setminus\{a,b\}$ separating $a, b$ equals the maximum number of independent $a$-$b$-paths.
 
@@ -137,8 +145,6 @@ Graph $G$ is $k$-connected iff $\forall a,b \in V(G)$ there exist $k$ independen
 
 Ear-decomposition of $G$ is a sequence of graphs $G_0 \subseteq G_1 \subseteq \cdots \subseteq G_k$ s.t. $G_0$ is a cycle, $G_i$ results from $G_{i-1}$ by adding an ear and $G_k = G$.
 
-\spacing
-
 $G$ is $2$-connected iff it has an ear-decomposition.
 
 \subsection*{Block-cut-vertex-graph}
@@ -147,8 +153,6 @@ Blocks of $G$ are the maximal $2$-connected subgraphs and bridges.
 
 The \emph{block-cut-vertex-graph} of $G$ is the bipartite graph s.t. its partite sets are the blocks on the one side and the cut-vertices on the other side.
 
-\spacing
-
 Block-cut-vertex-graph of connected $G$ is a tree.
 
 \section*{Planar Graphs}
@@ -172,16 +176,16 @@ $|E(G)| \leq 3|V(G)|-6$ (equal if $G$ is triangulation)
 
 $|E(G)| \leq 2|V(G)|-4$ if no face is bound by triangle.
 
+\subsection*{Tutte's Theorem}
+
+Every $4$-connected planar graph is Hamiltonian.
+
 \subsection*{Graph minors}
 
 $H$ is \emph{minor} of $G$ (i.e. $MH \subseteq G$) if it can be generated from $G$ by deleting vertices, deleting or contracting edges.
 
-\spacing
-
 $H$ is a \emph{subdivision} of $G$ if it can be generated from $G$ by subdividing edges.
 
-\spacing
-
 $H$ is a \emph{topological minor} of $G$ (i.e. $TH \subseteq G$) if a subgraph of $G$ is a subdivision of $H$.
 
 \subsubsection*{Kuratowski's Theorem}
@@ -197,6 +201,8 @@ For graph $G$ the following is equivalent:
 
 \section*{Colorings}
 
+The \emph{chromatic number} $\chi(G)$ and the \emph{chromatic index} $\chi'(G)$ are defined as follows:
+
 \vspace*{-4mm}
 \begin{align*}
 \chi(G) :&= \min_{k \in \N} : G \text{ has proper $k$-vertex coloring} \\
@@ -209,6 +215,7 @@ $k$-regular bipartite $G$ has proper $k$-edge-coloring.
 
 A \emph{clique} is a subgraph of $G$ that is a complete graph.
 The \emph{clique number} $\omega(G)$ is the maximum order of a clique in $G$.
+The \emph{co-clique number} $\alpha(G)$ is the largest order of an independent set in $G$.
 
 \spacing
 
@@ -230,7 +237,7 @@ $G$ is \emph{$L$-list-colorable} if $\exists$ a proper coloring $c$ s.t. $\foral
 
 $G$ is \emph{$k$-list-colorable} or \emph{$k$-choosable} if it is $L$-list-colorable for all lists of $k$ colors.
 
-\subsubsection*{Choosability}
+\spacing
 
 \emph{Choosability} $ch(G) := \min_{k\in\N}\{ G$ is $k$-choosable$\}$
 
@@ -248,7 +255,7 @@ If $G$ is connected and neither complete nor an odd cycle then $\chi(G) \leq \De
 
 \subsection*{König's Theorem}
 
-$G$ bipartite $\implies \chi'(G) = \Delta(G)$
+$$G \text{ bipartite} \implies \chi'(G) = \Delta(G)$$
 
 \subsection*{Vizing's Theorem}
 
@@ -373,6 +380,7 @@ e.g. $R(2,k) = R(k,2) = k$ and $R(3) = 6$
 
 \subsection*{Ramsey Theorem}
 
+\vspace*{-2mm}
 $$\forall k \in \N : \sqrt{2}^k \leq R(k) \leq 4^k$$
 
 Particularly Ramsey, asymmetric Ramsey and graph Ramsey numbers are finite.
@@ -395,14 +403,14 @@ $\implies \exists x, y, z \in \N$ of the same color s.t. $x+y=z$.
 
 Let $G$ be a multigraph, $T := \{(x,e,y) | xy = e \in E(G)\}$.
 
-$f : T \to \mathbb{K}$ defines a \emph{circulation} on $G$ if:
+For abelian group $H$ the function $f : T \to H$ defines a \emph{circulation} on $G$ if:
 
 \begin{enumerate}
 	\item $\forall (x,e,y) \in T, x \neq y : f(x,e,y) = -f(y,e,x)$
 	\item $\forall v \in V(G) : f(v,V) = 0$
 \end{enumerate}
 
-$f(X,Y) := \displaystyle\sum_{(x,e,y) \in T, x \neq y, x \in X, y \in Y} f(x,y)$
+Let $f(X,Y) := \sum_{(x,e,y) \in T, x \neq y, x \in X, y \in Y} f(x,y)$
 
 \spacing
 
@@ -440,7 +448,7 @@ $(S,\overline S)$ for $S \subseteq V(G)$ s.t. $s \in S, t \notin S, \overline S
 
 \spacing
 
-Its \emph{capacity} is $c(S,\overline S) := \displaystyle\sum_{x \in S, y \in \overline S, (x,e,y) \in T} c(x,y)$.
+Its \emph{capacity} is $c(S,\overline S) := \sum_{x \in S, y \in \overline S, (x,e,y) \in T} c(x,y)$.
 
 \spacing
 
@@ -448,9 +456,9 @@ For any flow $f$ and cut $(S,\overline S) : f(S,\overline S) = f(s,V(G))$.
 
 \subsubsection*{Ford-Fulkerson Theorem}
 
-In any network the max value of a flow equals the min capacity of a cut.
+In any network the maximum value of a flow equals the minimum capacity of a cut.
 
-There is an integral flow with this max flow value.
+An integral flow $f$ with this max flow value exists.
 
 \section*{Random Graphs}
 
@@ -464,6 +472,7 @@ A \emph{property} $\mathcal{P}$ is a set of graphs.
 
 $G \in \mathcal{G}(n,p_n)$ \emph{almost always} has property $\mathcal{P}$ if:
 
+\vspace*{-2mm}
 $$\mathbb{P}(G \in \mathcal{G}(n,p_n) \cap \mathcal{P}) \to 1 (n \to \infty)$$
 
 If $p_n$ is constant it is said that \emph{almost all} $G \in \mathcal{G}(n,p)$ have property $\mathcal{P}$.
@@ -479,6 +488,13 @@ $f : \N \to [0,1]$ is called \emph{threshold function} for $\mathcal{P}$ if:
 
 Such functions do not exist for all properties $\mathcal{P}$.
 
+\subsection*{Simple probabilities}
+
+Let $G$ be a graph on $n$ vertices and $m$ edges.
+
+\vspace*{-2mm}
+$$\mathbb{P}(G = \mathcal{G}(n,p)) = p^m (1-p)^{{n \choose 2}-m}$$
+
 \subsection*{Expected values and indicators}
 
 Let $X : \mathcal{G}(n,p) \to \N$ be a random variable.
@@ -488,20 +504,17 @@ When $X$ counts e.g. the number of a certain class of subgraphs $\mathbb{E}(X)$
 \vspace*{-4mm}
 $$\mathbb{E}X = \mathbb{E}\left(\sum_{i=1}^N X_i\right) = \sum_{i=1}^N \mathbb{E}X_i = \sum_{i=1}^N \mathbb{P}(X_i=1)$$
 
-\subsection*{Erd\H{o}s-Hajnal}
+\subsubsection*{Expected number of $k$-cycles}
 
-$\forall k \geq 3 \exists$ a graph $G$ s.t. $g(G), \chi(G) > k$.
+$$\mathbb{E}(\#k\text{-cycles in } G \in \mathcal{G}(n,p)) = \frac{n_k}{2k} \cdot p^k$$
 
-\section*{Hamiltonian Cycles}
+for $n_k := n \cdot (n-1) \cdots (n-k+1)$.
 
-A \emph{Hamiltonian cycle} is a cycle that visits each vertex of $G$ exactly once.
+\subsection*{Erd\H{o}s' lower bound on $R(k,k)$}
 
-Correspondingly a \emph{Hamiltonian path} is a path that visits each vertex of $G$ exactly once.
-
-\subsection*{Dirac Theorem}
+$$R(k.k) \geq 2^{k/2}$$
 
-Every graph $G$ with $|V(G)| \geq 3$ and $\delta(G) \geq \frac{n}{2}$ has a Hamiltonian cycle.
+\subsection*{Erd\H{o}s-Hajnal}
 
-\subsection*{Tutte Theorem}
+$\forall k \geq 3 \exists$ a graph $G$ s.t. $g(G), \chi(G) > k$.
 
-Every $4$-connected planar graph is Hamiltonian.