# zbMATH — the first resource for mathematics

Sets of independent edges of a hypergraph. (English) Zbl 0337.05135
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 0136.21302)], A. J. W. Hilton and E. C. Milner [Quart. J. Math., Oxford II. Ser. 18, 369-384 (1967; Zbl 0168.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 0334.05118)] and others.
Theorem 1: Let $$G=(V,T)$$ be an $$r$$-graph with $$r \geq 2$$, $$k \geq 1$$, $$|V| =n>2r^3k$$ 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.Plesník
Show Scanned Page ##### MSC:
 05C99 Graph theory
Full Text: