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. (...)