Expand graph theory digest

1 files changed, 48 insertions, 5 deletions

diff --git a/content/graph_theory.tex b/content/graph_theory.tex
index 93e1561..50b28dd 100644
--- a/content/graph_theory.tex
+++ b/content/graph_theory.tex
@@ -93,12 +93,20 @@ Let $q(G)$ be the number of odd components in $G$.
 
 $G$ has perfect matching iff $\forall S \subseteq V : q(G-S) \leq |S|$.
 
+\spacing
+
+Any $k$-regular bipartite graph has a perfect matching and a proper $k$-edge coloring.
+
 \subsection*{König's Theorem}
 
 For bipartite $G$ the size of the smallest matching equals the size of a smallest vertex cover.
 
 \subsection*{Hajnal and Szemer\'{e}di}
 
+Let $H, G$ be graphs. An \emph{$H$-factor} of $G$ is a spanning subgraph that is a set of disjoint copies of $H$ in $G$ whose vertex sets form a partition of $V(G)$.
+
+\spacing
+
 $\delta(G) \geq (1-\frac{1}{k})n$ for $k | n \implies G$ has a $K_k$-factor.
 
 \section*{Connectivity}
@@ -113,7 +121,7 @@ For any non-trivial connected $G$:
 
 $$\kappa(G) \leq \kappa'(G) \leq \delta(G)$$
 
-\subsection*{Meger's Theorem}
+\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.
 
@@ -166,7 +174,7 @@ $|E(G)| \leq 2|V(G)|-4$ if no face is bound by triangle.
 
 \subsection*{Graph minors}
 
-$H$ is \emph{minor} of $G$ if it can be generated from $G$ by deleting vertices, deleting or contracting edges.
+$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
 
@@ -174,7 +182,7 @@ $H$ is a \emph{subdivision} of $G$ if it can be generated from $G$ by subdividin
 
 \spacing
 
-$H$ is a \emph{topological minor} of $G$ if a subgraph of $G$ is a subdivision of $H$.
+$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}
 
@@ -250,6 +258,7 @@ $$\chi'(G) \in \{\Delta(G), \Delta(G)+1\}$$
 
 For $n \in \N$ and graph $H$ the \emph{extremal number} $ex(n,H)$ is the max number of edges in a graph of order $n$ s.t. it doesn't contain subgraph $H$.
 
+\vspace*{-3mm}
 $$ex(n,H):=\max\{\|G\| : |G|=n, H \not\subseteq G\}$$
 
 Correspondingly $EX(n,H$ is the set of graphs on $n$ vertices and $ex(n,H)$ edges that are $H$-free.
@@ -262,12 +271,26 @@ e.g. $ex(n,K_2) = 0, \ EX(n,K_2) = \{E_n\}, \ ex(n,P_3)=\lfloor\frac{n}{2}\rfloo
 
 For $1 \leq r \leq n$ the \emph{Tur\'{a}n graph} $T(n,r)$ is the unique complete $r$-partite graph of order $n$ s.t. the partite set sizes differ by at most one.
 
+\spacing
+
+i.e. $T(n,r)$ has $n$ mod $r$ partite sets of size $\lceil\frac{n}{r}\rceil$ and $r - (n$ mod $r)$ partite sets of size $\lfloor\frac{n}{r}\rfloor$.
+
+$\forall v \in V(T(n,r)) : d(v) \in \{ n - \lceil\frac{n}{r}\rceil, n - \lfloor\frac{n}{r}\rfloor \}$
+
+\spacing
+
 $T(n,r)$ doesn't contain $K_{r+1}$ and $t(n,r) := \|T(n,r)\|$.
 
 For $r | n \ T(n,r)$ is denoted by $K_r^s$ where $n=r \cdot s$.
 
 $$t(n,r) = t(n-r,r)+(n-r)(r-1)+{r \choose 2}$$
 
+\spacing
+
+Comparing the number of edges in $K_n$ and $T(n,r)$:
+
+$$\lim_{n \to \infty} \frac{t(n,r)}{{n \choose 2}} = \left( 1-\frac{1}{r} \right)$$
+
 \subsubsection*{Tur\'{a}n's Theorem}
 
 $$EX(n,K_r) = \{T(n,r-1)\}$$
@@ -298,12 +321,30 @@ $\forall \epsilon > 0, m \geq 1 \exists M \in \N$ s.t. every graph $G$ with $|G|
 
 \subsection*{Erd\H{o}s-Stone}
 
-$\forall r > s \geq 1, \epsilon > 0 \exists n_0 \in \N$ s.t. all graphs with $n \geq n_0$ vertices and $|E(G)| \geq t_{r-1}(n)+\epsilon n^2$ contain $K_r^s$ as a subgraph.
+$\forall r > s \geq 1, \epsilon > 0 \exists n_0 \in \N$ s.t. all graphs with $|V(G)| =: n \geq n_0$ vertices and
+
+\vspace*{-2mm}
+$$|E(G)| \geq t_{r-1}(n)+\epsilon n^2$$
+
+contain $K_r^s$ as a subgraph.
+
+\subsection*{Asymptotic extremal number}
+
+$$\lim_{n \to \infty} \frac{ex(n,H)}{{n \choose 2}} = \frac{\chi(H)-2}{\chi(H)-1}$$
+
+e.g. $ex(n,K_5 \setminus \{e\}) \simeq \frac{2}{3} \cdot {n \choose 2}$ as $\chi(K_5 \setminus \{e\}) = 4$.
 
 \subsection*{Zarankiewicz function}
 
 $z(m,n;s,t)$ denotes the maximum number of edges that a bipartite graph on sets of size $m$ and $n$ can have without containing $K_{s,t}$.
 
+\subsubsection*{K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n Theorem}
+
+$z(m,n;s,t) \leq (s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m$
+
+i.e. for $m=n$ and $t=s$:
+
+\vspace*{-2mm}
 $$z(n,n;t,t) \in \mathcal{O}(n^{2-\frac{1}{t}})$$
 
 \section*{Ramsey Theory}
@@ -363,6 +404,8 @@ $f : T \to \mathbb{K}$ defines a \emph{circulation} on $G$ if:
 
 $f(X,Y) := \displaystyle\sum_{(x,e,y) \in T, x \neq y, x \in X, y \in Y} f(x,y)$
 
+\spacing
+
 For any circulation $f$ and $X \subseteq V(G)$:
 
 $f(X,X)=0, \ f(X,V(G))=0, \ f(X,V(G) \setminus X)=0$.
@@ -415,7 +458,7 @@ $\mathcal{G}(n,p)$ is the probability space on graphs of order $n$ for which the
 
 This is called \emph{Erd\H{o}s-R\'{e}nyi model}.
 
-\spacing
+\subsection*{Properties}
 
 A \emph{property} $\mathcal{P}$ is a set of graphs.