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