Theorema Magnum MMXVIII: die Hodge-Riemann-Relationen für Matroide

Wenn das Coxeter-System von einer halbeinfachen Lie-Gruppe kommt, entsprechen die Soergelschen Bimoduln der äquivarianten Schnittkohomologie der zugehörigen Schubert-Varietät und das Lefschetz-Paket entspricht der klassischen Hodge-Theorie. Eine andere Situation, wo man ein Analogon zur Hodge-Theorie hat, ist die kombinatorische Schnittkohomologie von Polytopen, das ist die Schnittkohomologie der zum Polytop zugeordneten torischen Varietät. Die klassischen Dehn-Sommerville-Gleichungen für die Anzahlen d-dimensionaler Seiten des Polytops wurden hier von Stanley mittels Poincaré-Dualität interpretiert. Für diese Schnittkohomologie bewies Peter McMullen 1993 die Existenz von Lefschetz-Paketen und vereinfachte damit Stanleys Beweis der g-Vermutung für polytopale Sphären. Die g-Vermutung formuliert Bedingungen für den f-Vektor (den Vektor aus den Anzahlen d-dimensionaler Seiten eines Polytops für d=0,1,,…) für polytopale Sphären. In ihrer allgemeinen Form für simpliziale Sphären (und sogar Homologiesphären) wurde die g-Vermutung Ende 2018 von Adiprasito bewiesen, wobei er für den Beweis des schweren Lefschetz-Satzes die Hodge-Riemann-Relationen durch eine noch stärkere Bedingung (Hall-Laman-Relationen) ersetzen mußte. Eine Anwendung war der Beweis der Grünbaum-Kalai-Sarkaria-Vermutung, die für den f-Vektor eines d-dimensionalen Simplizialkomplexes die Ungleichung behauptete.

In der Konvexgeometrie kennt man seit dem Ende des 19. Jahrhunderts die Brunn-Minkowski-Ungleichung für das Volumen von Minkowski-Summen und als weitreichende Verallgemeinerung die Alexandrow-Fenchel-Ungleichungen, deren Beweis von 1938 einen elementaren Fall von Hodge-Riemann-Relationen verwendet. Aus den Alexandrow-Fenchel-Ungleichungen folgt, dass die gemischten Volumina konvexer Körper eine log-konkave (und damit unimodale) Folge bilden. Stanley hatte das in den 1980er Jahren benutzt, um die Log-Konkavität von in der Kombinatorik vorkommenden Folgen zu beweisen. 2011 bewies June Huh die Log-Konkavität des chromatischen Polynoms von Graphen, indem er seine Koeffizienten als Betti-Zahlen eines Hyperbenenkomplements interpretierte, diese wiederum algebraisch als gemischte Vielfachheiten von Idealen berechnete und deren Log-Konkavität dann aus den Alexandrow-Fenchel-Ungleichungen für die gemischten Volumina zugeordneter Gitterpolytope folgerte.

Das chromatische Polynom P(k) eines Graphen an der Stelle k gibt die Anzahl der Färbungen des Graphen mit k Farben. Zum Beispiel gibt der Vierfarbensatz die Ungleichung P(4)≥1 für planare Graphen.

Planare Graphen unterscheiden sich von beliebigen Graphen dadurch, dass man zu ihnen einen dualen Graphen definieren kann: die von Kanten eingeschlossenen Flächenstücke der Ebene geben die Knoten des dualen Graphen, Kanten zwischen Flächenstücken werden Kanten des dualen Graphen.

In seiner Dissertation von 1932 war es Hassler Whitney gelungen, diese schon lange bekannte Dualität ebener Graphen rein kombinatorisch zu formulieren und daraus eine neue Charakterisierung ebener Graphen herzuleiten. Ausgehend von den dualen Begriffen Baum-Kreis arbeitete er dann in der 1935 im American Journal of Mathematics veröffentlichten Arbeit “On the abstract properties of linear dependence” die genauen Axiome für die Existenz eines kombinatorischen Duals in beliebigen Mengensystemen heraus – den Begriff des Matroids. 

Ein Matroid besteht aus einer endlichen Menge E und einer Menge von Teilmengen, unabhängige Mengen genannt, mit und den Eigenschaften: wenn und , dann ist , und wenn und kleiner als ist, dann gibt es ein Element , so dass .
Das klassische Beispiel eines Matroids sind die Spalten einer gegebenen Matrix mit dem üblichen Begriff linearer Unabhängigkeit. Jede Teilmenge linear unabhängiger Spalten ist ebenfalls linear unabhängig, und zu einer Menge aus p und einer anderen aus p+1 linear unabhängigen Spalten kann man eine Spalte aus der zweiten Menge finden, die zusammen mit den p Spalten der ersten Menge linear unabhängig ist – das ist eine Variante des Austauschlemmas von Steinitz.
Whitney bewies in seiner Arbeit elementare Eigenschaften solcher Matroide, insbesondere dass alle maximalen unabhängigen Mengen dieselbe Kardinalität haben. Weiter definierte er zu jedem Matroid M ein duales Matroid M*, dessen maximal unabhängige Mengen gerade die Komplementärmengen der maximal unabhängigen Mengen aus M sind.
Das Matroid eines Graphen besteht aus der Menge der Kanten des Graphen, wobei eine Teilmenge von Kanten als unabhängig definiert wird, wenn sie kreisfrei ist. Analog zu Kuratowskis Charakterisierung ebener Graphen kann man beweisen, dass ein Graph genau dann ein ebener Graph ist, wenn sein duales Matroid das Matroid eines Graphen ist. Zum Beispiel haben K₅ und K_3,3 kein kombinatorisches Dual und können deshalb nicht in die Ebene eingebettet werden.