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.

Formulierung des Satzes

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

Seien $n,m,r,\delta ,\tau$ natürliche Zahlen.

Sei dazu $H=(X,{\mathcal {F}})$ ein endlicher Hypergraph, bestehend aus einer endlichen Knotenmenge $X$ mit $n$ Knoten und einem System ${\mathcal {F}}\subseteq 2^{X}$ von $m$ Hyperkanten.

Dabei sei vorausgesetzt, dass

jeder Knoten $x\in X$ mindestens den Grad $\deg _{H}(x)\geq \delta$ hat

und

jede Hyperkante aus höchstens $r$ Knoten besteht.

Weiter sei

$\tau =\min(\{|{\mathcal {E}}|\colon {\mathcal {E}}\subseteq {\mathcal {F}}\;,\;\bigcup {\mathcal {E}}=X\})$

die kleinste Anzahl von Hyperkanten, die benötigt wird, um die gesamte Knotenmenge $X$ zu überdecken.

Dann gilt:

$\tau \leq {\frac {m}{\delta }}\cdot {\bigl (}1+\ln(r){\bigr )}$.

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 (englisch covering design) ein $r$-uniformer Hypergraph, dessen $n$ Knoten bzw. $m$ Hyperkanten aufgefasst werden als Punkte bzw. Blöcke eines Blockplans mit der Eigenschaft, dass je $l$ verschiedene Punkte in mindestens einem der Blöcke enthalten sind (mit $n,r,l,m\in \mathbb {N}$). Sind die Kennziffern $n,r,l$ gegeben, so wird die kleinste unter den möglichen Anzahlen $m$ mit $M(n,r,l)$ bezeichnet.

Dabei ist stets

$M(n,r,l)\geq {\frac {n \choose l}{r \choose l}}$.

Mit dem Satz von Lovász-Stein lässt sich $M(n,r,l)$ nun nach oben abschätzen:

$M(n,r,l)\leq {\frac {n \choose l}{r \choose l}}\cdot {\bigl (}1+\ln {n \choose l}{\bigr )}$.

Quellen und Hintergrundliteratur

• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer Verlag, Heidelberg, Dordrecht, London, New York 2011, ISBN 978-3-642-17363-9.  MR2865719
• L. Lovász: On the ratio of optimal integral and fractional covers. In: Discrete Mathematics. Band 13, 1975, S. 383–390 (sciencedirect.com).  MR0384578
• S. K. Stein: Two combinatorial covering theorems. In: Journal of Combinatorial Theory. Series A. Band 16, 1974, S. 391–397 (sciencedirect.com).  MR0340062