From 8f6051ec07faac2c574eb6ff9ca22e18cf46a4c8 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Tue, 21 Mar 2017 12:36:14 +0100
Subject: Adding section about partially ordered sets.

---
 other/other.tex | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

(limited to 'other/other.tex')

diff --git a/other/other.tex b/other/other.tex
index 61f7a46..7a941bf 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -110,6 +110,20 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen.
 	Alle Kofaktoren von $R$ sind gleich und die Anzahl der Spannbäume von $G$.
 	\newline
 	Entferne letzte Zeile und Spalte und berechne Betrag der Determinante.
+
+	\item \textbf{\textsc{Dilworth}'s-Theorem:}
+	Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset).
+	Eine \emph{Kette} ist eine Teilmenge $\{x_1,\ldots,x_n\}$ mit $x_1 \leq \ldots \leq x_n$.
+	Eine \emph{Partition} ist eine Menge von Ketten, sodass jedes $s \in S$ in genau einer Kette ist.
+	Eine \emph{Antikette} ist eine Menge von Elementen, die paarweise nicht vergleichbar sind.
+	\newline
+	Es gilt: Die Größe der längsten Antikette gleicht der Größe der kleinsten Partition.
+	$\Rightarrow$ \emph{Weite} des Poset.
+	\newline
+	Berechnung: Maximales Matching in bipartitem Graphen.
+	Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.
+	Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.
+	Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. 
 \end{itemize}
 
 \subsection{Tipps \& Tricks}
-- 
cgit v1.2.3

