Der Satz von Lovász-Stein, benannt nach den Mathematikern László Lovász und Sherman K. Stein, ist ein Lehrsatz des mathematischen Teilgebiets der Graphentheorie. Der Satz formuliert eine Ungleichung, welche die kleinste Anzahl von Hyperkanten, die zur Überdeckung der gesamten Knotenmenge eines gegebenen endlichen Hypergraphen benötigt wird, zu anderen Kennziffern dieses Hypergraphen in Beziehung setzt.[1]

Formulierung des Satzes

Bearbeiten

Der Darstellung von Stasys Jukna folgend lässt sich der Satz wie folgt formulieren:[1]

Seien   natürliche Zahlen.
Sei dazu   ein endlicher Hypergraph, bestehend aus einer endlichen Knotenmenge   mit   Knoten und einem System   von   Hyperkanten.
Dabei sei vorausgesetzt, dass
jeder Knoten   mindestens den Grad   hat
und
jede Hyperkante aus höchstens   Knoten besteht.
Weiter sei
 
die kleinste Anzahl von Hyperkanten, die benötigt wird, um die gesamte Knotenmenge   zu überdecken.
Dann gilt:
 .

Anwendung auf spezielle Blockpläne

Bearbeiten

Der Satz gibt als Anwendung eine obere Abschätzung über gewisse Anzahlen von Blöcken bei sogenannten Überdeckungsblockplänen.

Dabei ist ein Überdeckungsblockplan (englisch covering design) ein  -uniformer Hypergraph, dessen   Knoten bzw.   Hyperkanten aufgefasst werden als Punkte bzw. Blöcke eines Blockplans mit der Eigenschaft, dass je   verschiedene Punkte in mindestens einem der Blöcke enthalten sind (mit  ). Sind die Kennziffern   gegeben, so wird die kleinste unter den möglichen Anzahlen   mit   bezeichnet.

Dabei ist stets

 .

Mit dem Satz von Lovász-Stein lässt sich   nun nach oben abschätzen:[2]

 .

Quellen und Hintergrundliteratur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b Stasys Jukna: Extremal Combinatorics. 2011, S. 34 ff
  2. Stasys Jukna: Extremal Combinatorics. 2011, S. 37–38