Das 4-Stichproben-Theorem für planare Graphen

Das berühmte 4-Farben-Theorem aus der Graphentheorie besagt, dass die Knoten jedes planaren Graphen mit vier Farben so gefärbt werden können, dass benachbarte Knoten keine gleiche Farbe haben. Das 4-Stichproben-Theorem aus der algebraischen Statistik besagt, dass der Maximum-Likelihood-Schätzer für ein Gaußsches Graphmodell eines planaren Graphen mit Wahrscheinlichkeit 1 existiert, wenn mindestens vier Stichproben vorliegen. Diese notwendige Stichprobenanzahl, die Maximum-Likelihood-Schwelle, ist ein neues Graphinvariante aus der algebraischen Statistik und steht nicht nur mit Parameterschätzung, sondern auch mit Matrixvervollständigung, der Theorie der Ausfüllung partieller Matrizen und der Starrheitstheorie, welche die Stabilität von Objekten behandelt, in Verbindung.