17
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

Das Flussgitter affiner Punktkonfigurationen Robert Nickel, Winfried Hochstättler Mathematische Grundlagen der Informatik Institut für Mathematik Brandenburgische

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.

Slide 16 of 14

Und was nun?

Graphenfärbung

orientierte Matroide

Polytope

?

Tutte

Slide 17 of 14

Danke für Eure Aufmerksamkeit