Forschung

Gibt es in einer Stadt einen Rundweg, so dass jede Brücke genau einmal benutzt wird? Kann eine Landkarte mit 4 Farben gefärbt werden? Auf wieviele Arten können Damen auf einem Schachbrett platziert werden, so dass sie sich nicht gegenseitig schlagen?

Dies sind typische Fragen in der Kombinatorik, die zu viel interessanter Mathematik führt. Wir interessieren uns dabei für die Existenz, Konstruktion, für das Zählen und Erzeugen verschiedenster kombinatorischer Strukturen. Wir betreiben den Combinatorial Object Server, auf dem wir Algorithmen bereitsstellen, um verschiedenste kombinatorische Objekte zu erzeugen.

In diesem Zusammenhang ergeben sich auch immer wieder spannende studentische Arbeiten, bei denen neue Algorithmen entwickelt und auf dem Combinatorial Object Server bereitgestellt werden.
Der Combinatorial Object Server ist das Pendant zur bekannten Online-Enzyklopädie für Zahlenfolgen, die alle möglichen (z.B. Catalan-Zahlen, Fibonacci-Zahlen, Primzahlen, ...) und unmöglichen (z.B. Busy-Beaver, Look-and-say, Golomb, ...)  Zahlenfolgen enthält.

Graphen beschreiben Beziehungen zwischen Objekten, und spielen in vielen Anwendungen eine zentrale Rolle, z.B. in Verkehrsnetzwerken, Freundschaftsnetzwerken, Computernetzwerken.

Daraus ergeben sich strukturelle Fragen, z.B.: Welche Strukturen gibt es in einem größeren Graphen/Netzwerk? Welche Eigenschaften hat ein Graph, und in welcher Beziehung stehen diese Eigenschaften zueinander?

Des Weiteren ergeben sich auch direkt algorithmische Fragen, z.B.: Wie komme ich in einem Verkehrsnetzwerk am schnellsten von A nach B? Welche Gruppen von Freunden gibt es im Freundschaftsnetzwerk Facebook? Wie kann ein Computernetzwerk am besten verbunden werden, um schnelle und störungsfreie Kommunikation zwischen den Computern zu ermöglichen?

Wir entwickeln Algorithmen für solche Aufgaben, beweisen deren Eigenschaften, oder zeigen, dass es solche Algorithmen nicht geben kann.

In der diskreten Geometrie betrachten wir geometrischen Objekten, wie z.B. Punkten, Geraden, Ebenen im 2-dimensionalen, 3-dimensionalen oder sogar höherdimensionalen Räumen.

Diese Objekte bilden Strukturen wie z.B. Triangulierungen, Arrangements, Diagramme, Polytope, deren Eigenschaften wir untersuchen, und die wir effizient berechnen und visualisieren wollen.

Auch beim Origami bieten sich zahlreiche mathematische Fragen, wie z.B.: Kann eine Figur nach gewissen Regeln aus einem Blatt Papier ohne Schneiden gefaltet werden? Kann eine 3-dimensionale Figur in ein 2-dimensionales Netz zerlegt werden, welches dann ausgeschnitten und zusammengefaltet werden kann?

Wir untersuchen kombinatorische Spiele und Puzzle wie Nim, Klotski, Rubik's Cube usw. bezüglich Gewinnstrategien, Lösbarkeit, Algorithmen, Komplexität usw.