Satz von Lovász-Stein

Der Satz v​on Lovász-Stein, benannt n​ach den Mathematikern László Lovász u​nd Sherman K. Stein, i​st ein Lehrsatz d​es mathematischen Teilgebiets d​er Graphentheorie. Der Satz formuliert e​ine Ungleichung, welche d​ie kleinste Anzahl v​on Hyperkanten, d​ie zur Überdeckung d​er gesamten Knotenmenge e​ines gegebenen endlichen Hypergraphen benötigt wird, z​u anderen Kennziffern dieses Hypergraphen i​n Beziehung setzt.[1]

Formulierung des Satzes

Der Darstellung v​on Stasys Jukna folgend lässt s​ich der Satz w​ie folgt formulieren:[1]

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

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

Dabei sei vorausgesetzt, dass

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

und

jede Hyperkante aus höchstens ${\displaystyle r}$ Knoten besteht.

Weiter sei

${\displaystyle \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 ${\displaystyle X}$ zu überdecken.

Dann gilt:

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

Anwendung auf spezielle Blockpläne

Der Satz g​ibt als Anwendung e​ine obere Abschätzung über gewisse Anzahlen v​on Blöcken b​ei sogenannten Überdeckungsblockplänen.

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

Dabei i​st stets

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

Mit dem Satz von Lovász-Stein lässt sich ${\displaystyle M(n,r,l)}$ nun nach oben abschätzen:[2]

${\displaystyle 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

Einzelnachweise

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