##
**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 > 2r^{3}k 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 > 2r^{3}(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}r^{3}/(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