BannerBannerBanner

Kombinatorische Geometrie


Was ist Kombinatorische Geometrie?

Kombinatorische Geometrie beschäftigt sich mit Phänomenen im Grenzbereich von kombinatorischen und metrischen Strukturen. Typische kombinatorische Daten, die hierbei betrachtet werden, sind die Inzidenzen der beteiligten Objekte, relative Orientierungen, Koplanaritäten, etc.

papAsm1.gif
Nicht-streckbares Pseudogeradenarrangement
Nebenstehendes Pseudogeradenarrangement hat z.B. neben seiner metrischen Realisation auch eine rein kombinatorische Ebene nämlich die Struktur des Zellkomplexes, welches es ausschneidet (wieviele Dreiecke gibt es, wie sind Dreiecke und Vierecke benachbart, etc). Kombinatorische Geometrie beschäftigt sich nun meit dem Zusammenspiel von Metrik und Kombinatorik.

Typische Fragestellungen

Obwohl die Objekte die man betrachtet durchaus verschiedener Art sein können, sind die charakteristische Fragestellung oftmals verwandt.

Realisierbarkeit

Eine typische Frage, die man z.B. bezüglich eines Pseudogeradearrangements stellt ist, ob sich die selbe kombinatorische Struktur auch mit Geraden statt Pseudogeraden erzeugen lässt (die so genannte Streckbarkeitsproblematik). Konkret im Falle des nebenstehen Bildes fragt man danch, ob es neun Geraden gibt, welche den gleichen Zellkomplex erzeugen. Tatsächlich ist das Beispiel auf dieser Seite (bis auf kombinatorische Äquivalenz) der einzige nichtstreckbare Vertreter unter insgesamt 4382 kombinatorisch möglichen Typen von Zellkomplexen mit neun Pseudogeraden. Es stellt sich heraus, dass hinter nicht-realisierbaren Pseudogeraden Arrangements im Wesentlichen immer ein geometrischer Schliessungssatz steht. Somit können Algorithmen, die nicht-Realisierbarkeit beweisen, auch direkt zum automatischen Beweisen geometrischer Sätze ausgenutzt werden.

Ennumeration

In der Tat ist es keine leichte Aufgabe fetstzustellen wieviele kombinatorische Typen einer bestimmten Klasse von Objekten es gibt (für Arrangements mit 10 Pseudogeraden liegt die Zahl bei 312356; für 11 Pseudogeraden bei 41848591 und für Arrangements mit 12 Pseudogeraden ist die Anzahl (noch) unbekannt).

Zono.gif
Raum Zonotopaler Pflasterungen
Ähnliche Ennumerationsprobleme stellen sich auch für andere typische Objekte der kombinatorischen Geometrie (z.B. Polytope, Triangulierungen). Solche Ennumerationen dienen insbesondere als reicher Beispielschatz zum Widerlegen geometrischer Vermutungen.

Strukturtheorie

Die kombinatorisch geometrischen Objekte eines bestimmten Typs stehen nicht unabhängig nebeneinander. Oftmals gibt es ein Konzept einer minimalen Veränderung (eines Flips), mit dem man von einem Beispiel zum nächsten kommt. Bei Pseudogeraden wäre dies z.B. das Umklappen eines Dreiecks. Auf diese Art entstehen natürliche Nachbarschaftsbeziehungen zwischen den Objekten, die es ermöglichen z.B. vom "Raum aller Pseudogeradenarrangements" zu sprechen. Von algorithmisch fundamentalem Interesse ist es die Topologie (und insbesondere den Zusammenhang) dieser Räume zu studieren. Ist ein Raum zusammenhängend, kann er effektiv mit Suchalgorithmen exploriert werden.

Realisationsräume

Ebenso von fundamentalem Interesse sind Realisationsräume. Ist ein bestimmtes Objekt realisierbar, so ist man nämlich an der Struktur des Raumes aller mögliche Realisierungen interessiert. Es stellt sich heraus, dass abhängig von Dimension und Objektgrösse derartige Räume in der Regel sehr komplex werden können. So gelang es mir beispielsweise in meiner Habilitationsschrifft (siehe Springer Lecture Notes in Mathematics 1643) zu zeigen, das für 4-dimensionale Polytope die Realisierungsräume die Komplexität beliebiger Lösungsräume von polynomiale Ungleichungssystemen annehmen können.

Typische Objekte

Kurz seien hier ein paar Typische Objekte genannt, mit denen man sich in kombinatorische Geometrie beschäftigt: Pseudogeraden, Matroide, orientierte Matroide, Polytope, polytopale Kegel, Triangulierungen, Zellzerlegungen, Graphen, Lineare Programme und viele mehr.

-- RichterGebert - 25 Apr 2007