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 .
- Let us be a finite hypergraph, consisting of a finite set of nodes with nodes and a system of hyperedges.
-
It is assumed that
- each node of at least the degree has
-
and
- each hyperedge consists of at most nodes.
-
Be further
- the smallest number of hyperedges required to cover the entire set of nodes .
-
Then:
- .
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.
There is always
- .
With Lovász-Stein's theorem one can now estimate upwards:
- .
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