Diese Vorlesung gibt eine Einführung in die Algebraische Kombinatorik. Im ersten Teil der Vorlesung werden Mengensysteme (Simplizialkomplete, Multikomplexe, Ordnungsideale etc.) durch Monomideale dargestellt und mit Mitteln der kommutativen und homologischen Algebra (Hilbert-Funktionen, Betti-Zahlen, Auflösungen etc.) untersucht. Dabei lernen wir starke Zusammenhänge zwischen den kombinatorischen, algebraischen und topologischen Eigenschaften der Objekte kennen (z. B. Reisners Theorem). Falls die Zeit es zulässt machen wir einen kurzen Abstecher zu Punktkonfigurationen, torischen Idealen und Triangulierungen. Im zweiten Teil der Vorlesung betrachten wir nicht-kommutative algebraische Strukturen auf Klassen von kombinatorischen Objekten (z. B. Inzidenzkoalgebren). Das bringt uns zur Theorie der Ko-/Bialgebren und der kombinatorischen Hopfalgebren. Insbesondere werden wir uns für Malvenuto-Reutenauer Hopfalgebra der Permutationen und quasisymmetrische Funktionen (sowas wie unendlichen Permutationen) interessieren.
Link zum Vorlesungsverzeichnis.Vorlesung: | Dienstag | 12 - 14 Uhr | RM10 107 |
Donnerstag | 10 - 12 Uhr | RM10 711gr | |
Übung: | Dienstag | 14 - 16 Uhr | RM10 901 |
Abgabe: 30. April | Blatt 1 |
Abgabe: 7. Mai | Blatt 2 |
Abgabe: 14. Mai | Blatt 3 |
Abgabe: 21. Mai | Blatt 4 |
Abgabe: 28. Mai | Blatt 5 |
Abgabe: 4. Juni | Blatt 6 |
Abgabe: 11. Juni | Blatt 7 |
Abgabe: 18. Juni | Blatt 8 |
Abgabe: 25. Juni | Blatt 9 |
Abgabe: 2. Juli | Blatt 10 |
Abgabe: 9. Juli | Blatt 11 |
16/18. April |
Mengen, Teilmengen, Binomialkoeffizienten; Eigenschaften via
multivariater Polynome: Rekursion (Enumeration), Symmetrie
(lineare Relationen), Ungleichungen (unimodal, log-konkav);
Mengensysteme aus der diskreten Mathematik: Kantenmengen
kreisfreier Untergraphen, stabile Knotenmengen von Graphen,
linear-unabhängige Teilmengen einer Vektorkonfiguration,
Teilbarkeitsketten von natürlichen Zahlen,
Positionen nicht-schlagender Türme auf Schachbrettern,
Nicht-kreuzende Diagonalen in Polygonen; Enumeration und
Eigenschaften mittels Algebra; multivariate Polynome und
Quadratfreier Unterring; perfekte Paarung und Symmetrie von
Binomialkoeffizienten; Linearformen und Unimodalität; (Kurzer
Ausblick nicht-kommutative Polynome) Geometrie: Polytope und Seitenflächen; (Knoten)Mengen von Seitenflächen und f-Vektoren; Upper Bound Problem und simpliziale Polytope; Zyklische Polytope und Nachbarschaftlichkeit; McMullens Upper Bound Theorem (Motzkin Vermutung plus Gleichheitsfall); f-Vektoren und h-Vektoren: Nicht-negativität und Dehn-Sommerville Gleichungen; Upper Bound Theorem in h-Vektoren; Interpretation via Multimengen |
23/25. April |
Abstrakte Simplizialkomplexe und (bisherige) Beispiele; Dimension,
Ecken, Kanten, Facetten; Graphen von Komplexen und Zusammenhang;
reine Komplexe; f- und h-Vektoren und Polynome; partitionierbare
Komplexe haben nicht-negative h-Vektoren; Simplexe und
geometrische Simplizialkomplexe; Satz: abstrakte und geometrische
Simplizialkomplexe sind das gleiche; Beispiel zum ausprobieren:
xxxxxxxxxx S = SimplicialComplex([ [1,2,3], [2,4], [3,4], [4,5] ] ) print 'Dimension = ', S.dimension() print 'Rein? ', S.is_pure() print 'Zusammenhaengend? ', S.is_connected() print 'f-vector = ', S.f_vector() print 'h-vector = ', S.h_vector() Homöomorphe Komplexe; Ränder von simplizialen Polytopen gleicher Dimension sind homöomorph; simpliziale Sphären; es gibt simpliziale 3-Sphären die nicht von Rändern von 4-Polytopen kommen; modellieren von geometrischen/topologischen Objekten durch Simplizialkomplexe; Satz: Ob ein 3-Komplex eine Sphäre ist ist unentscheidbar; Invarianten um Komplexe zu unterscheiden: simpliziale Homologie; Kettengruppen und Randabbildungen; Kettenkomplexe, Ketten- und Randgruppen; simpliziale Homologie; Satz: Homöomorphe Komplexe haben gleiche Homologie |
30. April/2. Mai |
(-1)ste und 0-te Homologie; Homologie von Graphen; Homologie von
Simplexen und, allgemeiner, von Kegeln; Kegel sind azyklische
Komplexe; Homologie simplizialer Sphären; triangulierte Tori und
Homologiebasen; reduzierte Bettizahlen und Flächen
(Unter)mannigfaltigkeiten; (abgeschlossene) Sterne und Links; Join von Komplexen; kombinatorische Mannigfaltigkeiten; Pseudomannigfaltigkeiten; duale Graphen und starker Zusammenhang; Homologie-Mannigfaltigkeiten und Homologie-Spähren; Upper Bound Theorem for homology spheres; Euler Charakteristik als alternierende Summe über f-Vektor or Betti-Vektor; Kurze exakte Sequenzen |
7/9. Mai |
Mayer-Vietoris Sequenz; konstruierbare und schälbare Komplexe;
schälbar impliziert konstruierbar impliziert Homoligie von
Bouquet von gleich-dim Sphären; schälbar impliziert
partitionierbar
Satz: Schälbare Pseudomannigfaltigkeiten sind Sphären; Links und Sterne schälbarer Komplexe sind schälbar; Satz: (simpliziale) Polytope sind schälbar (Stichwort: Raketenflug); Matroide und unahbängige Mengen; Graphische Matroide; Vektormatroide; Punktkonfigurationen; Basen und Rang; Charakterisierung von Basen |
14/16. Mai |
Kreise von Matroiden; lexikographische Ordnung; Satz: Jede
lexikographische Ordnung der Basen ist eine Schälung des Komplex
der unabhängigen Mengen; Charaktierisierung von unabhängigen
Matroiden über lexikographische Schälungen; Beispiel!;
Partiell-geordnete Mengen (Posets); Inklusion-Exklusion und
Möbiusinversion
xxxxxxxxxx #Graph mit Kanten 1, 2, 3, 4, 5 G = Graph( [ (10,11,1), (10,12,2), (11,12,3), (12,13,4), (11,13,5) ] ) # Menge mit der aufspannenden Baeume F = [ Set([ G.edge_label(i,j) for i,j,_ in t.edges() ]) for t in G.spanning_trees() ] # lexikographisch geordnet F = sorted(F, cmp=lambda A,B: int( min(A.difference(B)) - min(B.difference(A))) ) II = SimplicialComplex(F) print 'II schaelbar? ', II.is_shellable() print 'F ist Schaelreihenfolge?', II.is_shelling_order(F) print 'Restriktionen = ', II.restriction_sets(F) print 'h-Vektor = ', II.h_vector(), ' (insbesondere ist h_3 = Anzahl Restriktionen mit 3 Elementen)' print 'Betti = ', II.betti(), ' (H_2 = k^2 und alles andere 0)' Inzidenzalgebra eines Posets; Kriterium für die Existenz von Inversen; lineare Erweiterungen und obere Dreiecksmatrizen mit vorgeschriebenen 0-Einträgen; Zeta- und Möbiusfunktionen; Kombinatorik mit Zeta-Funktionen; Zeta-Polynome |
21/23. Mai |
Ordnungskomplexe; Satz(Hall): Möbiusfunktionen und reduzierte
Euler-Charakteristik von Ordnungskomplexen; graduierte Posets;
baryzentrische Unterteilungen von Simplizialkomplexen;
(semi-)Eulersche Posets und Homologie-Mannigfaltigkeiten;
Vorzeichen-alternierende Posets und schälbare Ordnungskomplexe
Ränge von Ketten in graduierten Posets; Fahnen-f-Vektoren und Fahnen-h-Vektoren; maximale Ketten in rank-selected Posets; Satz: Für Bool'sche Verbände zählt beta(S) die Anzahl Permutationen mit Abstiegsmenge S; R-Beschrifungen und R-Posets; Satz: Für ein R-Poset ist der Fahnen-h-Vektor nichtnegativ xxxxxxxxxx P = Poset(([],[[ 'a', 'b' ], [ 'a', 'c' ], [ 'b', 'd' ], [ 'c', 'd' ], [ 'c', 'e' ], [ 'd', 'f' ], [ 'd', 'g' ], [ 'e', 'g' ], [ 'f', 'h' ], [ 'g', 'h' ]])) P.show() f = P.flag_f_polynomial() for e,c in zip(f.exponents(),f.coefficients()): print 'alpha(',[ i for i in range(P.rank()) if e[i] == 1], ') = ', print c h = P.flag_h_polynomial().numerator() for e,c in zip(h.exponents(),h.coefficients()): print 'beta(',[ i for i in range(P.rank()) if e[i] == 1], ') = ', print c |
27. Mai |
Beispiel und Beweis zu R-Beschriftungen; Supremum, Infimum und
Verbände; distributive Verbände und Birkhoff Theorem; lattices
of flats; semimodulare Verbände; Satz: Semimodulare Verbände
haben R-Beschriftung; L-Beschriftung und EL-schälbare Posets;
Satz: L-Beschriftung impliziert Ordnungskomplex schälbar
Das Beispiel hier zeigt das 'lattice of flats' aus der Vorlesung samt R-Beschriftung und der lexikographischen Ordnung der Beschriftungen auf allen maximalen Ketten: xxxxxxxxxx m = matrix( [(0, 1, 2, 0, 0), (0, 0, 0, 1, 2), (1, 1, 1, 1, 1)] ) M = Matroid( groundset=[1..5], matrix=m) L = M.lattice_of_flats() L.show(element_labels={ a:tuple(a) for a in L}) Lambda = { (A,B):min(B.difference(A)) for A,B in L.cover_relations() } Chains = [] for C in L.maximal_chains(): l = [ Lambda[(C[i],C[i+1])] for i in range(L.rank()) ] Chains.append( l ) def lex(u,v): d = len(u) i = min([ j for j in range(d) if u[j] != v[j] ]) return int(u[i] - v[i]) Chains = sorted(Chains,cmp=lex) for c in Chains: print c, print |
3+5. Juni |
assoziative Algebren; unitär und kommutativ; Beispiele:
Produkte, Funktionen, multivariate Polynomringe;
Halbgruppenalgebren und nicht kommutative Polynomringe; binäre
Relationen und Inzidenzalgebren; Algebra-Homomorphismen und
Isomorphie
Bilder von Algebra-Homomorphismen sind Unteralgebren; endlich-erzeugte (Unter)Algebren; Kern eines Algebra-Homomorphismus und Ideale; Quotienten nach Idealen sind Algebren; nipotente Elemente und Nullteiler; reduzierte Algebren und Integritätsbereiche; radikale Ideale und Primideale; Aufsteigende Ketten Bedingung und noethersche Algebren; Prop: alle Ideale endlich erzeugt gdw noethersch; Hilbert'scher Basissatz |
11+13. Juni |
Moduln über Algebren; endlich-erzeugt und frei; noethersche
Moduln; Prop: Wenn A noethersch, dann ist jeder endlich-erzeugte
Modul noethersch; G-graduierte / multigraduierte Algebren;
homogene Algebrahomomorphismen, homogene Ideale und Quotienten;
positive Multigraduierungen
positive Multigraduierung: alle graduierten Bestandteile haben endliche Dimension; multigraduierte Hilbert-Funktionen/-Reihen; Satz: Hilbert-Reihe ist rational |
18+18. Juni |
fein graduierte Polynomringe und Monomideale; fein-graduierte
Hilbertreihen; Vergröberung der Graduierung und
Spezialisierung der Hilbertreihe; standard graduierte
Algebren; Stanley-Reisner ringe; minimale Nichtseiten; feine
Hilbertreihen
Vergröberung und h-Vektoren; Poset Ringe als Stanley-Reisner Ringe von Ordnungskomplexen; graduierte Posets, Graduierungen und Fahnen-Vektoren; Lemma zur Reziprozität feiner Hilbertreihen; Homologie-Sphären und Dehn-Sommerville Gleichungen |
25+27. Juni |
Wann sind h-Vektoren nicht-negativ?; reguläre Elemente und
Sequenzen; Tiefe eines Moduls; algebraische Unabhängigkeit und
Krull Dimension;
Ganzheit und Noether Normalisierung; Krull Dimension als Ordnung Pol von Hilbertreihe; |
2. Juli 4. Juli |
Cohen-Macaulay Ringe und Cohen-Macaulay Komplexe; Satz: Wie findet man lsops eines Stanley-Reisner Rings; Schälbare Komplexe sind Cohen-Macaulay |
9+11. Juli |
Homologischer Zugang zu Tiefe; Kozul Komplexe für 1 und 2
Elemente; Kozul Komplexe allgemein entdecken reguläre
Sequenzen
kurzer Ausblick auf Chech Komplexe (und lokale Kohomologie); Multimengen, Multikomplexe und Hilbert Funktionen; Macaulay: alle möglichen Hilbert Funktionen werden auf Monomidealen realisiert; O-Sequenzen und Charakterisierung; h-Vektoren von schälbaren/CM Komplexen |
Lectures on polytopes. Günter Ziegler
Combinatorics and commutative algebra. Richard Stanley
Elements of algebraic topology. James Munkres
Combinatorial commutative algebra. Ezra Miller, Bernd Sturmfels
Twenty-four hours of local cohomology. Iyengar et al
Hopf Algebras in Combinatorics. Darij Grinberg, Victor Reiner
Combinatorial Reciprocity Theorems. Matthias Beck, Raman Sanyal