Vier Farben
Torsten Ueckerdt arbeitet seit 2012 in der Arbeitsgruppe Diskrete Mathematik an unserer Fakult\xe4t f\xfcr Mathematik am Karlsruher Institut f\xfcr Technologie (KIT). Er hat an der TU Berlin Mathematik studiert und promoviert. Anschlie\xdfend forschte er f\xfcr einige Zeit in Prag mit Jan Kratochvil. Er arbeitet unter anderem mit geometrischen Graphen. Graphen sind allgegenw\xe4rtige Modelle in vielen und sehr unterschiedlichen Anwendungen. Im jedem Fall bestehen sie aus Knoten und Kanten (zwischen den Knoten). Ein Beispiel f\xfcr einen geometrischen Graphen, auf das wir im Gespr\xe4ch mehrfach zur\xfcckkommen, ist die folgende Reduktion von Landkarten: Knoten stehen f\xfcr die L\xe4nder und Kanten zwischen zwei Knoten symbolisieren eine gemeinsame Grenze der L\xe4nder. Damit ist der Graph eine abstrakte aber dabei auch sehr klare Fassung der nachbarschaftlichen Lage der L\xe4nder in der Landkarte. Das hei\xdft, dass f\xfcr die Darstellung im Graphen die meiste geometrische Information der Landkarte aussortiert wird. Andere Beispiele f\xfcr geometrische Graphen sind Sichtbarkeitsgraphen, geometrische Vergleichbarkeits- und Schnittgraphen (z.B. Intervallgraphen), Einheitsdistanz-Graphen oder geordnete Graphen die etwa bei Schedulingproblemen eine gro\xdfe Rolle spielen. Wenn ein geometrisches Problem mittels eines Graphen abstrahiert wird, kann das immense Vorteile bringen. Zum Beispiel k\xf6nnen so Resultate, Konzepte und Techniken f\xfcr allgemeine Graphen verwendet werden. Auch das blo\xdfe "Vergessen" der geometrischen Einbettung kann die Argumentationen und Objekte erheblich vereinfachen. Andererseits ist das erstrebte Resultat f\xfcr allgemeine Graphen eventuell gar nicht g\xfcltig. 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\xe4ngliche Beispiele f\xfcr die N\xfctzlichkeit der Abstraktion durch Graphen sind das K\xf6nigsberger Br\xfcckenproblem und das Springerproblem. Andere Fragen, die Torsten umtreiben sind das F\xe4rben (z.B. von Knoten oder Kanten) und \xdcberdecken von Graphen. Einige Bekanntheit erlangte z.B. das Vier-Farben-Problem. Die Frage ist dabei, ob es f\xfcr alle Landkarten m\xf6glich ist, die L\xe4nder mit vier unterschiedlichen Farben so einzuf\xe4rben, dass Nachbarl\xe4nder stets unterschiedliche Farben haben. Der Beweis daf\xfcr, dass dies eine wahre Aussage ist, ist inzwischen gelungen und hat zwei Hauptschritte. Im ersten Schritt werden die potentiell unendlich viele F\xe4lle, die bei Landkarten auftreten k\xf6nnen, auf endlich viele (leider noch sehr viele) zur\xfcckgef\xfchrt. Anschlie\xdfend wird der Beweis durch Fallunterscheidungen f\xfcr mehrere 1000 F\xe4lle auf Computer ausgelagert. (...)