Satz von Lovász-Stein
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
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
Der Satz gibt als Anwendung eine obere Abschätzung über gewisse Anzahlen von Blöcken bei sogenannten Überdeckungsblockplänen.
Dabei ist ein Überdeckungsblockplan (Vorlage:EnS) 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]
- .