Vier Farben

Torsten Ueckerdt arbeitet seit 2012 in der Arbeitsgruppe Diskrete
Mathematik an unserer Fakultät für Mathematik am Karlsruher
Institut für Technologie (KIT). Er hat an der TU Berlin
Mathematik studiert und promoviert. Anschließend forschte er für
einige Zeit in Prag mit Jan Kratochvil.


Er arbeitet unter anderem mit geometrischen Graphen. Graphen sind
allgegenwärtige Modelle in vielen und sehr unterschiedlichen
Anwendungen. Im jedem Fall bestehen sie aus Knoten und Kanten
(zwischen den Knoten). Ein Beispiel für einen geometrischen
Graphen, auf das wir im Gespräch mehrfach zurückkommen, ist die
folgende Reduktion von Landkarten: Knoten stehen für die Länder
und Kanten zwischen zwei Knoten symbolisieren eine gemeinsame
Grenze der Länder. Damit ist der Graph eine abstrakte aber dabei
auch sehr klare Fassung der nachbarschaftlichen Lage der Länder
in der Landkarte. Das heißt, dass für die Darstellung im Graphen
die meiste geometrische Information der Landkarte aussortiert
wird. Andere Beispiele für geometrische Graphen sind
Sichtbarkeitsgraphen, geometrische Vergleichbarkeits- und
Schnittgraphen (z.B. Intervallgraphen), Einheitsdistanz-Graphen
oder geordnete Graphen die etwa bei Schedulingproblemen eine
große Rolle spielen.


Wenn ein geometrisches Problem mittels eines Graphen abstrahiert
wird, kann das immense Vorteile bringen. Zum Beispiel können so
Resultate, Konzepte und Techniken für allgemeine Graphen
verwendet werden. Auch das bloße "Vergessen" der geometrischen
Einbettung kann die Argumentationen und Objekte erheblich
vereinfachen. Andererseits ist das erstrebte Resultat für
allgemeine Graphen eventuell gar nicht gültig. Eine wichtige
Aufgabe ist es deshalb, eine gute Balance zu finden zwischen
Abstraktion und wesentlicher geometrischer Information, die die
Untersuchung beeinflusst. Interessant ist, dass bestimmte
Eigenschaften des Graphen von der Geometrie "dahinter" diktiert
werden.


Sehr zugängliche Beispiele für die Nützlichkeit der Abstraktion
durch Graphen sind das Königsberger Brückenproblem und das
Springerproblem.


Andere Fragen, die Torsten umtreiben sind das Färben (z.B. von
Knoten oder Kanten) und Überdecken von Graphen. Einige
Bekanntheit erlangte z.B. das Vier-Farben-Problem. Die Frage ist
dabei, ob es für alle Landkarten möglich ist, die Länder mit vier
unterschiedlichen Farben so einzufärben, dass Nachbarländer stets
unterschiedliche Farben haben. Der Beweis dafür, dass dies eine
wahre Aussage ist, ist inzwischen gelungen und hat zwei
Hauptschritte. Im ersten Schritt werden die potentiell unendlich
viele Fälle, die bei Landkarten auftreten können, auf endlich
viele (leider noch sehr viele) zurückgeführt. Anschließend wird
der Beweis durch Fallunterscheidungen für mehrere 1000 Fälle auf
Computer ausgelagert.


