Upload
erika-dressler
View
213
Download
0
Embed Size (px)
Citation preview
Das Flussgitter affiner Punktkonfigurationen
Robert Nickel, Winfried Hochstättler
Mathematische Grundlagen der Informatik
Institut für Mathematik
Brandenburgische Technische Universität Cottbus
oder ein anderer lustiger Titel
Slide 2 of 14
Outline
Rundflüsse in Digraphen
Punkte in allgemeiner Lage
Punkte in der Ebene
Punkte, Kreise und das Flussgitter
“Graphische” Punktmengen
Slide 3 of 14
Kreise und Rundflüsse in Digraphen
Kreis mit Umlaufsinn:
Rundfluss
Nichtnullfluss: Flusszahl:
2
3
4
5
6
7
8
9
1
1
-11
-1
1
1
1
1
-12
-21 1 1
Slide 4 of 14
Zu jedem Digraphen existiert eine Punktmenge, deren Radon-Partitionen die gleiche Kreisstruktur definiert (graphische Punktmengen)
Punkte im Raum
Satz von Radon (1952): Seien paarweise verschieden. Dann existiert für alle mit eine Partitionierung (Radon-Partition), so dass
S
ST
T
ST
1
2
3
45
67
1
2
3
4
5
6
3
1 2
45
6
123: +-+000146: +00+0-256: 0+00+-345: 00+-+01245:+-0+-01356:+0+0+-2346:0+-+0-
Radon-Partitionen verallgemeinern den Kreisbegriff in Digraphen(genauso Rundfluss, Nichtnull-Fluss, Flusszahl)
Slide 5 of 14
Reorientierung
In Digraphen geschieht Reorientierung durch Umorientieren der KantenFür Punktmengen benötigen wir etwas projektive Geometrie:
Die Punkte befinden sich auf der projektiven SphäreReorientieren eines Elements bedeutet, dass anstelle des Punktes sein auf der anderen Sphärenhälfte liegendes Double benutzt wirdDurch eine projektive Abbildung wird die neue Punktmenge wieder auf eine Halbkugel transformiert (siehe Grünbaum – Convex Polytopes)
Kreise vorher:1234:+--+01235:+--0+1245:+-0-+1345:+0+-+2345:0++-+
Kreise nachher:1234:+-++01235:+-+0+1245:+-0-+1345:+0--+2345:0+--+
Slide 6 of 14
Wir betrachten das ganzzahlige Gitter der Kreise
Jedes Element von charakterisiert also einen “Rundfluss” in der Punktmenge
Die Flusszahl von wird dann analog zu Digraphen definiert:
Insbesondere wird uns die Dimension des Flussgitters interessierenDas Flussgitter ist reorientierungsinvariant
Das Flussgitter
Slide 7 of 14
Punkte in allgemeiner Lage
Annahme: Punkte liegen nicht auf einer HyperebeneAlle Kreise haben Elemente
Beispiel:
Slide 8 of 14
Für ungerade Dimension gilt: (Hochstättler, Nešetřil 2003)
Satz: Sei gerade, und . Dann gibt es eine Reorientierung von mit so dass Insbesondere ist
Es gibt eine Reorientierung die nur balancierte Kreise enthält,
Beispiel :
Slide 9 of 14
Neighborly Polytope
Sei nun so reorientiert, dass alle Kreise balanciert sind ist konvex unabhängig
Sei weiterhin eine -elementige Menge Für jede -elementige Teilmenge von gilt:
Jede Menge von Punkten ist eine Seitenfläche von
gehört zur Klasse der neighborly Polytope
Slide 10 of 14
Charakterisierung des Flussgitters
Genauer gilt: genau dann wenn reorientierungsequivalent zu
einem neighborly Polytop ist
Auf dieser Grundlage konnten wir das Flussgitter für Punkte in allgemeiner Lage vollständig charakterisieren:
Daraus lässt sich sofort die Flusszahl ablesen:
Slide 11 of 14
Sei nun und die Punkte in beliebiger Lage. Wie ist nun die Dimension des Flussgitters?
Induktionsanfang: (für weniger Punkte ist die Dimension 1 oder 0)
Dies sind alle Reorientierungsklassen(Lukas Finschi 2001)
Punkte in der Ebene
Slide 12 of 14
Noch mehr Punkte in der Ebene
Um eine sinnvolle Vermutung äußern können schauen wir uns noch den Fall an (17 Reorientierungsklassen).
Die einzigen nicht volldimensionalen Flussgitter gehören zu
Slide 13 of 14
Satz: Seien Punkte in der Ebene, die nicht parallel, nicht neighborly und nicht graphisch sind. Dann gilt:
Beweis: Eine Gerade hat volle DimensionHinzunahme von zwei Punkten, die nicht beide auf der Gerade liegen erhöht die Dimension um genau eins.Eine Erweiterung einer Menge mit -Punkt-Geraden-Minor hat nur dann niedere Dimension, wenn der neue Punkt auf der Gerade liegtalle Erweiterungen von neighborly oder graphischen Punktemengen haben volle Dimension (sofern sie nicht wieder neighborly oder graphisch sind)
Die Dimension für Punkte in der Ebene
Slide 14 of 14
Graphische Punktmengen
Satz: Sei eine Punktmenge. Dann gilt:
Offene Fragen:Struktur des Flussgitters und Flusszahl für Punkte in der Ebene (coming soon)Struktur des Flussgitters und Flusszahl für graphische Punktmengen (Das ist aber viel zu schwer!!), Tutte’s 5-flow conjectureDimension des Flussgitters für beliebige Punktmengen (hopefully coming)
Slide 15 of 14
Orientierte Matroide
Aussagen für orientierte Matroide:
Ein uniformes orientiertes Matroid von ungeradem Rang hat Flussgitterdimension genau dann wenn es neighborly ist.
Ein simples und cosimples orientiertes Matroid mit Rang 3 hat volle Flussgitterdimension genau dann wenn es nicht regulär oder neighborly ist.
Ein orientiertes Matroid mit Rang ist regulär genau dann wenn es Flussgitterdimension hat.