Diskrete Mathematik / Theorie, Konstruktion, Computation, Anwendungen

Kombinatorik und Homologische Algebra

Der Zusammenhang zwischen Homologischer Algebra und Monomialen Idealen ist seit den Arbeiten von Reisner ein viel studiertes Thema.

Zu jedem Graphen G=(V,E) hat man das monomiale Ideal < x_i x_j | (i,j) ∈ E > ⊂ K[x_i | i ∈ V]. Die Dimension der Nullstellenmenge ist die Cliquen-Zahl des Komplementärgraphen. Der Grad ist die Anzahl der maximalen Cliquen. Will man diese Zahlen mit Gröbnerbasen berechnen, dann ist die Castelnuovo - Mumford - Regularität das entscheidende Maß für die Komplexität.

Fragen und Aufgaben

1. Wie interpretiert man diese in graphentheoretischen Begriffen?
2. Für einen Graphen mit vorgegebenen Ecken und Kantenzahlen bestimme man eine obere Schranke der Castelnuovo Mumford Regularität. Was ist der Erwartungswert der Regularität bei für zufällige Graphen?
3. Berechnung der Castelnuovo Mumford Regularität mit graphentheoretischen Algorithmen.

Direktlinks: Einleitung | Themenübersicht