Lovász Stone's Theorem

The set of Lovász Stone , named after the mathematicians László Lovász and Sherman K. Stein , is a theorem of mathematical sub-region of the graph theory . The theorem formulates an inequality which relates the smallest number of hyperedges required to cover the entire set of nodes of a given finite hypergraph to other parameters of this hypergraph.

Formulation of the sentence

Following the presentation by Stasys Jukna , the sentence can be formulated as follows:

Be natural numbers . ${\displaystyle n,m,r,\delta ,\tau }$

Let us be a finite hypergraph, consisting of a finite set of nodes with nodes and a system of hyperedges. ${\displaystyle H=(X,{\mathcal {F}})}$ ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {F}}\subseteq 2^{X}}$ ${\displaystyle m}$

It is assumed that

each node of at least the degree has ${\displaystyle x\in X}$ ${\displaystyle \deg _{H}(x)\geq \delta }$

and

each hyperedge consists of at most nodes. ${\displaystyle r}$

Be further

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

the smallest number of hyperedges required to cover the entire set of nodes . ${\displaystyle X}$

Then:

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

Application to special block plans

As an application, the theorem gives an upper estimate over a certain number of blocks in so-called cover block plans .

In this case, an overlap block plan ( English covering design ) a - uniform Hyper graph whose nodes or hyperedges be considered as points or blocks of a block plan with the property that each different points are included in at least one of the blocks (with ). Are the figures given, the smallest is among the possible numbers with designated. ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle l}$ ${\displaystyle n,r,l,m\in \mathbb {N} }$ ${\displaystyle n,r,l}$ ${\displaystyle m}$ ${\displaystyle M(n,r,l)}$

There is always

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

With Lovász-Stein's theorem one can now estimate upwards: ${\displaystyle M(n,r,l)}$

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

Sources and background literature

• Stasys Jukna: Extremal Combinatorics (=  Texts in Theoretical Computer Science ). 2nd Edition. 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 . tape 13 , 1975, p. 383-390 ( sciencedirect.com ). MR0384578
• SK Stein: Two combinatorial covering theorems . In: Journal of Combinatorial Theory. Series A . tape 16 , 1974, p. 391-397 ( sciencedirect.com ). MR0340062

Individual evidence

1. ↑ ^{a b} Stasys Jukna: Extremal Combinatorics. 2011, p. 34 ff
2. ↑ Stasys Jukna: Extremal Combinatorics. 2011, pp. 37-38