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