Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  337.05135
Autor:  Bollobás, Béla; Daykin, D.E.; Erdös, Paul
Title:  Sets of independent edges of a hypergraph. (In English)
Source:  Q. J. Math., Oxf. II. Ser. 27, 25-32 (1976).
Review:  An r-graph (hypergraph) G is a pair (V,T) where V is a finite set and T is a subset of the set of all r-element subsets of V. The paper contains results related to those of P. Erdös [Ann. Univ. Sci. Budapest, Rolando Eötvös Sect. Math. 8, 93-95 (1965; Zbl 136.21302)], A. J. W. Hilton and E. C. Milner [Quart. J. Math., Oxford II. Ser. 18, 369-384 (1967; Zbl 168.26205)], A. J. W. Hilton [Infinite finite Sets, Colloq. Honour Paul Erdös, Keszthely 1973, Colloq. Math. Soc. János Bolyai 10, 875-886 (1975; Zbl 334.05118)] and others.
Theorem 1: Let G = (V,T) be an r-graph with r \geq 2, k \geq 1, |V| = n > 2r3k and

|T| > \binom{n}{r}-\binom{n-k}{r}-\binom{n-k-r}{r-1}+1.

Suppose G contains at most k independent r-tuples. Then there exists W \subset V with |W| = k such that every r-tuple of G intersects W. Theorem 2: Let G = (V,T) be an r-graph with r \geq 2, k \geq 1 and |V| = n > 2r3(k+2). Suppose G contains at most k independent r-tuples. If

\deg v > \binom{n-1}{r-1}-\binom{n-k}{r-1}+\binom{n-k-1}{r-2}r3/(n-k+1)

for every v in V then there exists W \subset V with |W| = k such that every r-tuple of G intersects W.
Reviewer:  J.Plesnik
Classif.:  * 05C99 Graph theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag