diff options
| -rw-r--r-- | content/graph_theory.tex | 17 |
1 files changed, 16 insertions, 1 deletions
diff --git a/content/graph_theory.tex b/content/graph_theory.tex index f8b9a04..93e1561 100644 --- a/content/graph_theory.tex +++ b/content/graph_theory.tex @@ -1,6 +1,17 @@ \section*{Basics} -A graph $G$ is the tuple $(V,E)$ where $V$ is a finite set of vertices and $E \subset {V \choose 2}$ is the set of edges. +A \emph{graph} $G$ is a tuple $(V,E)$ where $V$ is a finite set of vertices and $E \subset {V \choose 2}$ is the set of edges. + +\spacing + +A \emph{multigraph} $G$ is a tuple $(V,E)$ where $V$ is a set of vertices and $E$ is a multiset of elements from ${V \choose 1} \cup {V \choose 2}$ i.e. multiedges and loops. + +\spacing + +A \emph{hypergraph} $H$ is a tuple $(X,E)$ where $X$ is a finite set and $E \subseteq 2^X \setminus \{\emptyset\}$. + +i.e. edges may join any number of vertices. + \subsection*{Notation of special graphs} @@ -313,6 +324,10 @@ For graphs $G, H$ the \emph{induced Ramsey number} $R_\text{ind}(G,H)$ is the mi \spacing +For $r, l_1, \dots, l_k \in \N$ the \emph{hypergraph Ramsey number} $R_r(l_1,\dots,l_k)$ is the min $n$ s.t. for every $k$-coloring of ${[n] \choose r}$ there $\exists i \in [k], V \subseteq [n]$ with $|V|=l_i$ s.t. all sets in $V \choose r$ have color $i$. + +\spacing + e.g. $R(2,k) = R(k,2) = k$ and $R(3) = 6$ \subsection*{Ramsey Theorem} |