An diesem Beispiel zeigen sich auch deutlich einige typische
Aspekte von Torstens Arbeit. Einerseits scheint es nicht sehr
befriedigend, dass man auf Computer im Beweis nicht verzichten
kann. Andererseits ist der schwierige Schritt eigentlich der
erste und die hier entwickelte Idee ist in der Tat eine sehr
allgemeine Methode, die inzwischen auch für andere Fragen immer
wieder eingesetzt wurde. Sie ist also bedeutsamer als "nur"
Hilfsmittel im Beweis des Vier-Farben-Satzes zu sein.
Andererseits trägt die Idee zwar weit genug für das Problem, aber
wahrscheinlich ist sie nicht wirklich optimal für die untersuchte
Struktur, da noch zu viele Fälle zu betrachten bleiben, die dann
brutal durchprobiert werden. So gibt es auch spannende
Verallgemeinerungen des Vier-Farben-Problems die bis heute
ungelöst sind. Beim sogenannten Earth-Moon Problem fragt man zum
Beispiel was passiert wenn jedes Land der Erde zusätzlich eine
Kolonie auf dem Mond errichtet und wir nun die Länder mit
möglichst wenigen Farben einfärben wollen, so dass keine zwei
Länder die auf der Erde oder auf dem Mond benachbart sind
die gleiche Farbe erhalten. Wir wissen nur, dass die kleinste
Anzahl benötigter Farben irgendwo zwischen 9 und 12 liegt. Es
sind letztlich nicht die errechneten Zahlen (wie die vier im
Vier-Farben-Satz) das eigentlich Interessante, sondern die für
deren Bestimmung entwickelten neuen Methoden.


Ein weiterer Aspekt ist die enge Verbindung von Kombinatorik und
Geometrie. Die Tatsache dass in so vielen Fällen die
kontinuierliche und überabzählbare Welt der Geometrie eindeutig
durch die diskrete und endliche Welt der Kombinatorik beschrieben
werden kann, ist faszinierend und immer wieder spannend. In der
diskreten und kombinatorischen Geometrie versucht Torsten zum
Einen geometrische Arrangements kombinatorisch zu beschreiben und
zum Anderen kombinatorische Objekte, wie zum Beispiel Graphen,
geometrisch zu realisieren. Die einfach formulierbaren Fragen in
Torstens Arbeiten haben häufig schwierige Antworten bzw.
entziehen sich einer Bearbeitung noch ganz. Nicht zuletzt liegt
das auch daran, dass die Kombinatorik schnell mit der
explodierenden Komplexität an die Wand fährt. Am Beispiel der
Landkarte: Nur für zehn (oder weniger) Länder lassen sich Ideen
relativ schnell (innerhalb eines Tages auf einem gängigen
Computer) kombinatorisch ausprobieren - es hier genau 1.140.916
verschiedene Landkarten. Im Allgemeinen wächst die Anzahl der
Landkarten allerdings exponentiell in der Anzahl der Länder - es
gibt zwischen und viele Karten mit n Ländern. Die einzige
realistische Möglichkeit geometrische Graphen zu untersuchen,
bspw. in Hinblick auf ihre Färbungen oder Überdeckungen, besteht
also in der rigorosen Analyse im wiederholten Wechsel zwischen
Geometrie und Kombinatorik - eine Herausforderung die Kreativität
und Kontinuität erfordert, aber viel Freude und Inspiration
birgt.
Literatur und weiterführende Informationen

Jaroslav Nesetril: Diskrete Mathematik: Eine
Entdeckungsreise, Springer-Lehrbuch, 2007.

Martin Aigner: Graphentheorie: Eine Einführung aus dem
4-Farben Problem. Springer Fachmedien Wiesbaden, 2015.

Michael Reeken et al: Das Königsberger Brückenproblem - Eine
Handreichung für Schüler und Schülerinnen, MathePrisma, 1998.

Podcasts

C. Schulz: Graphpartitionierung, Gespräch mit Gudrun Thäter
im Modellansatz Podcast, Folge 38, Fakultät für Mathematik,
Karlsruher Institut für Technologie (KIT), 2014.
http://modellansatz.de/graphpartitionierung

J. Breitner: Incredible Proof Machine, Gespräch mit S.
Ritterbusch im Modellansatz Podcast, Folge 78, Fakultät für
Mathematik, Karlsruher Institut für Technologie (KIT), 2016.
http://modellansatz.de/incredible-proof-machine