\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[left=2.5cm,right=2.5cm,top=2cm,bottom=3cm]{geometry}
\usepackage[ngerman]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{cancel}
\usepackage{tikz}
\usepackage{natbib}
\usepackage{hyperref}
\usetikzlibrary{backgrounds}

\setcounter{secnumdepth}{1}

\newtheorem{satz}{Satz}[section]
\newtheorem{defi}[satz]{Definition}
\newcommand{\defiterm}[1]{\emph{#1}}
\newtheorem{beispiel}[satz]{Beispiel}
\newenvironment{beweis}
    {\textbf{Beweis\ }}
    {}
\newcommand{\del}{\,\backslash\,} % 'delete' operation
\newcommand{\where}{\ |\ }        % senkrechter Strich bei Mengen
\newcommand{\se}{\quad = \quad}   % spaced equal
\newcommand{\ind}{\mathcal{I}}    % independent set

\tikzstyle{matroid}=[rectangle,draw]
\tikzstyle{knoten}=[circle,fill,inner sep=0mm,minimum size=1mm]
\tikzstyle{uknoten}=[fill=black!50,knoten] % unwichtiger Knoten
\tikzstyle{unwichtig}=[draw=black!50]      % unwichtige Kante
\tikzstyle{every loop}=[] % suppress loop arrows

\newcommand{\bgbox}[2]{%
    \begin{pgfonlayer}{background}
        \filldraw [line width=5mm,join=round,black!15]
            (#1) rectangle (#2);
    \end{pgfonlayer}}


\begin{document}

%-- Test area ---------------------------------
%----------------------------------------------

\title{Minoren \\ (Seminar Matroidtheorie)}
\author{Volker Grabsch}
\date{3. März 2008}
\maketitle

\abstract{
In meinem Vortrag geht es um
Minoren in der Matroidtheorie.

Zunächst werden zwei neue
Operationen auf Matroiden eingeführt,
das \emph{Löschen}
und
das \emph{Zusammenziehen}.
Ähnlich der Dualisierung haben
sie sehr angenehme Eigenschaften,
was ihre Hintereinanderausführung betrifft.

Mit ihrer Hilfe können wir dann \emph{Minoren} definieren.
Wir schauen uns wesentliche Eigenschaften an
und werden u.a. feststellen,
dass Minoren fast immer zur selben Klasse gehören
wie ihr Ursprungs-Matroid.
Das nennt man \emph{Abgeschlossenheit}.

Doch was nützt uns diese Minor-Abgeschlossenheit?
Was ist daran so wichtig?
Diese Frage klärt ein kleiner Ausblick:
Mit Hilfe von
\emph{verbotenen Minoren}
können wir unsere Matroid-Klassen sehr geschickt beschreiben.

Die neuen Begriffe und Zusammenhänge
werden an zahlreichen Beispielen illustriert.
}

\tableofcontents

\newpage

\section{Kleines Wörterbuch}

Da es über die Matroidtheorie
fast nur englischsprachige Literatur gibt,
haben viele Fachbegriffe
keine offizielle deutsche Übersetzung.
Hier sind die Übersetzungen,
die ich verwende:

\bigskip

\begin{tabular}{ll}
englisch        & deutsch \\
\hline
matroid         & Matroid \\
independent set & unabhängige Menge \\
base            & Basis \\
circuit         & Kreis \\
representation  & Darstellung \\
duality         & Dualität \\
deletion        & Löschung \\
contraction     & Zusammenziehung \\
minor           & Minor \\
proper minor    & echter Minor \\
minor-closed    & minor-abgeschlossen \\
excluded minor  & verbotener Minor
\end{tabular}

\section{Einleitung}

Heute wollen wir Matroide verkleinern.

Kein Problem:
Wir schnappen uns einen Matroiden $M = (E,\ind)$,
und werfen ein paar Elemente aus $E$ heraus.
Zusätzlich
verkleinern wir einige unabhängige Mengen,
oder streichen gleich ganze Mengen aus $I$ heraus:
\begin{align*}
M    &= (E, \ind) \\
E    &= \{ a, b, \cancel{c} \} \\
\ind &= \Big\{ \varnothing, \{a\}, \cancel{\{b\}}, \{c\},
            \{a, b\}, \{a, \cancel{c}\} \Big\}
\end{align*}

Halt!
Sind dann noch unsere Axiome $(I1)$ -- $(I3)$ erfüllt?
Und was ist mit den unabhängigen Mengen aus $I$,
die noch alte Elemente enthalten?
\begin{align*}
M    &= (E, \ind) \\
E    &= \{ a, b \} \\
\ind &= \Big\{ \varnothing, \{a\}, \{\underline{c}\},
               \{a, \underline{b}\}, \{a\} \Big\}
\end{align*}

Ganz so einfach ist es also nicht.

Wir könnten nun systematisch
alle denkbaren Verkleinerungen erforschen,
bei denen als Ergebnis wieder ein Matroid herauskommt.
Danach müssten wir untersuchen,
wie diese Operationen
konkret bei Graphen und Matrizen aussehen.

Sinnvoller erscheint jedoch der umgekehrte Weg:
Wir schauen uns zuerst an,
wie man Graphen verkleinert,
und verallgemeinern es dann auf Matroide.
So wissen wir schon,
wie die Operationen auf Graphen aussehen,
und brauchen nur noch ihre Wirkung auf Matrizen untersuchen.

Diese Strategie kommt uns bekannt vor,
bei der Dualisierung sind wir genauso vorgegangen.

\section{Verkleinerungs-Operationen}

Graphen verkleinert man schrittweise.
Dabei gibt es 3 elementare Operationen:
\begin{itemize}
\item Knoten löschen
\item Kanten löschen
\item Kanten zusammenziehen
\end{itemize}

Am liebsten würden wir alle drei Operationen
auf Matroide verallgemeinern.
Schauen wir mal, ob das geht.

\subsection{Löschen von Knoten}

Das Löschen von Knoten ist leider nicht verallgemeinerbar.
Denn dazu müssten wir in einem Matroid zumindest
Knoten \emph{benennen} können.

\begin{beispiel}
Nehmen wir folgenden Matroiden:\footnote{%
    Es ist ein uniformer Matroid,
    $M \cong U_{3,3}$.}
\begin{align*}
M    &= (E, \ind) \\
E    &= \{ a, b, c \} \\
\ind &= \Big\{ \varnothing, \{a\}, \{b\}, \{c\},
               \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \Big\}
\end{align*}

Er wird u.a. durch folgende Graphen dargestellt:

\begin{center}
\begin{tikzpicture}[auto,swap]
    \node[knoten] (A) {};
    \node[knoten] (B) [right of=A] {}
        edge node     {a} (A);
    \node[knoten] (C) [right of=B] {}
        edge node     {b} (B);
    \node[knoten] (D) [right of=C] {}
        edge node     {c} (C);

    \bgbox{current bounding box.south west}{current bounding box.north east}
\end{tikzpicture}
\quad
\begin{tikzpicture}[auto,swap]
    \node[knoten] (A) {};
    \node[knoten] (B) [right of=A] {}
        edge node (a) {a} (A);
    \node[knoten] (C) [right of=B] {}
        edge node     {b} (B);
    \node[knoten] (D) [below of=a] {};
    \node[knoten] (E) [right of=D] {}
        edge node     {c} (D);

    \bgbox{current bounding box.south west}{current bounding box.north east}
\end{tikzpicture}
\quad
\begin{tikzpicture}[auto,swap]
    \node[knoten] (A) {};
    \node[knoten] (B) [right of=A] {}
        edge node     {a} (A);
    \node[knoten] (C) [right of=B] {}
        edge node     {b} (B);
    \node[knoten] (E) [below of=A] {};
    \node[knoten] (F) [below of=B] {}
        edge node     {c} (B);
    \node[knoten] (G) [below of=C] {};

    \bgbox{current bounding box.south west}{current bounding box.north east}
\end{tikzpicture}
\end{center}

Sie haben eine unterschiede Anzahl von Knoten,
und die Knoten haben völlig unterschiedliche Grade.
Wenn wir auf $M$ so etwas wie "`Knoten"' definieren wollen,
auf welchen dieser Graphen sollten wir uns dann beziehen?
\end{beispiel}

Dieses Beispiel macht klar,
dass es auf der Ebene der Matroide
so etwas wie "`Knoten"'
einfach nicht mehr gibt.

\subsection{Löschen und Zusammenziehen von Kanten}

Beim
Löschen und Zusammenziehen von Kanten
sieht es schon besser aus.
Wiederholen wir zunächst,
wie diese Operationen auf Graphen definiert sind:

\begin{defi}\label{graph-loeschung}
Unter der
\defiterm{Löschung}
\begin{align*}
G \del e
\end{align*}
einer Kante $e$ aus einem Graphen $G$
verstehen wir einen neuen Graphen,
der die selben Knoten besitzt
und alle Kanten bis auf $e$.
\end{defi}

\begin{defi}\label{graph-zusammenziehung}
Unter der
\defiterm{Zusammenziehung}
\begin{align*}
G / e
\end{align*}
einer Kante $e$ in einem Graphen $G$
verstehen wir
eine Löschung von $e$
mit nachfolgender
Identifikation der Endknoten von $e$.
\end{defi}

\begin{beispiel}
Löschung und Zusammenziehung einer Kante
in unserem Standard-Graphen:

\begin{center}
\begin{tikzpicture}[auto]
    \begin{scope}
        \node[uknoten] (D) {};
        \node[uknoten] (B) [above left of=D]  {};
        \node[knoten]  (C) [above right of=D] {};
        \node[knoten]  (A) [above right of=B] {};

        \path (A) edge [unwichtig,loop above] node (a) {} (A)
                  edge [unwichtig]                        (B)
              (B) edge [unwichtig]                        (C)
              (D) edge [unwichtig]                        (B)
                  edge [unwichtig,bend left]              (C)
                  edge [unwichtig,bend right]             (C);

        \path (A) edge [draw] node {$e$} (C);

        \node (G) at (0,2.6) {$G$};

        \bgbox{B |- a}{C |- D}
    \end{scope}

    \begin{scope}[xshift=3cm]
        \node[uknoten] (D) {};
        \node[uknoten] (B) [above left of=D]  {};
        \node[knoten]  (C) [above right of=D] {};
        \node[knoten]  (A) [above right of=B] {};

        \path (A) edge [unwichtig,loop above] node (a) {} (A)
                  edge [unwichtig]                        (B)
              (B) edge [unwichtig]                        (C)
              (D) edge [unwichtig]                        (B)
                  edge [unwichtig,bend left]              (C)
                  edge [unwichtig,bend right]             (C);

        \node (G) at (0,2.6) {$G \del e$};

        \bgbox{B |- a}{C |- D}
    \end{scope}

    \begin{scope}[xshift=6cm]
        \node[uknoten] (D) {};
        \node[uknoten] (B) [above left of=D]  {};
        \node[knoten]  (C) [above right of=D] {};

        \path (C) edge [unwichtig,loop above] node (c) {} (C)
                  edge [unwichtig]                        (B)
              (B) edge [unwichtig,bend left]              (C)
              (D) edge [unwichtig]                        (B)
                  edge [unwichtig,bend left]              (C)
                  edge [unwichtig,bend right]             (C);

        \node (G) at (0,2.6) {$G / e$};

        \bgbox{B |- a}{C |- D}
    \end{scope}
\end{tikzpicture}
\end{center}
\end{beispiel}

\begin{satz}\label{graph-schlaufe-zusammenziehen}
Ist $e$ eine Schlaufe in $G$,
so sind Löschung und Zusammenziehung
gleichbedeutend:
\begin{align*}
G \del e & \se G / e
\end{align*}
\end{satz}

\begin{beweis}
Nach Definition
\ref{graph-loeschung}
und
\ref{graph-zusammenziehung}
unterscheiden sich
Löschung und Zusammenziehung
nur durch die nachfolgende Identifikation der Endknoten.
Bei einer Schlaufe sind die Endknoten
aber schon identisch.
\hfill $_\blacksquare$
\end{beweis}

\begin{beispiel}
Löschung und Zusammenziehung einer
Schlaufe:

\begin{center}
\begin{tikzpicture}[auto]
    \begin{scope}
        \node[uknoten] (D) {};
        \node[uknoten] (B) [above left of=D]  {};
        \node[uknoten] (C) [above right of=D] {};
        \node[knoten]  (A) [above right of=B] {};

        \path (A) edge [unwichtig]            (B)
                  edge [unwichtig]            (C)
              (B) edge [unwichtig]            (C)
              (D) edge [unwichtig]            (B)
                  edge [unwichtig,bend left]  (C)
                  edge [unwichtig,bend right] (C);

        \path (A) edge [loop above] node [right] {$e$} (A);

        \node (G) at (0,2.6) {$G$};

        \bgbox{B |- a}{C |- D}
    \end{scope}

    \begin{scope}[xshift=3cm]
        \node[uknoten] (D) {};
        \node[uknoten] (B) [above left of=D]  {};
        \node[uknoten] (C) [above right of=D] {};
        \node[knoten]  (A) [above right of=B] {};

        \path (A) edge [unwichtig]            (B)
                  edge [unwichtig]            (C)
              (B) edge [unwichtig]            (C)
              (D) edge [unwichtig]            (B)
                  edge [unwichtig,bend left]  (C)
                  edge [unwichtig,bend right] (C);

        \node (G) at (0,2.6) {$G \del e$};

        \bgbox{B |- a}{C |- D}
    \end{scope}

    \begin{scope}[xshift=6cm]
        \node[uknoten] (D) {};
        \node[uknoten] (B) [above left of=D]  {};
        \node[uknoten] (C) [above right of=D] {};
        \node[knoten]  (A) [above right of=B] {};

        \path (A) edge [unwichtig]            (B)
                  edge [unwichtig]            (C)
              (B) edge [unwichtig]            (C)
              (D) edge [unwichtig]            (B)
                  edge [unwichtig,bend left]  (C)
                  edge [unwichtig,bend right] (C);

        \node (G) at (0,2.6) {$G / e$};

        \bgbox{B |- a}{C |- D}
    \end{scope}
\end{tikzpicture}
\end{center}
\end{beispiel}

Nachdem wir uns wieder klar gemacht haben, was
Löschung und Zusammenziehung
auf Graphen bedeuten,
wollen wir sie auf Matroiden verallgemeinern.
Dazu muss es uns gelingen,
diese Operationen
ausschließlich durch
\emph{Elemente} und \emph{unabhängige Mengen}
zu beschreiben,
d.h. durch Kanten und kreisfreie Teilgraphen.

\begin{satz}\label{graph-matroid}
Sei $G$ ein Graph,
$e$ eine Kante
und
$X$ eine Teilmenge der Kanten von $G$.
Dann gilt:
\begin{enumerate}
\item[(i)]
        $X$ ist kreisfreier Teilgraph in $G \del e$
    \\ $\Leftrightarrow$\quad
        $e \notin X$
        und
        $X$ ist kreisfreier Teilgraph in $G$

\item[(ii)]
        $X$ ist kreisfreier Teilgraph in $G / e$
        und
        $e$ ist keine Schlaufe
    \\ $\Leftrightarrow$\quad
        $e \notin X$
        und
        $X \cup \lbrace e \rbrace$ ist kreisfreier Teilgraph in $G$
\end{enumerate}
\end{satz}

\begin{beweis}
\begin{itemize}
\item[(i), $\Rightarrow$]
    Sei $X$ ein kreisfreier Teilgraph in $G \del e$.
    Dann ist $X$ nach Definition ein Teilgraph von $G$
    und es gilt: $e \notin X$.
    Da $X$ in $G \del e$ kreisfrei ist,
    muss $X$ auch in $G$ kreisfrei sein,
    da die Elemente von $X$ nach wie vor die selben Kanten darstellen.
    \hfill $_\blacksquare$

\item[(i), $\Leftarrow$]
    Sei $X$ ein kreisfreier Teilgraph in $G$
    mit $e \notin X$.
    Dann ist $X$ nach Definition auch ein Teilgraph von $G \del e$.
    Bezüglich $G \del e$ muss $X$ weiterhin kreisfrei sein,
    da die Elemente von $X$ nach wie vor die selben Kanten darstellen.
    \hfill $_\blacksquare$

\item[(ii), $\Rightarrow$]
    Sei $X$ ein kreisfreier Teilgraph in $G / e$
    und $e$ keine Schlaufe.
    Dann ist $X$ nach Definition ein Teilgraph von $G$
    und es gilt: $e \notin X$.

    Angenommen,
    $X \cup \lbrace e \rbrace$ hätte einen Kreis in $G$.
    Entfernen wir die Kante $e$
    und identifizieren stattdessen die Endpunkte von $e$,
    bleibt der Kreis weiterhin geschlossen,
    egal ob er durch $e$ ging oder nicht.
    Damit haben wir aber einen Kreis in $X$ bezüglich $G / e$ gefunden,
    im Widersprich zur Voraussetzung.
    Folglich ist die Annahme falsch,
    d.h.\ $X \cup \lbrace e \rbrace$ ist kreisfreier Teilgraph von $G$.
    \hfill $_\blacksquare$

\item[(ii), $\Leftarrow$]
    Sei $X \cup \lbrace e \rbrace$ ein kreisfreier Teilgraph in $G$
    und $e \notin X$.
    Dann ist $X$ nach Definition auch ein Teilgraph von $G / e$.
    Weil $X \cup \lbrace e \rbrace$ in $G$ kreisfrei ist,
    muss insbesondere $\lbrace e \rbrace$ kreisfrei sein,
    d.h. $e$ ist keine Schlaufe.

    Angenommen,
    $X$ hätte einen Kreis in $G / e$.
    In $G / e$ sind die Endpunkte von $e$ miteinander identifiziert worden.
    Wenn wir diese "`auftrennen"',
    unterbrechen wir eventuell den Kreis.
    Fügen wir $e$ jedoch dem Teilgraphen hinzu,
    ist der Kreis wieder geschlossen.
    Somit haben wir einen Kreis in $X \cup \lbrace e \rbrace$ bezüglich $G$ gefunden,
    im Widersprich zur Voraussetzung.
    Also ist die Annahme falsch,
    d.h. $X$ ist kreisfreier Teilgraph in $G / e$.
    \hfill $_\blacksquare$
\end{itemize}
\end{beweis}

\begin{beispiel}
Löschung und Zusammenziehung einer Kante
im Graphen und im zugehörigen Matroid:
\begin{center}
\begin{tabular}{lcl}
    $M[G]$
    &
    \begin{tikzpicture}[auto,baseline]
        \node[uknoten] (A)                {};
        \node          (A') [below of=A]  {};
        \node[knoten]  (B)  [left of=A']  {};
        \node[knoten]  (C)  [right of=A'] {};

        \path (A) edge [unwichtig,loop above] node       (d) {$d$} (A)
                  edge [unwichtig]            node[swap] (c) {$c$} (B)
                  edge [unwichtig]            node       (b) {$b$} (C)
              (B) edge [draw]                 node       (a) {$a$} (C);

        \bgbox{B |- d}{C |- A'}
    \end{tikzpicture}
    &
    $\ind = \Big\lbrace
                \varnothing,
                \lbrace a \rbrace,
                \lbrace b \rbrace,
                \lbrace c \rbrace,
                \lbrace a, b \rbrace,
                \lbrace b, c \rbrace,
                \lbrace a, c \rbrace
            \Big\rbrace$
\\
\\
    $M[G] \del a$
    &
    \begin{tikzpicture}[auto,baseline]
        \node[uknoten] (A)                {};
        \node          (A') [below of=A]  {};
        \node[knoten]  (B)  [left of=A']  {};
        \node[knoten]  (C)  [right of=A'] {};

        \path (A) edge [unwichtig,loop above] node       (d) {$d$} (A)
                  edge [unwichtig]            node[swap] (c) {$c$} (B)
                  edge [unwichtig]            node       (b) {$b$} (C);

        \bgbox{B |- d}{C |- A'}
    \end{tikzpicture}
    &
    $\ind = \Big\lbrace
                \varnothing,
                \lbrace b \rbrace,
                \lbrace c \rbrace,
                \lbrace b, c \rbrace
            \Big\rbrace$
\\
\\
    $M[G] / a$
    &
    \begin{tikzpicture}[auto,baseline]
        \node[uknoten] (A)                {};
        \node[knoten]  (A') [below of=A]  {};

        \path (A) edge [unwichtig,loop above] node       (d) {$d$} (A)
                  edge [unwichtig,bend right] node[swap] (c) {$c$} (A')
                  edge [unwichtig,bend left]  node       (b) {$b$} (A');

        \bgbox{c |- d}{b |- A'}
    \end{tikzpicture}
    &
    $\ind = \Big\lbrace
                \varnothing,
                \lbrace b \rbrace,
                \lbrace c \rbrace
            \Big\rbrace$
\end{tabular}
\end{center}
\end{beispiel}

Na also!
Nun haben wir
eine allgemeine Formulierung
für Matroide gefunden:
Beim Löschen von $e$
werden alle unabhängigen Mengen gestrichen,
in denen $e$ auftaucht.
Beim Zusammenziehen von $e$
werden zusätzlich alle unabhängigen Mengen gestrichen,
zu denen $e$ nicht hinzugefügt werden kann.

Wir müssen jedoch aufpassen,
wenn $e$ eine Schlaufe ist ($\lbrace e \rbrace \notin \ind$).
In dem Fall können wir $e$
nicht auf die beschriebene Weise zusammenziehen,
denn dort gilt
der Teil (ii)
des vorherigen Satzes gar nicht.\footnote{%
    Er \emph{kann} auch gar nicht gelten,
    denn für eine Schlaufe $e$
    ist $X \cup \lbrace e \rbrace$ niemals kreisfrei,
    d.h. dem Satz zufolge hätte $G / e$
    gar keine kreisfreien Teilgraphen,
    nicht einmal den leeren Teilgraph $X = \varnothing$.}
Wir müssen die Zusammenziehung einer Schlaufe
also anders beschreiben.
Am einfachsten geht das
mit Hilfe von Satz~\ref{graph-schlaufe-zusammenziehen}:
Wir definieren die Zusammenziehung einer Schlaufe
einfach durch ihre Löschung.

\newpage
    \begin{defi}\label{loeschen-und-zusammenziehen}
    Sei $M = (E, \ind)$ ein Matroid und $e \in E$.

    Löschen von $e$:
        \begin{align*}
        M \del e := (E', \ind')
        \text{ mit }
            E'    & := E \del \lbrace e \rbrace \\
            \ind' & := \lbrace X \in \ind \where e \notin X \rbrace
        \end{align*}

    Zusammenziehen von $e$:
        \begin{align*}
        M / e := (E', \ind')
        \text{ mit }
            E' & := E \del \lbrace e \rbrace \\
            \ind' & :=
                \begin{cases}
                \lbrace X \in \ind \where e \notin X \rbrace
                    & \text{falls $\lbrace e \rbrace \notin \ind$} \\
                \lbrace X \in \ind \where e \notin X, X \cup \lbrace e \rbrace \in \ind \rbrace
                    & \text{falls $\lbrace e \rbrace \in \ind$}
                \end{cases}
        \end{align*}
    \end{defi}
Zum Schluss dieses Kapitels
formulieren wir noch einige Sätze,
die uns bestätigen,
dass
Definition \ref{loeschen-und-zusammenziehen}
genau das liefert,
was wir haben wollen.
    \begin{satz}
    Sei $M = (E, \ind)$ ein Matroid und $e \in E$.
    Dann sind
    $M \del e$
    und
    $M / e$
    wiederum Matroide.
    \end{satz}

    \begin{beweis}
    (ausgelassen)
    \hfill $_\blacksquare$
    \end{beweis}

    \begin{satz}\label{graphen-sind-minor-abgeschlossen}
    Die Matroid-Operationen
    \emph{Löschen} und \emph{Zusammenziehen}
    sind Verallgemeinerungen
    der entsprechenden Graph-Operationen.
    Das heißt, es gilt:
        \begin{align*}
        M(G) \del e & = M(G \del e) \\
        M(G) / e & = M(G / e)
        \end{align*}
    für alle Graphen $G$ und Kanten $e$.
    \end{satz}

    \begin{beweis}
    Dieser Satz ist nur eine
    Umformulierung von
    Satz~\ref{graph-matroid}.
    \hfill $_\blacksquare$
    \end{beweis}


\section{Wichtige Eigenschaften}

Im vorherigen Kapitel
haben wir zwei neue Operationen eingeführt,
die Löschung und
die Zusammenziehung.
Schauen wir uns nun
einige wichtige Eigenschaften an.


\subsection{Wirkung auf Matrizen}

Wie das Löschen und Zusammenziehen
auf Graphen ausieht,
wissen wir bereis.
Schließlich haben wir sie gerade so konstruiert,
dass sie dort mit den entsprechenden
elementaren Graphen-Operationen übereinstimmen.

Doch was passiert mit einem Matroid,
der durch eine $\mathbb{F}$-Matrix dargestellt wird?
Sind die Matroide,
die man nach dem Löschen bzw. Zusammenziehen erhält,
überhaupt noch
durch eine $\mathbb{F}$-Matrix darstellbar?

Die Antwort ist \emph{ja}
und die neue Matrix ist nicht einmal
besonders kompliziert.
Die Löschung entspricht
dem Streichen einer Spalte,
und die Zusammenfassung entspricht
dem Eliminations-Schritt im Gauß-Algorithmus.
    \begin{satz}\label{matrizen-sind-minor-abgeschlossen-1}
    Sei $A$ eine Matrix
    über dem Körper $\mathbb{F}$.
        \begin{align*}
        A  & = \begin{pmatrix}
                    a_{11} & \ldots & a_{1,i-1} & a_{1i} & a_{1,i+1} & \ldots & a_{1m} \\
                    \vdots &        & \vdots    & \vdots & \vdots    &        & \vdots \\
                    a_{n1} & \ldots & a_{n,i-1} & a_{ni} & a_{n,i+1} & \ldots & a_{nm}
               \end{pmatrix}
        \end{align*}
    $A'$ entstehe aus $A$ durch
    Herausstreichen der
    $i$-ten Spalte:
        \begin{align*}
        A' & = \begin{pmatrix}
                    a_{11} & \ldots & a_{1,i-1} & a_{1,i+1} & \ldots & a_{1m} \\
                    \vdots &        & \vdots    & \vdots    &        & \vdots \\
                    a_{n1} & \ldots & a_{n,i-1} & a_{n,i+1} & \ldots & a_{nm}
               \end{pmatrix}
        \end{align*}
    Dann gilt:
        \begin{align*}
        M[A'] & = M[A] \del i
        \end{align*}
    \end{satz}

    \begin{beweis}
    (ausgelassen)
    \hfill $_\blacksquare$
    \end{beweis}

    \begin{satz}\label{matrizen-sind-minor-abgeschlossen-2}
    Sei $A$ eine Matrix
    über dem Körper $\mathbb{F}$.
    Sei die $i$-te Spalte keine Nullspalte (d.h. $i$ ist keine Schlaufe in $M[A]$).
        \begin{align*}
        A   & = \begin{pmatrix}
                    a_{11} & \ldots & a_{1,i-1} & a_{1i} & a_{1,i+1} & \ldots & a_{1m} \\
                    a_{21} & \ldots & a_{2,i-1} & a_{2i} & a_{2,i+1} & \ldots & a_{2m} \\
                    \vdots &        & \vdots    & \vdots & \vdots    &        & \vdots \\
                    a_{n1} & \ldots & a_{n,i-1} & a_{ni} & a_{n,i+1} & \ldots & a_{nm}
                \end{pmatrix}
        \end{align*}
    $A'$ entstehe aus $A$
    durch äquivalente Umformungen (ohne Spaltenvertauschungen!) derart,
    dass die $i$-te Spalte zum Einheitsvektor
    $\left(\begin{smallmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{smallmatrix}\right)$
    wird:
        \begin{align*}
        A'  & = \begin{pmatrix}
                    a_{11} & \ldots & a_{1,i-1} & 1      & a_{1,i+1} & \ldots & a_{1m} \\
                    a_{21} & \ldots & a_{2,i-1} & 0      & a_{2,i+1} & \ldots & a_{2m} \\
                    \vdots &        & \vdots    & \vdots & \vdots    &        & \vdots \\
                    a_{n1} & \ldots & a_{n,i-1} & 0      & a_{n,i+1} & \ldots & a_{nm}
                \end{pmatrix}
        \end{align*}
    $A''$ entstehe aus $A'$
    durch Streichen der ersten Zeile und der $i$-ten Spalte:
        \begin{align*}
        A'' & = \begin{pmatrix}
                    a_{21} & \ldots & a_{2,i-1} & a_{2,i+1} & \ldots & a_{2m} \\
                    \vdots &        & \vdots    & \vdots    &        & \vdots \\
                    a_{n1} & \ldots & a_{n,i-1} & a_{n,i+1} & \ldots & a_{nm}
                \end{pmatrix}
        \end{align*}
    Dann gilt:
        \begin{align*}
        M[A''] & = M[A] / i
        \end{align*}
    \end{satz}

    \begin{beweis}
    (ausgelassen)
    \hfill $_\blacksquare$
    \end{beweis}

    \begin{beispiel}
    Wir wollen die 4.\ Spalte
    der folgenden Matrix zusammenziehen:
        \begin{align*}
        A   & = \begin{pmatrix}
                     1 &  0 &  0 &  1 &  0 &  0 & 0 \\
                    -1 &  1 &  1 &  0 &  0 &  0 & 0 \\
                     0 & -1 &  0 & -1 &  1 &  1 & 0 \\
                     0 &  0 & -1 &  0 & -1 & -1 & 0 \\
                \end{pmatrix}
        \end{align*}
    Diese Spalte können wir leicht in einen Einheitsvektor umformen.
    Wir brauchen in der Matrix nur
    die 1.\ Zeile auf die 3.\ Zeile zu addieren:
        \begin{align*}
        A'  & = \begin{pmatrix}
                     1 &  0 &  0 &  1 &  0 &  0 & 0 \\
                    -1 &  1 &  1 &  0 &  0 &  0 & 0 \\
                     1 & -1 &  0 &  0 &  1 &  1 & 0 \\
                     0 &  0 & -1 &  0 & -1 & -1 & 0 \\
                \end{pmatrix}
        \end{align*}
    Zum Schluss streichen wir
    die 1.\ Zeile und die 4.\ Spalte:
        \begin{align*}
        A'' & = \begin{pmatrix}
                    -1 &  1 &  1 &  0 &  0 & 0 \\
                     1 & -1 &  0 &  1 &  1 & 0 \\
                     0 &  0 & -1 & -1 & -1 & 0 \\
                \end{pmatrix}
        \end{align*}
    \end{beispiel}


\subsection{Wirkung auf uniforme Matroide}

Wie bei den Matrizen
stellt sich
auch bei den uniformen Matroiden
die Frage,
wie ihre Verkleinerungen im Einzelnen aussehen,
und ob dabei
überhaupt noch uniforme Matroide
herauskommen.
Auch hier lautet die Antwort \emph{ja}
und alles ist schön einfach.

    \begin{satz}\label{uniforme-sind-minor-abgeschlossen}
    Sei $U_{r,n}$ ein uniformer Matroid
    und $e$ ein Element aus $U_{r,n}$,
    so gilt:
        \begin{align*}
        U_{r,n} \del e & \cong \begin{cases}
                                    U_{r,n-1}   & \text{falls $r<n$} \\
                                    U_{r-1,n-1} & \text{falls $r=n$}
                               \end{cases} \\
        U_{r,n} /    e & \cong \begin{cases}
                                    U_{r-1,n-1} & \text{falls $r>0$} \\
                                    U_{r,n-1}   & \text{falls $r=0$}
                               \end{cases}
        \end{align*}
    \end{satz}

    \begin{beweis}
    (ausgelassen)
    \hfill $_\blacksquare$
    \end{beweis}


\subsection{Hintereinanderausführung}

Es ist egal,
in welcher Reihenfolge
wir einen Matroiden verkleinern.
    \begin{satz}\label{reihenfolge-egal}
    Sei $M$ ein Matroid
    und $e, f$ zwei verschiedene Elemente von $M$,
    so gilt:
    \begin{enumerate}
    \item[(i)]
        Die Lösch-Reihenfolge ist egal:
        \begin{align*}
        (M \del e) \del f \se (M \del f) \del e
        \end{align*}
    \item[(ii)]
        Die Zusammenzieh-Reihenfolge ist egal:
        \begin{align*}
        (M /    e) /    f \se (M /    f) /    e
        \end{align*}
    \item[(iii)]
        Es ist egal, ob zuerst gelöscht oder zuerst zusammengezogen wird:
        \begin{align*}
        (M \del e) /    f \se (M /    f) \del e
        \end{align*}
    \end{enumerate}
    \end{satz}

    \begin{beweis}
    Sei $M = (E, \ind)$ und $e, f \in E$ mit $e \neq f$.
    Dann gilt:
    \begin{align*}
        (M \del e) \del f
        & = ((E, \ind) \del e) \del f \\
        & = (E \del \lbrace e \rbrace,
             \lbrace X \in \ind \where
                e \notin X
             \rbrace)
            \del f \\
        & = (E \del \lbrace e, f \rbrace,
             \lbrace X \in \ind \where
                e \notin X,
                f \notin X
             \rbrace) \\
        & = (E \del \lbrace f \rbrace,
             \lbrace X \in \ind \where
                f \notin X
             \rbrace)
            \del e \\
        & = (M \del f) \del e
    \end{align*}
    Damit ist (i) gezeigt.
    $_\blacksquare$

    Ist $f$ eine Schlaufe,
    können wir (iii) auf (i) zurückführen:
    \begin{align*}
        (M \del e) / f &= (M \del e) \del f = (M \del f) \del e = (M / f) \del e
    \end{align*}
    Ist $f$ hingegen keine Schlaufe,
    so gilt:
    \begin{align*}
        (M \del e) / f
        & = ((E, \ind) \del e) / f \\
        & = (E \del \lbrace e \rbrace,
             \lbrace X \in \ind \where
                e \notin X
             \rbrace)
            / f \\
        & = (E \del \lbrace e, f \rbrace,
             \lbrace X \in \ind \where
                e \notin X,
                f \notin X,
                X \cup \lbrace f \rbrace \in \ind
             \rbrace) \\
        & = (E \del \lbrace f \rbrace,
             \lbrace X \in \ind \where
                f \notin X,
                X \cup \lbrace f \rbrace \in \ind
             \rbrace)
            \del e \\
        & = (M / f) \del e
    \end{align*}
    Damit ist (iii) gezeigt.
    $_\blacksquare$

    Ist $e$ eine Schlaufe,
    können wir (ii) auf (iii) zurückführen:
    \begin{align*}
        (M / e) / f &= (M \del e) / f = (M / f) \del e = (M / f) / e
    \end{align*}
    Anderenfalls gilt:
    \begin{align*}
        (M / e) / f
        & = ((E, \ind) / e) / f \\
        & = (E \del \lbrace e \rbrace,
             \lbrace X \in \ind \where
                e \notin X,
                X \cup \lbrace e \rbrace \in \ind
             \rbrace)
            / f \\
        & = (E \del \lbrace e, f \rbrace,
             \lbrace X \in \ind \where
                e \notin X,
                X \cup \lbrace e \rbrace \in \ind,
                f \notin X,
                X \cup \lbrace f \rbrace \in \ind
             \rbrace) \\
        & = (E \del \lbrace f \rbrace,
             \lbrace X \in \ind \where
                f \notin X,
                X \cup \lbrace f \rbrace \in \ind
             \rbrace)
            / e \\
        & = (M / f) / e
    \end{align*}
    Damit ist (ii) gezeigt.
    $_\blacksquare$
    \end{beweis}

    \begin{beispiel}
    Es ist egal, ob zuerst
    $a$ gelöscht oder
    $b$ zusammengezogen wird:
    \begin{center}
    \begin{tikzpicture}[auto,node distance=5cm,>=latex]
        \node[matroid] (M)
            {$I =   \Big\lbrace
                        \varnothing,
                        \lbrace a \rbrace,
                        \lbrace b \rbrace,
                        \lbrace c \rbrace,
                        \lbrace d \rbrace,
                        \lbrace a, b \rbrace,
                        \lbrace b, c \rbrace,
                        \lbrace b, d \rbrace
                    \Big\rbrace$};
        \node[matroid] (Ma) [below left of=M]
            {$I =   \Big\lbrace
                        \varnothing,
                        \lbrace b \rbrace,
                        \lbrace c \rbrace,
                        \lbrace d \rbrace,
                        \lbrace b, c \rbrace,
                        \lbrace b, d \rbrace
                    \Big\rbrace$};
        \node[matroid] (Mb) [below right of=M]
            {$I =   \Big\lbrace
                        \varnothing,
                        \lbrace a \rbrace,
                        \lbrace c \rbrace,
                        \lbrace d \rbrace
                    \Big\rbrace$};
        \node[matroid] (Mab) [below right of=Ma]
            {$I =   \Big\lbrace
                        \varnothing,
                        \lbrace c \rbrace,
                        \lbrace d \rbrace
                    \Big\rbrace$};
        \path (M)  edge[->] node[swap] {$a$ löschen}        (Ma)
              (M)  edge[->] node       {$b$ zusammenziehen} (Mb)
              (Ma) edge[->] node[swap] {$b$ zusammenziehen} (Mab)
              (Mb) edge[->] node       {$a$ löschen}        (Mab);
    \end{tikzpicture}
    \end{center}
    \end{beispiel}
Um die Verkleinerung eines Matroiden
zu beschreiben,
brauchen wir daher nur zu sagen,
welche Elemente gelöscht
und welche zusammengezogen
werden.
Die Reihenfolge ist egal.
Dies rechtfertigt folgende Notation:
    \begin{defi}
    Sei $M$ ein Matroid
    und $X=\lbrace x_1, \ldots, x_m \rbrace$,
    $Y=\lbrace y_1, \ldots, y_n \rbrace$
    zwei disjunkte Elementmengen.
    Dann ist
        \begin{align*}
        M \del X / Y & \quad:=\quad M \del x_1 \del \ldots \del x_m / y_1 / \ldots / y_n
        \end{align*}
    Analog werden
        $M / Y \del X$ und
        $M \del X$ und
        $M / Y$
    definiert.
    \end{defi}


\newpage
\subsection{Basen und Kreise}

Schauen wir uns nun an,
wie sich das Löschen und Zusammenziehen
mehrerer Elemente
auf die
unabhängigen Mengen, Basen und Kreise
eines Matroiden auswirken:
    \begin{satz}
    Sei $M$ ein Matroid über $E$,
    und sei $T \subseteq E$.
    Dann ist $M \del T$ ein Matroid über $E \del T$,
    und für jede Elementmenge $X \subseteq E \del T$ gilt:
        \begin{enumerate}
        \item[(i)]
            $X$ ist unabhängig in $M \del T$ \\
            $\Leftrightarrow$
                $X$ ist unabhängig in $M$.
        \item[(ii)]
            $X$ ist ein Kreis von $M \del T$ \\
            $\Leftrightarrow$
                $X$ ist ein Kreis von $M$.
        \item[(iii)]
            $X$ ist eine Basis von $M \del T$ \\
            $\Leftrightarrow$
                $X$ ist eine maximale Teilmenge von $E \del T$,
                die unabhängig in $M$ ist.
        \end{enumerate}
    Weiterhin ist $M / T$ ein Matroid über $E \del T$,
    und für jedes $X \subseteq E \del T$ gilt:
        \begin{enumerate}
        \item[(iv)]
            $X$ ist unabhängig in $M / T$ \\
            $\Leftrightarrow$
                $X \cup B_T$ ist unabhängig in $M$
                für eine maximale Teilmenge $B_T \subseteq T$,
                die unabhängig in $M$ ist.
        \item[(v)]
            $X$ ist ein Kreis von $M / T$ \\
            $\Leftrightarrow$
                $X$ ist ein minimales nichtleeres Element von
                $\lbrace C \del T \where \text{$C$ ist ein Kreis von $M$} \rbrace$.
        \item[(vi)]
            $X$ ist eine Basis von $M / T$ \\
            $\Leftrightarrow$
                $X \cup B_T$ ist eine Basis von $M$
                für eine maximale Teilmenge $B_T \subseteq T$,
                die unabhängig in $M$ ist.
        \end{enumerate}
    \end{satz}

    \begin{beweis}
    (ausgelassen)
    \hfill $_\blacksquare$
    \end{beweis}


\subsection{Dualität}

Im dualen Matroid
vertauschen
Löschung und Zusammenziehung
ihre Rollen.
    \begin{satz}\label{dualitaet}
    Sei $M = (E, \ind)$ ein Matroid und $e \in E$.
    Dann gilt:
        \begin{align*}
        M^* \del e & = (M /    e)^* \\
        M^* /    e & = (M \del e)^*
        \end{align*}
    \end{satz}

    \begin{beweis}
    (ausgelassen)
    \hfill $_\blacksquare$
    \end{beweis}


\section{Minoren}

Wir haben inzwischen schon viel mit Minoren gearbeitet.
Es wird Zeit, das Kind beim Namen zu nennen:
    \begin{defi}\label{matroid}
    Sei $M$ ein Matroid.
    Ein
    \defiterm{Minor} von $M$
    ist ein Matroid $M'$ mit
    \begin{align*}
    M' & \se M \del X / Y
    \end{align*}
    für gewisse Mengen $X$ und $Y$ von Elementen aus $M$.

    $M'$ ist ein
    \defiterm{echter Minor},
    wenn er eine echte Verkleinerung darstellt
    (d.h. $M \neq M'$ bzw. $X \cup Y \neq \varnothing$).
    \end{defi}
Man kann sich Minoren auch so vorstellen:
Wir haben zwei Operationen,
die einen Matroiden $M = (E,\ind)$ echt verkleinern.
Wenden wir unsere Operationen
$|E|$-mal hintereinander an,
so erhalten wir den leeren Matroid.\footnote{%
    Denn mit jeder Operation
    entfernen wir
    genau ein Element aus $E$.}
Die Matroide,
die wir auf dem Wege dorthin erhalten,
nennen wir (echte) \emph{Minoren}.

\subsection{Abgeschlossenheit}

Bisher haben wir die Auswirkungen
des Löschens und des Zusammenziehens
für einzelne Matroide genaustens erforscht.
Da wird es Zeit, sich das Gesamtbild anzusehen.

Wir betrachten ganze Klassen von Matroiden
(uniforme, graphische, ...)
und fragen uns,
wo ihre Minoren liegen.
Besonders praktisch wäre es,
wenn die Minoren die jeweilige Klasse
gar nicht verlassen.
Genauer:
    \begin{defi}
    Eine Klasse $\mathcal{M}$ von Matroiden heißt
    \defiterm{minor-abgeschlossen},
    wenn die Minoren aller Matroide aus $\mathcal{M}$
    wieder in $\mathcal{M}$ liegen.
    \end{defi}

    \begin{satz}
    Folgende Matroidklassen sind minor-abgeschlossen:
    \begin{itemize}
    \item uniforme Matroide
    \item graphische Matroide
    \item kographische Matroide
    \item $\mathbb{F}$-repräsentierbare Matroide
    \end{itemize}
    \end{satz}

    \begin{beweis}
    Dieser Satz ist nur eine
    Zusammenfassung von
    Satz~\ref{uniforme-sind-minor-abgeschlossen},
    Satz~\ref{graphen-sind-minor-abgeschlossen},
    Satz~\ref{dualitaet},
    Satz~\ref{matrizen-sind-minor-abgeschlossen-1} und
    Satz~\ref{matrizen-sind-minor-abgeschlossen-2}.
    \hfill $_\blacksquare$
    \end{beweis}

\subsection{Ausblick: Verbotene Minoren}

Wir wissen nun,
dass praktisch alle interessanten Matroidklassen
minor-abgeschlossen sind.
Aber hilft uns das,
diese Klassen besser zu verstehen?
Ja!
Denn diese Eigenschaft ermöglicht
die Untersuchung von verbotenen Minoren:
    \begin{defi}
    Sei $\mathcal{M}$ eine
    minor-abgeschlossene Matroidklasse.
    Ein
    \defiterm{verbotener Minor}
    von $\mathcal{M}$
    ist
    ein minimaler Matroid
    außerhalb von $\mathcal{M}$.
    Das heißt,
    all seine echten Minoren
    liegen in $\mathcal{M}$,
    aber er selbst liegt nicht in $\mathcal{M}$.
    \end{defi}
Verbotene Minoren sind gewissermaßen "`Muster"',
die verhindern,
dass ein Matroid zu einer bestimmten Klasse gehört.
Um festzustellen,
ob ein bestimmter Matroid zu einer Klasse gehört,
brauchen wir "`nur"' schauen,
ob er einen verbotenen Minor enthält.

Dieses Prinzip ist keineswegs neu.
Wie kennen das schon
aus der Graphentheorie:%
    \begin{beispiel}
    Um festzustellen, ob ein Graph zur
    Klasse der planaren Graphen
    gehört,
    können wir einerseits eine planare Darstellung suchen.
    Wir können aber auch einfach schauen,
    ob er einen $K_{3,3}$ oder $K_5$ als Teilgraph\footnote{%
        Der Begriff "`Teilgraph"' ist nicht ganz korrekt.
        Genauer gesagt
        man muss untersuchen,
        ob sich der Graph durch
        Zusammenziehen oder Löschen von Kanten bzw. Knoten
        in $K_{3,3}$ oder $K_5$ überführen lässt.
        (Satz von Kuratowski)}
    enthält.
    Denn $K_{3,3}$ und $K_5$
    sind die kleinsten nicht-planaren Graphen.
    \end{beispiel}
Diese Form der Untersuchung funktioniert natürlich nur,
wenn wir
\emph{alle} verbotenen Minoren einer Matroidklasse
kennen.
Für manche Klassen sind sie sehr leicht zu bestimmen.
Es gibt sogar Klassen,
die nur einen einzigen verbotenen Minor haben.
Doch es gibt auch Klassen,
deren verbotenene Minoren nur sehr schwer zu bestimmen sind.
Für einige Klassen
ist noch nicht einmal geklärt,
ob sie endlich oder unendlich viele verbotenene Minoren haben.


\bibliography{Literatur}
%\bibliographystyle{alphadin}
\bibliographystyle{geralpha}
\nocite{Oxley}

\end{document}