aboutsummaryrefslogtreecommitdiff
path: root/content
diff options
context:
space:
mode:
authorAdrian Kummerlaender2018-02-11 21:55:22 +0100
committerAdrian Kummerlaender2018-02-11 21:55:22 +0100
commit97f5c9e161f97cb55f6d11cc5fd8620d07476b1a (patch)
tree86ab769943dae5a44c21bf986b69517163fd4321 /content
parentd9bb5e81ffb8a0fd21a72c2c56e1553c228d1a1a (diff)
downloadmath_reference_sheets-97f5c9e161f97cb55f6d11cc5fd8620d07476b1a.tar
math_reference_sheets-97f5c9e161f97cb55f6d11cc5fd8620d07476b1a.tar.gz
math_reference_sheets-97f5c9e161f97cb55f6d11cc5fd8620d07476b1a.tar.bz2
math_reference_sheets-97f5c9e161f97cb55f6d11cc5fd8620d07476b1a.tar.lz
math_reference_sheets-97f5c9e161f97cb55f6d11cc5fd8620d07476b1a.tar.xz
math_reference_sheets-97f5c9e161f97cb55f6d11cc5fd8620d07476b1a.tar.zst
math_reference_sheets-97f5c9e161f97cb55f6d11cc5fd8620d07476b1a.zip
Add random graph section
Diffstat (limited to 'content')
-rw-r--r--content/graph_theory.tex36
1 files changed, 36 insertions, 0 deletions
diff --git a/content/graph_theory.tex b/content/graph_theory.tex
index ff3f73a..84e3222 100644
--- a/content/graph_theory.tex
+++ b/content/graph_theory.tex
@@ -316,3 +316,39 @@ $\implies \exists x, y, z \in \N$ of the same color s.t. $x+y=z$.
\section*{Flows}
\section*{Random Graphs}
+
+$\mathcal{G}(n,p)$ is the probability space on graphs of order $n$ for which the edge-existence is independently decided by fixed probability $p \in [0,1]$.
+
+This is called \emph{Erd\H{o}s-R\'{e}nyi model}.
+
+\spacing
+
+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:
+
+$$\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}$.
+
+\subsection*{Threshold functions}
+
+$f : \N \to [0,1]$ is called \emph{threshold function} for $\mathcal{P}$ if:
+
+\begin{enumerate}
+ \item For $\frac{p_n}{f(n)} \to 0 (n \to \infty)$ graphs $G \in \mathcal{G}(n,p_n)$ almost always don't have property $\mathcal{P}$
+ \item For $\frac{p_n}{f(n)} \to 1 (n \to \infty)$ graphs $G \in \mathcal{G}(n,p_n)$ almost always have property $\mathcal{P}$
+\end{enumerate}
+
+Such functions do not exist for all properties $\mathcal{P}$.
+
+\subsection*{Expected values and indicators}
+
+Let $X : \mathcal{G}(n,p) \to \N$ be a random variable.
+
+When $X$ counts e.g. the number of a certain class of subgraphs $\mathbb{E}(X)$ may be calculated by summing indicators over the maximum number $N$ of such subgraphs in $\mathcal{G}(n,p)$ and applying linearity:
+
+\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)$$
+
+\section*{Hamiltonian Cycles}