Untergrenzen für die Größe der unabhängigen Menge in einem Diagramm?

Ich habe kürzlich erfahren, dass für jeden Fall ein k-SAT-Problem mit $m$ Klauseln und $n$ Literale, wir haben eine Zuordnung von Literalen, so dass zumindest $m(1 - 2^{-k})$ Klauseln sind erfüllt.

Ich habe mich gefragt, ob wir eine (nicht triviale) Untergrenze zeigen können, wie sie jeder Graph hat $G = (V,E)$ hat einen unabhängigen Satz von Größe $S$ wo $S$ Ist eine Funktion in der Anzahl der Eckpunkte und Kanten oder dergleichen?

Da wir in der Optimierungsversion versuchen, eine maximale unabhängige Teilmenge zu finden, ist es umso besser, je enger die Untergrenze ist. Daher habe ich mich gefragt, ob es eine solche Untergrenze gibt, wie eng können wir sie machen?

Das relevante Ergebnis ist als Turáns Theorem bekannt . Es heißt, wenn ein Graph weniger als (ungefähr) hat$n(n-1)/(2r)$ Kanten dann hat es einen unabhängigen Satz von Größe $r+1$und das ist eng.

Es gibt auch ein algorithmisches Ergebnis. Gegeben ein$n$-vertex planar graph $G=(V,E),$ man kann in linearer Zeit eine unabhängige Menge von Eckpunkten mit einem Grad kleiner als berechnen $12$ deren Größe ist mindestens $\left\lceil\frac{n}{24}\right\rceil.$Siehe z. B. Das, Goodrich, Zur Komplexität von Optimierungsproblemen für dreidimensionale konvexe Polyeder und Entscheidungsbäume