×

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

MSC:
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: DOI